# PC4 at Age 40

Michael Freedman  Michael Freedman
Microsoft Research, Station Q, and Department of Mathematics
University of California, Santa Barbara
Santa Barbara, CA 93106

This article is not a proof of the Poincaré conjecture but a discussion of the
proof, its context, and some of the people who played a prominent role. It is
a personal, anecdotal account. There may be omission or transpositions as
these recollections are 40 years old and not supported by contemporaneous
notes, but memories feel surprisingly fresh. I have not looked up old papers
to check details of statements; this article is merely a download from my
current mental state.111This is a written version for a CMSA lectured
delivered at Harvard on September 28, 2020.

Poincaré liked to argue in many ways: analytically, combinatorially, and
topologically. He seemed averse to even fixing a definition for the term
“manifold,” so one should not impose modern notions like TOP, PL, and DIFF on
his famous conjecture. He himself seems to have thought little about his own
conjecture, since it asked if simply connected manifolds were spheres; clearly
he meant to also specify that the homology should also vanish (except in the
highest and lowest dimensions). The modern statement, now known to be true in
every dimension is: a closed topological manifold $M$ that is homotopy
equivalent to a sphere is homeomorphic to that sphere. One cannot replace
homeomorphism with diffeomorphism throughout the statement because of examples
like Milnor’s exotic 7-spheres. In all dimensions you still experience most of
the excitement if you presume from the start that the manifold $M^{n}$ has a
smooth structure and the goal is to prove it homeomorphic to $S^{n}$. We will
take this perspective.222In dimension $>3$ work of Lashoff [lashof70] smooths
a connected, contractible, topological $M$ and this can be used to bridge to
the strongest statement, but the cost is one must use a technically more
difficult (proper) version of the work of Smale discussed below. In dimensions
$<4$ there are canonical smooth structures [moise52a, moise52b].

When the dimension $n$ is 0 or 1 there is not much to prove. The $n=2$ result
is a special case of uniformization. The first modern work is Smale’s
[smale56] in which he proved PC$n$, $n\geq 5$. I will need to say something
about his proof since the case of PC4 starts the same way but encounters a
special problem when $n=4$. Solving this problem brings in the topological
category in a way not present in Smale’s work. The reader might think Smale
must also have labored in the topological category since the conclusion is
only homeomorphism not diffeomorphism. But 99% of Smale’s work is in a smooth
setting; his great achievement, the $h$-cobordism, theorem is smooth category.
The step from the $h$-cobordism theorem to PC$n$ is small and in some
dimensions involves a gluing along an $S^{n-1}$ which might not be extended to
a diffeomorphism over $D^{n}$. So PC4 amounts to Smale’s outline with a
topological twist. But here the tail wags the dog. When you delve into this
detail the twist expands to fill your entire field of view. The final case
(historically), dimension 3, was proved by Perelman [perelman03a, perelman03b]
using Hamilton’s theory of Ricci flow. It is entirely different in outline,
more like Beethoven’s 9th than a conventional proof, and still stands as the
greatest accomplishment of 21st century mathematics.

I worked towards PC4 from 1974 to 1981, roughly half time. I had many mental
pictures but no notes when it came to writing the proof. I realized I had no
letters (in my mind) for any of the spaces, maps, or relations. Apparently as
a youngster I had not learned yet to think in or with symbols. When written,
the proof was hard for others to understand; when I tried to explain it, I did
not know where to begin. To this day I regret that in my lectures at Berkeley
with Smale in the audience, I never even mentioned that it was his proof, with
a twist, that I was presenting. From the perspective of a youth in 1981, 1959
might as well have been 1859, I did not feel the historical connections. Now
they seem obvious and I will try to capture them here.

Three streams of thought enter the proof and I will personify them with the
names of three mathematicians: Steve Smale, Andrew Casson, and Bob Edwards. Of
course, each represents a field and there are other names as well, but in all
three cases the power of their individual ideas is so strong and so
determinative of the form of the final proof that little is lost by
identifying them with their fields of work. To put a name to their work (as
relevant here):

  * $\bullet$

Smale: Classical smooth topology and dynamics.

  * $\bullet$

Casson: How to get started in 4D: “finger moves” simplify $\pi_{1}$, leading
eventually to “Casson handles.”

  * $\bullet$

Edwards: Manifold factors, decomposition spaces, shrinking.

I will explain, in order, the input from each of these three streams and
recall the occasional anecdote.

By the time (1959) of Smale’s paper Morse theory had already moved on to
infinite dimensions. People knew the Morse inequalities and that seemed to be
regarded as a satisfactory link between critical points and homology of
manifolds. Smale took a much closer look. Let us recall his set up.
Henceforth, all manifolds are assumed to be compact and smooth. Let $W^{n+1}$
be an $(n+1)$-dimensional manifold with two boundary components, $M_{0}$ and
$M_{1}$. Let us assume all three fundamental groups are trivial, and the
relative homology vanishes: $H_{\ast}(W,M_{0};\mathbb{Z})=0$. (Of course by
duality, the relative homology groups also vanish if we replace $M_{0}$ with
$M_{1}$.) With these hypotheses $W$ is called a (simply connected)
$h$-cobordism.

######  Theorem 1 (Smale’s $h$-cobordism theorem (hCT)).

A simply connected $h$-cobordism $W^{n+1}$ is diffeomorphic to a product
$M_{0}\times I$, provided $n>4$.

The idea of the proof is to relentlessly match the algebra of the Morse
complex of a smooth Morse function, $f:W\rightarrow[0,1]$ to the geometry, or
as Smale would say, the dynamics of the gradient ($\nabla f$) flow. The Morse
complex has critical points of index $k$ as its chain group generators in
dimension $k$, and the differential of the complex records in matrix form the
algebraic number $\\#_{i,j}$ of times the boundary of the $i$th $k$-cell wraps
over the $j$th $(k-1)$-cell. The Morse cancelation lemma states that if the
geometric count $\\#_{i,j}=\pm 1$, the two critical points can be cancelled,
and the Morse functions simplified. Smale realized that the in the simply
connected case, the vanishing of the relative homology groups was the only
obstruction to performing a series of deformations to $f$ (called “handle
slides,” or in the algebra, “row operations”) that lead to cancelation of
_all_ critical points. Once there are no critical points left, the gradient
flow lines define the desired product structure.

Matching the geometry to the algebra consists of turning the algebraic
information that the signed sum of intersection points
$\\#_{i,j}=1\in\mathbb{Z}$ into the stronger geometric information that the
$i$th descending sphere truly meets the $j$th ascending sphere in one
transverse point, not for example three points in a $+,-,+$ pattern. To
accomplish this he employed Whitney’s trick [whitney44] for removing pairs of
oppositely signed double points. These double points live in an
$n$-dimensional cross-section $L^{n}$ of $W$, often called the middle level,
and Whitney’s method requires $n>4$. The dimension restriction arises because
a 2 dimensional disk, the “Whitney disk,” guides the cancellation of the extra
$(+,-)$ pair and we need that disk to be embedded; an easy thing when
$\dim(L)=n>4$, and a difficult thing otherwise. The proof of PC4 follows Smale
up to this point, from there forward it is all about how to locate the Whitney
disks necessary to make $\\{A\\}$ and $\\{D\\}$, the ascending and descending
2-spheres in the middle level $L$, intersect each other _geometrically_ in
single transverse points, as the algebra would indicate. So Smale has gotten
us started but we are left with the problem of simplifying, say, a canonical
picture in the middle level $L^{4}$ of two embedded 2-spheres $A$ and $D$
which meet in three points $+,-,+$.

It is here where Casson’s work begins. Before turning to Casson, this is a
good place to explain how the hCT implies various PCn. There are actually two
overlapping techniques (both due to Smale). Suppose $\Sigma^{n}$ is a homotopy
$n$ sphere. We can cut out two disjoint balls from $\Sigma^{n}$ to obtain an
$n$ dimensional $h$-cobordism $W^{n}$. If $n$ is at least 6 the hCT recognizes
$W$ as diffeomorphic to $S^{n-1}\times I$. $\Sigma^{n}$ is now obtained by
gluing back the two balls, but the gluing diffeomorphisms reflect the
complexity of the product structure output of the hCT and we don’t know that
the result is diffeomorphic to $S^{n}$. We see from this picture that $\Sigma$
is two balls glued together by a homeomorphism of their boundaries. It is
elementary (via Alexander’s coning trick) that the union is homeomorphic to
$S^{n}$. To handle the lowest dimensional case treated by Smale, $\Sigma^{5}$,
a different strategy is required. Some algebraic topology and a bit of surgery
theory is used to construct a 6D $h$-cobordism $W^{6}$ between $\Sigma^{5}$
and $S^{5}$ and the hCT is applied to $W^{6}$. Interestingly, this proves
more, that $\Sigma^{5}$ is diffeomorphic, not just homeomorphic, to $S^{5}$.
This approach using surgery only succeeds in finding $W$ in some dimensions
but when it works the conclusion is stronger. In our case $n=4$, the surgery
approach actually does work and we find a smooth $h$-cobordism $W^{5}$ from
$\Sigma^{4}$ to $S^{4}$. The reason that our proof concludes only a
homeomorphism at the end of the day is that there is a terrific struggle
involving lots of limits and point set topology to find the Whitney disks and
they end up being merely topological category objects. The Whitney disks we
find spoil the smooth category context of the rest of the proof. It is an
astonishing historical coincidence that within 6 months of PC4, Simon
Donaldson had figured out enough about which four dimensional homotopy types
do not contain smooth manifolds to know for sure that the Whitney disks I
built cannot generally be smoothed. These Whitney disks are all that stand in
the way of realizing the quadratic form $E_{8}\oplus E_{8}$ as the
intersection form of a close smooth 4-manifold, which is excluded by
Donaldson’s “Theorem C” [donaldson86]. So the excursion into the topological
category is necessary if one speaks generally in terms of 4-manifold
constructions. Of course there may be some as yet unimagined workaround—or
entirely new method—satisfactory to the study of a smooth homotopy sphere
$\Sigma^{4}$. I think it safe to say that the greatest open problem in
topology (“The last man standing”) is the smooth category PC4: Is every
homotopy 4-sphere diffeomorphic to $S^{4}$?

Now to Casson. Casson’s first great insight was that there was some hope for
Whitney disks in 4D. He realized that the problem of finding an embedded
Whitney disk is qualitatively different from finding a slice disk for a
classical knot in $S^{3}$. That prototypical 2-disk embedding problem had been
studied starting in the 50s by Fox and Milnor [fox66]: Given a knot $K$ in
$S^{3}$ does it bound a smoothly embedded disk in the 4-ball $B^{4}$? This
problem is infinitely rich, and generally has a negative answer. But Casson
realized that Whitney disks in all applications would have homological duals,
so by standing farther back, and taking more of the manifold topology into
account, the embedding problem might turn out to be less obstructed than in
knot theory. This hope bore fruit. It is easy to show that these three spaces
are simply connected: The middle level $L$, and the complements $L\setminus
A$, and $L\setminus D$. To look for a Whitney disk $D$ in $L$ meeting $A\cup
D$ only where it is supposed to, long the boundary of $D$, we would also like
$L\setminus(A\cup D)$ to be simply connected. The duality Casson observed
implies that $\pi_{1}(L\setminus(A\cup D))$ is perfect. He realized that it
might help to make things worse before trying to make them better. If one
takes ones finger and pushes a generic patch of $A$ along an arc and through a
generic point on $D$ this “finger move” will create two new $+,-$ points of
intersection. Each such point will microscopically look like the intersection
of two complex lines in $\mathbb{C}^{2}$ and linking these complex lines is a
“Clifford torus.” The algebraic point is that the top cell of these Clifford
tori are relations saying the two loops linking the two sheets (complex lines
in the model) commute in $\pi_{1}$ of their joint complement. If you take a
perfect group and start forcing pairs of elements to commute pretty soon you
have a trivial group. In this way Casson got off the ground, by doing enough
finger moves between $A$ and $D$ to kill $\pi_{1}(L\setminus(A\cup D))$. This
enabled him to at least immerse the Whitney disk $W$ (with the required normal
framing data) he was looking for [casson86].

From here the finger moves simply explode in number. Fearlessly, Casson
decides to cure the problem of the Whitney disk double points by capping them
off with subsidiary Whitney disks in a hierarchy later called a Casson tower.
When taken to its infinite limit, the open, tapered, regular neighborhood is
called a “Casson handle.” I draw a dimensionally reduced schematic of a Casson
handle in Figure 1.

$\ddots$attaching
region$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$unbranchedbranchedWhitney disks
Figure 1. Casson handles.

Casson (1974) showed that his Casson handles $C$ had the correct proper
homotopy type to serve as neighborhoods of embedded Whitney disks,
$C\overset{P}{\simeq}(D^{2}\times\mathbb{R}^{2},\partial
D^{2}\times\mathbb{R}^{2})$. My contribution seven years later was to replace
proper homotopy equivalence—which was not strong enough for most geometric
applications—with homeomorphism. As I mentioned, I spent those seven years
staring at his handles about half time. I think this was the correct fraction.
I was young and needed to do some projects likely to work in order to get
tenure, raise a family, and preserve sanity. Those years I was either climbing
rocks, writing pleasant papers, or struggling with Casson handles. Not much
else. My mother had taught me that everything must be fun, “fun first,
pleasure second” as she put it. My father who was always at work on something
(and always enjoyed it) told me that there is “your work and, then, the
world’s work.” The idea of course was to do both. My papers were the “world’s
work.” I enjoyed them greatly and would surely have lost confidence in myself
if I was not publishing regularly. Casson handles were “my work.” The climbing
sheer pleasure. I had a reputation among my friends for “not thinking on
lead,” I just would tear ahead and see what happened. That is the way I liked
it: When I did math I tried to think (a bit); when I climbed I just let it
rip. Many of my friends asked me variations of, “Since Casson is obviously so
much smarter than you, why was it that he didn’t analyze his own handles.” The
answer, I think, is “opportunity costs”; he was so full of brilliant ideas:
secondary obstructions to knot cobordism (with Gordon), the Casson invariant,
what became “weak Heegaard reduction” (also with Gordon), that he was simply
too busy.

