Central Exclusive Production at LHCb

Ronan McNulty (on behalf of the LHCb collaboraiton)

University College Dublin, Dublin 4, Ireland

> The installation of a new sub-detector has improved the ability of LHCb to
> measure central exclusive production in Run 2 at the LHC. A measurement of
> central exclusive $J/\psi$ production is presented and improvements for the
> analysis of hadronic final states are discussed.

> PRESENTED AT
>
>
>
>
> Presented at EDS Blois 2017, Prague,
> Czech Republic, June 26-30, 2017

##  1 Introduction

Central Exclusive Production (CEP) in hadron collisions occurs when colourless
propagators are exchanged between the hadrons creating a central system, with
the colliding hadrons remaining intact after the interaction. This leads to
the unique experimental signature of a small number of particles in the
central system with rapidity gaps extending to the projectiles. LHCb has
performed measurements of the exclusive differential cross-sections as a
function of rapidity of $J/\psi$, $\psi(2S)$ and $\Upsilon$ mesons [1, 2] in
$pp$ collisions at $\sqrt{s}$ of 7 and 8 TeV. These vector mesons are created
through photon-Pomeron fusion and the measurements probe the gluon PDF down to
fractional parton momenta of $2\times 10^{-6}$ [3, 4], being potentially
sensitive to saturation effects [5] or the existence of odderons [6],
colourless three-gluon states. LHCb has also measured double charmonia
production [7] in Pomeron-Pomeron fusion. This shows the complementarity of
measurements through CEP and conventional QCD production [8], and demonstrates
that CEP has potential to search for tetraquarks and exotic or hybrid mesons.
In particular, double Pomeron exchange, being rich in gluons, is a good
laboratory in which to search for glueball states.

In these proceedings, I discuss improvements made by LHCb in the collection
and understanding of CEP events during Run 2, present a recent measurement of
charmonia production in $pp$ collisions at $\sqrt{s}=13$ TeV, and outline the
future potential of CEP measurements.

##  2 Central Exclusive Production at Run 2

Experience of CEP analyses in Run 1 at the LHC showed it was relatively easy
to select events in the LHCb detector that had no other activity apart from
the particles making up the central system. However, it was more difficult to
determine whether these were truly exclusive, or whether the protons
dissociated with the remnants travelling outside the acceptance of the LHCb
detector. Discrimination was provided by considering the transverse momentum,
$p_{T}$, of the central system. The distribution of events as a function of
the Mandelstam variable, $t\approx p_{T}^{2}$ was assumed to follow a
distribution $\exp(bt)$ where the slope $b$ is greater for signal than for
background: thus a fit to data can extract the relative proportion of
exclusive events.

During Run 1, the LHCb detector was fully instrumented in the pseudorapidity
region $2<\eta<5$, and could register the presence of charged tracks in the
region $-3.5<\eta<-1.5$. In order to extend the region where particle activity
could be recorded, a new sub-detector, HeRSCheL [9], consisting of five planes
of scintillators was installed on both sides of LHCb in the LHC tunnel, during
the LHC shutdown following Run 1. It adds a veto region of $5<|\eta|<10$ to
the acceptance of LHCb for Run 2.

Each station of HeRSCheL consists of four scintillators, 30 cm square,
arranged symmetrically around the beam-pipe and read out by photomultiplier
tubes. The digitised signals undergo a callibration procedure and the summed
signal, $\Sigma_{H}$, is used as a discriminant. The response of HeRSCheL to
three classes of events is shown in Fig. 1. The first class is enriched in CEP
events, which have been selected from dimuon candidates having
$p_{T}^{2}<0.01$ GeV2 and masses greater than 1.5 GeV, but outside the
charmonium or bottomonium regions. The second class consists of $J/\psi$
candidates having $p_{T}^{2}>1$ GeV2 and are thus likely to be non-exclusive.
The third class has events triggered by a low-multiplicity muon trigger but
with 5 or more charged tracks. The activity observed in HeRSCheL for exclusive
events is lower than, and shows a clear distinction from, the activity in
inclusive events. Therefore, requiring low activity in HeRSCheL increases the
fraction of exclusive events.

Events with low multiplicity were selected with a two-stage trigger. The first
stage, L0, was a hardware trigger and required low multiplicity in the
scintillating pad detector in conjunction with deposits in the muon chambers,
electromagnetic or hadron calorimeters. The second stage was implemented in
software. Improvements to the trigger in Run 2 included a lowering of the
thresholds so that mesons produced with $p_{T}=0$ GeV could be selected by the
muon, electromagnetic and hadronic triggers if the mass of the meson was above
700, 300 and 400 MeV, respectively.

Figure 1: Summed energy in the HeRSCheL detector for three classes of dimuon
events: candidates for CEP from the QED continuum with $p_{T}^{2}<0.01$ GeV2;
$J/\psi$ non-exclusive candidates with $p_{T}^{2}>1$ GeV2; and low
multiplicity events with five or more reconstructed tracks. The vertical line
indicates the region used in the measurement of the $J/\psi$ and $\psi(2S)$
cross-sections at $\sqrt{s}=13$ TeV.

##  3 Exclusive production of $J/\psi$ and $\psi(2S)$ mesons

The selection of exclusive charmonia produced at $\sqrt{s}=13$ TeV [10] and
decaying to two muons was similar to the analysis published at 7 TeV [1], but
with the addition of requiring little activity in the newly installed HeRSCheL
sub-detector, as indicated by the vertical line in Fig. 1. Precisely two muons
were required in the event with no additional charged or neutral particles
reconstructed. The invariant mass of the two muons is shown in Fig. 2 and
candidates for $J/\psi$ and $\psi(2S)$ were required to be within 65 MeV of
their known masses. Contamination in the $J/\psi$ sample due to feed-down from
$\chi_{c}\rightarrow J\psi\gamma$ where the photon escapes detection was
estimated by scaling, using simulation, the number of reconstructed $\chi_{c}$
events where the photon was observed. A fit to the $p_{T}^{2}$ distribution is
sensitive to the relative amount of exclusive and non-exclusive events and is
shown in Fig. 3 before and after the HeRSCheL requirement. The new sub-
detector roughly halves both the feed-down and proton-dissociation components,
reducing the systematic uncertainties associated with knowledge of the
backgrounds.

Figure 2: Invariant mass of exclusive dimuon candidates. The lines are fits to
the data. The windows indicate the regions chosen for the $J/\psi$ and
$\psi(2S)$ analyses.

Figure 3: Transverse momentum squared of $J/\psi$ candidates without (left)
and with (right) the requirement that there be little activity in HeRSCheL.
The solid line represents the total fit. The dashed line is the estimated
exclusive component while the dotted line is the proton dissociation.

The efficiency for the selection was calculated using data. The efficiency for
triggering, tracking and the muon selection used a tag-and-probe technique
where one of the two muons was ‘tagged’ and the efficiency for the other was
measured. The efficiency for the requirement on activity in HeRSCheL was found
from the QED-produced dimuon sample shown in Fig. 1. The purity was obtained
from the fit shown in Fig. 3. The cross-section was obtained from the number
of events produced in the estimated integrated luminosity of $204\pm 8$ pb-1.
The differential cross-section as a function of rapidity for both $J/\psi$ and
$\psi(2S)$ are shown in Fig. 4 compared to approximate NLO theoretical
calculations [11].

Figure 4: Differential cross-section for $J/\psi$ (left) and $\psi(2S)$
(right) production at $\sqrt{s}=13$ TeV compared to theoretical predictions.

##  4 Central exclusive production of pion pairs

The new triggers installed for Run 2 have allowed LHCb to collect a large
sample of pion pairs with no other detector activity in proton-proton and
proton-lead collisions. The dominant production mechanism is double pomeron
exchange in the former while in the latter it is photoproduction with the
pions produced from the decay of the $\rho$ meson. Photoproduction of the
$\rho$ on protons was measured at HERA up to photon-proton centre-of-mass
energies of about 200 GeV [12]. However, LHCb can access values up to 1 TeV,
corresponding to a parton fractional momentum, $x=1\times 10^{-6}$. At such
small $x$ values, saturation effects might contribute, and these would lead to
a change in the cross-section rise measured at HERA.

A sample of exclusive dipions was selected by requiring precisely two charged
tracks coming from the interaction region, consistent with the pion hypothesis
(mainly coming from information in the RICH sub-detector), and with no other
neutral or charged deposits in the LHCb detector. These events appear
exclusive in LHCb but may not be truly exclusive if there exist other
particles outside the LHCb acceptance. However, the HeRSCheL sub-detector
allows activity in a much wider pseudorapidity region to be vetoed. Using the
response of the detector in QED-produced dimuon events, a threshold was
defined that was compatible with no activity in HeRSCheL. The invariant mass
distribution for dipion events below and above this threshold is shown in Fig.
5. The rho resonance is clear in both distributions, but the activity outside
the resonance region is strongly suppressed when no activity is present in
HeRSCheL. This suggests that the events without HeRSCheL activity are enriched
in central exclusive production.

Figure 5: Candidates for exclusive dipion production in proton-lead collisions
requiring activity in HeRSCheL above (left) and below (right) a threshold.

##  5 Conclusions

The installation of the HeRSCheL subdetector for Run 2 has increased the
sensitivity of LHCb to central exclusive production. The cross-section for
exclusive $J/\psi$ production has been measured at $\sqrt{s}=13$ TeV. Using
HeRSCheL together with improvements to the trigger, a large sample of central
exclusive produced hadronic final states now awaits analysis. In addition to
the potential to measure $\rho$ production, pion, kaon and proton pairs can be
measured in both proton-proton and proton-ion collisions thus allowing an
investigation of a wide variety of light meson and charm spectroscopy in both
photoproduction and double pomeron exchange processes. Such spectroscopy is
important in searches for glueballs and exotic hadrons as well as for new QCD
phenomena such as odderons and saturation.

## References

  * [1] R. Aaij et al. [LHCb Collaboration], J. Phys. G 41 (2014) 055002 doi:10.1088/0954-3899/41/5/055002 [arXiv:1401.3288 [hep-ex]].
  * [2] R. Aaij et al. [LHCb Collaboration], JHEP 1509 (2015) 084 doi:10.1007/JHEP09(2015)084 [arXiv:1505.08139 [hep-ex]].
  * [3] S. P. Jones, A. D. Martin, M. G. Ryskin and T. Teubner, Eur. Phys. J. C 76 (2016) no.11, 633 doi:10.1140/epjc/s10052-016-4493-y [arXiv:1610.02272 [hep-ph]].
  * [4] V. Guzey and M. Zhalov, JHEP 1310 (2013) 207 doi:10.1007/JHEP10(2013)207 [arXiv:1307.4526 [hep-ph]].
  * [5] V. P. Goncalves, F. S. Navarra and D. Spiering, Phys. Lett. B 768 (2017) 299 doi:10.1016/j.physletb.2017.03.009 [arXiv:1701.04340 [hep-ph]].
  * [6] A. Bzdak, L. Motyka, L. Szymanowski and J.-R. Cudell, Phys. Rev. D 75 (2007) 094023 doi:10.1103/PhysRevD.75.094023 [hep-ph/0702134].
  * [7] R. Aaij et al. [LHCb Collaboration], J. Phys. G 41 (2014) no.11, 115002 doi:10.1088/0954-3899/41/11/115002 [arXiv:1407.5973 [hep-ex]].
  * [8] R. Aaij et al. [LHCb Collaboration], JHEP 1706 (2017) 047 Erratum: [JHEP 1710 (2017) 068] doi:10.1007/JHEP06(2017)047, 10.1007/JHEP10(2017)068 [arXiv:1612.07451 [hep-ex]].
  * [9] LHCb-DP-2016-003, in preparation.
  * [10] The LHCb Collaboration [LHCb Collaboration], LHCb-CONF-2016-007, CERN-LHCb-CONF-2016-007.
  * [11] S. P. Jones, A. D. Martin, M. G. Ryskin and T. Teubner, PoS DIS 2016 (2016) 043 [arXiv:1608.03838 [hep-ph]].
  * [12] P. Newman and M. Wing, Rev. Mod. Phys. 86 (2014) no.3, 1037 doi:10.1103/RevModPhys.86.1037 [arXiv:1308.3368 [hep-ex]].


$(s_{123},t_{123})$-path checking for edges $(u_{1},v_{1})$ and
$(v_{1},w_{1})$ in $G$.

###### Vertex Gadgets

For each $i\in[k]$ and vertex $v\in V_{i}$, we construct a gadget graph
$G_{v}$ as depicted in Figure 7.

For every $r\in[l(i)]$, we include nodes $a_{r}(v)$ and $b_{r}(v)$.

We call the $a_{r}(v)$ and $b_{r}(v)$ the _top_ and _bottom_ nodes of $G_{v}$
respectively.

For every $r\in[l(i)]$, we include edges $e_{r}(v)=(a_{r}(v),b_{r}(v))$. For
each $r\in[l(i)-1]$, we include edges from $a_{r}(v)$ to $a_{r+1}(v)$ and from
$b_{r}(v)$ to $b_{r+1}(v)$.

This completes the description of $G_{v}$.

For convenience, if $L$ is the $r^{\text{th}}$ list containing $v$, we write
$a_{L}(v)=a_{r}(v)$ and $b_{L}(v)=b_{r}(v)$.

###### Arranging Gadgets in Rows