Let us turn to the third stream, Bob Edwards and the world of decomposition
space theory, the Bing shrinking criterion (BSC), and manifold factors. In
1980, Bob was the undisputed heavyweight champ in what might variously be
called Texas-topology, Bing-topology, the R.L.Moore-R.H.Bing school. It is an
area at the wild end of manifold topology, with roots and emphasis in low
dimensions. The Alexander horned sphere is what you should picture. It drew on
point set topology but was a very pictorial, concrete, and vivid undertaking.
It also had an enjoyably sportive feel that allows me to call Bob “Champ”
whereas it would never occur to me to call Hiranaka or Deligne the “Champ” of
algebraic geometry. During those seven years, I had discovered something, now
called re-imbedding. If you have a Casson tower of some critical minimum
height, then 7, later reduced to 5 (see [cha16, gs84]), you can leave the
lowest stage alone and build a new extension inside a neighborhood of the
original stage construction which has any, arbitrarily large, number of
stages. This quickly allows geometric control to be added to Casson handles.
The original construction just kind of flops around, the higher stages are in
no sense smaller than the lower ones. But with re-imbedding it is only a small
step to build Casson towers in which the higher stages converge beautifully to
a Cantor set. Now if one takes a tapered regular neighborhood and completes it
with this limiting Cantor set one obtains a compactified $\overline{C}$ in any
application where formerly a Casson handle $C$ was present. A handle has its
boundary divided into the attaching region and the co-attaching or “belt”
region. See Figure 2. In early fall of 1980 I used the Kirby calculus to draw
an exact picture of the belt region for the standard unbranching
$\overline{C}$. For the everyday closed 2-handle $(D^{2}\times
D^{2},S^{1}\times D^{2})$, the belt region is $D^{2}\times S^{1}$, a solid
torus. What I drew belt ($\overline{C}$) was what I later learned was a
decomposition space $D^{2}\times S^{1}/\operatorname{Wh}$, the solid torus
with a compactum called the Whitehead continuum crushed to a point (and
endowed with the quotient topology). A few weeks later I was sitting at a
pizza restaurant after a meeting of the recurring Southern California Topology
meeting with Bob Edwards. Apropos of nothing in particular, he was putting pen
to napkin to explain the “Andrews-Rubin” [andrews65] shrinking argument which
proves that the space $D^{2}\times S^{1}/\operatorname{Wh}$ is a manifold
factor. Even the concept to me was astonishing: $D^{2}\times
S^{1}/\operatorname{Wh}$ is most certainly not a manifold but it turns out
that its product with the real line $(D^{2}\times
S^{1}/\operatorname{Wh})\times\mathbb{R}$ is homeomorphic to $D^{2}\times
S^{1}\times\mathbb{R}$. Edwards understood this phenomenon well as he had just
completed his proof that the double suspension of the homology sphere bounding
the Mazur manifold was $S^{5}$. The single suspension is of course not a
manifold. My excitement was overwhelming. The frontier of my controlled Casson
handle $\overline{C}$, while not a manifold, was close—if it turned out to
have a product collar neighborhood that would, by Andrews-Rubin, be a manifold
and would harbor the Whitney disk I had been seeking for six years. In the
end, the proof proceeded somewhat differently but the fact that the belt
region of “frontier” of the controlled Casson handle was a manifold factor
convinced me that PC4 was likely true.

$\vdots$belt region $=D^{2}\times S^{1}/\operatorname{Wh}=$attaching
region$\operatorname{Wh}=\cap_{i=0}^{\infty}(D^{2}\times S^{1})_{i}$,each
nested the sameway as its predecessor.$(D^{2}\times S^{1})_{0}$$(D^{2}\times
S^{1})_{1}$$\operatorname{Wh}$ Figure 2. $(D^{2}\times
S^{1}/\operatorname{Wh})\times\mathbb{R}$ is homeomorphic to $D^{2}\times
S^{1}\times\mathbb{R}$.

To appreciate why $D^{2}\times S^{1}/\operatorname{Wh}$ is a manifold factor
we introduce the Bing Shrinking Criterion (BSC), as exposited by Edwards
[edwards80].

Let $X$ and $Y$ be compact metric spaces. A map $f:X\rightarrow Y$ is
approximable by homeomorphisms (ABH) if, for every $\epsilon>0$, $\exists$ a
homeomorphism: $g:X\rightarrow Y$ with
$\operatorname{dist}_{Y}(f(x),g(x))<\epsilon$ for all $x\in X$.

Bing Shrinking Criterion (BSC): $f:X\rightarrow Y$ is ABH iff for all
$\epsilon>0$ there is a homeomorphism $h:X\rightarrow X$ so that

  1. (1)

$\operatorname{dist}_{Y}(f\circ h(x),f(x))<\epsilon$ for all $x\in X$ and

  2. (2)

$\operatorname{diam}_{X}(h(f^{-1}(y)))<\epsilon$ for all $y\in Y$.

Andrew and Rubin found self-homeomorphisms $h_{\epsilon}$ of $(D^{2}\times
S^{1})\times\mathbb{R}$ so that $\pi\circ h_{\epsilon}$ is $\epsilon$-close to
$\pi$, and $\operatorname{diam}(h(\pi^{-1}(r)))<\epsilon$, where
$\pi:(D^{2}\times S^{1})\times\mathbb{R}\xrightarrow{\epsilon}(D^{2}\times
S^{1}/\operatorname{Wh})\times\mathbb{R}$ is the projection crushing each
$\operatorname{Wh}\times r$ to a point.

Their idea is to lift, at any deep stage $i$, the self clasp of the Whitehead
double $(D^{2}\times S^{1})_{i}\times r$ to an infinite chain of clasps and
then apply a global twist making each chain of the link small diameter. Figure
3 gives a hint of how this works.

$\mathbb{R}$lift$i$th stage$(i+1)$th stage,$(D^{2}\times S^{1})_{j}\times
h$twist$i$th stage solidtori appear smallafter lift/twistand contain
$\operatorname{Wh}\times r$ Figure 3.

The next step in the proof is what I called the design, but a better word
would be a “topographic map with some holes in it,” perhaps singed in a
campfire—but still useful. The map can be thought of as a certain closed
subset $D$ of the standard (open) 2-hanlde
$(D^{2}\times\mathbb{R}^{2},S^{1}\times\mathbb{R}^{2})$, but using the re-
imbedding lemma, and its concomitant geometric control is also a subset of the
(general Casson handle) $C$. Actually this topographic map varies in ways that
are not terribly important with different choices of $C$, but in all cases the
design $D$ includes into both $C$ and the standard (open) handle $H$. If this
map was fully extensive and covered both $C$ and $H$ it would by itself
describe the desired homeomorphism, but unfortunately it has a countable
number of bits missing, which we call “holes” in $H$, and “gaps” in $C$. The
gaps are bits of $C$ which remain terra incognita after the exploration that
lead to the design. To sketch the rest of the proof, I need to tell you how
the design is built, why it has these gaps, and finally what to do about them.

There will be a lot a branching going on in this paragraph, and I hope to keep
two quite different types straight as they are described. Let me call them
“bulk” and “radial” branching. In Figure 1 we already met bulk branching, this
comes from the fact that every Whitney disk that Casson installs to kill a
double point has itself many double points and requires that many Whitney
disks at the next level. Bulk branching, in the presence of geometric control,
limits to a Cantor set (which plays the role of the singular points in the
Andrews-Rubin argument). This branching is really only a distraction and does
not materially affect the proof. The reader would be served well by the
(false) fantasy that all Casson handles are unbranched (even when obtained via
the re-imbedding theorem) and just forget about bulk branching. The more
interesting branching is what I’m calling radial. Recall a 7-stage tower
contains a 14-stage tower (Casson handles are alive and can replicate!). We
can think of $14=7+7$ with a second 7-stage tower mounted on the top of the
first. But the same combinatorial technology that allows raising height also
allows us to build two alternative choices, $T_{7}$ and $T^{\prime}_{7}$ for
the second tower with $T_{7}^{\prime}$ contained in $T_{7}$. This binary
choice now occurs countably often as we may now identify 14 stage towers
within both $T_{7}^{\prime}$ and $T_{7}$, and again create a binary choice
(move in or stay out) in attaining the final 7 stages in these 14-ers.
Continuing in this way we realize each of two choices “in or out” every 7th
stage, always while maintaining geometric control so that the limits are as we
expect. We call this branching “radial” because when $D$ is embedded in $H$,
indeed at every such branch, the primed choice has a smaller $\rho$ coordinate
in the polar coordinates of the transverse $\mathbb{R}^{2}$. The design
carries a singular foliation. At radial coordinates which are not in the
standard Cantor set the leaf is a compact 3-maniold with boundary, at a Cantor
set radius the leaf is an Andrew-Rubin-like decomposition space. Corresponding
to the “middle thirds” are the holes or gaps where this procedure has not
succeeded in corresponding points of $H$ to points of $C$.

There is now a technical point, all but one of the holes is homeomorphic to
$S^{1}\times\mathbb{R}^{3}$ (the outlier is homeomorphic to $\mathbb{R}^{4}$).
At this point we don’t know what the topology of the gaps is-–-but long after
this proof is finished we do learn enough to know that they all along had the
topology of their corresponding holes. Our plan for the $\\{$holes$\\}$ and
the corresponding $\\{$gaps$\\}$ is eventually to crush them to points and
analyze the results. It is much better in applying the Bing/Edwards
mathematics that we crush only closed “cell-like” [edwards80] sets. Cell-like
means that when embedded in a Euclidean space (or Hilbert space) for any
neighborhood $U$ there is a smaller neighborhood $V$ that contracts within
$U$. Our holes/gaps are neither closed nor cell-like. The first deficiency is
easily corrected by taking the closures, the second by locating certain
2-disks to add to the holes or gaps. We use the notations hole+ and gap+ for
holes or gaps that have been closed and augmented with an additional 2-disk to
become cell-like. In a sense adding the + is taking a step back because we are
giving up some of the “explored region” of $C$ covered by the design, but
sometimes to take two steps forward one must take a step backwards. This is an
example.

Now comes the key diagram which will divide what remains of the proof into two
separate theorems: 1) the Edwards shrink and 2) the “Sphere to Sphere”
theorem.

$Q$$C$$H$$\alpha$ABH$\beta$ABH Figure 4. $\alpha$ crushes $\\{$holes+$\\}$ and
$\beta$ crushes $\\{$gaps+$\\}$.

Tautologically $H$ and $C$ have a common quotient $Q$, obtained by crushing
the holes+, respectively gaps+, to points. This is the benefit of having found
the design $D$ on both sides. It turns out both quotient maps can be shown to
be approximable by homeomorphisms (ABH). This, of course, would finish the
proof that Casson handles $C$ are homeomorphic to the standard open handle
$H$, by composing one approximating homeomorphism by the inverse of the other.
And with this result in hand the Poincaré Conjecture PC4, and much more within
4D topology follows.

Edwards analysis of the first map $\alpha$ is a tour de force of Bing
topology. Many of the best ideas in that field enter: It encompasses and
generalizes the Andrews-Rubin shrinking technology and also contains a
compound use of the principle that “Countable, null, star-like equivalent”
decompositions are shrinkable [bean67]. It is a beautiful and pure application
of the Bing shrinking criterion.

The arrow $\beta$, might be called the “blindfold shrink.” Ric Ancel
[ancel84], Jim Cannon, Frank Quinn, and Mike Starbird helped me revise this
argument and express it as an extension of Brown’s proof of the Schoenflies
theorem, a proof that I learned from them. The notation is a bit daunting but
the idea is simple. After the Edwards shrink we know that both domain and
range of $\beta$ are manifolds and ones that embed in $\mathbb{R}^{4}$, in
fact one readily reduces to the case that both domain and range are standard
4-spheres. Then the idea is to look at the 8D graph of the function $\beta$
and try to improve it to a homeomorphism by systematically modifying it to
remove its largest “flat spots.” The data (from the Edwards shrink) that the
quotient space has nice local and global topology and allows you to insert a
local “drawing” of the decomposition space structure into the target within a
small neighborhood of the image of these largest decomposition elements. A
natural procedure, see Figure 5, uses this inserted drawing to resolve these
most singular points and make the function one-to-one over them. There is a
blending problem: the resolution creates countably many small vertical spots,
that is the resolution is only a relation not a function. But one should not
worry, we are on the right track. One goes back and forth: sanding down first
the largest horizontal spots, then flipping the workpiece over and sanding
down the largest of these newly created vertical spots, flipping it back to
sand down somewhat smaller horizontal spots, etc. One moves back and forth
sanding and polishing until the limiting relation has neither horizontal nor
vertical thickness, i.e. becomes a homeomorphism.

$X$$X$$R^{4}\supseteq Q\cong H$flat spot$(s)$graph of $\beta$$C=$ Casson
handle Figure 5. The neighborhood of the largest gap+, $X$, is drawn on the
$y$-axis near $\beta(X)$ to facilitate a resolution of $\beta$ to a
homeomorphism on $X$. This is good, but small vertical spots inevitably result
from pulling points where $\beta$ is already a homeomorphism over other
smaller elements of $\\{$gaps+$\\}$. This deficit is corrected later.

I thank Arumina Ray and Mark Powell for including this lecture in their book;
it is hoped that these brief recollections may add context or at least
amusement. There is much left to be understood in four dimensions—the best of
luck!

## References


11institutetext: LaBRI, Université de Bordeaux, France 22institutetext: IRIF,
Université de Paris, France

# On the ESL algorithm for solving energy games

Antonio Casares 11 Pierre Ohlmann 22

###### Abstract

We propose a variant of an algorithm introduced by Schewe and also studied by
Luttenberger for solving parity or mean-payoff games. We present it over
energy games and call our variant the ESL algorithm (for Energy-Schewe-
Luttenberger). We find that using potential reductions as introduced by
Gurvich, Karzanov and Khachiyan allows for a simple and elegant presentation
of the algorithm, which repeatedly applies a natural generalisation of
Dijkstra’s algorithm to the two-player setting due to Khachiyan, Gurvich and
Zhao.

###### Keywords:

Mean-payoff games energy games pseudopolynomial algorithm

##  1 Introduction

Mean-payoff and energy games. In the games under study, two players, Min and
Max, take turns in moving a token over a sinkless finite directed graph whose
edges are labelled by (potentially negative) integers, interpreted as payoffs.
In a mean-payoff game, the players aim to optimise (minimising or maximising,
respectively) the average payoff in the long run. When playing an energy game,
Min and Max optimise the supremum of the cumulative sum of values which takes
values in $[0,+\infty]$.

These two games are determined [17]: for each initial vertex $v$, there is a
value $x$ such that starting from $v$, the minimiser can ensure an outcome
$\leq x$ whereas the maximiser can ensure at least $x$. They are moreover
positionaly determined [8, 3] which means that the players can achieve the
optimal value even when restricted to strategies that do only depend on the
current position of the game. We refer to Figure 1 for a complete example.

Figure 1: Example of a game; circles and squares represent vertices which
respectively belong to Min and Max. Mean-payoff values from left to right are
$-2,-2,-\frac{1}{2},-\frac{1}{2},1$ and $1$, and mean-payoff-optimal
positional strategies for both players are identified in bold. Energy values
are $0,2,9,0,\infty$ and $\infty$, and energy-optimal strategies are given by
arrows with double heads.

In this paper, we are interested in the problem of computing energy values of
the vertices in a given game which we call solving the energy game. As a
consequence of positional determinacy, the energy value of a vertex is finite
if and only if its mean-payoff value is non-positive [4], and therefore
solving an energy game also solves the so called threshold problem for mean-
payoff games. In fact, all state of the art algorithms [4, 7, 2] for the
threshold problem – further discussed below – actually go through solving the
energy game. The best algorithms for the more general problems of computing
the exact values or synthesising optimal strategies in the mean-payoff game
also rely on solving many auxiliary energy games [6].

Positional strategies achieving positive or non-positive mean-payoff values
can be checked in polynomial time, and therefore the threshold problem belongs
to $\mathrm{NP}\cap\mathrm{coNP}$. Despite numerous efforts, no polynomial
algorithm is known. Mean-payoff games are known [22] to be more general than
parity games [9, 20] which enjoy a similar complexity status but were recently
shown to be solvable in quasipolynomial time [5]. It is however unlikely that
algorithms for solving parity games in polynomial time generalise to mean-
payoff games [10].

Schewe’s algorithm. Schewe presented in [23] a strategy improvement algorithm
for solving parity games. Schewe points out that his framework can be adapted
to the more general case of mean-payoff games; one can actually see it as a
switching policy in the combinatorial strategy improvement framework proposed
by Björklund and Vorobiov [2]. Luttenberger [15] later formulated the same
algorithm as one iterating over non-deterministic strategies: over such
strategies, it can be rephrased as iterative applications of the natural “all-
switch” policy.

At that time, the connection between mean-payoff and energy games –
established only later in [3] and then simplified in [4] – was not well
understood. In particular, the algorithms above, following [2], introduce an
additional sink vertex, called retreat vertex, and restrict the iteration to
so called admissible strategies, which can be understood as those guaranteeing
a finite energy. Actually, Björklund and Vorobiov ask in their conclusion
whether one can avoid the need for a retreat vertex and admissible strategies;
a positive answer to this question is provided by the energy valuation
(details are provided in the second author’s PhD thesis [21]).

Our contribution. We propose a variant of Schewe’s algorithm; while the main
ideas are the same, the presentation as well as the precise execution of the
algorithm differ. In particular, we do not require introducing a retreat
vertex, or restrict to a subclass of strategies. We also do not require the
vocabulary from strategy improvements. Overall, we believe that our version is
conceptually simpler and allows to appreciate the core algorithmic idea in a
new light.

The algorithm is presented as one iterating succession of potential
reductions, as introduced by Gurvich, Karzanov and Khachiyan [13], until
obtaining a trivial game. Each iteration solves a game over only non-negative
weights, which is done in $O(m+n\log n)$ operations using a simple extension
of Dijkstra’s algorithm to the two-player setting at hands, due to Khachiyan,
Gurvich and Zhao [14].

Related work. It is worth noting that Schewe’s algorithm is a key component in
the LTL-synthesis tool STRIX [19, 16], which has won all editions of the main
annual synthesis competition SYNTCOMP. The algorithm was also ported to the
GPU by Meyer and Luttenberger [18]. We also believe that there are
similarities to be understood between the algorithm under study and the quasi-
dominion approach of Benerecetti, Dell’Erba and Mogavero [1].

Outline. The first section introduces all necessary concepts and recalls the
relationship between mean-payoff and energy games. The second section presents
the ESL algorithm, and the third one proves its correctness and termination.
We then conclude and discuss future work.

##  2 Preliminaries

In this preliminary section, we introduce mean-payoff and energy games, and
potential reductions.

Mean-payoff and energy games. In this paper, a game is a tuple
$\mathcal{G}=(G,w,V_{\mathrm{Min}},V_{\mathrm{Max}})$, where $G=(V,E)$ is a
finite directed graph with no sink, $w:E\to\mathbb{Z}$ is a labelling of its
edges by integer weights, and $V_{\mathrm{Min}},V_{\mathrm{Max}}$ is a
partition of $V$. We always use $n,m$ and $W$ respectively for $|V|,|E|$ and
$\max\limits_{e\in E}|w(e)|$; we say that vertices in $V_{\mathrm{Min}}$
belong to Min while those in $V_{\mathrm{Max}}$ belong to Max. We now fix a
game $\mathcal{G}=(G,w,V_{\mathrm{Min}},V_{\mathrm{Max}})$.

A path is a (possibly empty, possibly infinite) sequence of edges
$\pi=e_{0}e_{1}\dots$ with matching endpoints: if $e_{i+1}=v_{i+1}v_{i+2}$ is
defined then its first component $v_{i+1}$ matches the second component of
$e_{i}$. For convenience, we often write $v_{0}\rightarrow v_{1}\rightarrow
v_{2}\rightarrow\dots$ for the path
$e_{0}e_{1}\dots=(v_{0}v_{1})(v_{1}v_{2})\dots$. Given a finite or infinite
path $\pi=e_{0}e_{1}\dots$ we let $w(\pi)=w(e_{0})w(e_{1})\dots$ denote the
sequence of weights appearing on $\pi$. The sum of a finite path $\pi$ is the
sum of the weights appearing on it, we denote it by $\mathrm{sum}(\pi)$.

Given a finite or infinite path $\pi=e_{0}e_{1}\dots=v_{0}\rightarrow
v_{1}\rightarrow\dots$ and an integer $k\geq 0$, we let
$\pi_{<k}=e_{0}e_{1}\dots e_{k-1}=v_{0}\rightarrow
v_{1}\rightarrow\dots\rightarrow v_{k}$, and we let $\pi_{\leq k}=\pi_{<k+1}$.
Note that $\pi_{<0}$ is the empty path, and that $\pi_{<k}$ has length $k$ in
general: it belongs to $E^{k}$. We say that $\pi$ starts in $v_{0}$, and when
it is finite and of length $k$ that it ends in $v_{k}$. By convention, the
empty path starts and ends in all vertices. A cycle is a finite path which
starts and ends in the same vertex. A finite path $v_{0}\rightarrow
v_{1}\rightarrow\dots\rightarrow v_{k}$ is simple if there is no repetition in
$v_{0},v_{1},\dots,v_{k-1}$; note that a cycle may be simple. We let
$\Pi_{v}^{\omega}$ denote the set of infinite paths starting in $v$.

We use $\mathbb{R}^{\infty},\mathbb{Z}^{\infty}$ and $\mathbb{N}^{\infty}$ to
denote respectively $\mathbb{R}\cup\\{\infty\\},\mathbb{Z}\cup\\{\infty\\}$
and $\mathbb{N}\cup\\{\infty\\}$. A valuation is a map
$\mathrm{val}:\mathbb{Z}^{\omega}\to\mathbb{R}^{\infty}$ which assigns a
potentially infinite real number to infinite sequences of weights.

The three valuations which are studied in this paper are the mean-payoff,
energy, and positive-energy valuations, given by

$\begin{array}[]{lclcl}\mathrm{MP}(w_{0}w_{1}\dots)&=&\limsup_{k}\frac{1}{k}\sum_{i=0}^{k-1}w_{i}&\in&\mathbb{R},\\\
\mathrm{En}(w_{0}w_{1}\dots)&=&\sup_{k}\sum_{i=0}^{k-1}w_{i}&\in&\mathbb{N}^{\infty},\\\
\mathrm{En^{+}}(w_{0}w_{1}\dots)&=&\sum_{i=0}^{k_{\text{neg}}-1}w_{i}&\in&\mathbb{N}^{\infty},\end{array}$

where $k_{\text{neg}}=\min\\{k\mid w_{k}<0\\}\in\mathbb{N}^{\infty}$ is the
first index of a negative weight. For technical convenience, and only in the
context of energy games, we will also consider games in which weights are
potentially (positively) infinite. We thus extend the definitions of
$\mathrm{En}$ and $\mathrm{En^{+}}$ to words in
$(\mathbb{Z}^{\infty})^{\omega}$, using the same formula. Note that for any
$w\in(\mathbb{Z}^{\infty})^{\omega}$ we have $\mathrm{En^{+}}\leq\mathrm{En}$.
The three valuations are illustrated on a given weight profile in Figure 2.

Figure 2: The three valuations over a given weight-profile. The mean-payoff
value is given by the slope of the line, which corresponds to the long-term
average. In this case, the mean-payoff is $\leq 0$, and both $\mathrm{En}$ and
$\mathrm{En^{+}}$ are finite.

A strategy for Min is a map $\sigma:V_{\mathrm{Min}}\to E$ such that for all
$v\in V_{\mathrm{Min}}$, it holds that $\sigma(v)$ is an edge outgoing from
$v$. We say that a (finite or infinite) path
$\pi=e_{0}e_{1}\dots=v_{0}\rightarrow v_{1}\rightarrow\dots$ is consistent
with $\sigma$ if whenever $e_{i}=v_{i}v_{i+1}$ is defined and such that
$v_{i}\in V_{\mathrm{Min}}$, it holds that $e_{i}=\sigma(v_{i})$. We write in
this case $\pi\models\sigma$. Strategies for Max are defined similarly and
written $\tau:V_{\mathrm{Max}}\to E$. Paths consistent with Max strategies are
defined analogously and also denoted by $\pi\models\tau$. In common
vocabulary, the theorem below states that the three valuations are determined
with positional strategies over finite games. It is well known for
$\mathrm{MP}$ and $\mathrm{En}$ and easy to prove for $\mathrm{En^{+}}$ (Lemma
3 provides an algorithmic proof of this fact). We remark that positional
determinacy also holds for the two energy valuations $\mathrm{En}$ and
$\mathrm{En^{+}}$ over games where we allow for infinite weights.

######  Theorem 2.1 ([8, 3])

For each $\mathrm{val}\in\\{\mathrm{MP},\mathrm{En},\mathrm{En^{+}}\\}$, there
exist strategies $\sigma_{0}$ for Min and $\tau_{0}$ for Max such that for all
$v\in V$ we have

$\sup_{\pi\models\sigma_{0}}\mathrm{val}(w(\pi))=\inf_{\sigma}\sup_{\pi\models\sigma}\mathrm{val}(w(\pi))=\sup_{\tau}\inf_{\pi\models\tau}\mathrm{val}(w(\pi))=\inf_{\pi\models\tau_{0}}\mathrm{val}(w(\pi)),$

where $\sigma,\tau$ and $\pi$ respectively range over strategies for Min,
strategies for Max, and infinite paths from $v$.

The quantity defined by the equilibrium above is called the value of $v$ in
the $\mathrm{val}$ game, and we denote it by
$\mathrm{val}_{\mathcal{G}}(v)\in\mathbb{R}^{\infty}$; the strategies
$\sigma_{0}$ and $\tau_{0}$ are called $\mathrm{val}$-optimal, note that they
do not depend on $v$. The following result relates the values in the mean-
payoff and energy games; this direct consequence of Theorem 2.1 was first
stated in [4].

######  Corollary 1 ([4])

For all $v\in V$ it holds that

$\mathrm{MP}_{\mathcal{G}}(v)\leq
0\iff\mathrm{En}_{\mathcal{G}}(v)<\infty\iff\mathrm{En}_{\mathcal{G}}(v)\leq(n-1)N.$

Therefore computing $\mathrm{En}$ values of the games is harder than the
threshold problem. As explained in the introduction, all state-of-the-art
algorithms for the threshold problem actually compute $\mathrm{En}$ values.
This shifts our focus from mean-payoff to energy games.

Potential reductions. We fix a game
$\mathcal{G}=(G=(V,E),w,V_{\mathrm{Min}},V_{\mathrm{Max}})$. A potential is a
map $\phi:V\to\mathbb{N}^{\infty}$. Potentials are partially ordered
coordinatewise. Given an edge $vv^{\prime}\in E$, we define its
$\phi$-modified weight to be

$w_{\phi}(vv^{\prime})=\begin{cases}\infty&\text{ if
}\phi(v),\phi^{\prime}(v)\text{ or }w(vv^{\prime})\text{ is }\infty\\\
w(vv^{\prime})+\phi(v^{\prime})-\phi(v)&\text{ otherwise}.\end{cases}$