For each $i\in[k]$, we list the vertices of $V_{i}$ in some arbitrary order

$v_{i,1},\dots,v_{i,n}.$

For every $j\in[n-1]$, we connect $G_{v_{i,j}}$ to $G_{v_{i,j+1}}$ by
including edges from

$a_{l(i)}(v_{i,j})\text{ to }a_{1}(v_{i,j+1})\quad\text{and}\quad
b_{l(i)}(v_{i,j})\text{ to }b_{1}(v_{i,j+1}).$

For every $j\in[n-2]$, we additionally include the edge from
$a_{l(i)}(v_{i,j})$ to $b_{1}(v_{i,j+2})$, which we call the _skip edge_ for
$v_{i,j+1}$, because traversing this edge corresponds to skipping the gadget
for $v_{i,j+1}$. Skip edges are depicted with dashed lines in Figure 8. We
view this construction as arranging the $G_{v}$ gadgets for all $v\in V_{i}$
in the “$i^{\text{th}}$ row of $G^{\prime}$.”

###### Terminal Vertices Checking Nodes

We now introduce source and target nodes and describe how they connect to the
$G_{v}$ gadgets.

For each $i\in[k]$, we introduce new vertices $s_{i}$ and $t_{i}$.

We include edges from $s_{i}$ to $a_{1}(v_{i,1})$ and from $b_{l(i)}(v_{i,n})$
to $t_{i}$.

Additionally, we include skip edges from $s_{i}$ to $b_{1}(v_{i,2})$ and from
$a_{l(i)}(v_{i,n-1})$ to $t_{i}$ (traversing these edges corresponds to
skipping $G_{v_{i,1}}$ and $G_{v_{i,n}}$ respectively).

###### Paths Between Rows of Gadgets

For every choice of indices $x,y\in[k]$ with $x<y$, list $L\in\mathcal{L}$
covering $(x,y)$, and vertices $u\in V_{x}$ and $w\in V_{y}$ such that $(u,w)$
is an edge in $G$, we include a path $\Pi_{L}(u,w)$ of length $2(y-x)-1$ from
$b_{L}(u)$ to $a_{L}(w)$ in $G^{\prime}$. These paths encode adjacency
information about $G$. We say the $\Pi_{L}(u,w)$ are the paths between rows
corresponding to list $L$.

###### Terminal Vertices Checking Edges

For each list $L$ in our collection, we introduce source node $s_{L}$ and
target node $t_{L}$.

Suppose $i$ is the first element in $L$. Then for all $v\in V_{i}$, we have
edges from $s_{L}$ to $a_{L}(v)$.

Suppose $j$ is the final element in $L$. Then for all $v\in V_{j}$, we have
edges from $a_{L}(v)$ to $t_{L}$.

We observe that any $(s_{L},t_{L})$-path in $G^{\prime}$ must pass through
nodes in row $i$ of $G^{\prime}$ for all $i\in L$.

This completes our construction of the graph $G^{\prime}$, an example of which
is depicted in Figure 8.

We claim that $G^{\prime}$ has disjoint paths from its sources to its targets
if and only if $G$ has a $k$-clique.

To prove this result, it will be helpful to first identify some special paths
in $G^{\prime}$.

For any $i\in[k]$ and $v\in V_{i}$, we let $P(v)$ be the path which begins at
$s_{i}$, passes through the top nodes of $G_{u}$ for all $u\in V_{i}$ before
$v$, then takes the skip edge skipping over $G_{v}$, passes through the bottom
nodes of $G_{w}$ for all $w\in V_{i}$ after $v$, and then finally ends at
$t_{i}$.

######  Lemma 47.

For every $v\in V$, $P(v)$ is a shortest path in $G^{\prime}$.

###### Proof.

Fix $v\in V$. Let $i\in[k]$ be the index such that $v\in V_{i}$.

Recall that for any $j\in[k]$, row $j$ of $G^{\prime}$ consists of the all
gadgets $G_{u}$ for vertices $u\in V_{i}$. The graph $G^{\prime}$ is
structured so that there is no edge from row $q$ to $p$ whenever $q>p$. Then
since $s_{i}$ only has edges to nodes in row $i$ and $t_{i}$ only has edges
from nodes in row $i$, any $(s_{i},t_{i})$-path in $G^{\prime}$ must lie
completely in row $i$. Such a path can use at most one skip edge, since a skip
edge goes from a top node to a bottom node, and there are no edges from bottom
nodes to top nodes within row $i$. If an $(s_{i},t_{i})$-path uses no skip
edges, it has exactly $n\cdot l(i)+1$ internal nodes. If instead the path uses
one skip edge, it has exactly $(n-1)\cdot l(i)+1$ internal nodes, because it
skips over one gadget.

This implies that any $(s_{i},t_{i})$-path in $G^{\prime}$ which uses a skip
edge is a shortest path.

Since $P(v)$ uses a skip edge, it is an $(s_{i},t_{i})$-shortest path as
claimed. ∎

######  Lemma 48 (Clique $\Rightarrow$ Disjoint Shortest Paths).

If $G$ has a $k$-clique, then $G^{\prime}$ has node-disjoint shortest paths
from its sources to its targets.

###### Proof.

Let $(v_{1},\dots,v_{k})\in V_{1}\times\dots\times V_{k}$ be a $k$-clique in
$G$.

For each list

$L=\langle i_{1},\dots,i_{\ell}\rangle$

in $\cal{L}$, let $Q(L)$ be the path which begins at $s_{L}$, passes through
nodes

$a_{L}(v_{i_{1}}),b_{L}(v_{i_{1}}),\dots,a_{L}(v_{i_{\ell}}),b_{L}(v_{i_{\ell}})$

in that order using the paths corresponding to list $L$, and then ends at
$t_{L}$. More precisely, $Q(L)$ goes from $a_{L}(v_{i_{j}})$ to
$b_{L}(v_{i_{j}})$ for each $j\in[\ell]$ by taking the edge between these
vertices in $G^{\prime}$, and goes from $b_{L}(v_{i_{j}})$ to
$a_{L}(v_{i_{j+1}})$ for each $j\in[\ell-1]$ by traversing the path
$\Pi(v_{i_{j}},v_{i_{j+1}})$.

######  Claim 49.

For every list $L\in\cal{L}$, $Q(L)$ is a shortest path.

The path $\Pi(v_{i_{j}},v_{i_{j+1}})$ has length $2(i_{j+1}-i_{j})-1$. By
telescoping, this means the sum of the lengths of the paths of
$\Pi(v_{i_{j}},v_{i_{j+1}})$ over all $j\in[\ell-1]$ is
$2(i_{\ell}-i_{1})-\ell$. The only edges of $Q(L)$ not in the
$\Pi(v_{i_{j}},v_{i_{j+1}})$ paths are the edge from $s_{L}$ to
$a_{L}(v_{i_{1}})$, the edges from $a_{L}(v_{i_{j}})$ to $b_{L}(v_{i_{j}})$
for each $j\in[\ell]$, and the edge from $b_{L}(v_{i_{\ell}})$ to $t_{L}$. It
follows that the length of $Q(L)$ is

$2+\ell+\left(2(i_{\ell}-i_{1})-\ell\right)=2(i_{\ell}-i_{1}+1).$

To prove the claim, it suffices to show that any $(s_{L},t_{L})$-path in
$G^{\prime}$ has length at least

$2(i_{\ell}-i_{1}+1).$

To that end, take an arbitrary $(s_{L},t_{L})$-path $Q$ in $G^{\prime}$. Let
$j_{1},\dots,j_{r}\in[k]$ be the sequence of distinct rows $Q$ visits in
order. Since $G^{\prime}$ only includes edges going from row $x$ to row $y$
for $x<y$, we must have $j_{1}<j_{2}<\dots<j_{r}$.

By construction the only way to go from row $x$ to row $y$ in $G^{\prime}$ is
to traverse a path $\Pi_{L^{\prime}}(u,w)$ for some nodes $u\in V_{x}$ and
$w\in V_{y}$, and list $L^{\prime}\in\mathcal{L}$. Such a path begins at the
bottom of row $x$ at $b_{L}^{\prime}(u)$, ends at the top of row $y$ at
$a_{L}^{\prime}(w)$, and has length $2(y-x)-1$. So the sum of the lengths of
all such paths $Q$ traverses to hit rows $j_{1},\dots,j_{r}$ is at least
$2(j_{r}-j_{1})-r$ by telescoping. Moreover, $Q$ must traverse at least one
edge within each row it visits, to get from the top of that row to the bottom
of that row. This accounts for at least $r$ additional edges, so $Q$ has
length at least

$\left(2(j_{r}-j_{1})-r\right)+r=2(j_{r}-j_{1}).$

Finally, $Q$ also must contain an edge leaving $s_{L}$, and an edge entering
$t_{L}$. This accounts for two more edges, so $Q$ has length at least
$2(j_{r}-j_{1}+1)$.

By definition, $i_{1}$ and $i_{\ell}$ are the first and final elements in list
$L$ respectively. Consequently, edges exiting $s_{L}$ must go to row $i_{1}$,
and edges entering $t_{L}$ must depart from $i_{\ell}$. This forces
$j_{1}=i_{1}$ to be the first row $Q$ enters, and $j_{r}=i_{\ell}$ to be the
last row $Q$ enters. Thus $Q$ has length at least

$2(j_{r}-j_{1}+1)=2(i_{\ell}-i_{1}+1).$

This lower bound for the length of an arbitrary $(s_{L},t_{L})$-path in
$G^{\prime}$ is equal to the length of $Q(L)$. Thus $Q(L)$ is a shortest path
in $G^{\prime}$, as claimed.

We claim that the collection of paths obtained by taking $P(v_{i})$ for each
$i\in[k]$ and $Q(L)$ for each $L\in\mathcal{L}$ is a collection of node-
disjoint paths in $G^{\prime}$.

Indeed, for each $i\in[k]$, $P(v_{i})$ is in the $i^{\text{th}}$ row of
$G^{\prime}$, so $P(v_{i})$ and $P(v_{j})$ are disjoint for $i\neq j$.
Similarly, for each choice of lists $L\neq K$ in $\mathcal{L}$, $Q(L)$ and
$Q(K)$ pass through distinct vertices.

Take $i\in[k]$ and $L\in\mathcal{L}$. The only way $Q(L)$ can intersect
$P(v_{i})$ is if $i\in L$. If $i\in L$, the only nodes at which $Q(L)$ can
intersect $P(v_{i})$ are $a_{L}(v_{i})$ and $b_{L}(v_{i})$. However,
$P(v_{i})$ skips $G_{v_{i}}$, so neither of these nodes occur in $P(v_{i})$.
Thus $P(v_{i})$ and $Q(L)$ are disjoint.

Since by Lemma 47 the $P(v_{i})$ are shortest paths, and by Claim 49 the
$Q(L)$ are shortest paths, we have proven the desired result. ∎

######  Lemma 50 (Disjoint Paths $\Rightarrow$ Clique).

If $G^{\prime}$ has node-disjoint paths from its sources to its targets, then
$G$ has a $k$-clique.

###### Proof.

Let $\mathcal{F}$ be a family of node-disjoint paths from the sources to the
targets of $G^{\prime}$.

For each $i\in[k]$, let $P_{i}$ denote the $(s_{i},t_{i})$-path in
$\mathcal{F}$.

For each $L\in\mathcal{L}$, let $Q_{L}$ denote the $(s_{L},t_{L})$-path in
$\mathcal{F}$.

By construction of $G^{\prime}$, each $P_{i}$ must stay in row $i$. Since skip
edges take us from the top of a row to the bottom of a row, each $P_{i}$ uses
at most one skip edge.

We say a path $Q$ “uses the edges corresponding to a list $L\in\mathcal{L}$”
if $Q$ uses an edge of $\Pi_{L}(u,w)$, for some vertices $u$ and $w$.

######  Claim 51.

For each list $L\in\cal{L}$, the path $Q_{L}$ does not use edges corresponding
to list $L^{\prime}\in\mathcal{L}$, for any $L^{\prime}\neq L$.

Suppose to the contrary that there does exist a list $L\in\cal{L}$ such that
$Q_{L}$ uses edges corresponding to lists distinct from $\cal{L}$. Pick such
an $L$ which occurs latest in the ordering of $\cal{L}$.

Consider the first edge $Q_{L}$ uses which corresponds to another list.

Suppose this edge belongs to $\Pi_{L^{\prime}}(u,w)$ for some list
$L^{\prime}\neq L$, and vertices $u$ and $w$. Let $x\in[k]$ be the index such
that $u\in V_{x}$. Since the edge we are considering is the first edge $Q_{L}$
uses which corresponds to a list other than $L$, before this edge $Q_{L}$ can
only have entered rows with indices contained in $L$. Thus $x\in L$, and
$Q_{L}$ must have entered row $x$ at a vertex $a_{L}(v)$, for some $v\in
V_{x}$. We also know that $x\in L^{\prime}$, since otherwise
$\Pi_{L^{\prime}}(u,w)$ would not exist. Since $Q_{L}$ uses an edge of
$\Pi_{L^{\prime}}(u,w)$, we know that the starting vertex of this path
$b_{L^{\prime}}(u)$ must occur after $a_{L}(v)$ in the topological order of
$G^{\prime}$.