The $\phi$-modified game $\mathcal{G}_{\phi}$ is simply the game
$(G,w_{\phi},V_{\mathrm{Min}},V_{\mathrm{Max}})$; informally, all weights are
replaced by the modified weights. Note that the underlying graph does not
change, in particular paths in $\mathcal{G}$ and $\mathcal{G}_{\phi}$ are the
same. Note that any edge outgoing a vertex $v$ with potential $\phi(v)=\infty$
has weight $\infty$ in the modified game, therefore $v$ has $\mathrm{En}$ and
$\mathrm{En^{+}}$-values $\infty$ in $G_{\phi}$.

Observe that for a finite path $\pi=v_{0}\rightarrow
v_{1}\rightarrow\dots\rightarrow v_{k}$ which visits only vertices with finite
potential, its sum in $\mathcal{G}_{\phi}$ is given by

$\mathrm{sum}_{\phi}(v)=\mathrm{sum}(\pi)-\phi(v_{0})+\phi(v_{k}).$

We let $0$ denote the constant zero potential; note that
$\mathcal{G}_{0}=\mathcal{G}$. For convenience, we use $\mathrm{En}_{\phi}$ to
denote $\mathrm{En}_{\mathcal{G}_{\phi}}$ (we remark that
$\mathrm{En}_{0}=\mathrm{En}_{\mathcal{G}}$). We will omit the subscript
whenever the game or potential under consideration is clear from the context.

Moving from $\mathcal{G}$ to $\mathcal{G}_{\phi}$ for a given potential $\phi$
is called a potential reduction; these were introduced by Gallai [12] for
studying network related problems such as shortest-paths problems. In the
context of mean-payoff or energy games, they were introduced in [13] and later
rediscovered numerous times. The result below describes the effect of
potential reductions over energy values.

###### Theorem 2.2

If $\phi$ satisfies $\phi\leq\mathrm{En}_{0}$, then it holds that
$\mathrm{En}_{0}=\phi+\mathrm{En}_{\phi}$ over $V$.

A full proof is given in Appendix 0.A for completeness, and an illustration is
given in Figure 3. We say that a potential $\phi$ is sound if it satisfies the
hypothesis of Theorem 2.2: $\phi\leq\mathrm{En}_{0}$.

Figure 3: An illustration of the second item in Theorem 2.2. For the three
vertices on the right, energy values in both games are $\infty$.

Observe that
$(\mathcal{G}_{\phi})_{\phi^{\prime}}=\mathcal{G}_{\phi+\phi^{\prime}}$:
sequential applications of potential reductions correspond to reducing with
respect to the sum of the potentials. The following is easily derived as a
consequence of Theorem 2.2.

###### Lemma 1

If $\phi$ is sound for $\mathcal{G}$, and $\phi^{\prime}$ is sound for
$\mathcal{G}_{\phi}$, then $\phi+\phi^{\prime}$ is sound for $\mathcal{G}$.

Simple games. A game is simple if all simple cycles have nonzero sum. The
following result is folklore and states that one may reduce to a simple game
at the cost of a linear blow up on $W$. It holds thanks to the fact that
positive mean-payoff values are $\geq 1/n$, which is a well-known consequence
of Theorem 2.1.

###### Lemma 2

Let $\mathcal{G}=(G,V,V_{\mathrm{Min}},V_{\mathrm{Max}})$ be an arbitrary
game. The game
$\mathcal{G}^{\prime}=(G,V,(n+1)w-1,V_{\mathrm{Min}},V_{\mathrm{Max}})$ is
simple and has the same vertices of positive mean-payoff values as
$\mathcal{G}$.

Note moreover that simplicity is preserved by potential transformations, since
sums of weights over cycles are left unchanged.

##  3 The ESL algorithm

###  3.1 Presentation of the algorithm

The ESL algorithm is based on successively applying sound potential reductions
$\phi_{0},\dots,\phi_{j}$ until a game $\mathcal{G}^{\prime}$ is reached where
energy-values are either 0 or $\infty$. Thanks to Theorem 2.2 and Lemma 1, we
then have
$\mathrm{En}_{\mathcal{G}}=\mathrm{En}_{\mathcal{G}^{\prime}}+\phi_{0}+\dots+\phi_{j}$;
in particular, a vertex has finite energy (or non-positive mean-payoff) in
$\mathcal{G}$ if and only if it has energy 0 in $\mathcal{G}^{\prime}$, and in
this case its energy in $\mathcal{G}$ is given by
$\phi_{0}(v)+\dots+\phi_{j}(v)$.

The potential reductions computed by each iteration of the ESL algorithm are
precisely the $\mathrm{En^{+}}$-values in the game. Intuitively, the players
optimise the (non-negative) sum of the weights seen before the first negative
weight. Since $\mathrm{En^{+}}\leq\mathrm{En}$ in general, the potential
$\mathrm{En^{+}}:V\to\mathbb{Z}^{\infty}$ is indeed sound, as required by our
approach. The fact that it can be computed efficiently follows from the fact
that only non-negative weights are considered, and therefore a straightforward
two-player extension of Dijkstra’s algorithm, due to111This corresponds to
Theorem 1 in [14], case $(i)$ with blocking systems $\mathcal{B}_{2}$.
Khachiyan, Gurvich and Zhao [14] can be applied. A similar subroutine was also
given by Schewe [23], whereas Luttenberger [15] uses an adaptation of the
algorithm of Bellman-Ford which is less efficient.

######  Lemma 3 (Based on [14])

Over simple games, the $\mathrm{En^{+}}$-values can be computed in $O(m+n\log
n)$ operations.

###### Proof

We start by determining in linear time $O(m)$ the set $N$ of vertices from
which Min can force to immediately visit an edge of negative weight; these
have $\mathrm{En^{+}}$-value 0. We will successively update a set $F$
containing the set of vertices over which $\mathrm{En^{+}}$ is currently
known. We initialise this set $F$ to $N$. Note that all remaining Min vertices
have only non-negative outgoing edges, and all remaining Max vertices have (at
least) a non-negative outgoing edge.

We then iterate the two following steps illustrated in Figure 4. (A complexity
analysis is given below.)

  1. 1.

If there is a Max vertex $v\notin F$ all of whose non-negative outgoing edges
$vv^{\prime}$ lead to $F$, set $\mathrm{En^{+}}(v)$ to be the maximal
$w(vv^{\prime})+\mathrm{En^{+}}(v^{\prime})$, add $v$ to $F$, and go back to
1.

  2. 2.

Otherwise, let $vv^{\prime}$ be an edge from $V_{\mathrm{Min}}\setminus F$ to
$F$ (it is necessarily positive) minimising
$w(vv^{\prime})+\mathrm{En^{+}}(v^{\prime})$; set
$\mathrm{En^{+}}(v)=w(vv^{\prime})+\mathrm{En^{+}}(v^{\prime})$, add $v$ to
$F$ and go back to 1. If there is no such edge, terminate.

Figure 4: The game version of Dijkstra’s algorithm; blue edges are negative
and red ones are non-negative. If there is a vertex such as $v$ (it belongs to
$\mathrm{Max}$ and all edges pointing out of $F$ are $<0$), one may set the
value of $v$. Otherwise, set the value of a Min vertex $v$ minimising
$w(vv^{\prime})+\mathrm{En^{+}}(v^{\prime})$ over edges going to $F$; if there
is no such edge, terminate (Max can force seeing $\geq 0$ edges forever).

After the iteration has terminated, there remains to deal with
${F}^{\mathsf{c}}$, which is the set of vertices from which Max can ensure to
visit only non-negative edges forever. Since the arena is assumed to be simple
(no simple cycle has weight zero) it holds that $\mathrm{En^{+}}$ is $\infty$
over $F$, and we are done222If the arena is not simple, one must additionally
solve a Büchi game, and the complexity of the iteration is increased. We
believe that this increased cost can be amortised overall, but give no details
for this claim..

As is standard, by storing the number of edges outgoing from Max vertices in
${F}^{\mathsf{c}}$ to $F$, step 1 induces only a total linear runtime $O(m)$.
For step 2, one should store, for each $v\in V_{\mathrm{Max}}\setminus F$, the
edge towards $F$ minimising $w(vv^{\prime})+\mathrm{En^{+}}(v^{\prime})$ in a
priority queue. Using a Fibonacci heap as was first suggested by Fredman and
Tarjan [11] for Dijkstra’s algorithm lowers the complexity from $O(m\log n)$
to $O(m+n\log n)$. ∎

###  3.2 Termination and correctness

Termination. To prove that the ESL algorithm terminates in finitely many
steps, we rely on a simple lemma which states that the set of vertices from
which Min can ensure to immediately see a negative weight (and thus stop the
game) can only shrink throughout the iteration.

###### Lemma 4

Let $\mathcal{G}^{\prime}=\mathcal{G}_{\mathrm{En}_{\mathcal{G}}^{+}}$, let
$N$ and $N^{\prime}$ be the sets of vertices from which Min can ensure to
immediately visit a negative weight, respectively in $\mathcal{G}$ and
$\mathcal{G}^{\prime}$. We have $N^{\prime}\subseteq N$.

###### Proof

We show that ${N}^{\mathsf{c}}\subseteq{N^{\prime}}^{\mathsf{c}}$; let
$v\in{N}^{\mathsf{c}}$. If $\mathrm{En^{+}}_{\mathcal{G}}(v)=\infty$ then $v$
has only outgoing edges of infinite weight in $\mathcal{G}^{\prime}$ thus is
cannot belong to $N^{\prime}$; we assume otherwise.

  * •

Assume $v\in V_{\mathrm{Max}}$. Let $\tau$ be an
$\mathrm{En^{+}}_{\mathcal{G}}$-optimal strategy in $\mathcal{G}$, and let
$\tau(v)=vv^{\prime}\in E$. Since $v\notin N$ we have $w(vv^{\prime})\geq 0$
and
$\mathrm{En^{+}}_{\mathcal{G}}(v)=w(vv^{\prime})+\mathrm{En^{+}}_{\mathcal{G}}(v^{\prime})$.
Hence we have
$w_{\mathrm{En^{+}}_{\mathcal{G}}}(vv^{\prime})=w(vv^{\prime})+\mathrm{En^{+}}_{\mathcal{G}}(v^{\prime})-\mathrm{En^{+}}_{\mathcal{G}}(v)=0\geq
0$ so $v\notin N^{\prime}$.

  * •

Assume now that $v\in V_{\mathrm{Min}}$. We have for all $vv^{\prime}\in E$
that $w(vv^{\prime})\geq 0$ hence $\mathrm{En^{+}}_{\mathcal{G}}(v)\leq
w(vv^{\prime})+\mathrm{En^{+}}_{\mathcal{G}}(v^{\prime})$, and thus
$w_{\mathrm{En^{+}}_{\mathcal{G}}}(vv^{\prime})\geq 0$, so $v\notin
N^{\prime}$. ∎

We now let $\mathcal{G}_{0}=\mathcal{G}$ denote the initial game, and for each
$j\geq 0$ we let $\phi_{j}=\mathrm{En}_{\mathcal{G}_{j}}^{+}$ and
$\mathcal{G}_{j+1}=(\mathcal{G}_{j})_{\phi_{j}}$ be the game obtained after
$j$ iterations of the ESL algorithm. We also let
$\Phi_{j}=\phi_{0}+\dots+\phi_{j-1}$; it holds that
$\mathcal{G}_{j}=(\mathcal{G}_{0})_{\Phi_{j}}$.

This lemma directly gives (with obvious notations) $N_{0}\supseteq
N_{1}\supseteq\dots$ and therefore vertices $v^{\prime}$ in $N_{j}$ satisfy
$\Phi_{j}(v^{\prime})=0$. Now if $v$ is a vertex such that
$\phi_{j}(v)=\mathrm{En}_{\mathcal{G}_{j}}^{+}(v)$ is finite, then by
definition there is a simple path $\pi=v_{0}\rightarrow\dots\rightarrow v_{k}$
in $\mathcal{G}$ from $v$ to some $v^{\prime}\in N_{j}$ whose
$\Phi_{j}$-modified sum is $\mathrm{sum}_{\Phi_{j}}(\pi)=\phi_{j}(v)$. This
rewrites as

$\phi_{j}(v)=-\Phi_{j}(v)+\underbrace{\Phi_{j}(v^{\prime})}_{0}+\underbrace{\sum_{i=0}^{k-1}w_{\Phi_{j}}(v_{i}v_{i+1})}_{\leq
nW},$

and thus $\Phi_{j}(v)\leq nW$. Stated differently, finite values remain $\leq
nW$, which guarantees termination in at most $O(n^{2}N)$ iterations.

Using an implementation similar to the BCDGR algorithm [4], where the set of
vertices with positive $\mathrm{En^{+}}$ (as well as relevant internal data
structures) is stored from an iteration to the next, one may lower the global
complexity upper bound to $O((m+n\log n)nW)$, at least for simple arenas. Such
an implementation was already suggested by Schewe [23], but no complexity
bound is given for mean-payoff games333Schewe’s presentation is done over
parity games; no complexity bound is given for mean-payoff games, which are
only mentioned in a footnote. This is quite unfortunate, since his algorithm
would have improved over the state of the art at that time (and also suggests
the fruitful link with energy games, which was exploited by [4] only a few
years later)..

We give a full example over a game of size 15 in Figure 5.

Figure 5: A complete execution of the ESL algorithm. In each iteration, we
indicate the $\mathrm{En^{+}}$-values of each vertex. Optimal strategies are
indicated with bold arrows. Vertices from which Min can force to immediately
see a negative weight are coloured in blue, and those with a strictly positive
$\mathrm{En^{+}}$-value in red.

Correctness. The iteration terminates after $j$ steps if
$\Phi_{j+1}=\Phi_{j}$. We now state and prove correctness of the ESL
algorithm.

###### Lemma 5

If $\Phi_{j+1}=\Phi_{j}$ then $\mathrm{En}_{\mathcal{G}_{j}}$ takes values in
$\\{0,\infty\\}$ over $V$.

###### Proof

Note that vertices such that $\Phi_{j}(v)=\infty$ have only outgoing edges of
weight $\infty$ in $\mathcal{G}_{j}$ and therefore they have
$\mathrm{En^{+}}$-value $\infty$. Hence, the hypothesis rewrites as
$\Phi_{j}(v)<\infty\implies\mathrm{En^{+}}_{\mathcal{G}_{j}}(v)=0$; we let $F$
be the set of vertices $v$ with $\Phi_{j}(v)<\infty$. This implies that all
Min vertices in $F$ have a non-positive outgoing edge in $\mathcal{G}_{j}$
towards $F$, and all Max vertices in $F$ have all their outgoing edges non-
positive and towards $F$, hence the result. ∎

##  4 Conclusion

We have presented the ESL algorithm using potential reductions. This allows to
reduce to several iterations over non-negative weights, each of which can be
treated efficiently using Dijkstra’s algorithm. In particular, presenting the
algorithm does not require introducing a retreat vertex, or using vocabulary
from strategy improvements. We believe that this new presentation sheds a lot
of clarity on this important algorithmic idea.

We end the paper with a possible extension of these ideas. One may also
compute, in the very same fashion, the $\mathrm{En^{-}}$-values of the game,
where $\mathrm{En^{-}}:\mathbb{Z}^{\omega}\to[-\infty,0]$ is given by
$\mathrm{En^{-}}(w_{0}w_{1}\dots)=\sum_{i=0}^{k_{\text{pos}}-1}w_{i}$, with
$k_{\text{pos}}=\min\\{k\mid w_{k}>0\\}$. Iterating $\mathrm{En^{-}}$
potential transformations gives rise to a dual algorithm, which of course
terminates with similar complexity.

We have observed empirically that alternately iterating444This requires
working with potentials with values in $\mathbb{Z}\cup\\{-\infty,\infty\\}$,
which is a formality. $\mathrm{En^{+}}$ and $\mathrm{En^{-}}$ potential
transformation leads to a terminating algorithm over any instance. Moreover,
it achieves even fewer iterations that the (asymmetric) ESL algorithm, and
especially so over parity games, for which we have witnessed a significant
gain over large random instances.

However, we have not been able to derive its termination using the currently
available tools. Could one prove termination of the (symmetric) alternating
algorithm? Could we hope for a subexponential combinatorial upper bound?

Acknowledgments. We are grateful to Alexander Kozachinskyi for pointing out to
us several important references. We also thank Thomas Colcombet, Nathanaël
Fijalkow and Olivier Serre for fruitful discussions.

## References

  * [1] Benerecetti, M., Dell’Erba, D., Mogavero, F.: Solving mean-payoff games via quasi dominions. In: TACAS. Lecture Notes in Computer Science, vol. 12079, pp. 289–306. Springer (2020)
  * [2] Björklund, H., Vorobyov, S.G.: Combinatorial structure and randomized subexponential algorithms for infinite games. Theor. Comput. Sci. 349(3), 347–360 (2005)
  * [3] Bouyer, P., Fahrenberg, U., Larsen, K.G., Markey, N., Srba, J.: Infinite runs in weighted timed automata with energy constraints. In: FORMATS. Lecture Notes in Computer Science, vol. 5215, pp. 33–47. Springer (2008)
  * [4] Brim, L., Chaloupka, J., Doyen, L., Gentilini, R., Raskin, J.: Faster algorithms for mean-payoff games. Formal Methods in System Design 38(2), 97–118 (2011)
  * [5] Calude, C.S., Jain, S., Khoussainov, B., Li, W., Stephan, F.: Deciding parity games in quasipolynomial time. In: STOC. pp. 252–263 (2017)
  * [6] Comin, C., Rizzi, R.: Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games. Algorithmica 77(4), 995–1021 (2017)
  * [7] Dorfman, D., Kaplan, H., Zwick, U.: A faster deterministic exponential time algorithm for energy games and mean payoff games. In: ICALP. pp. 114:1–114:14 (2019)
  * [8] Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. International Journal of Game Theory 109(8), 109–113 (1979)
  * [9] Emerson, E.A., Jutla, C.S.: Tree automata, $\mu$-calculus and determinacy. In: FOCS. pp. 368–377. IEEE Computer Society (1991)
  * [10] Fijalkow, N., Gawrychowski, P., Ohlmann, P.: Value iteration using universal graphs and the complexity of mean payoff games. In: MFCS. LIPIcs, vol. 170, pp. 34:1–34:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
  * [11] Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. In: FOCS. pp. 338–346. IEEE Computer Society (1984)
  * [12] Gallai, T.: Maximum-minimum sätze über graphen. Acta Math. Acad. Sci. Hung. (9), 395–434 (1958)
  * [13] Gurvich, V.A., Karzanov, A.V., Khachiyan, L.G.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics 28, 85–91 (1988)
  * [14] Khachiyan, L., Gurvich, V., Zhao, J.: Extending Dijkstra’s algorithm to maximize the shortest path by node-wise limited arc interdiction. In: CSR. Lecture Notes in Computer Science, vol. 3967, pp. 221–234. Springer (2006)
  * [15] Luttenberger, M.: Strategy iteration using non-deterministic strategies for solving parity games. CoRR (2008), http://arxiv.org/abs/0806.2923
  * [16] Luttenberger, M., Meyer, P.J., Sickert, S.: Practical synthesis of reactive systems from LTL specifications via parity games. Acta Informatica 57(1-2), 3–36 (2020)
  * [17] Martin, D.A.: Borel determinacy. Annals of Mathematics 102(2), 363–371 (1975)
  * [18] Meyer, P.J., Luttenberger, M.: Solving mean-payoff games on the GPU. In: ATVA. Lecture Notes in Computer Science, vol. 9938, pp. 262–267 (2016)
  * [19] Meyer, P.J., Sickert, S., Luttenberger, M.: Strix: Explicit reactive synthesis strikes back! In: CAV. Lecture Notes in Computer Science, vol. 10981, pp. 578–586. Springer (2018)
  * [20] Mostowski, A.W.: Games with forbidden positions. Tech. Rep. 78, University of Gdansk (1991)
  * [21] Ohlmann, P.: Monotonic graphs for parity and mean-payoff games. Ph.D. thesis, Université de Paris (2021)
  * [22] Puri, A.: Theory of Hybrid Systems and Discrete Event Systems. Ph.D. thesis, EECS Department, University of California, Berkeley (dec 1995)
  * [23] Schewe, S.: An optimal strategy improvement algorithm for solving parity and payoff games. In: CSL. Lecture Notes in Computer Science, vol. 5213, pp. 369–384. Springer (2008)

##  Appendix 0.A Proof of Theorem 2.2

This short appendix is devoted to the proof of Theorem 2.2. We use the
following result.

###### Lemma 6

Let $\sigma_{0}$ be an $\mathrm{En}$-optimal Min strategy in $\mathcal{G}$ and
$\pi=v_{0}\rightarrow v_{1}\rightarrow\dots\rightarrow v_{k}$ be a finite path
consistent with $\sigma_{0}$ such that $\mathrm{En}_{0}(v_{k})<\infty$. Then
we have $\mathrm{sum}(\pi)\leq\mathrm{En}_{0}(v_{0})-\mathrm{En}_{0}(v_{k})$.

###### Proof

Let $\pi^{\prime}$ be an infinite path from $v_{k}$ consistent with
$\sigma_{0}$ and such that
$\mathrm{En}_{0}(v_{k})=\mathrm{En}(w(\pi^{\prime}))$. Then $\pi\pi^{\prime}$
is consistent with $\sigma_{0}$ thus
$\mathrm{En}_{0}(v_{0})\geq\mathrm{En}(w(\pi\pi^{\prime}))$ by optimality. We
thus obtain

$\begin{array}[]{lcl}\mathrm{En}_{0}(v_{0})\ \ \geq\ \
\mathrm{En}(w(\pi\pi^{\prime}))&=&\sup_{k^{\prime}\geq
0}(\mathrm{sum}((\pi\pi^{\prime})_{<k^{\prime}}))\\\
&\geq&\sup_{k^{\prime}\geq
k}(\mathrm{sum}((\pi\pi^{\prime})_{<k^{\prime}}))\\\
&=&\mathrm{sum}(\pi)+\sup_{k^{\prime}\geq
0}\mathrm{sum}(\pi^{\prime}_{<k^{\prime}})\\\
&=&\mathrm{sum}(\pi)+\mathrm{En}(w(\pi^{\prime}))\ \ =\ \
\mathrm{sum}(\pi)+\mathrm{En}_{0}(v_{k}).\end{array}$

∎

We may now derive the wanted result.

######  Proof (of Theorem 2.2)

Let $\phi:V\to\mathbb{N}^{\infty}$ be a potential such that
$\phi\leq\mathrm{En}_{0}$; we aim to prove that
$\mathrm{En}_{0}=\phi+\mathrm{En}_{\phi}$ over $V$. Consider first a vertex
$v$ with $\mathrm{En}_{0}(v)=\infty$, fix an optimal Max strategy $\tau_{0}$
in $\mathcal{G}$ and an infinite path $\pi=e_{0}e_{1}\dots=v_{0}\rightarrow
v_{1}\rightarrow\dots$ consistent with $\tau_{0}$ from $v$: by definition we
have $\mathrm{En}(w(\pi))=\sup_{k}\sum_{i=0}^{k-1}w(e_{i})=\infty$. We claim
that $\mathrm{En}(w_{\phi}(\pi))=\infty$ which proves the wanted equality over
$v$ (both terms are infinite).

  * •

If for some $i$, $w(e_{i})=\infty$ then $w_{\phi}(e_{i})=\infty$ which implies
the result.

  * •

If for some $i$, $\phi(v_{i})=\infty$ then again we have
$w_{\phi}(e_{i})=\infty$.

  * •

Otherwise, we have for all $k$

$\mathrm{sum}_{\phi}(\pi_{<k})=\underbrace{\phi(v_{k})-\phi(v_{0})}_{\text{bounded}}+\mathrm{sum}(\pi_{<k}),$

and therefore
$\sup_{k}\mathrm{sum}_{\phi}(\pi_{<k})=\sup_{k}\mathrm{sum}(\pi_{<k})=\infty$,
the wanted result.

We now consider a vertex $v$ such that $\mathrm{En}_{0}(v)<\infty$. Consider
an $\mathrm{En}$-optimal Min strategy $\sigma_{0}:V_{\mathrm{Min}}\to E$ in
$\mathcal{G}$ and let $\pi=v_{0}\rightarrow v_{1}\rightarrow\dots$ be an
infinite path consistent with $\sigma_{0}$ starting from $v_{0}=v$. Note that
for any $k\geq 0$, $v_{k}$ has finite energy value, and thus we obtain thanks
to Lemma 6 and the hypothesis $\phi\leq\mathrm{En}_{0}$ that

$\begin{array}[]{lcl}\mathrm{sum}_{\phi}(\pi_{<k})&=&\mathrm{sum}(\pi_{<k})+\phi(v_{k})-\phi(v_{0})\\\
&\leq&\mathrm{En}_{0}(v_{0})\underbrace{-\mathrm{En}_{0}(v_{k})+\phi(v_{k})}_{\leq
0}-\phi(v_{0})\ \ \leq\ \ \mathrm{En}_{0}(v_{0})-\phi(v_{0}),\end{array}$

hence $\mathrm{En}_{\phi}(v_{0})=\sup_{\pi\models\sigma_{0}}\sup_{k\geq
0}\mathrm{sum}_{\phi}(\pi_{<k})\leq\mathrm{En}_{0}(v_{0})-\phi(v_{0})$.

For the other inequality, consider an optimal Min strategy $\sigma_{\phi}$ in
$\mathcal{G}_{\phi}$, and let $\pi$ be an infinite path from $v_{0}=v$
consistent with $\sigma_{\phi}$. By applying Lemma 6 in $\mathcal{G}_{\phi}$
we now get

$\begin{array}[]{lcl}\mathrm{sum}(\pi_{<k})&=&\mathrm{sum}_{\phi}(\pi_{<k})-\phi(v_{k})+\phi(v_{0})\\\
&\leq&\mathrm{En}_{\phi}(v_{0})-\underbrace{\mathrm{En}_{\phi}(v_{k})}_{\geq
0}-\underbrace{\phi(v_{k})}_{\geq 0}+\phi(v_{0})\ \ \leq\ \
\mathrm{En}_{\phi}(v_{0})+\phi(v_{0}),\end{array}$

and the wanted result follows by taking a supremum. ∎


# A note on gaps

Hisanobu Shinya

###### Abstract

Let $p_{k}$ denote the $k$-th prime and $d(p_{k})=p_{k}-p_{k-1}$, the
difference between consecutive primes. We denote by $N_{\epsilon}(x)$ the
number of primes $\leq x$ which satisfy the inequality $d(p_{k})\leq(\log
p_{k})^{2+\epsilon}$, where $\epsilon>0$ is arbitrary and fixed, and by
$\pi(x)$ the number of primes less than or equal to $x$. In this paper, we
first prove a theorem that $\lim_{x\to\infty}N_{\epsilon}(x)/\pi(x)=1$. A
corollary to the proof of the theorem concerning gaps between consecutive
squarefree numbers is stated.

Email address<EMAIL_ADDRESS>
2000 MSC: 11B05.

##  1 Introduction

Let $p_{k}$ denote the $k$-th prime and for $k>1$,

$d(p_{k}):=p_{k}-p_{k-1}.$

Concerning $d(p_{k})$, Harald Cramér conjectured that there exists a positive
real number $M$ such that

$d(p_{k+1})=p_{k+1}-p_{k}\leq M(\log p_{k})^{2}$

for all $k\geq 1$.

Cramér himself showed [2] that

$p_{k+1}-p_{k}=o((\log p_{k})^{3})$

for all but at most $o\left(x/(\log x)^{4}\right)$ primes $\leq x$.

We denote the number of primes less than or equal to a positive real number
$x$ with $\pi(x)$. In this paper, we prove the following theorem, which
supports Cramér’s conjecture.

######  Theorem 1.