Previously, we observed that each $P_{i}$ uses at most one skip edge. We claim
that path $P_{x}$ uses the skip edge to skip gadget $G_{v}$ in row $x$.
Suppose to the contrary that $P_{x}$ does not use this skip edge. Since
$P_{x}$ and $Q_{L}$ are disjoint, $P_{x}$ must pass through $b_{L}(v)$
(otherwise it would hit $a_{L}(v)$). Since $b_{L^{\prime}}(u)$ occurs after
$a_{L}(v)$ in the topological order, this means that $P_{x}$ passes through
$b_{L^{\prime}}(u)$. This contradicts our assumption that $P_{x}$ and $Q_{L}$
are disjoint.

Thus $P_{x}$ uses the skip edge corresponding to $G_{v}$ in row $x$, as
claimed.

Since $P_{x}$ uses this skip edge, we know that $P_{x}$ passes through
$b_{K}(v^{\prime})$ for all lists $K$ containing $x$ and all $v^{\prime}\in
V_{x}$ after $v$ in the order on $V_{x}$. Since $b_{L^{\prime}}(u)$ is not in
$P_{x}$ (because $P_{x}$ and $Q_{L}$ are disjoint), we must have $u=v$.

Then for $a_{L}(v)$ to occur before $b_{L^{\prime}}(v)$ in the topological
order, we must have $L$ occur before $L^{\prime}$ in the ordering for
$\cal{L}$.

Now, observe that $Q_{L^{\prime}}$ cannot cross between rows while only using
edges corresponding to $L^{\prime}$. Indeed, if $Q_{L^{\prime}}$ only uses
edges corresponding to $L^{\prime}$ to go between rows, it would pass through
a column of row $x$, since $x\in L^{\prime}$. To be disjoint from $P_{x}$,
this is only possible if $Q_{L^{\prime}}$ uses a column of $G_{v}$, since
$P_{x}$ hits the columns of every other gadget in row $x$. But $Q_{L}$ and
$Q_{L^{\prime}}$ are disjoint, and we already said that $Q_{L}$ hits the
column of $G_{v}$ corresponding to $L^{\prime}$.

Thus, $Q_{L^{\prime}}$ must use an edge corresponding to a list distinct from
$L^{\prime}$. We also observed earlier that $L^{\prime}$ occurs after $L$ in
the ordering on $\cal{L}$.

This contradicts our choice of $L$ as the final list in $\cal{L}$ with the
property that $Q_{L}$ uses an edge corresponding to a list distinct from $L$.

Thus our initial assumption was false, and the claim holds.

######  Claim 52.

For every $i\in[k]$, $P_{i}$ uses a skip edge.

Suppose to the contrary that there exists an index $i\in[k]$ such that $P_{i}$
does not use a skip edge. Then for every $v\in V_{i}$ and $r\in[s(i)]$, the
path $P_{i}$ passes through at least one of $a_{r}(v)$ and $b_{r}(v)$. Let
$L\in\mathcal{L}$ be a list containing $i$ (such a list exists because
$\mathcal{L}$ is a $k$-covering family). By Claim 51 and the fact that each
$P_{i}$ uses at most one skip edge, the path $Q_{L}$ must pass through
vertices $a_{L}(v)$ and $b_{L}(v)$ for some $v\in V_{i}$. Consequently,
$Q_{L}$ intersects $P_{i}$, which contradicts the assumption that paths in
$\mathcal{F}$ are disjoint. So each $P_{i}$ traverses a skip edge as claimed.

Since a skip edge moves a path from the top nodes to the bottom nodes of a
row, by Claim 52 we know that each $P_{i}$ traverses exactly one skip edge.

For each $i\in[k]$, let $v_{i}\in V_{i}$ be the unique vertex such that
$P_{i}$ traverses the edge skipping $G_{v_{i}}$. Then we claim that
$(v_{1},\dots,v_{k})$ is a clique in $G$.

Indeed, take any pair $(i,j)\in[k]^{2}$ with $i<j$. Let $L\in\mathcal{L}$ be a
list covering $(i,j)$.

By Claim 51, the path $Q_{L}$ traverses a path $\Pi_{L}(u,w)$ for some $u\in
V_{i}$ and $w\in V_{j}$.

Since the only gadgets skipped by $P_{i}$ and $P_{j}$ are $G_{v_{i}}$ and
$G_{v_{j}}$ respectively, and $Q_{L}$ is disjoint from $P_{i}$ and $P_{j}$, we
see that in fact $Q_{L}$ traverses the path $\Pi_{L}(v_{i},v_{j})$.

But this path exists in $G^{\prime}$ only if $(v_{i},v_{j})$ is an edge in
$G$.

So $(v_{i},v_{j})$ is an edge in $G$ for all $i<j$, and thus $G$ contains a
$k$-clique as claimed. ∎

See 9

###### Proof.

Construct a collection $\mathcal{L}$ of $\lambda=\lfloor k^{2}/4\rfloor$ lists
which form a $k$-covering family using Lemma 46. For constant $k$, this takes
$O(1)$ time. This collection has the property that each element of $[k]$ shows
up in fewer than $k$ list of $\mathcal{L}$.

Let $G$ be the input instance of $k$-Clique.

Using $\mathcal{L}$ and $G$, construct the graph $G^{\prime}$ described
previously in this section.

By Lemmas 48 and 50, solving $p$-DP or $p$-DSP on $G^{\prime}$ solves
$k$-Clique on $G$, where

$p=k+\lambda=k+\lfloor k^{2}/4\rfloor.$

Since $G^{\prime}$ consists of $2(k+\lambda)$ terminals and $kn$ gadget graphs
$G_{v}$, each on fewer than $2k$ nodes, the graph $G^{\prime}$ has at most
$O(kn)$ nodes. Since we can construct $G^{\prime}$ in time linear in its size,
this proves the desired result. ∎

##  7 Conclusion

In this work, we obtained linear time algorithms for 2-DSP in undirected
graphs and DAGs. These algorithms are based off algebraic methods, and as a
consequence are _randomized_ and only solve the _decision_ , rather than
search, version of 2-DSP. This motivates the following questions:

######  Open Problem 1.

Is there a _deterministic_ linear time algorithm solving 2-DSP?

######  Open Problem 2.

Given a DAG or undirected graph $G$ with sources $s_{1},s_{2}$ and targets
$t_{1},t_{2}$, is there a linear time algorithm _finding_ disjoint
$(s_{i},t_{i})$-shortest paths in $G$ for $i\in\left\\{1,2\right\\}$?

It is also an interesting research direction to see if algebraic methods can
help design faster algorithms for $k$-DSP in undirected graphs and DAGs when
$k\geq 3$, or help tackle this problem in the case of general directed graphs.

In this work, we also established tighter reductions from finding cliques to
disjoint path and shortest path problems. There still remain large gaps
however, between the current best conditional lower bounds and current fastest
algorithms for these problems.

######  Open Problem 3.

Is there a fixed integer $k\geq 3$ and constant $\delta>0$ such that $k$-DSP
in DAGs can be solved in $O(n^{k+1-\delta})$ time? Or does some popular
hypothesis rule out such an algorithm?

Since $k$-Clique admits nontrivial algorithms by reduction to matrix
multiplication, it is possible that $k$-DSP can be solved faster using fast
matrix multiplication algorithms. On the other hand, if we want to rule out
this possibility and obtain better conditional lower bounds for $k$-DSP, we
should design reductions from problems which are harder than $k$-Clique. In
this context, a natural strategy would be to reduce from Negative $k$-Clique
and 3-Uniform $k$-Hyperclique instead, since these problems are conjectured to
require $n^{k-o(k)}$ time to solve (and it is not known how to leverage matrix
multiplication to solve these problems faster than exhaustive search).

For all $k\geq 3$, the current fastest algorithm for $k$-DSP in undirected
graphs takes $n^{O(k\cdot k!)}$ time, much slower than the $O(mn^{k-1})$ time
algorithm known for the problem in DAGs. Despite this, every conditional lower
bound that has been established for $k$-DSP in undirected graphs so far also
extends to showing the same lower bound for the problem in DAGs. This is
bizarre behavior, and suggests we should try establishing a lower bound which
separates the complexities of $k$-DSP in undirected graphs and DAGs. If
designing such a lower bound proves difficult, that would offer circumstantial
evidence that far faster algorithms for $k$-DSP in undirected graphs exist.

######  Open Problem 4.

Can we show a conditional lower bound for $k$-DSP in undirected graphs, which
is stronger than any conditional lower bound known for $k$-DSP in DAGs?

Finally, for large $k$, the best conditional time lower bounds we have for
$k$-DP in DAGs are far weaker than the analogous lower bounds we have for
$k$-DSP in DAGs. This is despite the fact that the fastest algorithms we have
for both problems run in the same time. It would nice to resolve this
discrepancy, either by designing faster algorithms for the latter problem, or
showing better lower bounds for the former problem.

######  Open Problem 5.

Is there a fixed integer $k\geq 3$ such that we can solve $k$-DP in DAGs
faster than we can solve $k$-DSP in weighted DAGs?

######  Open Problem 6.

Can we show a conditional lower bound for $k$-DP in DAGs matching the best
known conditional lower bound for $k$-DSP in DAGs?

## References

  * [Akh20] Maxim Akhmedov.  Faster 2-disjoint-shortest-paths algorithm.  In Computer Science – Theory and Applications, pages 103–116. Springer International Publishing, 2020.
  * [BH19] Andreas Björklund and Thore Husfeldt.  Shortest two disjoint paths in polynomial time.  SIAM Journal on Computing, 48(6):1698–1710, January 2019.
  * [BHK22] Andreas Björklund, Thore Husfeldt, and Petteri Kaski.  The shortest even cycle problem is tractable.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. ACM, June 2022.
  * [BHT12] Andreas Björklund, Thore Husfeldt, and Nina Taslaman.  Shortest cycle through specified elements.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, January 2012.
  * [BK17] Kristof Berczi and Yusuke Kobayashi.  The Directed Disjoint Shortest Paths Problem.  In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:13, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [BNRZ20] Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche.  Using a geometric lens to find k disjoint shortest paths, 2020.
  * [BNRZ21] Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche.  Using a Geometric Lens to Find k Disjoint Shortest Paths.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:14, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [BS83] Walter Baur and Volker Strassen.  The complexity of partial derivatives.  Theoretical Computer Science, 22(3):317–330, February 1983.
  * [CFK+15] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer International Publishing, 2015.
  * [CGS15] Marek Cygan, Harold N. Gabow, and Piotr Sankowski.  Algorithmic applications of baur-strassen’s theorem.  Journal of the ACM, 62(4):1–30, September 2015.
  * [Chi21] Rajesh Chitnis.  A tight lower bound for edge-disjoint paths on planar dags, 2021.
  * [DW22] Mina Dalirrooyfard and Virginia Vassilevska Williams.  Induced cycles and paths are harder than you think.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 531–542. IEEE, 2022.
  * [EG04] Friedrich Eisenbrand and Fabrizio Grandoni.  On the complexity of fixed parameter clique and dominating set.  Theoretical Computer Science, 326(1-3):57–67, October 2004.
  * [EKW23] Eduard Eiben, Tomohiro Koana, and Magnus Wahlström.  Determinantal sieving, 2023.
  * [ET98] Tali Eilam-Tzoreff.  The disjoint shortest paths problem.  Discrete Applied Mathematics, 85(2):113–138, June 1998.
  * [FGK+22] Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Kirill Simonov, and Giannos Stamoulis.  Fixed-parameter tractability of maximum colored path and beyond, 2022\.
  * [FHW80] Steven Fortune, John Hopcroft, and James Wyllie.  The directed subgraph homeomorphism problem.  Theoretical Computer Science, 10(2):111–121, February 1980.
  * [KKR12] Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed.  The disjoint paths problem in quadratic time.  Journal of Combinatorial Theory, Series B, 102(2):424–435, March 2012.
  * [KPS24] Tuukka Korhonen, Michał Pilipczuk, and Giannos Stamoulis.  Minor containment and disjoint paths in almost-linear time, 2024.
  * [Loc21] Willian Lochet.  A polynomial time algorithm for the $k$-disjoint shortest paths problem.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 169–178. Society for Industrial and Applied Mathematics, January 2021.
  * [RS95] N. Robertson and P.D. Seymour.  Graph minors .XIII. the disjoint paths problem.  Journal of Combinatorial Theory, Series B, 63(1):65–110, January 1995.
  * [Sli10] Aleksandrs Slivkins.  Parameterized tractability of edge-disjoint paths on directed acyclic graphs.  SIAM Journal on Discrete Mathematics, 24(1):146–157, January 2010\.
  * [SY09] Amir Shpilka and Amir Yehudayoff.  Arithmetic circuits: A survey of recent results and open questions.  Foundations and Trends® in Theoretical Computer Science, 5(3-4):207–388, 2009.
  * [Tho97] M. Thorup.  Undirected single source shortest paths in linear time.  In Proceedings 38th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc, 1997.
  * [Tho05] Torsten Tholey.  Solving the 2-disjoint paths problem in nearly linear time.  Theory of Computing Systems, 39(1):51–78, November 2005.
  * [Tho12] Torsten Tholey.  Linear time algorithms for two disjoint paths problems on directed acyclic graphs.  Theoretical Computer Science, 465:35–48, December 2012.
  * [Wil18] Virginia Vassilevska Williams.  On some fine-grained questions in algorithms and complexity.  In Proceedings of the international congress of mathematicians: Rio de janeiro 2018, pages 3447–3487. World Scientific, 2018.
  * [WXXZ23] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou.  New bounds for matrix multiplication: from alpha to omega, 2023.

##  Appendix A Standard Reductions

In this section, we collect proofs of some standard reductions that allow us
to move between different variants of disjoint path problems.

######  Proposition 53 (Edge-Disjoint $\leq$ Vertex-Disjoint).

There is a reduction from $k$-EDSP on $n$ vertices and $m$ edges to $k$-DSP on
$m+k(n+2)$ nodes and $2k(m+1)$ edges.

###### Proof.

Let $G$ be the instance of $k$-EDSP on $n$ vertices and $m$ edges, with
sources $s_{1},\dots,s_{k}$ and targets $t_{1},\dots,t_{k}$. Let $V$ and $E$
be the vertex and edge sets of $G$ respectively.

We construct a graph $G^{\prime}$ as follows. For every vertex $v\in V$,
$G^{\prime}$ has $k$ nodes $v_{1},\dots,v_{k}$ (we call these the _copies_ of
$v$ in $G^{\prime}$). For every edge $e\in E$, $G^{\prime}$ has a node $e$.
For every edge $e=(v,w)\in E$, we include edges in $G^{\prime}$ from $v_{i}$
to $e$ and from $e$ to $w_{i}$ for all $i\in[k]$. If $e=(v,w)$ had weight
$\ell(v,w)$ in $G$, then the $(v_{i},e)$ and $(e,w_{i})$ edges in $G$ each
have weight $\ell(v,w)$.

Finally, we introduce new sources $s^{\prime}_{1},\dots,s^{\prime}_{k}$ and
targets $t^{\prime}_{1},\dots,t^{\prime}_{k}$ in $G^{\prime}$. Then for every
$i,j\in[k]$, we add edges from $s^{\prime}_{i}$ to $(s_{i})_{j}$ and from
$(t_{i})_{j}$ to $t^{\prime}_{i}$ of weight $1$.

From this construction, $G^{\prime}$ has $m+kn+2k$ nodes and $2km+2k$ edges as
claimed.

Suppose we have vertex-disjoint $(s^{\prime}_{i},t^{\prime}_{i})$-shortest
paths $P^{\prime}_{i}$ in $G^{\prime}$. We can assume each $P^{\prime}_{i}$
never traverses two copies of the same vertex $v\in V$ (otherwise, we could
remove the subpath between two copies of $v$ and obtain a shorter path than
$P^{\prime}_{i}$). We map each $P^{\prime}_{i}$ to an $(s_{i},t_{i})$-shortest
path $P_{i}$ in $G$, by having $P_{i}$ pass through the vertices $v\in V$ for
which $P^{\prime}_{i}$ contains a copy of $v$, in the order the copies appear
in $P^{\prime}_{i}$.

By construction, if $P_{i}$ has length $\ell$, then $P^{\prime}_{i}$ has
length $2\ell+2$. So since the $P^{\prime}_{i}$ are shortest paths, the
$P_{i}$ are also shortest paths. The $P_{i}$ are also edge-disjoint, since if
some $P_{i}$ and $P_{j}$ overlap at an edge $e$, the paths $P^{\prime}_{i}$
and $P^{\prime}_{j}$ would overlap at node $e$ in $G^{\prime}$, which would
contradict the assumption that the $P^{\prime}_{i}$ are vertex-disjoint.

So any solution to $k$-DSP on $G^{\prime}$ pulls back to a solution to
$k$-EDSP on $G$.

Conversely, given edge-disjoint $(s_{i},t_{i})$-shortest paths $P_{i}$ in $G$
of the form

$P_{i}=\langle v_{i,1},\dots,v_{i,\ell_{i}}\rangle$

we can produce $(s^{\prime}_{i},t^{\prime}_{i})$-paths $P^{\prime}_{i}$ in
$G^{\prime}$ of the form

$P^{\prime}_{i}=\langle
s^{\prime}_{i},(v_{i,1})_{i},((v_{i,1})_{i},(v_{i,2})_{i}),(v_{i,2})_{i},\dots,(v_{i,\ell_{i}})_{i},t^{\prime}_{i}\rangle.$

Similar reasoning to the above shows that the $P^{\prime}_{i}$ are shortest
paths in $G^{\prime}$. These paths are vertex-disjoint because each
$P^{\prime}_{i}$ only uses the $i^{\text{th}}$ copies of $v\in V$, and the
$P_{i}$ were edge-disjoint, so the $P^{\prime}_{i}$ cannot overlap at any
nodes of the form $e\in E$.

So any solution to $k$-EDSP in $G$ has a corresponding solution to $k$-DSP in
$G^{\prime}$.

This proves the desired result. ∎

As mentioned in Section 1, Proposition 53 combined with Theorems 1 and 2
implies Corollary 4, and Proposition 53 combined with the $O(mn^{k-1})$ time
algorithm for $k$-DSP in DAGs from [FHW80, Theorem 3] implies that $k$-EDSP in
DAGs can be solved in $O(m^{k})$ time for constant $k$.

######  Proposition 54 (Disjoint Paths $\leq$ Disjoint Shortest Paths).

There are reductions from $k$-DP on DAGs to $k$-DSP on DAGs and from $k$-EDP
on DAGs to $k$-EDSP on DAGs with the same number of nodes and edges
respectively.

###### Proof.

Let $G$ be the DAG which is an instance of $k$-DP or $k$-EDP. Take a
topological order $v_{1},\dots,v_{n}$ of the vertices in $G$. Let $G^{\prime}$
be the DAG with the same vertex and edge sets as $G$, but where each edge
$(v_{i},v_{j})$ has weight $(j-i)$. Then by telescoping, for any vertices
$v_{i}$ and $v_{j}$ in $G^{\prime}$, every path from $v_{i}$ to $v_{j}$ in
$G^{\prime}$ has total length $(j-i)$.

Consequently, every path in $G$ becomes a shortest path in $G^{\prime}$.

So solving $k$-DSP and $k$-EDSP in $G^{\prime}$ corresponds to solving $k$-DP
and $k$-EDP respectively in $G$, which proves the desired result. ∎

As mentioned in Section 1, Proposition 54 shows that $k$-EDSP in weighted DAGs
generalizes the $k$-EDP problem in DAGs.


# Log Centres of Noncommutative Crepant Resolutions are Kawamata Log Terminal:
Remarks on a paper of Stafford and van den Bergh

Colin Ingalls  School of Mathematics and Statistics, Carleton University,
Canada<EMAIL_ADDRESS>and  Takehiko Yasuda  Department of
Mathematics, Graduate School of Science, Osaka University, Toyonaka, Osaka
560-0043, Japan<EMAIL_ADDRESS>
###### Abstract.

We show that if a finitely generated prime algebra $\Delta$ is a finitely
generated maximal Cohen-Macaulay module over its centre $Z$, and has global
dimension equal to $\dim Z$, then the pair given by its centre and
ramification divisor is Kawamata log terminal.

Ingalls was supported by an NSERC Discovery Grant. Yasuda was supported by
JSPS KAKENHI Grant Numbers JP22740020, JP18H01112, JP21H04994. The first
author would like to thank Kenneth Brown and Michael Wemyss for helpful
conversations. We would also like to thank an anonymous referee for helpful
comments.

##  1\. Introduction

We will work over an algebraically closed field of characteristic zero.
Noncommutative crepant resolutions (NCCRs), as discussed in [2], indicate an
interplay between noncommutative algebra and algebraic geometry. It is not
clear when a commutative algebra admits an NCCR, and various necessary
conditions have been found. In [18], it is shown that any commutative algebra
admitting an NCCR has rational singularities. In particular, they show that if
an affine prime algebra $\Delta$ that is finite over its centre is
homologically homogenous, or equivalently $\Delta$ is Cohen-Macaulay over its
centre with finite global dimension, then its centre has rational
singularities. We use standard results about the singularities of the minimal
model program [11], and the argument of [18] to show that the singularities of
the log pair given by the centre and the ramification divisor is Kawamata log
terminal. This shows in particular that the pair is $\mathbb{Q}$-Gorenstein.
We now review the contents of this paper.

In Section 2, we discussion the singularities of the minimal model program and
we recall the definitions and properties of log canonical covers. In Section
3, we compute the centralizers of the canonical bimodule $\omega$ for a
hereditary order over a DVR. We also quote relevant results from [11]. This
will be used in the proof of the main result. In Section 4, we recall the
properties of homologically homogeneous algebras that are finite over their
centres. This material is from [18]. In Section 5, we prove the main result.
Given $\Delta$, a prime affine algebra that finite over its centre and
homologically homogeneous, with centre $Z$ and discriminant $D$, we show that
the centre of the canonical cover $\Gamma$ of the order $\Delta$ is the log
canonical cover of the pair $(Z,\Delta)$. Lastly, in Section 6, we list
algebras to which the main theorem applies, and present some relevant
examples.

There are many cases of singularities which are known to not admit a NCCR, for
example see [7].

The results of this paper suggest the following question.

######  Question 1.1.

Let $Z$ be a commutative local ring. Under what conditions is $Z$ the centre
of a prime affine homologically homogeneous ring $A$? In other words, if we
allow the flexibility of adding a boundary divisor $D$, and allowing $A$ to
have a non-trivial generic Brauer class, can we obtain a twisted ramified NCCR
of the pair $(\mathrm{Spec}\,Z,D)$?

See 4.2 for the definitions of the relevant terms. The results and a sketch of
the proofs of this paper were presented in [9]. The paper [8] works in the
setting of NCCRs and Theorem 1.1(a) and Corollary 1.7 of [8] prove our main
results in that special case.

##  2\. The Singularities of Birational Geometry

In this section we review some material about the singularities that arise in
the study of birational geometry and the minimal model program. Standard
references include [6, 11, 13].

###  2.1. Kawamata log terminal, log terminal and canonical singularities

Let $X$ be a normal variety. A $\mathbb{Q}$-divisor in $X$ is a linear
combination of codimension one subvarieties of $X$ with rational coefficients.
A $\mathbb{Q}$-divisor is effective if all its coefficients are non-negative.
A $\mathbb{Q}$-divisor $D$ is $\mathbb{Q}$-Cartier if there is an integer $m$
so that $mD$ is a Cartier divisor. A log variety is a pair $(X,D)$ consisting
of a normal variety $X$ with a $\mathbb{Q}$-divisor $D$.

Let $(X,D)$ be a log variety such that $K_{X}+D$ is $\mathbb{Q}$-Cartier. In
this case we say that $(X,D)$ is $\mathbb{Q}$-Gorenstein. Then for a proper
birational morphism $f:Y\to X$ with $Y$ smooth, we write

$K_{Y}=f^{*}(K_{X}+D)+\sum_{E}a_{E}E,\,a_{E}\in\mathbb{Q}$

where $E$ runs over exceptional divisors and strict transforms of prime
divisors appearing in $D.$ The coefficient $a_{E}$ is independent of the
morphism $f$ and depends only on the divisorial valuation of the function
field associated to $E$. The map $f:Y\to(X,D)$ is called crepant if all
$a_{E}=0,$ even in the case where $Y$ is only normal and not necessarily
smooth. We say that $(X,D)$ has Kawamata log terminal (klt) singularities if
$a_{E}>-1$ for every $E.$ When $(X,D)$ is $\mathbb{Q}$-Gorenstein and $D=0,$
then $X$ is $\mathbb{Q}$-Gorenstein. In this case, we say that $X$ has log
terminal (resp. canonical) singularities if $a_{E}>-1$ (resp. $\geq 0$) for
every $E.$ Note that $K_{X}$ is Cartier if and only if $X$ is Gorenstein. We
recall the following well known results.

######  Proposition 2.1 ([11, Cor. 5.24]).

Suppose that $K_{X}$ is Cartier. Then $X$ has rational singularities if and
only if it has canonical singularities.

######  Proposition 2.2 ([11, Th. 5.22]).

If $(X,D)$ has Kawamata log terminal singularities with $D$ effective, then
$X$ has rational singularities.

###  2.2. Log canonical covers

Next we recall the standard technique of log canonical covers (see [10,
§8.5][14, §1.3]).

Suppose now that a $\mathbb{Q}$-Gorenstein log variety $(X,D)$ has its
boundary divisor of the form

$D=\sum_{i}\frac{e_{i}-1}{e_{i}}D_{i},\,\,e_{i}\in\mathbb{Z}_{>0}$

with $D_{i}$ prime divisors. We say that $D$ has standard coefficients. Let
$m$ be the index of $(X,D),$ that is, the least positive integer such that
$m(K_{X}+D)$ is Cartier. Given a coherent sheaf $\mathcal{F}$ on $X$ we write
$\mathcal{F}^{(n)}:=(\mathcal{F}^{\otimes n})^{**}$, the reflexive hull of the
tensor power. Locally on $X,$ fixing an isomorphism
$\omega_{X}^{(m)}(mD)\cong\mathcal{O}_{X}$, we obtain an
$\mathcal{O}_{X}$-algebra

(2.1) $\mathcal{A}:=\bigoplus_{i=0}^{m-1}\omega_{X}^{(i)}\left(\left\lfloor
iD\right\rfloor\right).$

(In [10, 14], a slightly different description of the sheaf,
$\bigoplus_{i=0}^{m-1}\mathcal{O}_{X}\left(\left\lfloor-i(K_{X}+D)\right\rfloor\right)$,
is used, though it is isomorphic to $\mathcal{A}$.) The associated finite
morphism