Let $x$ be any positive real number and $N_{\epsilon}(x)$ the number of primes
$\leq x$ which satisfy the inequality

$d(p_{k})\leq(\log p_{k})^{2+\epsilon},$

where $\epsilon>0$ is arbitrary and fixed. Then we have

$\lim_{x\to\infty}\frac{N_{\epsilon}(x)}{\pi(x)}=1.$

Note that the function for the upper bound of $d(p_{k})$ in Theorem 1 is
$(\log p_{k})^{2}$, while that in Cramér’s conjecture is $(\log p_{k-1})^{2}$;
the function is evaluated at the smaller prime of the gap in Cramér’s
conjecture. Nevertheless, the prime number theorem implies that

$\lim_{k\to\infty}\frac{p_{k}}{p_{k+1}}=1,$

so replacing the function for the upper bound in Cramér’s conjecture by $(\log
p_{k})^{2}$ does not change the statement of the conjecture essentially.

In proving Theorem 1, the following lemmas are used.

######  Lemma 1.

[1, pp. 77] For any arithmetical function $a(n)$ let

$A(x)=\sum_{n\leq x}a(n),$

where $A(x)=0$ if $x<1$. Assume that $f$ has a continuous derivative on the
interval $[y,x]$, where $0<y<x$. Then we have

$\sum_{y<n\leq x}a(n)f(n)=A(x)f(x)-A(y)f(y)-\int_{y}^{x}A(t)f^{\prime}(t)dt.$

######  Lemma 2.

[2] For all $k\geq 1$, we have

$d(p_{k+1})=O(p_{k}^{\frac{1}{2}+\frac{7}{200}}).$

##  2 Proof of Theorem 1

In this section, we give a proof of Theorem 1.

Define

$d(p_{1}):=p_{1}.$

We begin by an elementary analysis of the partial sums

$Q(t):=\sum_{p_{k}\leq t}d(p_{k})-\sum_{n\leq t}1.$

######  Lemma 3.

For all positive real numbers $t\geq 2$, if $p_{k-1}\leq t\leq p_{k}$ ($k\geq
2$) then we have

$-(p_{k}-p_{k-1})\leq Q(t)\leq 0.$

###### Proof.

It is easy to see that for $N=2,3,\ldots$, we have

$\begin{split}\sum_{p_{k}\leq
p_{N}}d(p_{k})&=d(p_{1})+d(p_{2})+d(p_{3})+\cdots+d(p_{N})\\\
&=p_{1}+p_{2}-p_{1}+p_{3}-p_{2}+\cdots+p_{N}-p_{N-1}\\\ &=p_{N}.\end{split}$

Hence, for $N\geq 2$ we have

$Q(p_{N})=0.$ (1)

If $t$ satisfies $p_{N-1}<t<p_{N}$ ($N\geq 2$), then the first partial sums of
$Q$ is constant, and the second ones decrease by $1$ as $t$ increases by $1$.
The lemma now follows from (1).

∎

Using all the preliminary lemmas above, Theorem 1 is proved as follows. Let
$\epsilon>0$ be arbitrary.

We define a function $\delta_{\epsilon}(x)$ such that

$N_{\epsilon}(x)=(1-\delta_{\epsilon}(x))\pi(x).$ (2)

It is plain that $0<\delta_{\epsilon}(x)<1$. We show that

$\lim_{x\to\infty}\delta_{\epsilon}(x)=0,$ (3)

thereby proving Theorem 1.

By the definition of $N_{\epsilon}(x)$, there are
$(1-\delta_{\epsilon}(x))\pi(x)$ primes which are $\leq x$ and satisfy the
inequality

$d(p_{k})\leq(\log p_{k})^{2+\epsilon}.$

This is equivalent to stating the following:

$\begin{split}&\text{ There are $\delta_{\epsilon}(x)\pi(x)$ primes which are
$\leq x$ and satisfy}\\\ &d(p_{k})>(\log p_{k})^{2+\epsilon}.\end{split}$ (4)

At this point, we pay our attention to the partial sums

$\sum_{p\leq x}\frac{d(p)}{p}-\sum_{n\leq x}\frac{1}{n}.$

Define

$p(n):=\begin{cases}1&:\text{$n$ is prime}\\\ 0&:\text{otherwise}.\end{cases}$

In Lemma 1, we choose

$f(t)=\frac{1}{t},\quad a(n)=d(n)p(n)-1,\quad\text{and}\quad y=1/2,$

and obtain

$\sum_{p\leq x}\frac{d(p)}{p}-\sum_{n\leq
x}\frac{1}{n}=\frac{Q(x)}{x}+\int_{1}^{x}\frac{Q(t)dt}{t^{2}}.$ (5)

By Lemmas 2 and 3, it is plain that the limit of the right side of (5) as
$x\to\infty$ exists. Since

$\sum_{n\leq x}\frac{1}{n}\sim\log x,\quad\text{as $x\to\infty$},$

it follows from (5) that

$\sum_{p\leq x}\frac{d(p)}{p}\sim\log x,\quad\text{as $x\to\infty$}.$ (6)

Now, given $\epsilon$ and $x>0$, let $S_{\epsilon}(x)$ be the set of all
primes $\leq x$ which satisfy the last inequality in (4), $|S_{\epsilon}(x)|$
the number of elements in $S_{\epsilon}(x)$, and

$\chi_{\epsilon,x}(n):=\begin{cases}1&:n\in S_{\epsilon}(x)\\\
0&:\text{otherwise}.\end{cases}$

Choosing

$f(t)=q_{\epsilon}(t):=\frac{(\log t)^{2+\epsilon}}{t},\quad
a(n)=\chi_{\epsilon,x}(n),\quad\text{and}\quad y=1/2$

in Lemma 1, we have for each $w\leq x$

$\begin{split}\sum_{p\in S_{\epsilon}(x),p\leq
w}\frac{d(p)}{p}&\geq\sum_{n\leq w}\frac{(\log
n)^{2+\epsilon}\chi_{\epsilon,x}(n)}{n}\\\ &=\frac{\xi_{\epsilon,x}(w)(\log
w)^{2+\epsilon}}{w}-\int_{2}^{w}\xi_{\epsilon,x}(t)q^{\prime}_{\epsilon}(t)dt,\end{split}$

where

$\xi_{\epsilon,x}(t):=\sum_{n\leq t}\chi_{\epsilon,x}(n)$

and $0\leq\xi_{\epsilon,x}(w)\leq|S_{\epsilon}(x)|$ for $w\leq x$. In
particular, when $w=x$, we have

$\sum_{p\in S_{\epsilon}(x),p\leq
x}\frac{d(p)}{p}\geq\frac{|S_{\epsilon}(x)|(\log
x)^{2+\epsilon}}{x}-\int_{2}^{x}\xi_{\epsilon,x}(t)q^{\prime}_{\epsilon}(t)dt.$
(7)

But since

$q^{\prime}_{\epsilon}(t)=\frac{(2+\epsilon)(\log t)^{1+\epsilon}-(\log
t)^{2+\epsilon}}{t^{2}},$

it is plain that for each arbitrary $\epsilon>0$, there exists
$t_{\epsilon}>0$ such that $q^{\prime}(\epsilon)(t)<0$ for all $t\geq
t_{\epsilon}$. This in turn implies that for each arbitrary $\epsilon>0$, with

$\xi_{\epsilon,x}(t)\geq 0\quad\text{for all $t\geq 0$},$

there exists a positive real number $M_{\epsilon}$, which depends only on
$\epsilon$, such that the integral in (7) satisfies

$-\int_{2}^{x}\xi_{\epsilon,x}(t)q^{\prime}_{\epsilon}(t)dt>-M_{\epsilon}$ (8)

for all $x\geq 2$.

With (8), the inequality (7) becomes

$\begin{split}\sum_{p\in S_{\epsilon}(x),p\leq
x}\frac{d(p)}{p}&=\frac{|S_{\epsilon}(x)|(\log
x)^{2+\epsilon}}{x}-\int_{2}^{x}\xi_{\epsilon,x}(t)q^{\prime}_{\epsilon}(t)dt\\\
&\geq\frac{|S_{\epsilon}(x)|(\log
x)^{2+\epsilon}}{x}-M_{\epsilon}.\end{split}$ (9)

Furthermore, by (4), we have $|S_{\epsilon}(x)|=\delta_{\epsilon}(x)\pi(x)$,
and so (9) gives

$\begin{split}\sum_{p\in S_{\epsilon}(x),p\leq
x}\frac{d(p)}{p}&\geq\frac{|S_{\epsilon}(x)|(\log
x)^{2+\epsilon}}{x}-M_{\epsilon}\\\ &=\frac{\delta_{\epsilon}(x)\pi(x)(\log
x)^{2+\epsilon}}{x}-M_{\epsilon}.\end{split}$ (10)

Finally, by (6) and the prime number theorem

$\pi(x)\sim\frac{x}{\log x},\quad\text{as $x\to\infty$},$

letting $x\to\infty$, the inequality (10) becomes

$\begin{split}\log x\sim\sum_{p\leq x}\frac{d(p)}{p}\geq\sum_{p\in
S_{\epsilon}(x),p\leq
x}\frac{d(p)}{p}\geq\frac{\delta_{\epsilon}(x)\pi(x)(\log
x)^{2+\epsilon}}{x}-M_{\epsilon},\end{split}$

by which (3) follows immediately. This completes the proof of Theorem 1.

##  3 Distribution of squarefree numbers

We note the following theorem, which is a corollary to the proof of Theorem 1
in the previous section.

######  Theorem 2.

Let $\\{a_{k}\\}$ be the sequence of squarefree numbers,

$s(n):=\begin{cases}1&:n=a_{k}\\\ 0&:\text{otherwise},\end{cases}$
$d(a_{k}):=a_{k}-a_{k-1},$

and

$S(x):=\sum_{n\leq x}s(n).$

Let $\epsilon>0$ be arbitrary and $N_{\epsilon}(x)$ the number of squarefree
numbers $\leq x$ which satisfy the inequality

$d(a_{k})\leq M(\log a_{k})^{1+\epsilon}$

for some positive constant $M$. Then we have

$\lim_{x\to\infty}\frac{N_{\epsilon}(x)}{S(x)}=1.$

###### Proof.

We recall that [3]

$S(x)=Ax+O(x^{\frac{1}{2}}),$ (11)

for some constant $A$. By (11), it is easy to see that

$d(a_{k})=O(a_{k}^{\frac{1}{2}}).$

If we recall how Lemma 3 was derived with Lemma 2, it is plain that

$R(t):=\sum_{a_{k}\leq t}d(a_{k})-\sum_{n\leq t}1=O(t^{\frac{1}{2}}).$

The rest of the proof follows a similar pattern. In particular, we note the
following analogues:

  1. 1.

the analogue of (6) is

$\sum_{a_{k}\leq x}\frac{d(a_{k})}{a_{k}}\sim\log x,\quad\text{as
$x\to\infty$};$

  2. 2.

the analogue of $Q(t)$ is $R(t)$;

  3. 3.

the analogue of $q_{\epsilon}(t)$ is the function $\frac{(\log
t)^{1+\epsilon}}{t}$.

∎

From Theorem 2, one may wonder if the exact order of $d(a_{k})$ is $O(\log
a_{k})$.