$\phi:\widetilde{X}:=\mathcal{S}\mathrm{pec}_{X}\,\mathcal{A}\to X$

is called a log canonical cover and has the following properties:

######  Proposition 2.3.

[10, §8.5][14, §1.3] Let $(X,D)$ be a $\mathbb{Q}$-Gorenstein log variety with
log canonical cover $\widetilde{X}$. Then $\widetilde{X}$ is an irreducible
normal variety, $K_{\widetilde{X}}$ is Cartier, and

$K_{\widetilde{X}}=\phi^{*}(K_{X}+D).$

Note that the map $\psi:\tilde{X}\rightarrow(X,D)$ is crepant by definition.

######  Proposition 2.4.

[11, Prop. 5.20] With the notation as above, $\widetilde{X}$ has canonical
singularities if and only if $(X,D)$ has Kawamata log terminal singularities.

##  3\. Centralizers of Powers of $\omega$

Let $R$ be a DVR with parameter $t$. We write $(t^{i})=t^{i}R$ for
$i\in\mathbb{Z}$, the fractional ideal generated by $t^{i}$ and
$(t^{0})=(1)=R$. Let $\Delta$ be a standard hereditary order over $R$ with
ramification index $e,$ defined to be

$\Delta=\begin{pmatrix}(1)&\cdots&\cdots&(1)\\\ (t)&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\vdots\\\ (t)&\cdots&(t)&(1)\end{pmatrix}\subseteq
R^{\,e\times e}.$

The dualizing module of $\Delta$ is described as a bimodule by
$\omega=\mathrm{Hom}_{R}(\Delta,\omega_{R})$ as described in [18, Prop. 2.7].
We compute this bimodule by forming the dual of $\Delta$ into $R$ component
wise and taking the transpose. Let $J$ be the Jacobson radical of $\Delta$, we
have:

$\omega\simeq\begin{pmatrix}(1)&(t^{-1})&\cdots&(t^{-1})\\\
\vdots&\ddots&\ddots&\vdots\\\ \vdots&\ddots&\ddots&(t^{-1})\\\
(1)&\cdots&\cdots&(1)\end{pmatrix}\text{ and
}J=\begin{pmatrix}(t)&(1)&\cdots&(1)\\\ \vdots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&(1)\\\ (t)&\cdots&\cdots&(t)\end{pmatrix}.$

Let

$y=\begin{pmatrix}0&1&0&\cdots&0\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&0\\\ 0&\ddots&\ddots&\ddots&1\\\
t&0&\cdots&\cdots&0\end{pmatrix}$

Note that $y$ is a normal element in ${\Delta}$ and

$J=y{\Delta}={\Delta}y\quad\quad
y^{e}=t\quad\quad\omega=y^{1-e}{\Delta}=yt^{-1}{\Delta}.$

An induction computation shows that

$J^{i}=y^{i}{\Delta}=\begin{pmatrix}\left(t^{-\lfloor\frac{-i}{e}\rfloor}\right)&\cdots&\left(t^{-\lfloor\frac{e-1-i}{e}\rfloor}\right)\\\
\vdots&\ddots&\vdots\\\
\left(t^{-\lfloor\frac{-e+1-i}{e}\rfloor}\right)&\cdots&\ddots\end{pmatrix}$

We note that

$\omega^{i}=y^{-i(e-1)}{\Delta}=\begin{pmatrix}\left(t^{-\lfloor\frac{i(e-1)}{e}\rfloor}\right)&\cdots&\left(t^{-\lfloor\frac{(i+1)(e-1)}{e}\rfloor}\right)\\\
\vdots&\ddots&\vdots\\\
\left(t^{-\lfloor\frac{(i-1)(e-1)}{e}\rfloor}\right)&\cdots&\ddots\end{pmatrix}$

So the centralizer of the bimodule $\omega^{i}$ is

$Z(\omega^{i})=\left(t^{-\lfloor\frac{i(e-1)}{e}\rfloor}\right).$

Write $a^{m\times n}$ for the $m\times n$ matrix with entries all $a$. We will
use this notation for $a$ being an ideal or an element of a ring.

Given a sequence of natural numbers $[N]=[n_{1},\ldots,n_{e}]$, we let
$\Delta$ be a block hereditary order given by

$\Delta=\begin{pmatrix}(1)^{n_{1}\times n_{1}}&\cdots&\cdots&(1)^{n_{1}\times
n_{e}}\\\ (t)^{n_{2}\times n_{1}}&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\vdots\\\ (t)^{n_{e}\times n_{1}}&\cdots&(t)^{n_{e}\times
n_{e-1}}&(1){}^{n_{e}\times n_{e}}\end{pmatrix}$

which we abbreviate as

$\Delta\simeq\begin{pmatrix}(1)&\cdots&\cdots&(1)\\\
(t)&\ddots&\ddots&\vdots\\\ \vdots&\ddots&\ddots&\vdots\\\
(t)&\cdots&(t)&(1)\end{pmatrix}^{[N]}$

We note that $\Delta$ is Morita equivalent to the standard hereditary
$R$-order with ramification index $e$. Since we can multiply matrices by
blocks, we have the following equations

$J=(y\Delta)^{[N]}=(\Delta
y)^{[N]}\quad\quad(y^{e})^{[N]}=t\quad\quad\omega=(y^{1-e}\Delta)^{[N]}=(yt^{-1}\Delta)^{[N]}.$

As above we get the following lemma.

######  Lemma 3.1.

Let $R$ be a DVR with parameter $t.$ Let $\Delta$ be a block hereditary order
over with ramification index $e$. Then the centralizer of powers of the
dualizing module $\omega^{i}$ are given by

$Z(\omega^{i})=\left(t^{-\lfloor\frac{i(e-1)}{e}\rfloor}\right).$

##  4\. Noncommutative Resolutions or Algebraic set up

We firstly recall some results and notation from [18]. Recall that a
$k$-algebra is affine if it is finitely generated as an algebra. We let
$\Delta$ be an affine prime $k$-algebra which is finitely generated as a
module over its centre $Z:=Z(\Delta)$. Note that $Z$ is an integral domain
[12, §10, Ex. 1], and we will write $K$ for its fraction field. Let $A$ be the
simple Artinian ring of fractions of $\Delta.$ We have that $A$ is a central
simple $K$-algebra.

We say $\Delta$ is a _tame_ $Z$-order if $\Delta$ is a finitely generated,
reflexive $Z$ module and $\Delta_{p}$ is hereditary for all codimension one
primes $p$ of $Z$. We say that $\Delta$ is homologically homogeneous if the
projective dimensions of all simple $\Delta$ modules are equal. We recall the
following result, mostly due to Brown-Hajarnavis [5], which we cite from [18].

######  Proposition 4.1.

[18, Th. 2.3] Let $\Delta$ be an affine homologically homogeneous order of
dimension $d$ with centre $Z$, then

  1. (1)

$\Delta$ is a Cohen-Macaulay module over $Z.$

  2. (2)

$\mathrm{gldim}\,\Delta=\mathrm{GKdim}\,\Delta=d$.

  3. (3)

$Z$ is an affine Cohen-Macaulay normal domain.

  4. (4)

$\Delta$ is a tame $Z$-order.

Note that the third conclusion depends on our base field $k$ having
characteristic zero.

We will now define the discriminant of a tame order in codimension one. Let
$p$ be a codimension one prime of $Z$. Since $\Delta_{p}$ is hereditary, there
is an étale extension $R$ of the DVR $Z_{p}$ so that
$\Delta_{R}:=\Delta\otimes R$ is isomorphic to

$\Delta_{R}\simeq\begin{pmatrix}(1)^{n_{1}\times
n_{1}}&\cdots&\cdots&(1)^{n_{1}\times n_{e_{p}}}\\\ (t)^{n_{2}\times
n_{1}}&\ddots&\ddots&\vdots\\\ \vdots&\ddots&\ddots&\vdots\\\
(t)^{n_{e_{p}}\times n_{1}}&\cdots&(t)^{n_{e_{p}}\times
n_{e_{p}-1}}&(1){}^{n_{e_{p}}\times n_{e_{p}}}\end{pmatrix}$

where $t$ is a parameter of $R$ [1, 16]. We will write
$[N]=[n_{1},\ldots,n_{e_{p}}]$ and abbreviate as

$\Delta_{R}\simeq\begin{pmatrix}(1)&\cdots&\cdots&(1)\\\
(t)&\ddots&\ddots&\vdots\\\ \vdots&\ddots&\ddots&\vdots\\\
(t)&\cdots&(t)&(1)\end{pmatrix}^{[N]}$

We call $e_{p}$ the ramification index of $\Delta$ at $p$. We define the
discriminant of $\Delta$ to be the $\mathbb{Q}$-divisor

$D=\sum_{\begin{array}[]{c}p\subset Z\\\
\mathrm{cod}\,p=1\end{array}}\left(\frac{e_{p}-1}{e_{p}}\right)D_{p}.$

Note that this sum is finite since $\left\lceil D\right\rceil$ is the
classical discriminant of the order $\Delta$ which is defined via the reducued
trace pairing [16, §25]. We will combine the centre of $\Delta$ with its
discriminant into the log centre,
$\mathrm{logZ}(\Delta)=(\mathrm{Spec}\,Z(\Delta),D)$.

Suppose $\Delta$ is an affine prime algebra that is a finite module over its
centre. We have [18, Lemma 2.4] that $\Delta$ is homologically homogeneous if
and only if $\Delta$ is a Cohen-Macaulay $R$-module and
$\mathrm{GKdim}\,\Delta=\mathrm{gldim}\,\Delta$.

######  Definition 4.2.

Let $\Delta$ be a prime, affine $k$-algebra, module finite over its centre. If
$\Delta$ is homologically homogeneous, or equivalently by [18, Lemma 2.4], the
algebra $\Delta$ is a Cohen-Macaulay with
$\mathrm{GKdim}\,\Delta=\mathrm{gldim}\,\Delta$, then we say that $\Delta$ is
a twisted ramified noncommutative crepant resolution (NCCR) of the pair
$\mathrm{logZ}(\Delta)=(X,D).$ If furthermore $D=0$ then we say the NCCR is
unramified. Let $K$ be the fraction field of the centre $Z$. The twist of a
twisted NCCR $\Delta$ is the class of $\Delta\otimes_{Z}K$ in
$\mathrm{Br}\,K.$ If this is trivial, then we say $\Delta$ is an untwisted
NCCR of the pair $\mathrm{logZ}(\Delta)$. A classical NCCR is untwisted and
unramified, and this the usual defintion of an NCCR in the literature.

Note that in the case that $Z(\Delta)$ is Gorenstein, our definition of a
classical NCCR is equivalent to the definition of an NCCR in [2, Defn. 2.2]
and our definition of twisted unramified NCCR is equivalent to the definition
of a twisted NCCR in [2, Defn. 2.2].

The next statement is well known.

######  Proposition 4.3.

If $\Delta$ is a maximal order and a classical NCCR of the pair $(Z,D)$ then
$D=0$ and there is a reflexive $Z$-module $M$ so that
$\Delta\simeq\mathrm{End}_{Z}(M)$.

###### Proof.

Since the generic Brauer class of $\Delta$ is trivial and $Z$ is a normal
integral domain, the above statement is true in codimension one, and so taking
the reflexive hull gives us the result. ∎

##  5\. Noncommutative Crepant Resolutions and Canonical Covers

######  Proposition 5.1.

Let
$\Gamma=\Delta\oplus\omega_{\Delta}\oplus\cdots\oplus\omega_{\Delta}^{(r-1)}$
be the canonical cover of $\Delta$ and put $\widetilde{Z}:=Z(\Gamma)$ and
$\widetilde{X}:=\mathrm{Spec}\,{}\widetilde{Z}.$ Then the morphism
$\widetilde{X}\to X$ is a log canonical cover of $(X,D)$.

###### Proof.

Let $p$ be a codimension one prime of $Z$. By [1], there is an étale extension
$R$ of $\Delta_{p}$ so that $\Delta_{R}:=\Delta\otimes R$ is isomorphic to

$\Delta_{R}\simeq\begin{pmatrix}R^{n_{1}\times
n_{1}}&\cdots&\cdots&R^{n_{1}\times n_{k}}\\\ (tR)^{n_{2}\times
n_{1}}&\ddots&\ddots&\vdots\\\ \vdots&\ddots&\ddots&\vdots\\\
(tR)^{n_{k}\times n_{1}}&\cdots&(tR)^{n_{k-1}\times n_{k}}&R{}^{n_{k}\times
n_{k}}\end{pmatrix}$

where $t$ is a parameter of the DVR $R$. Now Lemma 3.1 shows that

$Z(\omega_{\Delta_{R}}^{i})=\left(t^{-\lfloor\frac{i(e-1)}{e}\rfloor}\right)$

and so

$Z(\omega_{\Delta}^{(i)})=\omega_{X}^{(i)}(\left\lfloor iD\right\rfloor).$

étale locally in codimension one. Both sides are naturally isomorphic at the
generic point, so we obtain this isomorphism globally since both sides are
reflexive. It follows immediately that

$\widetilde{Z}=Z(\Gamma)=\bigoplus_{i=0}^{m-1}Z(\omega_{\Delta}^{(i)})=\bigoplus_{i=0}^{m-1}\omega_{X}^{(i)}(\left\lfloor
iD\right\rfloor)$