## References

  * [1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, New York, 1976.
  * [2] A. Granville, Harald Cramér and the distribution of prime numbers, Scandinavian Actuarial J. 1 (1995), 12-28
  * [3] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 4th ed., Oxford, New York, 1960.


* Reimer et al. [2019] Reimer A., Böttcher M., Buson S., 2019, Cascading Constraints from Neutrino-emitting Blazars: The Case of TXS 0506+056, ApJ 881, 46 (doi:10.3847/1538-4357/ab2bff)
  * Reuter et al. [2020] Reuter C., Vieira J.D., Spilker J.S., et al., 2020, The Complete Redshift Distribution of Dusty Star-forming Galaxies from the SPT-SZ Survey, ApJ 902, 78 (doi:10.3847/1538-4357/abb599)
  * Ricci et al. [2022] Ricci L., Boccardi B., Nokhrina E., et al., 2022, Exploring the disk-jet connection in NGC 315, A&A 664, A166 (doi:10.1051/0004-6361/202243958)
  * Ricci et al. [2018] Ricci L., Isella A., Liu S., Li H., 2018,  Imaging Planetary Systems in the Act of Forming with the ngVLA, In: Murphy E. (ed.) Science with a Next Generation Very Large Array, Vol. 517. Astronomical Society of the Pacific Conference Series, p. 147 (https://ui.adsabs.harvard.edu/abs/2018ASPC..517..147R)
  * Riechers et al. [2020] Riechers D.A., Boogaard L.A., Decarli R., et al., 2020, VLA-ALMA Spectroscopic Survey in the Hubble Ultra Deep Field (VLASPECS): Total Cold Gas Masses and CO Line Ratios for z = 2-3 Main-sequence Galaxies, ApJ 896, L21 (doi:10.3847/2041-8213/ab9595)
  * Riechers et al. [2021] Riechers D.A., Nayyeri H., Burgarella D., et al., 2021, Rise of the Titans: Gas Excitation and Feedback in a Binary Hyperluminous Dusty Starburst Galaxy at z $\sim$ 6, ApJ 907, 62 (doi:10.3847/1538-4357/abcf2e)
  * Riechers et al. [2019] Riechers D.A., Pavesi R., Sharon C.E., et al., 2019, COLDz: Shape of the CO Luminosity Function at High Redshift and the Cold Gas History of the Universe, ApJ 872, 7 (doi:10.3847/1538-4357/aafc27)
  * Riechers et al. [2022] Riechers D.A., Weiss A., Walter F., et al., 2022, Microwave background temperature at a redshift of 6.34 from H2O absorption, Nature 602, 58 (doi:10.1038/s41586-021-04294-5)
  * Riess et al. [2023] Riess A.G., Anand G.S., Yuan W., et al., 2023, Crowded No More: The Accuracy of the Hubble Constant Tested with High Resolution Observations of Cepheids by JWST, arXiv e-prints arXiv:2307.15806 (doi:10.48550/arXiv.2307.15806)
  * Riggi et al. [2016] Riggi S., Ingallinera A., Leto P., et al., 2016, Automated detection of extended sources in radio maps: progress from the SCORPIO survey, MNRAS 460, 1486 (doi:10.1093/mnras/stw982)
  * Riggi et al. [2019] Riggi S., Vitello F., Becciani U., et al., 2019, Cuc(aesar) source finder: Recent developments and testing, PASA 36, e037 (doi:10.1017/pasa.2019.29)
  * Rioja & Dodson [2011] Rioja M., Dodson R., 2011, High-precision Astrometric Millimeter Very Long Baseline Interferometry Using a New Method for Atmospheric Calibration, AJ 141, 114 (doi:10.1088/0004-6256/141/4/114)
  * Rioja & Dodson [2020] Rioja M.J., Dodson R., 2020, Precise radio astrometry and new developments for the next-generation of instruments, A&A Rev. 28, 6 (doi:10.1007/s00159-020-00126-z)
  * Rioja et al. [2015] Rioja M.J., Dodson R., Jung T., Sohn B.W., 2015, The Power of Simultaneous Multifrequency Observations for mm-VLBI: Astrometry up to 130 GHz with the KVN, AJ 150, 202 (doi:10.1088/0004-6256/150/6/202)
  * Ripperda et al. [2022] Ripperda B., Liska M., Chatterjee K., et al., 2022, Black Hole Flares: Ejection of Accreted Magnetic Flux through 3D Plasmoid-mediated Reconnection, ApJ 924, L32 (doi:10.3847/2041-8213/ac46a1)
  * Rizzo et al. [2023] Rizzo F., Roman-Oliveira F., Fraternali F., et al., 2023, The ALMA-ALPAKA survey I: high-resolution CO and [CI] kinematics of star-forming galaxies at z = 0.5-3.5, arXiv e-prints arXiv:2303.16227 (doi:10.48550/arXiv.2303.16227)
  * Robotham et al. [2018] Robotham A.S.G., Davies L.J.M., Driver S.P., et al., 2018, ProFound: Source Extraction and Application to Modern Survey Data, MNRAS 476, 3137 (doi:10.1093/mnras/sty440)
  * Rodrigues et al. [2021] Rodrigues X., Garrappa S., Gao S., et al., 2021, Multiwavelength and Neutrino Emission from Blazar PKS 1502 + 106, ApJ 912, 54 (doi:10.3847/1538-4357/abe87b)
  * Rodriguez et al. [2006] Rodriguez C., Taylor G.B., Zavala R.T., et al., 2006, A Compact Supermassive Binary Black Hole System, ApJ 646, 49 (doi:10.1086/504825)
  * Rolffs et al. [2011] Rolffs R., Schilke P., Wyrowski F., et al., 2011, Hot HCN around young massive stars at 0.1” resolution, A&A 529, A76 (doi:10.1051/0004-6361/201116544)
  * Ros et al. [2020] Ros E., Kadler M., Perucho M., et al., 2020, Apparent superluminal core expansion and limb brightening in the candidate neutrino blazar TXS 0506+056, A&A 633, L1 (doi:10.1051/0004-6361/201937206)
  * Ruge et al. [2016] Ruge J.P., Flock M., Wolf S., et al., 2016, Gaps, rings, and non-axisymmetric structures in protoplanetary disks: Emission from large grains, A&A 590, A17 (doi:10.1051/0004-6361/201526616)
  * Sabater et al. [2019] Sabater J., Best P.N., Hardcastle M.J., et al., 2019,  The LoTSS view of radio AGN in the local Universe. The most massive galaxies are always switched on,  (doi:10.1051/0004-6361/201833883)
  * Sadaghiani et al. [2020] Sadaghiani M., Sánchez-Monge Á., Schilke P., et al., 2020, Physical properties of the star-forming clusters in NGC 6334. A study of the continuum dust emission with ALMA, A&A 635, A2 (doi:10.1051/0004-6361/201935699)
  * Sánchez-Monge et al. [2017] Sánchez-Monge Á., Schilke P., Schmiedeke A., et al., 2017, The physical and chemical structure of Sagittarius B2. II. Continuum millimeter emission of Sgr B2(M) and Sgr B2(N) with ALMA, A&A 604, A6 (doi:10.1051/0004-6361/201730426)
  * Sanna et al. [2017] Sanna A., Reid M.J., Dame T.M., et al., 2017, Mapping spiral structure on the far side of the Milky Way, Science 358, 227 (doi:10.1126/science.aan5452)
  * Schmidt et al. [1993] Schmidt B.P., Kirshner R.P., Eastman R.G., et al., 1993, The unusual supernova SN1993J in the galaxy M81, Nature 364, 600 (doi:10.1038/364600a0)
  * Schmidt, K. et al. [2022] Schmidt, K.Geyer, F.Fröse, S.et al., 2022, Deep learning-based imaging in radio interferometry, A&A 664, A134 (doi:10.1051/0004-6361/202142113)
  * Scholz et al. [2020] Scholz P., Cook A., Cruces M., et al., 2020, Simultaneous X-Ray and Radio Observations of the Repeating Fast Radio Burst FRB $\sim$ 180916.J0158+65, ApJ 901, 165 (doi:10.3847/1538-4357/abb1a8)
  * Scoville et al. [2007] Scoville N., Aussel H., Brusa M., et al., 2007, The Cosmic Evolution Survey (COSMOS): Overview, ApJS 172, 1 (doi:10.1086/516585)
  * Segal et al. [2023] Segal G., Parkinson D., Norris R., et al., 2023, Identifying anomalous radio sources in the Evolutionary Map of the Universe Pilot Survey using a complexity-based approach, MNRAS 521, 1429 (doi:10.1093/mnras/stad537)
  * Segura-Cox et al. [2020] Segura-Cox D.M., Schmiedeke A., Pineda J.E., et al., 2020, Four annular structures in a protostellar disk less than 500,000 years old, Nature 586, 228 (doi:10.1038/s41586-020-2779-6)
  * Selina et al. [2018a] Selina R.J., Murphy E.J., McKinnon M., et al., 2018a,  The ngVLA Reference Design, In: Murphy E. (ed.) Science with a Next Generation Very Large Array, Vol. 517. Astronomical Society of the Pacific Conference Series, p. 15 (doi:10.48550/arXiv.1810.08197)
  * Selina et al. [2018b] Selina R.J., Murphy E.J., McKinnon M., et al., 2018b,  The ngVLA Reference Design, In: Murphy E. (ed.) Science with a Next Generation Very Large Array, Vol. 517. Astronomical Society of the Pacific Conference Series, p. 15 (doi:10.48550/arXiv.1810.08197)
  * Shen et al. [2013] Shen S., Madau P., Guedes J., et al., 2013, The Circumgalactic Medium of Massive Galaxies at z ~3: A Test for Stellar Feedback, Galactic Outflows, and Cold Streams, ApJ 765, 89 (doi:10.1088/0004-637X/765/2/89)
  * Shimwell et al. [2022] Shimwell T.W., Hardcastle M.J., Tasse C., et al., 2022, The LOFAR Two-metre Sky Survey. V. Second data release, A&A 659, A1 (doi:10.1051/0004-6361/202142484)
  * Shimwell et al. [2019] Shimwell T.W., Tasse C., Hardcastle M.J., et al., 2019, The LOFAR Two-metre Sky Survey. II. First data release, A&A 622, A1 (doi:10.1051/0004-6361/201833559)
  * Shukla & Mannheim [2020] Shukla A., Mannheim K., 2020, Gamma-ray flares from relativistic magnetic reconnection in the jet of the quasar 3C 279, Nature Communications 11, 4176 (doi:10.1038/s41467-020-17912-z)
  * Slijepcevic et al. [2023] Slijepcevic I.V., Scaife A.M.M., Walmsley M., et al., 2023, Radio Galaxy Zoo: Building a multi-purpose foundation model for radio astronomy with self-supervised learning, arXiv e-prints arXiv:2305.16127 (doi:10.48550/arXiv.2305.16127)
  * Smartt [2009] Smartt S.J., 2009, Progenitors of Core-Collapse Supernovae, ARA&A 47, 63 (doi:10.1146/annurev-astro-082708-101737)
  * Smolčić et al. [2017a] Smolčić V., Delvecchio I., Zamorani G., et al., 2017a, The VLA-COSMOS 3 GHz Large Project: Multiwavelength counterparts and the composition of the faint radio population, A&A 602, A2 (doi:10.1051/0004-6361/201630223)
  * Smolčić et al. [2017b] Smolčić V., Novak M., Bondi M., et al., 2017b, The VLA-COSMOS 3 GHz Large Project: Continuum data and source catalog release, A&A 602, A1 (doi:10.1051/0004-6361/201628704)
  * Sol et al. [1989] Sol H., Pelletier G., Asseo E., 1989, Two-flow model for extragalactic radio jets., MNRAS 237, 411 (doi:10.1093/mnras/237.2.411)
  * Springel et al. [2008] Springel V., Wang J., Vogelsberger M., et al., 2008, The Aquarius Project: the subhaloes of galactic haloes, MNRAS 391, 1685 (doi:10.1111/j.1365-2966.2008.14066.x)
  * Stammler et al. [2023] Stammler S.M., Lichtenberg T., Drążkowska J., Birnstiel T., 2023, Leaky dust traps: How fragmentation impacts dust filtering by planets, A&A 670, L5 (doi:10.1051/0004-6361/202245512)
  * Stil et al. [2006] Stil J.M., Taylor A.R., Dickey J.M., et al., 2006, The VLA Galactic Plane Survey, AJ 132, 1158 (doi:10.1086/505940)
  * Stuber et al. [2023] Stuber T.A., Kirchschlager F., Pearce T.D., et al., 2023, How much large dust could be present in hot exozodiacal dust systems?, A&A 678, A121 (doi:10.1051/0004-6361/202346109)
  * Subramanian [2016] Subramanian K., 2016, The origin, evolution and signatures of primordial magnetic fields, Reports on Progress in Physics 79, 076901 (doi:10.1088/0034-4885/79/7/076901)
  * Sulzenauer et al. [2021] Sulzenauer N., Dannerbauer H., Díaz-Sánchez A., et al., 2021, Milky Way-like Gas Excitation in an Ultrabright Submillimeter Galaxy at z = 1.6, ApJ 923, L27 (doi:10.3847/2041-8213/ac2eba)
  * Sun et al. [2022] Sun J., Leroy A.K., Rosolowsky E., et al., 2022, Molecular Cloud Populations in the Context of Their Host Galaxy Environments: A Multiwavelength Perspective, AJ 164, 43 (doi:10.3847/1538-3881/ac74bd)
  * Sur et al. [2021] Sur S., Basu A., Subramanian K., 2021, Properties of polarized synchrotron emission from fluctuation-dynamo action - I. Application to galaxy clusters, MNRAS 501, 3332 (doi:10.1093/mnras/staa3767)
  * Suray & Troitsky [2024] Suray A., Troitsky S., 2024, Neutrino flares of radio blazars observed from TeV to PeV, MNRAS 527, L26 (doi:10.1093/mnrasl/slad136)
  * Syed et al. [2023] Syed J., Beuther H., Goldsmith P.F., et al., 2023, Cold atomic gas identified by HI self-absorption. Cold atomic clouds toward giant molecular filaments, arXiv e-prints arXiv:2310.02077 (doi:10.48550/arXiv.2310.02077)
  * Tan et al. [2014] Tan J.C., Beltrán M.T., Caselli P., et al., 2014,  Massive Star Formation, In: Beuther H., Klessen R.S., Dullemond C.P., Henning T. (eds.) Protostars and Planets VI., p.149 (doi:10.2458/azu_uapress_9780816531240-ch007)
  * Tang et al. [2023] Tang H., Yue S., Wang Z., et al., 2023, A model local interpretation routine for deep learning based radio galaxy classification, arXiv e-prints arXiv:2307.03453 (doi:10.48550/arXiv.2307.03453)
  * Tavecchio & Ghisellini [2015] Tavecchio F., Ghisellini G., 2015, High-energy cosmic neutrinos from spine-sheath BL Lac jets, MNRAS 451, 1502 (doi:10.1093/mnras/stv1023)
  * Tavecchio et al. [2010] Tavecchio F., Ghisellini G., Ghirlanda G., et al., 2010, TeV BL Lac objects at the dawn of the Fermi era, MNRAS 401, 1570 (doi:10.1111/j.1365-2966.2009.15784.x)
  * Tavecchio et al. [2014] Tavecchio F., Ghisellini G., Guetta D., 2014, Structured Jets in BL Lac Objects: Efficient PeV Neutrino Factories?, ApJ 793, L18 (doi:10.1088/2041-8205/793/1/L18)
  * Tchekhovskoy & Bromberg [2016] Tchekhovskoy A., Bromberg O., 2016, Three-dimensional relativistic MHD simulations of active galactic nuclei jets: magnetic kink instability and Fanaroff-Riley dichotomy, MNRAS 461, L46 (doi:10.1093/mnrasl/slw064)
  * Teague et al. [2018] Teague R., Bae J., Bergin E.A., et al., 2018, A Kinematical Detection of Two Embedded Jupiter-mass Planets in HD 163296, ApJ 860, L12 (doi:10.3847/2041-8213/aac6d7)
  * The CTA Consortium & Ong, Rene A. [2019] The CTA ConsortiumOng, Rene A. 2019, The Cherenkov Telescope Array Science Goals and Current Status, EPJ Web Conf. 209, 01038 (doi:10.1051/epjconf/201920901038)
  * Ueda et al. [2019] Ueda T., Flock M., Okuzumi S., 2019, Dust Pileup at the Dead-zone Inner Edge and Implications for the Disk Shadow, ApJ 871, 10 (doi:10.3847/1538-4357/aaf3a1)
  * Ueda et al. [2021] Ueda T., Ogihara M., Kokubo E., Okuzumi S., 2021, Early Initiation of Inner Solar System Formation at the Dead-zone Inner Edge, ApJ 921, L5 (doi:10.3847/2041-8213/ac2f3b)
  * Ueda et al. [2022] Ueda T., Ricci L., Flock M., Castro Z., 2022, Probing the Inner Edge of Dead Zones in Protoplanetary Disks with ALMA and Next Generation Very Large Array, ApJ 928, 110 (doi:10.3847/1538-4357/ac56d8)
  * Urry & Padovani [1995] Urry C.M., Padovani P., 1995, Unified Schemes for Radio-Loud Active Galactic Nuclei, PASP 107, 803 (doi:10.1086/133630)
  * Vacca et al. [2018] Vacca V., Murgia M., Govoni F., et al., 2018, Magnetic Fields in Galaxy Clusters and in the Large-Scale Structure of the Universe, Galaxies 6, 142 (doi:10.3390/galaxies6040142)
  * Valdivia-Mena et al. [2022] Valdivia-Mena M.T., Pineda J.E., Segura-Cox D.M., et al., 2022, PRODIGE - envelope to disk with NOEMA. I. A 3000 au streamer feeding a Class I protostar, A&A 667, A12 (doi:10.1051/0004-6361/202243310)
  * Valentino et al. [2020] Valentino F., Daddi E., Puglisi A., et al., 2020, CO emission in distant galaxies on and above the main sequence, A&A 641, A155 (doi:10.1051/0004-6361/202038322)
  * van Weeren et al. [2019] van Weeren R.J., de Gasperin F., Akamatsu H., et al., 2019, Diffuse Radio Emission from Galaxy Clusters, Space Sci. Rev. 215, 16 (doi:10.1007/s11214-019-0584-z)
  * Vanderlinde et al. [2019] Vanderlinde K., Liu A., Gaensler B., et al., 2019,  The Canadian Hydrogen Observatory and Radio-transient Detector (CHORD), In: Canadian Long Range Plan for Astronomy and Astrophysics White Papers, Vol. 2020., p. 28 (doi:10.5281/zenodo.3765414)
  * Vardoulaki et al. [2021] Vardoulaki E., Jiménez Andrade E.F., Delvecchio I., et al., 2021, FR-type radio sources at 3 GHz VLA-COSMOS: Relation to physical properties and large-scale environment, A&A 648, A102 (doi:10.1051/0004-6361/202039488)
  * Vardoulaki et al. [2019] Vardoulaki E., Jiménez Andrade E.F., Karim A., et al., 2019, A closer look at the deep radio sky: Multi-component radio sources at 3 GHz VLA-COSMOS, A&A 627, A142 (doi:10.1051/0004-6361/201832982)
  * Varga et al. [2018] Varga J., Ábrahám P., Chen L., et al., 2018, VLTI/MIDI atlas of disks around low- and intermediate-mass young stellar objects, A&A 617, A83 (doi:10.1051/0004-6361/201832599)
  * Vastel et al. [2014] Vastel C., Ceccarelli C., Lefloch B., Bachiller R., 2014, The Origin of Complex Organic Molecules in Prestellar Cores, ApJ 795, L2 (doi:10.1088/2041-8205/795/1/L2)
  * Vazza et al. [2021] Vazza F., Locatelli N., Rajpurohit K., et al., 2021, Magnetogenesis and the Cosmic Web: A Joint Challenge for Radio Observations and Numerical Simulations, Galaxies 9, 109 (doi:10.3390/galaxies9040109)
  * Veach et al. [2013] Veach T.J., Groppi C.E., Hedden A., 2013, Vibrationally Excited HCN around AFGL 2591: A Probe of Protostellar Structure, ApJ 765, L34 (doi:10.1088/2041-8205/765/2/L34)
  * Vegetti et al. [2023] Vegetti S., Birrer S., Despali G., et al., 2023, Strong gravitational lensing as a probe of dark matter, arXiv e-prints arXiv:2306.11781 (doi:10.48550/arXiv.2306.11781)
  * Vernstrom et al. [2023] Vernstrom T., West J., Vazza F., et al., 2023, Polarized accretion shocks from the cosmic web, Science Advances 9, eade7233 (doi:10.1126/sciadv.ade7233)
  * von Fellenberg et al. [2022] von Fellenberg S.D., Gillessen S., Stadler J., et al., 2022, The Young Stars in the Galactic Center, ApJL 932, L6 (https://ui.adsabs.harvard.edu/abs/2022ApJ...932L...6V)
  * Walch et al. [2015] Walch S., Girichidis P., Naab T., et al., 2015, The SILCC (SImulating the LifeCycle of molecular Clouds) project - I. Chemical evolution of the supernova-driven ISM, MNRAS 454, 238 (doi:10.1093/mnras/stv1975)
  * Walter et al. [2008] Walter F., Brinks E., de Blok W.J.G., et al., 2008, THINGS: The H I Nearby Galaxy Survey, AJ 136, 2563 (doi:10.1088/0004-6256/136/6/2563)
  * Walter et al. [2020] Walter F., Carilli C., Neeleman M., et al., 2020, The Evolution of the Baryons Associated with Galaxies Averaged over Cosmic Time and Space, ApJ 902, 111 (doi:10.3847/1538-4357/abb82e)
  * Wang et al. [2021] Wang H., Stephan A.P., Naoz S., et al., 2021, Gravitational-wave Signatures from Compact Object Binaries in the Galactic Center, ApJ 917, 76 (https://ui.adsabs.harvard.edu/abs/2021ApJ...917...76W)
  * Wang et al. [2020a] Wang Y., Beuther H., Rugel M.R., et al., 2020a, The HI/OH/Recombination line survey of the inner Milky Way (THOR): data release 2 and H I overview, A&A 634, A83 (doi:10.1051/0004-6361/201937095)
  * Wang et al. [2020b] Wang Y., Bihr S., Beuther H., et al., 2020b, Cloud formation in the atomic and molecular phase: H I self absorption (HISA) towards a giant molecular filament, A&A 634, A139 (doi:10.1051/0004-6361/201935866)
  * Watkins et al. [2023] Watkins E.J., Kreckel K., Groves B., et al., 2023, Quantifying the energetics of molecular superbubbles in PHANGS galaxies, A&A 676, A67 (doi:10.1051/0004-6361/202346075)
  * Wendel et al. [2021] Wendel C., Shukla A., Mannheim K., 2021, Pair Cascades at the Edge of the Broad-line Region Shaping the Gamma-Ray Spectrum of 3C 279, ApJ 917, 32 (doi:10.3847/1538-4357/ac0a6e)
  * Whiting & Humphreys [2012] Whiting M., Humphreys B., 2012, Source-Finding for the Australian Square Kilometre Array Pathfinder, PASA 29, 371 (doi:10.1071/AS12028)
  * Wilkinson et al. [2016] Wilkinson M.D., Dumontier M., Aalbersberg I.J., et al., 2016, The FAIR Guiding Principles for scientific data management and stewardship, Scientific Data 3 (doi:10.1038/sdata.2016.18)
  * Willott et al. [2001] Willott C.J., Rawlings S., Blundell K.M., et al., 2001, The radio luminosity function from the low-frequency 3CRR, 6CE and 7CRS complete samples, MNRAS 322, 536 (doi:10.1046/j.1365-8711.2001.04101.x)
  * Witzel et al. [2018] Witzel G., Martinez G., Hora J., et al., 2018, Variability Timescale and Spectral Index of Sgr A* in the Near Infrared: Approximate Bayesian Computation Analysis of the Variability of the Closest Supermassive Black Hole, ApJ 863, 15 (doi:10.3847/1538-4357/aace62)
  * Wolf et al. [2008] Wolf S., Schegerer A., Beuther H., et al., 2008, Submillimeter Structure of the Disk of the Butterfly Star, ApJ 674, L101 (doi:10.1086/529188)
  * Wu et al. [2019] Wu C., Wong O.I., Rudnick L., et al., 2019, Radio Galaxy Zoo: CLARAN - a deep learning classifier for radio morphologies, MNRAS 482, 1211 (doi:10.1093/mnras/sty2646)
  * Xu et al. [2021] Xu M.H., Anderson J.M., Heinkelmann R., et al., 2021, Observable quality assessment of broadband very long baseline interferometry system, Journal of Geodesy 95, 51 (doi:10.1007/s00190-021-01496-7)
  * Xu et al. [2022] Xu M.H., Savolainen T., Anderson J.M., et al., 2022, Impact of the image alignment over frequency for the VLBI Global Observing System, A&A 663, A83 (doi:10.1051/0004-6361/202140840)
  * Xu et al. [2023] Xu M.H., Savolainen T., Bolotin S., et al., 2023, Baseline Vector Repeatability at the Sub-Millimeter Level Enabled by Radio Interferometer Phase Delays of Intra-Site Baselines, Journal of Geophysical Research (Solid Earth) 128, e2022JB025198 (doi:10.1029/2022JB025198)
  * Yajima et al. [2021] Yajima Y., Sorai K., Miyamoto Y., et al., 2021, CO Multi-line Imaging of Nearby Galaxies (COMING). IX. 12CO(J = 2-1)/12CO(J = 1-0) line ratio on kiloparsec scales, PASJ 73, 257 (doi:10.1093/pasj/psaa119)
  * Yan et al. [2023] Yan X., Lu R.S., Jiang W., et al., 2023, Kinematics and Collimation of the Two-Sided Jets in NGC 4261: VLBI Study on Sub-parsec Scales, arXiv e-prints arXiv:2309.05567 (doi:10.48550/arXiv.2309.05567)
  * Yoon et al. [2018] Yoon D.H., Cho S.H., Yun Y., et al., 2018, Astrometrically registered maps of H2O and SiO masers toward VX Sagittarii, Nature Communications 9, 2534 (doi:10.1038/s41467-018-04767-8)
  * Zamponi et al. [2021] Zamponi J., Maureira M.J., Zhao B., et al., 2021, The young protostellar disc in IRAS 16293-2422 B is hot and shows signatures of gravitational instability, MNRAS 508, 2583 (doi:10.1093/mnras/stab2657)
  * Zhang et al. [2023] Zhang X., Yu W., Law C., et al., 2023, Temporal and Spectral Properties of the Persistent Radio Source Associated with FRB 20190520B with the VLA, arXiv e-prints arXiv:2307.16355 (doi:10.48550/arXiv.2307.16355)
  * Zhao et al. [2019] Zhao G.Y., Jung T., Sohn B.W., et al., 2019, Source-Frequency Phase-Referencing Observation of AGNS with KAVA Using Simultaneous Dual-Frequency Receiving, Journal of Korean Astronomical Society 52, 23 (doi:10.5303/JKAS.2019.52.1.23)
  * Zhao et al. [2022] Zhao J.H., Morris M.R., Goss W.M., 2022, Detection of a Dense Group of Hypercompact Radio Sources in the Central Parsec of the Galaxy, ApJL 927, L6 (https://ui.adsabs.harvard.edu/abs/2022ApJ...927L...6Z)
  * Zolotov et al. [2015] Zolotov A., Dekel A., Mandelker N., et al., 2015, Compaction and quenching of high-z galaxies in cosmological simulations: blue and red nuggets, MNRAS 450, 2327 (doi:10.1093/mnras/stv740)


Equivariant geometry of odd-dimensional complete intersections of two
Pure Appl. Math. Q., 18(4):1555–1597, 2022.

[41]
B. Hassett and Yu. Tschinkel.
Torsors and stable equivariant birational geometry.
Nagoya Math. J., 250:275–297, 2023.

[42]
P. Jahnke, Th. Peternell, and I. Radloff.
Threefolds with big and nef anticanonical bundles. II.
Cent. Eur. J. Math., 9(3):449–488, 2011.

[43]
A. Kresch and Yu. Tschinkel.
Cohomology of finite subgroups of the plane Cremona group, 2022.

[44]
A. Kresch and Yu. Tschinkel.
Equivariant birational types and Burnside volume.
Ann. Sc. Norm. Super. Pisa Cl. Sci. (5), 23(2):1013–1052,

[45]
A. Kuribayashi and K. Komiya.
On Weierstrass points and automorphisms of curves of genus three.
In Algebraic geometry (Proc. Summer Meeting, Univ.
Copenhagen, Copenhagen, 1978), volume 732 of Lecture Notes in
Math., pages 253–299. Springer, Berlin, 1979.

[46]
A. Kuznetsov and Yu. Prokhorov.
Rationality over non-closed fields of fano threefolds with higher
geometric picard rank, 2021.

[47]
K. Lauter.
Geometric methods for improving the upper bounds on the number of
rational points on algebraic curves over finite fields. Appendice by J.
-P. Serre.
J. Algebr. Geom., 10(1):19–36, 2001.

[48]
Z. Reichstein and B. Youssin.
Essential dimensions of algebraic groups and a resolution theorem for
Canad. J. Math., 52(5):1018–1056, 2000.
With an appendix by János Kollár and Endre Szabó.

[49]
A. Sarikyan.
On linearization problems in the plane Cremona group, 2020.

[50]
N. I. Shepherd-Barron.
The Hasse principle for 9-nodal cubic threefolds, 2012.

[51]
Yu. Tschinkel, Kaiqi Yang, and Zhijia Zhang.
Equivariant birational geometry of linear actions, 2023.

[52]
N. Tziolas.
Terminal 3-fold divisorial contractions of a surface to a curve. I.
Compos. Math., 139(3):239–261, 2003.

[53]
S. Viktorova.
On the classification of singular cubic threefolds, 2023.

[54]
C. Voisin.
Unirational threefolds with no universal codimension \(2\) cycle.
Invent. Math., 201(1):207–237, 2015.

[55]
L. Wei and X. Yu.
Automorphism groups of smooth cubic threefolds.
J. Math. Soc. Japan, 72(4):1327–1343, 2020.