where $m$ is the index of $K_{X}+D$.

∎

Let $\Delta$ be an affine prime $k$-algebra that is module finite over its
centre. Suppose further that $\Delta$ is homologically homogeneous. Let
$Z:=Z(\Delta)$ its centre and $X:=\mathrm{Spec}\,{}Z$ its spectrum. Stafford
and Van den Bergh proved an important result about the possible singularities
of the centre:

######  Theorem 5.2 ([18]).

$X$ has only rational singularities.

In fact, we can prove the following along the same line, which is a refinement
of their result because of Proposition 2.2.

######  Theorem 5.3.

Let $D$ be the discriminant divisor on $X$ associated to $\Delta.$ Then the
log variety $(X,D)$ has Kawamata log terminal singularities. Moreover, if $X$
is $\mathbb{Q}$ -Gorenstein, then $X$ has log terminal singularities.

###### Proof.

Since the proof is local on $X,$ we may suppose that if $m$ is the index of
$(X,D),$ then $\omega_{X}^{(m)}(mD)$ is isomorphic to $Z$. Then putting
$\widetilde{Z}:=\bigoplus\omega_{X}^{(i)}(\left\lfloor iD\right\rfloor),$ we
can construct a log canonical cover of $(X,D),$

$\phi:\widetilde{X}=\mathrm{Spec}\,{}\widetilde{Z}\to X=\mathrm{Spec}\,{}Z$

as in (2.1). On the other hand, the isomorphism $\omega_{X}^{(m)}(mD)\cong Z$
defines an isomorphism $\omega_{\Delta}^{(m)}\cong\Delta$ as
$\Delta$-bimodules and we have a canonical cover of $\Delta,$

$\Gamma:=\Delta\oplus\omega_{\Delta}\oplus\cdots\oplus\omega_{\Delta}^{(m-1)}.$

We show in 5.1 that $Z(\omega_{\Delta}^{(i)})=\omega_{X}^{(i)}(\left\lfloor
iD\right\rfloor)$ and $Z(\Gamma)=\widetilde{Z}.$

Since [18, Prop. 3.1(1)] shows that $\Gamma$ is also homologically
homogeneous, so by Theorem 5.2, $\widetilde{Z}$ has rational singularities.
Now, from Propositions 2.1 and 2.4, the pair $(X,D)$ has Kawamata log terminal
singularities. The last assertion is straightforward. ∎

We note the following corollaries.

######  Corollary 5.4.

Let $A$ be an unramified NCCR of a commutative algebra $R$. Then $R$ is log
terminal and $\mathbb{Q}$-Gorenstein.

######  Corollary 5.5.

Let $\mathcal{A}$ be a (twisted, ramified) NCCR of the pair $(X,D)$. Then the
pair is Kawamata log terminal and $\mathbb{Q}$-Gorenstein.

We present an alternate proof of the theorem above. First note that:

######  Proposition 5.6.

Let $\Delta$ be an affine, prime, finite over centre, homologically
homogeneous $k$-algebra. Let $\Gamma$ be the canonical cover of $\Delta$ as in
5.1. Let $(X,D)$ the the log centre of $\Delta$ and let
$\widetilde{X}=\mathrm{Spec}\,Z(\Gamma)$. Then we have that
$K_{\widetilde{X}}=\pi^{*}(K_{X}+D)$.

###### Proof.

Let $m$ be the index of $K_{X}+D$ and let $\hat{\otimes}$ denote the reflexive
hull of the tensor product. We have the following isomorphisms:

$\Gamma\hat{\otimes}_{\Delta}\omega_{\Delta}\simeq\omega_{\Gamma}$
$\omega_{\Gamma}\simeq\omega_{\widetilde{X}}\hat{\otimes}_{\widetilde{X}}\Gamma$
$\omega_{\Delta}^{(m)}=\omega_{X}^{(m)}(mD)\otimes_{X}\Delta.$

In other words if we consider the following diagram:

$\textstyle{\mathrm{Spec}\,{}\Delta\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathrm{Spec}\,{}\Gamma\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{(X,D)}$$\textstyle{\widetilde{X}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

We know that all maps except the bottom one are crepant. Hence the bottom map
is crepant as well.∎

Using Prop. 5.6 we obtain another proof of Theorem 5.3.

###### Proof.

Since $\Gamma$ is homologically homogeneous with $Z(\Gamma)=\widetilde{Z}$, by
Thm. 5.2, we know that $\mathrm{Spec}\,\widetilde{Z}=\widetilde{X}$ is has
rational singularities. Therefore $\widetilde{X}$ is canonical by Prop. 2.1
and hence log terminal. By Prop. 5.6 we have that
$K_{\widetilde{X}}=\pi^{*}(K_{X}+D).$ So by Prop. 2.4, we have that $(X,D)$ is
Kawamata log terminal. In particular if $X$ is $\mathbb{Q}-$Gorenstein then it
is log terminal. ∎

##  6\. Corollaries and Examples

Some algebras are well known to be homologically homogeneous and so provide
examples of twisted and ramified NCCRs. We would like to thank Kenneth Brown
for the references for the following statement.

######  Proposition 6.1.

Suppose that $\Delta$ is finite over its centre and $\Delta$ is one of

  1. (1)

a Hopf algebra over an algebraically closed field.

  2. (2)

a connected graded affine noetherian algebra of finite global dimension.

  3. (3)

a not necessarily connected Artin-Schelter regular algebra.

then $\Delta$ is a (twisted, ramified) NCCR of the pair
$(Z,D)=\mathrm{logZ}(\Delta)$ which is Kawamata log terminal and
$\mathbb{Q}$-Goreinstein.

###### Proof.

The first case is [4, Prop. 1.6]. The second case is in [19]. The third case
is in [17]. ∎

######  Corollary 6.2.

The log centres of the following algebras are Kawamata log terminal.

  * •

Quantised function algebras of semisimple groups $\mathcal{O}_{q}(G)$ when $q$
is a root of unity.

  * •

Quantised enveloping algebras of semisimple Lie algebras $U_{q}(\mathfrak{g})$
when $q$ is a root of unity.

Next, we produce an example of a variety $X$ which is not
$\mathbb{Q}$-Gorenstein, but we add an appropriate boundary divisor $D$, we
obtain a $\mathbb{Q}$-Goreinstein pair $(X,D)$ which is
$\mathbb{Q}$-Goreinstein and admits a ramified NCCR.

######  Example 6.3.

Consider the quiver with vertices $Q_{0}=\\{0,1\\}$ with two arrows $u,v$ from
$0$ to $1$ and two arrows $\bar{u},\bar{v}$ from $1$ to $0$. We let $A$ be the
path algebra of this quiver with relations

$u\bar{u}v=v\bar{u}u\quad u\bar{v}v=v\bar{v}u$
$\bar{u}u\bar{v}=\bar{v}u\bar{u},\quad\bar{u}v\bar{v}=\bar{v}v\bar{u}.$

Consider the commutative ring and fractional ideals

$R=k[a,b,c,d]/(ad-bc)$ $I=aR+cR\quad\quad I^{*}=R+\frac{b}{a}R.$

Note also that

$A\simeq\begin{pmatrix}R&I\\\ I^{*}&R\end{pmatrix}$

under the isomorphism

$u\mapsto\begin{pmatrix}0&a\\\ 0&0\end{pmatrix}\quad\quad
v\mapsto\begin{pmatrix}0&c\\\ 0&0\end{pmatrix}$
$\bar{u}\mapsto\begin{pmatrix}0&0\\\
1&0\end{pmatrix}\quad\quad\bar{v}\mapsto\begin{pmatrix}0&0\\\
\frac{b}{a}&0\end{pmatrix}.$

It is well known that $A$ is Azumaya except at the origin, and is an NCCR of
$R$. We consider an action of $\mathbb{Z}/2$ on $A$ that fixes the vertices
and acts as $-1,1,1,1$ on the arrows $u,v,\bar{u},\bar{v}$ respectively. Note
that the skew group ring

$A\rtimes\mathbb{Z}/2$

has global dimension three and is homologically homogeneous. Hence it is a
ramified NCCR of its log centre.

We compute

$Z(A)=R=k[a,b,c,d](ad-bc)$
$S=Z(A\rtimes\mathbb{Z}/2)=Z(A)^{\mathbb{Z}/2}=k[a^{2},ab,b^{2},c,d]\subset
R.$

The referee noted $S\simeq k[x,y,z,c,d]/(xz-y^{2},xd-yc,yd-zc)$ which is the
base of the Francia flip. So there is a small resolution
$f:Y\to\mathrm{Spec}\,S$ given by blowing up the ideal $(c,d)$. So $K_{Y}$
must be ample or anti-ample, and $K_{Y}=f^{*}K_{S}.$ For more details see [3,
(2$\cdot$1),Lem. 2] or [15, (3.8)]. If $S$ is $\mathbb{Q}$-Gorenstein then
$nK_{S}=0$ for some $n$, giving a contradiction. We also give a toric
computation below which shows that $S$ is not $\mathbb{Q}$-Gorenstein.

We write $N=\mathbb{Z}^{3}$ and
$N^{\prime}=\mathbb{Z}^{2}\oplus\frac{1}{2}\mathbb{Z}$ and let
$M=N^{\vee},M^{\prime}=N^{\prime\vee}$ be the dual lattices. Let $\sigma$ is
the cone generated by the columns of the matrix:

$\begin{pmatrix}0&0&1&1\\\ 0&1&0&1\\\ 1&1&1&1\end{pmatrix}.$

We will see that the map of toric varieties determined by $\sigma\subset N$ to
$\sigma\subset N^{\prime}$ is the map $\mathrm{Spec}\,R\to\mathrm{Spec}\,S$.
We write

$k[M]=k[x^{\pm 1},y^{\pm 1},z^{\pm 1}]\subset k[x^{\pm 1},y^{\pm 1},z^{\pm
2}]=k[M^{\prime}].$

We have

$R=k[a,b,c,d]=k[zx^{-1},zy^{-1},y,x]=k[\sigma^{\vee}]\subset k[M^{\prime}].$
$S=k[a^{2},ab,b^{2},c,d]=k[z^{2}x^{-2},z^{2}x^{-1}y^{-1},z^{2}y^{-2},y,x]=k[\sigma^{\vee}]\subset
k[M^{\prime}].$

We compute that $A\rtimes\mathbb{Z}/2$ is ramified with index two on the toric
divisor $D_{\rho}$ corresponding to the ray generated by
$\rho=(0,0,1/2)\in\sigma\subset N^{\prime}$. Hence the pair
$(\mathrm{Spec}\,S,\frac{1}{2}D_{\rho})$ is $\mathbb{Q}$-Gorenstein and admits
a ramified NCCR. If we write the primitive generators of the rays of $\sigma$
in terms of the basis $e_{1},e_{2},\frac{1}{2}e_{3}$ of $N^{\prime},$ we
obtain the columns of the following matrix

$C=\begin{pmatrix}0&0&1&1\\\ 0&1&0&1\\\ 1&2&2&2\end{pmatrix}.$

Let $D_{1},\ldots,D_{4}$ be the toric Weil divisors corresponding to the rays.
A toric Weil divisor $n_{1}D_{1}+n_{2}D_{2}+n_{3}D_{3}+n_{4}D_{4}$ is
$\mathbb{Q}$-Cartier if and only if $(n_{1},\ldots,n_{4})$ is in the
$\mathbb{Q}$ span of the rows of the matrix $B$. It is clear that
$K_{\mathrm{Spec}\,S}=-D_{1}-D_{2}-D_{3}-D_{4}$ is not in the row span of $C$.
However as above we have $\frac{1}{2}D_{\rho}=\frac{1}{2}D_{1}$ then

$K+B=-\frac{1}{2}D_{1}-D_{2}-D_{3}-D_{4}$

is in the row span of $C$, verifying that the pair
$(\mathrm{Spec}\,S,\frac{1}{2}D_{\rho})$ is $\mathbb{Q}$-Gorenstein. So we see
that the toric variety $\mathrm{Spec}\,S$ is not $\mathbb{Q}$-Goreinstein and
does not admit an unramified NCCR, and there is a ramified NCCR of the pair
$(\mathrm{Spec}\,S,\frac{1}{2}D_{\rho})$.

In the next example, the singularity $X$ is well known to not have a classical
NCCR [7, Thm. 3.1,Rmk. 3.2], but with an appropriate divisor $D$, we obtain a
twisted ramified NCCR of the pair $(X,D)$. This shows that the pair is
Kawamata log terminal and $\mathbb{Q}$-Gorenstein. We would like to thank
Michael Wemyss for providing us with this example.

######  Example 6.4.

Let $A$ be the $k$-algebra generated by $a,b,c$ with relations

$ac+ca,\quad bc+cb,\quad ab-ba-2c^{3}.$

The centre $Z(A)$ is generated by

$x:=a^{2},\quad y:=b^{2},\quad z:=ab+ba,\quad t:=c^{2}.$

One may verify that

$z^{2}-4xy=(ab-ba)^{2}=4c^{6}=4t^{3}.$

So the centre has the compound Du Val singularity with a quadric cone in its
resolution [13, Fig. 8-3-5]. This singularity does not have a noncommutative
crepant resolution [7, Thm. 3.1,Rmk. 3.2].

The resolution

$0\to
A\stackrel{{\scriptstyle\begin{pmatrix}b&a&c\end{pmatrix}}}{{\longrightarrow}}A^{3}\stackrel{{\scriptstyle\begin{pmatrix}-c&0&-a\\\
0&c&b\\\
-b&a&-2c^{2}\end{pmatrix}}}{{\longrightarrow}}A^{3}\stackrel{{\scriptstyle\begin{pmatrix}a\\\
b\\\ c\end{pmatrix}}}{{\to}}A\to k\to 0$

shows that $A$ is Artin-Schelter regular and so is homologically homogeneous.
Lastly, we compute that $A$ is ramified on the divisor $B$ defined by $t=0.$
So if we let $X=\mathrm{Spec}\,Z(A)$ and $D=\frac{1}{2}B$ we have that $(X,D)$
has a twisted noncommutative crepant resolution and so is Kawamata log
terminal and $\mathbb{Q}$-Gorenstein.

We also point out that $A$ can be viewed as a Clifford algebra. Let

$Z=k[x,y,z,t]/(z^{2}-4xy-4t^{3})$

and define a quadratic form $Q$ on $Z$ given by the Gram matrix

$\begin{pmatrix}2x&z&0\\\ z&2y&0\\\ 0&0&2t\end{pmatrix}.$

Write $\mathrm{Cl}(Q)$ for the Clifford algebra of this form, generated by
$a,b,c$ as an $Z$-algebra with relations

$2a^{2}=2x,\quad ab+ba=z,\quad 2b^{2}=2y,\quad ac+ca=bc+cb=0,\quad 2c^{2}=2t.$

Note that in this algebra we have $(ab-ba)^{2}=(2c^{3})^{2}$ giving a prime
ideal generated by $(ab-ba-2c^{3})$ so we have

$A=\mathrm{Cl}(Q)/(ab-ba-2c^{3}).$

This description can be used to show that $A$ is non-trivially twisted.

## References

  * [1] M. Artin, _Left ideals in maximal orders_ , Brauer groups in ring theory and algebraic geometry (Wilrijk, 1981), Lecture Notes in Math., vol. 917, Springer, Berlin-New York, 1982, pp. 182–193. MR 657429
  * [2] Michel Van den Bergh, _Non-commutative crepant resolutions, an overview_ , 2022\.
  * [3] Gavin Brown, _Flips arising as quotients of hypersurfaces_ , Math. Proc. Cambridge Philos. Soc. 127 (1999), no. 1, 13–31. MR 1692523
  * [4] K. A. Brown and K. R. Goodearl, _Homological aspects of Noetherian PI Hopf algebras of irreducible modules and maximal dimension_ , J. Algebra 198 (1997), no. 1, 240–265. MR 1482982
  * [5] K. A. Brown and C. R. Hajarnavis, _Homologically homogeneous rings_ , Trans. Amer. Math. Soc. 281 (1984), no. 1, 197–208. MR 719665
  * [6] Herbert Clemens, János Kollár, and Shigefumi Mori, _Higher-dimensional complex geometry_ , Astérisque (1988), no. 166, 144 pp. (1989). MR 1004926
  * [7] Hailong Dao, _Remarks on non-commutative crepant resolutions of complete intersections_ , Adv. Math. 224 (2010), no. 3, 1021–1030. MR 2628801
  * [8] Hailong Dao, Osamu Iyama, Ryo Takahashi, and Michael Wemyss, _Gorenstein modifications and $\mathbb{Q}$-Gorenstein rings_, J. Algebraic Geom. 29 (2020), no. 4, 729–751. MR 4158464
  * [9] Colin Ingalls, _Centres of nccrs are klt_ , https://www.msri.org/workshops/643/schedules/16756, A talk at the workshop ”Interactions Between Noncommutative Algebra, Representation Theory, And Algebraic Geometry”, MSRI, 2013.
  * [10] Yujiro Kawamata, _Log canonical models of algebraic $3$-folds_, Internat. J. Math. 3 (1992), no. 3, 351–357. MR 1163730
  * [11] János Kollár and Shigefumi Mori, _Birational geometry of algebraic varieties_ , Cambridge Tracts in Mathematics, vol. 134, Cambridge University Press, Cambridge, 1998, With the collaboration of C. H. Clemens and A. Corti, Translated from the 1998 Japanese original. MR 1658959
  * [12] T. Y. Lam, _A first course in noncommutative rings_ , second ed., Graduate Texts in Mathematics, vol. 131, Springer-Verlag, New York, 2001. MR 1838439
  * [13] Kenji Matsuki, _Introduction to the Mori program_ , Universitext, Springer-Verlag, New York, 2002. MR 1875410
  * [14] Yuri G. Prokhorov, _Lectures on complements on log surfaces_ , MSJ Memoirs, vol. 10, Mathematical Society of Japan, Tokyo, 2001. MR 1830440
  * [15] Miles Reid, _Decomposition of toric morphisms_ , Arithmetic and geometry, Vol. II, Progr. Math., vol. 36, Birkhäuser Boston, Boston, MA, 1983, pp. 395–418. MR 717617
  * [16] I. Reiner, _Maximal orders_ , London Mathematical Society Monographs. New Series, vol. 28, The Clarendon Press, Oxford University Press, Oxford, 2003, Corrected reprint of the 1975 original, With a foreword by M. J. Taylor. MR 1972204
  * [17] Manuel L. Reyes and Daniel Rogalski, _Graded twisted Calabi-Yau algebras are generalized Artin-Schelter regular_ , Nagoya Math. J. 245 (2022), 100–153. MR 4413364
  * [18] J. T. Stafford and M. Van den Bergh, _Noncommutative resolutions and rational singularities_ , vol. 57, 2008, Special volume in honor of Melvin Hochster, pp. 659–674. MR 2492474
  * [19] J. T. Stafford and J. J. Zhang, _Homological properties of (graded) Noetherian ${\rm PI}$ rings_, J. Algebra 168 (1994), no. 3, 988–1026. MR 1293638


# The Half-Life of a Tweet

Jürgen Pfeffer, Daniel Matter, Anahit Sargsyan

###### Abstract

Twitter has started to share an _impression_count_ variable as part of the
available public metrics for every Tweet collected with Twitter’s APIs. With
the information about how often a particular Tweet has been shown to Twitter
users at the time of data collection, we can learn important insights about
the dissemination process of a Tweet by measuring its impression count
repeatedly over time. With our preliminary111Data collection and analysis of
this short paper are limited, due to the fact that this new feature was
released just 10 days before the ICWSM 2023 submission deadline. analysis, we
can show that on average the peak of impressions per second is 72 seconds
after a Tweet was sent and that after 24 hours, no relevant number of
impressions can be observed for ${\sim}95\%$ of all Tweets. Finally, we
estimate that the median half-life of a Tweet, i.e. the time it takes before
half of all impressions are created, is about 80 minutes.

## Introduction

The idea that information can lose its value over time has long been studied
in library science and bibliometrics (Gosnell 1944; Burton and Kebler 1960). A
very important metric to assess this value loss is information _half-life_ ,
which describes the time span in which half of the information value is lost.
The information value of books can be measured with the number of times a
particular book is borrowed from a library, and one way to characterize the
value of a scientific article is the number of times an article is cited.
Modeling these temporal observations allows us to model decay functions and
estimate the time point of 50% under the curve.

In the context of scientific literature, half-life periods are typically on
the time level of years. When we turn to news articles, the half-life in terms
of stories published in relation to a certain topic or event comes down to
several days. With the advent of the 24-hour news cycle and the rise of social
media, the information value of news has suffered an even faster decay
(Barkemeyer et al. 2020).

On Twitter, presenting the number of likes and re-Tweets for every Tweet has
been an integral part of the platform since its beginning and has been used in
order to discuss a wide variety of scores for popularity and to approximate
the reach and life span of a Tweet (Kobayashi and Lambiotte 2016; Bae, Ryu,
and Kim 2014). So far, the actual number of how many people have seen a Tweet
was only available for a user’s own Tweets.

Starting December 15, 2022, Twitter has been making the number of _views_
—which is the name of the _impression_count_ in the platform’s GUIs—visible
for every Tweet via its web interface as well as via mobile APPs: “View counts
show the total number of times a Tweet has been viewed. With view counts, you
can easily see the reach …”222https://help.twitter.com/en/using-twitter/view-
counts On January 5, 2023, it was publicly
announced333https://twitter.com/suhemparack/status/1611085481395224576 that
the impression count will now also be available via Twitter’s API v2 for every
Tweet as part of the public metric information.

### Questions and contributions.

The availability of this feature in the API data has motivated our study. We
utilize the Academic API (Pfeffer et al. 2022), which is free for research
purposes and allows for full-archive searches on Twitter, We try to answer the
following questions, which also enumerate the contributions of this article:

_How can we observe the diffusion dynamics of a Tweet in terms of reach over
time?_ We will illustrate how the Academic API can be used to repeatedly
collect information about the same Tweets in order to create a time series
dataset of impressions.

_What are the properties of the short-term temporal impression distribution,
i.e., how many impressions happen when and when is the peak during the early
phase?_ We show how to use the time series dataset to interpolate an average
diffusion curve of impressions on a second timescale.

_Can we show evidence that the diffusion process of Tweets comes to a
relatively early stop so that we have sufficient overall impression counts in
order to identify the half-life time points?_ We can show that the impression
expansion slows down dramatically or even comes to a complete stop for the
vast majority of Tweets very quickly so that we can focus our analyses on the
first 24 hours of a Tweet’s life.

_Finally, can we determine the average half-life of a Tweet?_ We will show
that, by ignoring a small number of very successful and long-lasting Tweets,
we are able to define the median half-life of a Tweet with 79.5 minutes.

## Related Work

### Information half-life of scientific literature.

Information half-life, i.e., the time it takes until an entity of information
has lost half of its value, has been studied for decades in the context of
scientific articles (Burton and Kebler 1960) and books in libraries (Gosnell
1944). Historically, half-lives ranging from 3 to 12 years have been observed,
with longer half-lives in theoretical sciences (Line 1970). The processes of
discovery of new knowledge and the accumulation of existing knowledge
underlying the citation process result in the observed half-life phenomenon.
Publication delays (Egghe and Rousseau 2000) and forgetting knowledge (van
Raan 2000) account for some differences in half-life across disciplines. When
the half-life of academic material is modeled mathematically, exponential
decay functions are used to describe the dynamics (Gosnell 1944; Gupta 1990;
Tsay 1998).

### Half-life of news media.

For news stories, the journalistic production cycles have information decay
built into the system as a way to keep readership, viewership (Cushion and
Lewis 2021), and revenues (Clemons and Lang 2003). For a specific event that
is covered in the news, the half-life is measured as the time until half of
the corresponding articles appear. While there are nuanced differences in
half-life patterns of media coverage caused by various forms of online and
offline external factors (Jennings and Saunders 2019), the analysis of the
dynamics of coverage in printed news outlets reveals a faster decay in light
of the emergence of social media (Barkemeyer et al. 2020).

Figure 1: Distribution of number of views after ${\sim}30$ Minutes

### Information decay in social media

The success of posts on many social media platforms is dependent on shares or
views. In the case of Twitter, there are two main approaches to quantify the
popularity of a tweet: utilizing the number of retweets, and the audience
size, i.e., the number of users who had the tweet in their feed. In the past,
one way to calculate the audience size was to use the number of followers for
each person who retweets a post. Despite the advantages of potential audience
size and of approximation techniques for audience size (Kupavskii et al.
2013), the number of retweets, likes and comments have been used in numerous
studies to quantify and predict the reach (Kobayashi and Lambiotte 2016) and
the lifespan of a tweet (Bae, Ryu, and Kim 2014). The studies range from
analyzing the effect of multimedia on tweet popularity (Joseph et al. 2018;
Zhao, Buro et al. 2020), the success of personification of brands on Twitter
(Greene et al. 2022) to using social media engagement to not only improve
predictions of the traffic flow of the news articles, but also to estimate the
shelf-life, a variation of half-life, of the articles (Castillo et al. 2014).

With the new _impression_count_ variable in Twitter’s API data, we are—for the
first time—able to directly get information about the reach of a certain
Tweet.

## Data

With Twitter’s Academic API v2 (Pfeffer et al. 2022), we have collected 22,144
Tweets on January 6, 2023, as well as the number of views of these tweets in
the following way. During the time 9:00-20:00 UTC, we randomly selected ten
individual minutes and collected all Tweets (excluding re-Tweets) from the
$42^{nd}$ second of these minutes, as described in Pfeffer et al. (2023). For
every second of data (on average 2,214 Tweets), we first started to collect
the Tweets exactly 10 seconds after the expiration of the second of interest.
After this collection process had finished, we immediately re-started it and
collected the same set of Tweets again. We have repeated this collection
effort 99 times for every observed second of Twitter data. Since every single
API call is limited to a maximum of 500 Tweets, several calls (happening at
different timestamps) are necessary for data collection. Consequently, we have
stored the exact time of data collection for every API call. For the following
analyses, we kept 21,685 Tweets that were available (i.e., not deleted or
hidden) in all 99 collection attempts.

The time series of the Tweet views were, on average, collected over 1,893
seconds (${\sim}31.5$ minutes). While this dataset is sufficient for the
majority of the statistical analysis of this article, we do not expect Tweet
half-lives to be under half an hour. Consequently, we also collected a second
dataset to get a longer period of view data. We performed the following second
data collection similar to the approach described above. However, this time we
have collected impression counts of about 5,000 Tweets over the course of
eleven hours for 1,000 times, as well as the view counts of these Tweets after
24 hours.

## Analyses

Figure 2: Proportion of views over time.
Figure 3: Best log (red) and sigmoid (blue) fit over time.

### Number of Views.

The time series of the Tweet views were collected on average over 1,893
seconds (${\sim}31.5$ minutes) after the Tweets were sent. During this time,
the Tweets accumulated, on average, 46.2 views (range 0–43,870). 15.6% of
Tweets had zero views. Fig. 1 plots the $log_{10}$–distribution of the number
of views. Due to the nature of the long-tailed distribution with a small
number of Tweets with a very large number of views (about 0.5% having more
than 1,000 views), the median of 7 will better represent the view
distribution.

### Diffusion patterns.

In Fig. 2, we have plotted the views-over-time curves for all 2,723 Tweets of
our sample that received more than 50 impressions by the end of the data
collection. Looking more closely at our data, it becomes obvious that we can
observe two different diffusion dynamics.

The _sigmoid_ type (eq. 1) represents Tweets that reach their maximum
potential for impressions very fast and quickly saturate. Without further
analysis, we can assume that these Tweets remain within their local areas of
the network and they receive few or no retweets.

$T_{a,b}^{sigmoid}(t)=\frac{1}{1+(b*exp(-a*x))}-\frac{1}{1+b}$ (1)

Fig. 4 (which we will discuss later), appears to imply that new views are
distributed according to ${\sim}t^{-1}$, implying the cumulative view count to
follow a _log_ -curve, which can be described as:

$T_{a,b}^{log}(t)=b*\frac{log(a*x+1)}{log(a+1)}$ (2)

Fig. 3 is based on the same data as Fig. 2. Here, every time series was fit
with both model types and drawn with the better fitting (as measured by the
MSE every ten seconds) function. The curves are then colored red when the
_sigmoid_ -model (eq. 1) was used and blue for the _log_ -model (eq. 2). The
_sigmoid_ -model performs better if we allow estimation over 1.0, which makes
sense when imagining the future development of the curves.

Identifying the diffusion type of a Tweet at an early stage can be helpful in
predicting its future view count development. For our data, categorizing
Tweets as _log_ \- or _sigmoid_ -types improves the prediction of how many
views they received after 24 hours significantly. _Log_ -tweets receive, on
average, 29% more views after 24 hours, with a significance of $\alpha<1\%$.

### 15 Minutes of fame?

Another question for understanding the diffusion processes of Tweets is to
estimate the relative temporal peak, i.e., when will most users see a Tweet?
To answer this question, we took the approximately 18,000 Tweets of our
collected data that were available in all 99 data collections and had at least
1 view overall. We then extracted for every time series the differences in
views among all pairs of consecutive collection time stamps and divided these
numbers by the number of views for each Tweet after all collection rounds.
Every proportion of increase per time interval was then distributed evenly to
all seconds of the respective time interval. In other words, we have summed up
the distribution of the proportions of the view increases every second for
every Tweet. It is important to note that with this approach, we level out two
groups of outliers: a) Tweets with a very high view number because they
contribute the same 1.0 as an unimportant tweet, and b) tweets with
potentially diverging diffusion curves because their diverging contribution
will be negligible for the overall curve.

The result of this process can be seen in Fig. 4. The fact that the peak of
average views per second is reached quickly, followed by a steep decay,
resonates with our previous analytical steps. Here, we can see that the peak
at which most impressions per second are created is, on average, 72 seconds
after a Tweet is created.

### 24 hours later.

To better understand the diffusion dynamics of Tweets beyond the first
minutes, we have collected the above-described Tweets again after 1/2/3 days.
Let us first compare the view numbers of the Tweets at the age of 1 and 3
days. These results are very clear and are shown in Tab 1. In a nutshell,
almost 1/3 of all Tweets that have gotten views within the first 24 hours do
not receive any more views within the subsequent 48 hours, and only about 1 in
20 Tweets can increase the views by more than 50% during this time span.444And
just so that it is double-checked as well: No single Tweet had fewer views
after three days than it had after one day.

Increase Views Day 1 $\rightarrow$ 3 | Percentage
---|---
\+ 0% | 29.6%
<=10% | 36.3%
>10% … <=50% | 28.6%
>50% | 5.5%
Table 1: Proportion of Tweets that can/cannot increase view counts from day 1
to day 3

Figure 4: Average views per second within the first ${\sim}20$ min.

Figure 5: Distribution of half-life values with mean = 131.6 min. (dashed
line) and median = 79.5 min. (dotted line).

The picture does look different when comparing the number of views after the
initial 20 minutes of observation with the numbers after 24 hours. Here, the
median increase in view count is a factor of 3.75.

### Half-life of Tweets.

Since the view counts from 20 minutes to 24 hours changed by a factor of 3.75,
we cannot observe 50% of views within this dataset, and this data is not
sufficient for empirically measuring the half-life of a Tweet. Consequently,
we turned to the second dataset, which includes 1,000 data collections of
about 5,000 Tweets over the course of 11 hours. Consistently with the previous
data collection, 8.5% of Tweets had zero views after 24 hours. For the
remaining Tweets, we have evaluated how long it took for every Tweet to reach
50% of the 24h view numbers. In less than 4% of Tweets, this was not possible,
i.e., the Tweets reached the 50% level after the first eleven hours,
confirming our previous observation that view counts reduce quickly over time
for the vast majority of Tweets.

Fig. 5 illustrates the distribution of half-lives in our second dataset. The
right-skewed distribution has an arithmetic mean of $131.6$ minutes (dashed
line) and a median of 79.5 minutes (dotted line) with the following quantiles:

Quantile | 10% | 25% | 50% | 75% | 90%
---|---|---|---|---|---
Half-Life | 7.2 | 26.3 | 79.5 | 175.5 | 342.1

## Outlook

### Future research questions

The most obvious future research questions are related to identifying the
factors that drive view counts and half-life. At every data collection, we
also get the number of re-tweets and likes at the moment of data collection.
Mathematically modeling and studying the temporal interplay of these times
series with the number of views is a topic for a separate paper. Other
features that are available via the Twitter API are the number of followers of
the tweet senders, the tweet content, and possibly connected images and
websites, to name just a few.

We are aware that there are Tweets that go viral days or even months after
they were sent. We did not account for these dynamics. However, long-term
phenomena could be studied with our approach of repeatedly collecting
information about the same set of Tweets (e.g., once a day).

Finally, studying human behavior with social media data always comes with
challenges related to biases and data quality (Ruths and Pfeffer 2014). The
addition of the impression count to the list of variables, which researchers
can get from API calls, will open up great new research opportunities to study
popular users and content as well as more nuanced diffusion processes. At the
same time, research also has to focus on revealing technical details and
possible artifacts of view counts and, more broadly, Twitter metrics.

### Secrets.

One surprising observation of this study was that a significant proportion of
Tweets do not get any views. Are these Tweets getting banned, but not deleted?
This and many other questions are related to the fact that social media
platforms, including Twitter, are secretive about their algorithms and data
handling. Besides investigating platform dynamics to improve research quality,
we also need to hold the platforms accountable whenever possible to increase
transparency about data handling and algorithmic content filtering.

## Research Ethics and Reproducibility

In this study, we used only publicly available data from Twitter and only
utilized Twitter’s own APIs to collect data. We did not send any Tweets and
did not interact with other Twitter accounts. Our only variables extracted
from the Twitter data were Tweet IDs, timestamps of when the Tweets were
created, and the impression count, which is part of the public metric
variable. No Tweet texts, account profile information, or other information
that could identify individuals or groups (PII) were analyzed.

### Reproducibility.

All data from the analyses of this article are available online
(_www.pfeffer.at/data/halflife_). The data includes all Tweet IDs, Tweet
creation time, and for each collection iteration for every Tweet, its
collection time, and the number of views. Since the views are a function of
when the Tweets are collected, we have expanded the JSON response data from
the Twitter API that is stored in files with the exact time of every API
query.

## Acknowledgments

J.P. wants to thank Dr. Kathleen M. Carley and Dr. Larry Richard Carley for
discussing historical literature related to the topic as well as the potential
mathematical operationalization of information half-life.

## References

  * Bae, Ryu, and Kim (2014) Bae, Y.; Ryu, P.-M.; and Kim, H. 2014.  Predicting the lifespan and retweet times of tweets based on multiple feature analysis.  _Etri Journal_ , 36(3): 418–428.
  * Barkemeyer et al. (2020) Barkemeyer, R.; Faugère, C.; Gergaud, O.; and Preuss, L. 2020.  Media attention to large-scale corporate scandals: Hype and boredom in the age of social media.  _Journal of Business Research_ , 109: 385–398.
  * Burton and Kebler (1960) Burton, R. E.; and Kebler, R. W. 1960.  The “half-life” of some scientific and technical literatures.  _American Documentation_ , 11(1): 18–22.
  * Castillo et al. (2014) Castillo, C.; El-Haddad, M.; Pfeffer, J.; and Stempeck, M. 2014.  Characterizing the life cycle of online news stories using social media reactions.  In _Proceedings of the 17th ACM conference on Computer supported cooperative work & social computing_, 211–223.
  * Clemons and Lang (2003) Clemons, E. K.; and Lang, K. R. 2003.  The Decoupling of Value Creation from Revenue: A Strategic Analysis of the Markets for Pure Information Goods.  _Information Technology and Management_ , 4(2/3): 259–287.
  * Cushion and Lewis (2021) Cushion, S.; and Lewis, J. 2021.  _The Rise of 24-Hour News Television_.  New York, United States of America: Peter Lang Verlag.
  * Egghe and Rousseau (2000) Egghe, L.; and Rousseau, R. 2000.  The influence of publication delays on the observed aging distribution of scientific literature.  _Journal of the American Society for Information Science_ , 51(2): 158–165.
  * Gosnell (1944) Gosnell, C. F. 1944.  Obsolescence of Books in College Libraries.  _College & Research Libraries_, 5(2): 115–125.
  * Greene et al. (2022) Greene, T.; Seet, C.; Barrio, A. R.; McIntyre, D.; Kelly, B.; and Bragg, M. A. 2022\.  Brands with personalities–good for businesses, but bad for public health? A content analysis of how food and beverage brands personify themselves on Twitter.  _Public health nutrition_ , 25(1): 51–60.
  * Gupta (1990) Gupta, U. 1990.  Obsolescence of physics literature: Exponential decrease of the density of citations to Physical Review articles with age.  _J. Am. Soc. Inf. Sci._ , 41: 282–287.
  * Jennings and Saunders (2019) Jennings, W.; and Saunders, C. 2019.  Street demonstrations and the media agenda: An analysis of the dynamics of protest agenda setting.  _Comparative Political Studies_ , 52(13-14): 2283–2313.
  * Joseph et al. (2018) Joseph, N.; Sultan, A.; Kar, A. K.; and Vigneswara Ilavarasan, P. 2018.  Machine learning approach to analyze and predict the popularity of tweets with images.  In _Conference on e-Business, e-Services and e-Society_ , 567–576. Springer.
  * Kobayashi and Lambiotte (2016) Kobayashi, R.; and Lambiotte, R. 2016.  Tideh: Time-dependent hawkes process for predicting retweet dynamics.  In _Tenth International AAAI Conference on Web and Social Media_.
  * Kupavskii et al. (2013) Kupavskii, A.; Umnov, A.; Gusev, G.; and Serdyukov, P. 2013.  Predicting the audience size of a tweet.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 7(1), 693–696.
  * Line (1970) Line, M. B. 1970.  The ‘Half‐Life’ of periodical literature: apparent and real obsolescence.  _Journal of Documentation_ , 26: 46–54.
  * Pfeffer et al. (2023) Pfeffer, J.; Matter, D.; Jaidka, K.; Varol, O.; Mashhadi, A.; Lasser, J.; Assenmacher, D.; Wu, S.; Yang, D.; Brantner, C.; Romero, D. M.; Otterbacher, J.; Schwemmer, C.; Joseph, K.; Garcia, D.; and Morstatter, F. 2023.  Just Another Day on Twitter: A Complete 24 Hours of Twitter Data.  arXiv:2301.11429.
  * Pfeffer et al. (2022) Pfeffer, J.; Mooseder, A.; Lasser, J.; Hammer, L.; Stritzel, O.; and Garcia, D. 2022\.  This Sample seems to be good enough! Assessing Coverage and Temporal Reliability of Twitter’s Academic API.  arXiv:2204.02290.
  * Ruths and Pfeffer (2014) Ruths, D.; and Pfeffer, J. 2014.  Social Media for Large Studies of Behavior.  _Science_ , 346(6213): 1063–1064.
  * Tsay (1998) Tsay, M.-Y. 1998.  Library journal use and citation half-life in medical science.  _Journal of the American Society for Information Science_ , 49(14): 1283–1292.
  * van Raan (2000) van Raan, A. F. J. 2000.  On Growth, Ageing, and Fractal Differentiation of Science.  _Scientometrics_ , 47(2): 347–362.
  * Zhao, Buro et al. (2020) Zhao, M.; Buro, K.; et al. 2020.  Comparisons Between Text-Only and Multimedia Tweets on User Engagement.  In _2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC)_ , 3825–3831. IEEE.