11institutetext: Leiden University

# Pattern-defeating Quicksort

Orson R. L. Peters
<EMAIL_ADDRESS>
###### Abstract

A new solution for the Dutch national flag problem is proposed, requiring no
three-way comparisons, which gives quicksort a proper worst-case runtime of
$O(nk)$ for inputs with $k$ distinct elements. This is used together with
other known and novel techniques to construct a hybrid sort that is never
significantly slower than regular quicksort while speeding up drastically for
many input distributions.

##  1 Introduction

Arguably the most used hybrid sorting algorithm at the time of writing is
introsort[12]. A combination of insertion sort, heapsort[19] and
quicksort[10], it is very fast and can be seen as a truly hybrid algorithm.
The algorithm performs introspection and decides when to change strategy using
some very simple heuristics. If the recursion depth becomes too deep, it
switches to heapsort, and if the partition size becomes too small it switches
to insertion sort.

The goal of pattern-defeating quicksort (or pdqsort) is to improve on
introsort’s heuristics to create a hybrid sorting algorithm with several
desirable properties. It maintains quicksort’s logarithmic memory usage and
fast real-world average case, effectively recognizes and combats worst case
behavior (deterministically), and runs in linear time for a few common
patterns. It also unavoidably inherits in-place quicksort’s instability, so
pdqsort can not be used in situations where stability is needed.

In Section 2 we will explore a quick overview of pattern-defeating quicksort
and related work, in Section 3 we propose our new solution for the Dutch
national flag problem and prove its $O(nk)$ worst-case time for inputs with
$k$ distinct elements, Section 4 describes other novel techniques used in
pdqsort while Section 5 describes various previously known ones. Our final
section consists of an empirical performance evaluation of pdqsort.

This paper comes with an open source state of the art C++ implementation[14].
The implementation is fully compatible with std::sort and is released under a
permissive license. Standard library writers are invited to evaluate and adopt
the implementation as their generic unstable sorting algorithm. At the time of
writing the Rust programming language has adopted pdqsort for sort_unstable in
their standard library thanks to a porting effort by Stjepan Glavina. The
implementation is also available in the C++ Boost.Sort library.

##  2 Overview and related work

Pattern-defeating quicksort is a hybrid sort consisting of quicksort[10],
insertion sort and a fallback sort. In this paper we use heapsort as our
fallback sort, but really any $O(n\log n)$ worst case sort can be used - it’s
exceptionally rare that the heuristics end up switching to the fallback. Each
recursive call of pdqsort chooses either to fall back, use insertion sort or
partition and recurse.

Insertion sort is used for small recursive calls as despite its $O(n^{2})$
worst case it has great constant factors and outperforms quicksort for small
$n$. We later discuss (not novel but nevertheless important) techniques to
properly implement insertion sort for usage in a hybrid algorithm. We have
tried to use small sorting networks akin to Codish’s[5] approach as an
alternative base case but were unable to beat insertion sort. We conjecture
that the small code size of insertion sort has sufficient positive cache
effects to offset the slower algorithm when used in a hybrid sort.

For partitioning we use a novel scheme that indirectly ends up performing
tripartite partitioning. This is used in conjunction with the very important
technique from BlockQuicksort[7] that greatly speeds up partitioning with
branchless comparison functions. In a sense our partitioning scheme is similar
to Yaroslavskiy’s dual-pivot quicksort[18] from the perspective of equal
elements. We did consider dual- and multi-pivot[2] variants of quicksort but
chose to stick to traditional partitioning for simplicity, applicability of
the techniques described here, and due to the massive speedup from
BlockQuicksort, which does not trivially extend to multiple pivots (see
IPS4o[3] for that).

We use the well-known median-of-3 pivot selection scheme, with John Tukey’s
ninther[17] for sufficiently large inputs, which Kurosawa[11] finds has a
near-identical number of comparisons to selecting the true median, but is
significantly simpler.

Finally, we beat patterns with two novel additions. We diverge from introsort
by no longer simply using the call depth to switch to a fallback. Instead we
define a concept of a bad partition, and track those instead. This results in
a more precise heuristic on bad sorting behavior, and consequently fallback
usage. Whenever we detect a bad partition we also swap a couple well-selected
elements, which not only breaks up common patterns and introduces ’noise’
similar to how a random quicksort would behave, it introduces new pivot
candidates in the selection pool. We also use a technique (not known to us in
previous literature) due to Howard Hinnant to optimistically handle
ascending/descending sequences with very little overhead.

##  3 A faster solution for the Dutch national flag problem

A naive quicksort implementation might trigger the $\Theta(n^{2})$ worst case
on the all-equal input distribution by placing equal comparing elements in the
same partition. A smarter implementation either always or never swaps equal
elements, resulting in average case performance as equal elements will be
distributed evenly across the partitions. However, an input with many equal
comparing elements is rather common111It is a common technique to define a
custom comparison function that only uses a subset of the available data to
sort on, e.g. sorting cars by their color. Then you have many elements that
aren’t fundamentally equal, but do compare equal in the context of a sorting
operation., and we can do better. Handling equal elements efficiently requires
tripartite partitioning, which is equivalent to Dijkstra’s Dutch national flag
problem[6].

Figure 1: The invariant used by Bentley-McIlroy. After partitioning the equal
elements stored at the beginning and at the end are swapped to the middle.

Figure 2: The invariant used by partition_right of pdqsort, shown at
respectively the initial, halfway and finished state. When the loop is done
the pivot gets swapped into its correct position. $p$ is the single pivot
element. $r$ is the pointer returned by the partition routine indicating the
pivot position. The dotted lines indicate how $i$ and $j$ change as the
algorithm progresses. This is a simplified representation, e.g. $i$ is
actually off by one.

Pattern-defeating quicksort uses the fast ’approaching pointers’ method[4] for
partitioning. Two indices are initialized, $i$ at the start and $j$ at the end
of the sequence. $i$ is incremented and $j$ is decremented while maintaining
an invariant, and when both invariants are invalidated the elements at the
pointers are swapped, restoring the invariant. The algorithm ends when the
pointers cross. Implementers must take great care, as this algorithm is
conceptually simple, but is very easy to get wrong.

Bentley and McIlroy describe an invariant for partitioning that swaps equal
elements to the edges of the partition, and swaps them back into the middle
after partitioning. This is efficient when there are many equal elements, but
has a significant drawback. Every element needs to be explicitly checked for
equality to the pivot before swapping, costing another comparison. This
happens regardless of whether there are many equal elements, costing
performance in the average case.

Unlike previous algorithms, pdqsort’s partitioning scheme is not self
contained. It uses two separate partition functions, one that groups elements
equal to the pivot in the left partition (partition_left), and one that groups
elements equal to the pivot in the right partition (partition_right). Note
that both partition functions can always be implemented using a single
comparison per element as $a<b\Leftrightarrow a\ngeq b$ and $a\nless
b\Leftrightarrow a\geq b$.

For brevity we will be using a simplified, incomplete C++ implementation to
illustrate pdqsort. It only supports int and compares using comparison
operators. It is however trivial to extend this to arbitrary types and custom
comparator functions. To pass subsequences222Without exception, in this paper
subsequences are assumed to be contiguous. around, the C++ convention is used
of one pointer at the start, and one pointer at one-past-the-end. For the
exact details refer to the full implementation[14].

Both partition functions assume the pivot is the first element, and that it
has been selected as a median of at least three elements in the subsequence.
This saves a bound check in the first iteration.

⬇

int* part_left(int* l, int* r) { int* part_right(int* l, int* r) {

int* i = l; int* j = r; int* i = l; int* j = r;

int p = *l; int p = *l;

while (*--j > p); while (*++i < p);

if (j + 1 == r) { if (i - 1 == l) {

while (i < j && *++i <= p); while (i < j && *--j >= p);

} else { } else {

while (*++i <= p); while (*--j >= p);

} }

// bool no_swaps = (i >= j);

while (i < j) { while (i < j) {

std::swap(*i, *j); std::swap(*i, *j);

while (*--j > p); while (*++i < p);

while (*++i <= p); while (*--j >= p);

} }

std::swap(*l, *j); std::swap(*l, *(i - 1));

return j; return i - 1;

} }

Figure 3: An efficient implementation of partition_left and partition_right
(named part_left and part_right here due to limited page width). Note the
(almost) lack of bound checks, we assume that p was selected as the median of
at least three elements, and in later iterations previous elements are used as
sentinels to prevent going out of bounds. Also note that a pre-partitioned
subsequence will perform no swaps and that it is possible to detect this with
a single comparison of pointers, no_swaps. This is used for a heuristic later.

Given a subsequence $\alpha$ let us partition it using partition_right using
pivot $p$. We then inspect the right partition, calling its first element $q$
and the remaining subsequence of elements $\beta$:

If $p\neq q$ we have $q>p$, and apply partition_right on $q,\beta$. Rename
$q,\beta$ to be the left partition of this operation (marked as
$q^{\prime},\beta^{\prime}$ in the diagram to emphasize renaming). The right
partition is marked as ’$>$’, because in this process we have the perspective
of pivot $p$, but it’s definitely possible for elements equal to $q$ to be in
the partition marked ’$>$’.

We apply the above step recursively as long as $p\neq q$. If at some point
$q,\beta$ becomes empty, we can conclude there were no elements equal to $p$
and the tripartite partitioning was done when we initially partitioned
$\alpha$. Otherwise, consider $p=q$. We know that $\forall x\in\beta\colon
x\geq p$, thus $\nexists x\in\beta\colon x<q$. If we were to partition
$q,\beta$ using partition_left, any element smaller than or equal to $q$ would
be partitioned left. However, we just concluded that $\beta$ can not contain
elements smaller than $q$. Thus, $\beta$’s left partition only contains
elements equal to $q$ (and thus equal to $p$), and its right partition only
contains elements bigger than $q$:

∎

This leads to the partitioning algorithm used by pdqsort. The predecessor of a
subsequence is the element directly preceding it in the original sequence. A
subsequence that is leftmost has no predecessor. If a subsequence has a
predecessor $p$ that compares equal to the chosen pivot $q$, apply
partition_left, otherwise apply partition_right. No recursion on the left
partition of partition_left is needed, as it contains only equivalent
elements.

###  3.1 An $O(nk)$ worst case of pdqsort with $k$ distinct elements

###### Lemma 1

Any predecessor of a subsequence333Assuming only those subsequences that are
passed into recursive calls of pdqsort. was the pivot of an ancestor.

###### Proof

If the subsequence is a direct right child of its parent partition, its
predecessor is the pivot of the parent. However, if the subsequence is the
left child of its parent partition, its predecessor is the predecessor of its
parent. Since our lemma states that our subsequence has a predecessor, it is
not leftmost and there must exist some ancestor of which the subsequence is a
right child.

###### Lemma 2

The first time a distinct value $v$ is selected as a pivot, it can’t be equal
to its predecessor.

###### Proof

Assume $v$ is equal to its predecessor. By Lemma 1 this predecessor was the
pivot of an ancestor partition. This is a contradiction, thus $v$ is not equal
to its predecessor.

###### Corollary 1

The first time $v$ is selected as a pivot, it is always used to partition with
partition_right, and all elements $x$ such that $x=v$ end up in the right
partition.

###### Lemma 3

Until an element equal to $v$ is selected as a pivot again, for all $x$
comparing equal to $v$, $x$ must be in the partition directly to the right of
$v$.

###### Proof

By Corollary 1, $x$ can not be in a partition to the left of $v$ and thus any
other partitions with pivot $w<v$ are irrelevant. There also can’t be a
partition with pivot $w>v$ that puts any $x$ equal to $v$ in its right
partition, as this would imply $x\geq w>v$, a contradiction. So any elements
$x=v$ stay in a partition directly to the right of $v$.

###### Lemma 4

The second time a value equal to $v$ is selected as a pivot, all $x=v$ are in
the correct position and are not recursed upon any further.

###### Proof

The second time another element $x=v$ is selected as a pivot, Lemma 3 shows
that $v$ must be its predecessor, and thus it is used to partition with
partition_left. In this partitioning step all elements equal to $x$ (and thus
equal to $v$) end up in the left partition, and are not further recursed upon.
Lemma 3 also provides the conclusion we have just finished processing all
elements equal to $v$ passed to pdqsort.

###### Theorem 3.1

pdqsort has complexity $O(nk)$ when the input distribution has $k$ distinct
values.444Note that this is an upper bound. When $k$ is big $O(n\log n)$ still
applies.

###### Proof

Lemma 4 proves that every distinct value can be selected as a pivot at most
twice, after which every element equal to that value is sorted correctly. Each
partition operation has complexity $O(n)$. The worst-case runtime is thus
$O(nk)$.

∎

##  4 Other novel techniques

###  4.1 Preventing quicksort’s $O(n^{2})$ worst case

Pattern-defeating quicksort calls any partition operation which is more
unbalanced than $p$ (where $p$ is the percentile of the pivot, e.g.
$\frac{1}{2}$ for a perfect partition) a bad partition. Initially, it sets a
counter to $\log n$. Every time it encounters a bad partition, it decrements
the counter before recursing555This counter is maintained separately in every
subtree of the call graph - it is not a global to the sort process. Thus, if
after the first partition the left partition degenerates in the worst case it
does not imply the right partition also does.. If at the start of a recursive
call the counter is 0 it uses heapsort to sort this subsequence, rather than
quicksort.

###### Lemma 5

At most $O(n\log n)$ time is spent in pdqsort on bad partitions.

###### Proof

Due to the counter ticking down, after $\log n$ levels that contain a bad
partition the call tree terminates in heapsort. At each level we may do at
most $O(n)$ work, giving a runtime of $O(n\log n)$.

###### Lemma 6

At most $O(n\log n)$ time is spent in pdqsort on good partitions.

###### Proof

Consider a scenario where quicksort’s partition operation always puts $pn$
elements in the left partition, and $(1-p)n$ in the right. This consistently
forms the worst possible good partition. Its runtime can be described with the
following recurrence relation:

$T(n,p)=n+T(pn,p)+T((1-p)n,p)$

For any $p\in(0,1)$ the Akra-Bazzi[1] theorem shows
$\Theta(T(n,p))=\Theta(n\log n)$.

###### Theorem 4.1

Pattern-defeating quicksort has complexity $O(n\log n)$.

###### Proof

Pattern-defeating quicksort spends $O(n\log n)$ time on good partitions, bad
partitions, and degenerate cases (due to heapsort also being $O(n\log n)$).
These three cases exhaustively enumerate any recursive call to pdqsort, thus
pattern-defeating quicksort has complexity $O(n\log n)$.

∎

We have proven that for any choice of $p\in(0,1)$ the complexity of pattern-
defeating quicksort is $O(n\log n)$. However, this does not tell use what a
good choice for $p$ is.

Yuval Filmus[8] solves above recurrence, allowing us to study the slowdown of
quicksort compared to the optimal case of $p=\frac{1}{2}$. He finds that the
solution is

$\lim_{n\to\infty}\frac{T(n,p)}{T(n,\frac{1}{2})}=\frac{1}{H(p)}$

where $H$ is Shannon’s binary entropy function:

$H(p)=-p\log_{2}(p)-(1-p)\log_{2}(1-p)$

Plotting this function gives us a look at quicksort’s fundamental performance
characteristics:

$0$$0.05$$0.1$$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$0.45$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$4.5$$5$$p$factor
Figure 4: Slowdown of $T(n,p)$ compared to $T(n,\frac{1}{2})$. This
beautifully shows why quicksort is generally so fast. Even if every partition
is split 80/20, we’re still running only 40% slower than the ideal case.

From benchmarks we’ve found that heapsort is roughly about twice as slow as
quicksort for sorting randomly shuffled data. If we then choose $p$ such that
$H(p)^{-1}=2$ a bad partition becomes roughly synonymous with ‘worse than
heapsort’.

The advantage of this scheme is that $p$ can be tweaked if the architecture
changes, or you have a different worst-case sorting algorithm instead of
heapsort.

We have chosen $p=0.125$ as the cutoff value for bad partitions for two
reasons: it’s reasonably close to being twice as slow as the average sorting
operation and it can be computed using a simple bitshift on any platform.

Using this scheme as opposed to introsort’s static logarithmic recursive call
limit for preventing the worst case is more precise. While testing we noticed
that introsort (and to a lesser extent pdqsort) often have a rough start while
sorting an input with a bad pattern, but after some partitions the pattern is
broken up. Our scheme then procedes to use the now fast quicksort for the rest
of the sorting whereas introsort too heavily weighs the bad start and
degenerates to heapsort.

###  4.2 Introducing fresh pivot candidates on bad partitions

Some input patterns form some self-similar structure after partitioning. This
can cause a similar pivot to be repeatedly chosen. We want to eliminate this.
The reason for this can be found in Figure 4 as well. The difference between a
good and mediocre pivot is small, so repeatedly choosing a good pivot has a
relatively small payoff. The difference between a mediocre and bad pivot is
massive. An extreme example is the traditional $O(n^{2})$ worst case:
repeatedly partitioning without real progress.

The classical way to deal with this is by randomizing pivot selection (also
known as randomized quicksort). However, this has multiple disadvantages.
Sorting is not deterministic, the access patterns are unpredictable and extra
runtime is required to generate random numbers. We also destroy beneficial
patterns, e.g. the technique in section 5.2 would no longer work for
descending patterns and performance on ’mostly sorted’ input patterns would
also degrade.

Pattern-defeating quicksort takes a different approach. After partitioning we
check if the partition was bad. If it was, we swap our pivot candidates for
others. In our implementation pdqsort chooses the median of the first, middle
and last element in a subsequence as the pivot, and swaps the first and last
candidate for ones found at the 25% and 75% percentile after encountering a
bad partition. When our partition is big enough that we would be using Tukey’s
ninther for pivot selection we also swap the ninther candidates for ones at
roughly the 25% and 75% percentile of the partition.

With this scheme pattern-defeating quicksort is still fully deterministic, and
with minimal overhead breaks up many of the patterns that regular quicksort
struggles with. If the downsides of non-determinism do not scare you and you
like the guarantees that randomized quicksort provides (e.g. protection
against DoS attacks) you can also swap out the pivot candidates with random
candidates. It’s still a good idea to only do this after a bad partition to
prevent breaking up beneficial patterns.

##  5 Previously known techniques

###  5.1 Insertion sort

Essentially all optimized quicksort implementations switch to a different
algorithm when recursing on a small ($\leq 16$–$32$ elements) subsequence,
most often insertion sort. But even the simple insertion sort is subject to
optimization, as a significant amount of time is spent in this phase.

It’s important to use a series of moves instead of swaps, as this eliminates a
lot of unnecessary shuffling. Another big6665-15% from our benchmarks, for
sorting small integers. improvement can be made by eliminating bounds checking
in the inner insertion sort loop. This can be done for any subsequence that is
not leftmost, as there must exist some element before the subsequence you’re
sorting that acts as a sentinel breaking the loop. Although this change is
tiny, for optimal performance this requires an entirely new function as
switching behavior based on a condition defeats the purpose of this micro-
optimization. This variant is traditionally[13] called
unguarded_insertion_sort. This is a prime example where introducing more
element comparisons can still result in faster code.

###  5.2 Optimistic insertion sorting on a swapless partition

This technique is not novel, and is due to Howard Hinnants[9] std::sort
implementation, but has to our knowledge not been described in literature
before. After partitioning we can check whether the partition was swapless.
This means we didn’t have to swap any element (other than putting the pivot in
its proper place). Checking for this condition can be done with a single
comparison as shown in Figure 3 with the variable no_swaps.

If this is the case and the partition wasn’t bad we do a partial insertion
sort over both partitions that aborts if it has to do more than a tiny number
of corrections (to minimize overhead in the case of a misdiagnosed best case).
However, if little to no corrections were necessary, we are instantly done and
do not have to recurse.

If you properly choose your pivots777Frankly, this can be a bit fragile. Check
the pdqsort source code for the exact procedure used to select pivots, and you
notice we actually sort the pivot candidates and put the median one at the
start position, which gets swapped back to the middle in the event of a
swapless partition. A small deviation from the reference implementation here
might lose you the linear time guarantee. then this small optimistic heuristic
will sort inputs that are ascending, descending or ascending with an arbitrary
element appended all in linear time. We argue that these input distributions
are vastly overrepresented in the domain of inputs to sorting functions, and
are well worth the miniscule overhead caused by false positives.

This overhead really is miniscule, as swapless partitions become exceedingly
unlikely for large arrays to happen by chance. A hostile attacker crafting
worst-case inputs is also no better off. The maximum overhead per partition is
$\approx n$ operations, so it doubles performance at worst, but this can
already be done to pdqsort by crafting a worst case that degenerates to
heapsort. Additionally, the partial insertion sort is only triggered when the
partition wasn’t bad, forcing an attacker to generate good quicksort progress
if she intends to trigger repeated misdiagnosed partial insertion sorts.

###  5.3 Block partitioning

One of the most important optimizations for a modern quicksort is Edelkamp and
Weiß’ recent work on BlockQuicksort[7]. Their technique gives a huge88850-80%
from our benchmarks, for sorting small integers. speedup by eliminating branch
predictions during partitioning. In pdqsort it is only applied for
partition_right, as the code size is significant and partition_left is rarely
called.

Branch predictions are eliminated by replacing them with data-dependent moves.
First some static block size is determined999In our implementation we settled
on a static 64 elements, but the optimal number depends on your CPU and cache
architecture as well as the data you’re sorting.. Then, until there are fewer
than 2*bsize elements remaining, we repeat the following process.

We look at the first bsize elements on the left hand side. If an element in
this block is bigger or equal to the pivot, it belongs on the right hand side.
If not, it should keep its current position. For each element that needs to be
moved we store its offset in offsets_l. We do the same for offsets_r, but now
for the last bsize elements, and finding elements that are strictly less than
the pivot:

⬇

int num_l = 0; int num_r = 0;

for (int i = 0; i < bsize; ++i) { for (int i = 0; i < bsize; ++i) {

if (*(l + i) >= pivot) { if (*(r - 1 - i) < pivot) {

offsets_l[num_l] = i; offsets_r[num_r] = i + 1;

num_l++; num_r++;

} }

} }

But this still contains branches. So instead we do the following:

⬇

int num_l = 0; int num_r = 0;

for (int i = 0; i < bsize; ++i) { for (int i = 0; i < bsize; ++i) {

offsets_l[num_l] = i; offsets_r[num_r] = i + 1;

num_l += *(l + i) >= pivot; num_r += *(r - 1 - i) < pivot;

} }

This contains no branches. Now we can unconditionally swap elements from the
offset buffers:

⬇

for (int i = 0; i < std::min(num_l, num_r); ++i) {

std::iter_swap(l + offsets_l[i], r - offsets_r[i]);

}

Notice that we only swap std::min(num_l, num_r) elements, because we need to
pair each element that belongs on the left with an element that belongs on the
right. Any leftover elements are re-used in the next iteration101010After each
iteration at least one offsets buffer is empty. We fill any buffer that is
empty., however it takes a bit of extra code to do so. It is also possible to
re-use the last remaining buffer for the final elements to prevent any wasted
comparisons, again at the cost of a bit of extra code. For the full
implementation111111We skip over many important details and optimizations here
as they are more relevant to BlockQuicksort than to pattern-defeating
quicksort. The full implementation has loop unrolling, swaps elements using
only two moves per element rather than three and uses all comparison
information gained while filling blocks. and more explanation we invite the
reader to check the Github repository, and read Edelkamp and Weiß’ original
paper.

The concept is important here: replacing branches with data-dependent moves
followed by unconditional swaps. This eliminates virtually all branches in the
sorting code, as long as the comparison function used is branchless. This
means in practice that the speedup is limited to integers, floats, small
tuples of those or similar. However, it’s still a comparison sort. You can
give it arbitrarily complicated branchless comparison functions (e.g. a*c >
b-c) and it will work.

When the comparison function isn’t branchless this method of partitioning can
be slower. The C++ implementation is conservative, and by default only uses
block based partitioning if the comparison function is std::less or similar,
and the elements being sorted are native numeric types. If a user wishes to
get block based partitioning otherwise it needs to be specifically requested.

##  6 Experimental results

###  6.1 Methodology

We present a performance evaluation of pattern-defeating quicksort with (bpdq)
and without (pdq) block partitioning, introsort from libstdc++’s
implementation of std::sort (std), Timothy van Slyke’s C++ Timsort[15]
implementation[16] (tim), BlockQuicksort (bq) and the sequential version of
In-Place Super Scalar Samplesort[3] (is4o). The latter algorithm represents to
our knowledge the state of the art in sequential in-place comparison sorting
for large amounts of data.

In particular the comparison with BlockQuicksort is important as it is a
benchmark for the novel methods introduced here. The code repository for
BlockQuicksort defines many different versions of BlockQuicksort, one of which
also uses Hoare-style crossing pointers partitioning and Tukey’s ninther pivot
selection. This version is chosen for the closest comparison as it most
resembles our algorithm. The authors of BlockQuicksort also proposed their own
duplicate handling scheme. To compare the efficacy of their and our approach
we also chose the version of BlockQuicksort with it enabled.

We evaluate the algorithms for three different data types. The simplest is
int, which is a simple 64-bit integer. However, not all data types have a
branchless comparison function. For that reason we also have str, which is a
std::string representation of int (padded with zeroes such that lexicographic
order matches the numeric order). Finally to simulate an input with an
expensive comparison function we evaluate bigstr which is similar to str but
is prepended with $1000$ zeroes to artificially inflate compare time. An
algorithm that is more efficient with the number of comparisons it performs
should gain an edge there.

The algorithms are evaluated on a variety of input distributions. Shuffled
uniformly distributed values (uniform: $A[i]=i$), shuffled distributions with
many duplicates (dupsq: $A[i]=i\bmod\lfloor\sqrt{n}\rfloor$, dup8:
$A[i]=i^{8}+n/2\bmod n$, mod8: $A[i]=i\bmod 8$, and ones: $A[i]=1$), partially
shuffled uniform distributions (sort50, sort90, sort99 which respectively have
the first 50%, 90% and 99% of the elements already in ascending order) and
some traditionally notoriously bad cases for median-of-3 pivot selection
(organ: first half of the input ascending and the second half descending,
merge: two equally sized ascending arrays concatenated). Finally we also have
the inputs asc, desc which are inputs that are already sorted.

The evaluation was performed on an AMD Ryzen Threadripper 2950x clocked at
4.2GHz with 32GB of RAM. All code was compiled with GCC 8.2.0 with flags
-march=native -m64 -O2. To preserve the integrity of the experiment no two
instances were tested simultaneously and no other resource intensive processes
were run at the same time. For all random shuffling a seed was
deterministically chosen for each size and input distribution, so all
algorithms received the exact same input for the same experiment. Each
benchmark was re-run until at least 10 seconds had passed and for at least 10
iterations. The former condition reduces timing noise by repeating small
instances many times whereas the latter condition reduces the influence of a
particular random shuffle. The mean number of cycles spent is reported,
divided by $n\log_{2}n$ to normalize across sizes. In total the evaluation
program spent 9 hours sorting (with more time spent to prepare input
distributions).

As the full results are quite large ($12\text{ distributions}\times 3\text{
data types}=36$ plots), they are included in Appendix A.

###  6.2 Results and observations

First we’d like to note that across all benchmarks pdq and bpdq are never
significantly slower than their non-pattern defeating counterparts std and bq.
In fact, the only regression at all is $\approx 4.5\%$ for pdq v.s. std for
large instances of uniform-int (while being faster for smaller sizes and bpdq
being roughly twice as fast).

There is one exception, with bq beating bpdq for the organ and merge
distributions (and very slightly for sort99) with the bigstr data type. It is
unclear why exactly this happens here. Especially curious is that the former
two distributions were very clearly bad cases for bq with the int data type
when we compare the performance against uniform. But in bigstr the roles have
been reversed, bq is significantly faster on organ and merge than it is on
uniform. So it’s not that bpdq is slow here, bq is just mysteriously fast.
Regardless, we see that both pdq and bpdq maintain good performance (similar
to uniform) on these cases, effectively defeating the pattern.

With these observations it’s safe to say that the heuristics used in pattern-
defeating quicksort come with minimal to no overhead.

Interesting to note is the behavior regarding cache. On this system with
sizeof(std::string) being $32$ we see a drastic change of slope for all
quicksort based algorithms in the str benchmark around $n=2^{16}$, which is
right when the $1.5$MB L1 cache has filled up. It’s odd to see that this shift
in slope never happens for int, even when the input size well exceeds any CPU
cache. For bigstr the change of slope occurs slightly earlier, at around
$n=2^{12}$. Timsort is seemingly barely affected by this, but the clear winner
in this regard is is4o, which appears to be basically cache-oblivious.

We already knew this, but block partitioning isn’t always beneficial. However
even for types where the comparison can be done without branches, it still
isn’t always faster. In cases where the branch predictor would get it right
nearly every time because the data has such a strong pattern (e.g. for pdq in
merge-int), the traditional partitioning can still be significantly faster.

It should come at no surprise that for every input with long ascending or
descending runs Timsort is in the lead. Timsort is based on mergesort, so it
can fully exploit any runs in the data. We note that while pdqsort defeats the
patterns, meaning it doesn’t heavily slow down on unfavorable patterns, it
can’t exploit these runs either.

In previous benchmarks however Timsort’s constant factor was very high, making
it significantly slower for anything that does not have a pattern to exploit.
Looking at the results now, we congratulate Timothy van Slyke on his
performant implementation, which is significantly more competitive. Especially
for bigger or harder to compare types Timsort is now an excellent choice.

Our scheme for handling equal elements is very effective. Especially when the
number of equivalence classes approaches $1$ (such as in mod8 and ones) the
runtime goes down drastically, but even in milder cases such as dupsq we see
that the pattern-defeating sorts build a sizable lead over their counterparts
when compared to their performance in uniform.

Finally we note that due to the optimistic insertion sort on swapless
partitions pdqsort achieves an incredible speedup for the the ascending and
descending input case, rivalling Timsort.

##  7 Conclusion and further research

We conclude that the heuristics and techniques presented in this paper have
little overhead, and effectively handle various input patterns. Pattern-
defeating quicksort is often the best choice of algorithm overall for small to
medium input sizes or data type sizes. It and other quicksort variants suffer
from datasets that are too large to fit in cache, where is4o shines. The
latter algorithm however suffers from bad performance on smaller sizes, future
research could perhaps combine the best of these two algorithms.

## References

  * [1] Akra, M., Bazzi, L.: On the solution of linear recurrence equations. Computational Optimization and Applications 10(2), 195–210 (1998)
  * [2] Aumüller, M., Dietzfelbinger, M., Klaue, P.: How good is multi-pivot quicksort? ACM Trans. Algorithms 13(1), 8:1–8:47 (Oct 2016). https://doi.org/10.1145/2963102
  * [3] Axtmann, M., Witt, S., Ferizovic, D., Sanders, P.: In-place parallel super scalar samplesort (ipsssso). CoRR abs/1705.02257 (2017), http://arxiv.org/abs/1705.02257
  * [4] Bentley, J.L., McIlroy, M.D.: Engineering a sort function. Software: Practice and Experience 23(11), 1249–1265 (1993)
  * [5] Codish, M., Cruz-Filipe, L., Nebel, M., Schneider-Kamp, P.: Optimizing sorting algorithms by using sorting networks. Formal Aspects of Computing 29(3), 559–579 (May 2017). https://doi.org/10.1007/s00165-016-0401-3
  * [6] Dijkstra, E.W.: A Discipline of Programming. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1st edn. (1997)
  * [7] Edelkamp, S., Weiß, A.: BlockQuicksort: How branch mispredictions don’t affect quicksort. CoRR abs/1604.06697 (2016)
  * [8] Filmus, Y.: Solving recurrence relation with two recursive calls. Computer Science Stack Exchange, https://cs.stackexchange.com/q/31930
  * [9] Hinnant, H., et al.: libc++ C++ standard library. http://libcxx.llvm.org/ (2018), [Online; accessed 2018]
  * [10] Hoare, C.A.: Quicksort. The Computer Journal 5(1), 10–16 (1962)
  * [11] Kurosawa, N.: Quicksort with median of medians is considered practical. CoRR abs/1608.04852 (2016)
  * [12] Musser, D.: Introspective sorting and selection algorithms. Software Practice and Experience 27, 983–993 (1997)
  * [13] Musser, D.R., Stepanov, A.A.: Algorithm-oriented generic libraries. Software: Practice and Experience 24(7), 623–642 (1994)
  * [14] Peters, O.R.L.: Pattern-defeating Quicksort Implementation. https://github.com/orlp/pdqsort (2018), [Online; accessed 2018]
  * [15] Peters, T.: Timsort. http://svn.python.org/projects/python/trunk/Objects/listsort.txt (2002), [Online; accessed 2019]
  * [16] van Slyke, T.: Timsort implementation. https://github.com/tvanslyke/timsort-cpp (2018), [Online; accessed 2019]
  * [17] Tukey, J.W.: The ninther, a technique for low-effort robust (resistant) location in large samples. In: Contributions to Survey Sampling and Applied Statistics, pp. 251–257. Elsevier (1978)
  * [18] Wild, S., Nebel, M.E.: Average case analysis of java 7’s dual pivot quicksort. In: Epstein, L., Ferragina, P. (eds.) Algorithms – ESA 2012. pp. 825–836. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)
  * [19] Williams, J.W.J.: Algorithm 232: Heapsort. Communications of the ACM 7(6), 347–348 (1964)

##  Appendix 0.A Full experimental evaluation

All experiments ran are included here, for all three data types. All plots for
the same data type share the same axes, and the plots for each data type are
split into two figures, one per page.

Figure 5: Int benchmark. Figure 6: Int benchmark, continued. Figure 7: str
benchmark. Figure 8: str benchmark, continued. Figure 9: bigstr benchmark.
Figure 10: bigstr benchmark, continued.


# Continuous and discrete universality of zeta-functions: Two sides of the
same coin?

Athanasios Sourmelidis  Athanasios Sourmelidis
Institut für Analysis und Zahlentheorie
TU Graz
Steyrergasse 30
8010 Graz
Austria<EMAIL_ADDRESS>
###### Abstract.

In 1975 Voronin proved the universality theorem for the Riemann zeta-function
$\zeta(s)$ which roughly says that any admissible function $f(s)$ is
approximated by $\zeta(s)$. A few years later Reich proved a discrete analogue
of this result. The proofs of these theorems are almost identical but it is
not known whether one of them implies the other. We will see that if we
translate the question in the language of linear dynamics then there is a link
which we exploit to obtain in a straightforward way a big variety of discrete
universality results appearing in the literature.

###### Key words and phrases:

Riemann zeta-function, Hurwitz zeta-function, universality, linear dynamics,
strong recurrence

###### 2020 Mathematics Subject Classification:

Primary 11M06, 11M35; Secondary 47Axx, 37B20

The author is supported by FWF project M 3246-N

##  1\. Introduction and Main results

###  1.1. Introduction

The Riemann zeta-function $\zeta(s)$ is defined for every complex number
$s:=\sigma+it$ with $\sigma>1$ by the following two expressions

$\zeta(s):=\sum_{n\geq 1}\frac{1}{n^{s}}=\prod_{p}\left\lparen
1-\frac{1}{p^{s}}\right\rparen^{-1}.$

In his pathbreaking memoir [21], Riemann showed that $\zeta(s)$ has a
meromorphic continuation to the whole complex plane $\mathbb{C}$ with a simple
pole at $s=1$ and that it satisfies a certain functional equation connecting
$\zeta(s)$ with $\zeta(1-s)$. This in turn implies that the only real zeros of
$\zeta(s)$, the so called trivial zeros, are the negative even integers and
Riemann conjectured that all complex zeros of $\zeta(s)$, the so called non-
trivial zeros, lie on the vertical line $1/2+i\mathbb{R}$ (Riemann
hypothesis).

In 1975 Voronin [26] proved the following:

If $0<r<1/4$ and $f:\\{s\in\mathbb{C}:|s|\leq r\\}\to\mathbb{C}$ is a non-
vanishing continuous function which is analytic in the interior of the disk,
then for every $\varepsilon>0$ there is $\tau>0$ such that

(1.1) $\displaystyle\max_{|s|\leq r}|\zeta(s+3/4+i\tau)-f(s)|<\varepsilon.$

In the proof it is already implicit that the set of those $\tau>0$ satisfying
(1.1) has positive lower density in the non-negative real numbers
$\mathbb{R}_{+}$. Recall that a set $A\subseteq\mathbb{R}_{+}$ has positive
lower density if

$\liminf_{T\to\infty}\frac{1}{T}\mathrm{meas}(A\cap[0,T])>0,$

where $\mathrm{meas}(A)$ denotes the Lebesgue measure of the set $A$.

Since $\zeta(s)$ approximates a large family of analytic functions, the above
result has been known ever since as the (continuous) universality theorem for
$\zeta(s)$. Voronin’s theorem has been refined and generalized within the
decades for other zeta- and $L$-functions. There is an exhaustive literature
of results indicating that the universality property is rather the norm than
the exception when one deals with a Dirichlet series satisfying some natural
(for applications to number theory) conditions. We refer to [19, 11, 16, 24]
for a survey of such results.

In 1979/1981 Gonek [7] and (independently) Bagchi [1, 2] generalized Voronin’s
theorem in several directions. For instance, they improved his theorem by
replacing the disc centered at $3/4$ and having radius $0<r<1/4$, by any
compact set $K$ of the strip $\mathcal{D}:=\\{s\in\mathbb{C}:1/2<\sigma<1\\}$
that has connected complement.

######  Remark.

We take the chance here to introduce some notation in order to simplify the
upcoming exposition. A tuple $(K,f,\varepsilon)$ will be called admissible if
$K\subseteq\mathcal{D}$ is compact with connected complement,
$f:K\to\mathbb{C}$ is continuous in $K$ and analytic in its interior and
$\varepsilon>0$. A tuple $(K,f,\varepsilon)^{*}$ will also be called
admissible if the previous assumptions hold in addition to $f$ being non-
vanishing in $K$.

Gonek considered another generalization of $\zeta(s)$, namely the Hurwitz
zeta-function, which is defined by

$\zeta(s;\alpha):=\sum_{n\geq
0}\frac{1}{(n+\alpha)^{s}},\quad\sigma>1,\quad\alpha\in(0,1].$

Like $\zeta(s)$, the Hurwitz zeta-function has a meromorphic continuation to
$\mathbb{C}$ with a simple pole at $s=1$. Gonek showed that if the parameter
$\alpha$ is a fixed transcendental or rational number $\neq 1/2,1$ then the
following holds:

If $(K,f,\varepsilon)$ is admissible, then

(1.2)
$\displaystyle\liminf_{T\to\infty}\frac{1}{T}\mathrm{meas}\left\\{\tau\in[0,T]:\max_{s\in
K}|\zeta(s+i\tau;\alpha)-f(s)|<\varepsilon\right\\}>0.$

Observe that in this case the target function $f$ is allowed to have zeros in
$K$ and this is why we talk about (continuous) strong universality.

We will see later on that this property of the Hurwitz zeta-function is
equivalent to saying that the set $\\{\zeta(\cdot+i\tau;\alpha):\tau\geq 0\\}$
is dense in the space of analytic functions $f:\mathcal{D}\to\mathbb{C}$,
$H(\mathcal{D})$, equipped with the topology of uniform convergence on compact
sets. In particular, this set intersects any open subset of $H(\mathcal{D})$
frequently often as the positive lower density statement implies (we will give
a precise formulation of what this means in the following section). In this
context and in view of Voronin’s theorem, we also have that
$\\{\zeta(\cdot+i\tau):\tau\geq 0\\}$ intersects frequently often any open
subset of the subspace $H^{*}(\mathcal{D}):=\\{f\in H(\mathcal{D}):f\text{ is
non-vanishing}\\}$ which is endowed with the induced topology.

At the same time with Gonek and Bagchi, Reich [20] showed the discrete
analogue of Voronin’s theorem:

Let $h>0$. If $(K,f,\varepsilon)^{*}$ is admissible, then

(1.3) $\displaystyle\liminf_{N\to\infty}\frac{1}{N}\\#\left\\{n\leq
N:\max_{s\in K}|\zeta(s+ihn)-f(s)|<\varepsilon\right\\}>0,$

where $\\#A$ denotes the cardinality of the set $A\subset\mathbb{N}$.

In other words, the set $\\{\zeta(\cdot+ihn):n\geq 1\\}$ intersects frequently
often any open subset of $H^{*}(\mathcal{D})$. In this case we talk about
$h$-discrete universality while for the Hurwitz zeta-function one has
$h$-discrete strong universality (see for example [12]).

###  1.2. Main results

The proofs of continuous and $h$-discrete (strong) universality coincide up to
some point and then it seems that the two methods, though similar, are not
directly connected. As a matter of fact, in most cases (including the one of
the Hurwitz zeta-function) the $h$-discrete universality is obtained for all
$h>0$ except for a set of zero Lebesgue measure. As a consequence there are
many results which treat these phenomena separately. Particularly, if the
universality property for a zeta- or an $L$-function is established, then
shortly after its discrete analogue appears in the literature as well. So it
is natural to ask if there is a connection between these concepts and whether
one of them implies the other. We will see that if we translate this question
in the language of linear dynamics, then there is an affirmative answer which
we can employ to prove the following theorems.

######  Theorem 1.1.

Let $h>0$. The continuous strong universality of the Hurwitz zeta-function
implies its $h$-discrete strong universality. Conversely, the $h$-discrete
strong universality implies (1.2) with $\limsup$ in place of $\liminf$.

######  Theorem 1.2.

Let $h>0$. Assuming the Riemann hypothesis, the continuous universality of the
Riemann zeta-function is equivalent to its $h$-discrete universality.

It will be seen that in the case of strong universality the theorem is in fact
a consequence of the Conejero-Müller-Peris theorem and a classic result on
strong recurrence due to Gottschalk and Hedlund. The theorem for the Riemann
zeta-function will follow by the Conejero-Müller-Peris theorem and an
equivalent formulation of the Riemann hypothesis with the strong recurrence
property of $\zeta(s)$ due to Bagchi. In the end we present some heuristics on
why the Conejero-Müller-Peris theorem is not applicable if we assume the
existence of hypothetical non-trivial zeros of $\zeta(s)$ off the vertical
line $1/2+i\mathbb{R}$. Nevertheless, we will employ an older of result due to
Oxtoby and Ulam to obtain a much weaker result for $\zeta(s)$ unconditionally.

######  Theorem 1.3.

The continuous universality of the Riemann zeta-function implies the existence
of a dense $G_{\delta}$-set $J\subseteq\mathbb{R}_{+}$ such that if $t_{0}\in
J$, then for any admissible tuple $(K,f,\varepsilon)^{*}$, there is a sequence
$(n_{k})_{k\geq 1}\subseteq\mathbb{N}$ such that

$\max_{s\in K}|\zeta(s+it_{0}n_{k})-f(s)|<\varepsilon,\quad k\geq 1.$

The proofs of the theorems are based on properties of dynamical systems.
Hence, we prove them for the simplest cases of $\zeta(s)$ and
$\zeta(s;\alpha)$ with the purpose of exhibiting the method. The main point of
the present work is to show that any form of continuous universality for zeta-
functions implies in one way or the other its discrete analogue.

###  1.3. Structure and notations

In Section 2 we present the necessary material from the theory of linear
dynamics that will be repeatedly employed in the sequel. In Section 3 we show
how the questions we want to address on zeta-functions can be translated in
the language of linear dynamics and provide the proofs of the main results. In
the last two sections we state shortly further generalizations of the method
introduced in earlier sections.

##  2\. Linear dynamics and strong recurrence

The interested reader can turn to [5, 9] for a contemporary treatment of the
theory of linear dynamics.

In the sequel $X$ will denote a topological vector space over $\mathbb{C}$. A
continuous linear map $T:X\to X$ is called an operator and a vector $x\in X$
is called a hypercyclic vector of $T$ if its orbit

$\mathrm{orb}(x,T):=\left\\{T^{n}x:n\geq 0\right\\},$

is dense in $X$; here and in the sequel we use the usual convention from
operator theory $Tx:=T(x)$ and

$T^{n}x:=\underbrace{T\circ\dots\circ T}_{n\text{ times}}x.$

The set of hypercyclic vectors is denoted by $\mathrm{HC}(T)$. Hence, a vector
$x$ is hypercyclic if for every open set $U\subseteq X$, there is
$n\in\mathbb{N}$ such that $T^{n}x\in U$. If additionally we can show that

$\liminf_{N\to\infty}\frac{1}{N}\\#\left\\{n\leq N:T^{n}x\in U\right\\}>0$

for every open set $U\subseteq X$, then $x$ is called a frequently hypercyclic
vector of $T$ and the set of frequently hypercyclic vectors will be denoted by
$\mathrm{FHC}(T)\subseteq\mathrm{HC}(T)$.

In the continuous case, a one-parameter family $\mathcal{T}=(T_{t})_{\tau\geq
0}$ of operators defined on $X$ is called a strongly continuous semigroup (or
$C_{0}$-semigroup) if $T_{0}=I$, $T_{t}T_{s}=T_{t+s}$ for all $t,s\geq 0$, and
$\lim_{t\to s}T_{t}x=T_{s}x$ for all $s\geq 0$, $x\in X$. In this setting, a
vector $x\in X$ is called a hypercyclic vector of $\mathcal{T}$ if
$\mathrm{orb}(\mathcal{T},x):=\left\\{T_{t}x:t\geq 0\right\\}$ is dense in $X$
and a frequently hypercyclic vector of $\mathcal{T}$ if

$\liminf_{T\to\infty}\frac{1}{T}\mathrm{meas}\left\\{t\in[0,T]:T_{t}x\in
U\right\\}>0$

for every open set $U\subseteq X$. Completely analogously as in the discrete
case, the set of hypercyclic, respect. frequently hypercyclic, vectors of the
family $\mathcal{T}$ is denoted by $\mathrm{HC}(\mathcal{T})$, respect.
$\mathrm{FHC}(\mathcal{T})\subseteq\mathrm{HC}(\mathcal{T})$.

From the above definitions, it follows that
$\mathrm{HC}(T_{t})\subseteq\mathrm{HC}(\mathcal{T})$ for every $t>0$ because
$T_{t}^{n}=T_{nt}$. Whether the converse implication
$\mathrm{HC}(\mathcal{T})\subseteq\mathrm{HC}(T_{t})$ is true for some $t>0$,
has been first answered partially by Oxtoby and Ulam [18]. We also refer to
[9, Theorem 7.22] for a proof.

######  Theorem (Oxtoby-Ulam).

If $\mathcal{T}=(T_{t})_{t\geq 0}$ is a $C_{0}$-semigroup on a separable space
$X$ and $x\in\mathrm{HC}(\mathcal{T})$, then there is a dense $G_{\delta}$-set
$J\subseteq(0,+\infty)$ such $x\in\mathrm{HC}(T_{t})$ for any $t\in J$.

Whether one has $\mathrm{HC}(\mathcal{T})\subseteq\mathrm{HC}(T_{t})$ for
every $t>0$, it has been answered recently by Conejero, Müller and Peris [6].

######  Theorem (Conejero-Müller-Peris).

If $\mathcal{T}=(T_{t})_{t\geq 0}$ is a $C_{0}$-semigroup of operators that is
locally equicontinuous, then
$\mathrm{HC}(\mathcal{T})\subseteq\mathrm{HC}(T_{h})$ and
$\mathrm{FHC}(\mathcal{T})\subseteq\mathrm{FHC}(T_{h})$ for any $h>0$.

We close the section with the notion of strong recurrence. A vector $x\in X$
will be called strongly recurrent for the operator $T$, respectively for the
$C_{0}$-semigroup $\mathcal{T}$, if for every open set $U\subseteq X$ with
$x\in U$

$\limsup_{N\to\infty}\frac{\\#\left\\{n\leq N:T^{n}x\in U\right\\}}{N}>0,$

respectively

$\limsup_{T\to\infty}\frac{\mathrm{meas}\left\\{t\in[0,T]:T_{t}x\in
U\right\\}}{T}>0.$

There is a connection between continuous and discrete version of strong
recurrence which was established by Gottschalk and Hedlund [8, Theorem 2].

######  Theorem (Gottschalk-Hedlund).

Let $\mathcal{T}=(T_{t})_{t\geq 0}$ be a $C_{0}$-semigroup of operators and
assume that $h>0$. Then a vector $x\in X$ is strongly recurrent for
$\mathcal{T}$ if and only if is strongly recurrent for $T_{h}$.

The notion of strong recurrence in the context of zeta- and $L$-functions has
been realized by Bagchi in his thesis [1] and then in subsequent work in [2,
3].

######  Theorem (Bagchi).

The following statements are equivalent:

  1. (1)

The Riemann hypothesis is true.

  2. (2)

For any admissible $(K,\zeta,\varepsilon)$

$\liminf_{T\to\infty}\frac{1}{T}\mathrm{meas}\left\\{\tau\in[0,T]:\max_{s\in
K}|\zeta(s+i\tau)-\zeta(s)|<\varepsilon\right\\}>0.$

  3. (3)

Statement $(2)$ holds with $\limsup$ in place of $\liminf$.

It should be noted that Bagchi proves only $(1)\Leftrightarrow(3)$ but the
statement cited mostly in the relevant literature is $(1)\Leftrightarrow(2)$.
We give a sketch of the proof. The implication $(1)\Rightarrow(2)$ follows
from Voronin’s theorem while $(2)\Rightarrow(3)$ is obvious. Lastly, assuming
that $(3)$ holds but $(1)$ does not, it would imply by Rouché’s theorem the
existence of at least $cT$ many zeros in the rectangle $1/2<\sigma<1$,
$0<t<T$, for some $c>0$ and infinitely many $T$. But these would contradict
classic zero-density estimates of $\zeta(s)$ in the half-plane $\sigma>1/2$
(see for example [25, Chapter IX]).

##  3\. Proofs of the main results

Before giving the proofs we construct the space $X$ and the one-parameter
family of operators $\mathcal{T}$ which are connected to the universality of
zeta-functions.

Let $(K_{n})_{n\geq 1}$ be an exhaustion of
$\mathcal{D}=\left\\{s\in\mathbb{C}:1/2<\sigma<1\right\\}$ by compact sets,
that is $K_{n}\subseteq K_{n+1}\subseteq\mathcal{D}$, $n\geq 1$, and for every
compact set $K\subseteq U$, there is $N\geq 1$ such that $K\subseteq K_{N}$.
Since $\mathcal{D}$ is simply connected we can construct $K_{n}$ to have
connected complement. We equip
$H(\mathcal{D})=\left\\{f:\mathcal{D}\to\mathbb{C}\mid f\text{ is
analytic}\right\\}$ with the sequence of norms

$p_{n}(f):=\max_{s\in K_{n}}|f(s)|,\quad f\in H(\mathcal{D}),\quad n\geq 1,$

and it becomes a (separable) Fréchet space, i.e. a complete metric space with
the metric

$d(f,g):=\sum_{n\geq 1}\frac{1}{2^{n}}\min\left(1,p_{n}(f-g)\right),\quad
f,g\in H(\mathcal{D}).$

Lastly, we define the sequence of translation operators
$\mathcal{T}:=(T_{\tau})_{\tau\geq 0}$ by

$T_{\tau}f:=f(\cdot+i\tau),\quad f\in H(\mathcal{D}),\quad\tau\geq 0,$

and it can be quickly verified that it is a well-defined $C_{0}$-semigroup on
$H(\mathcal{D})$. The family is also locally equicontinuous because
$H(\mathcal{D})$ is a Fréchet space.

###### Proof of Theorem 1.1.

Let $h>0$. If $U$ is an open subset of $H(\mathcal{D})$, then there is $n\geq
1$ and an analytic function $h:\mathcal{D}\to\mathbb{C}$ such that

$V:=\left\\{g\in H(\mathcal{D}):\max_{s\in
K_{n}}|g(s)-h(s)|<\frac{1}{n}\right\\}\subseteq U.$

If the Hurwitz zeta-function is continuous strongly universal for some fixed
parameter $\alpha\in(0,1]$, then

$\liminf_{T\to\infty}\frac{1}{T}\mathrm{meas}\left\\{\tau\in[0,T]:\max_{s\in
K_{n}}|\zeta(s+i\tau;\alpha)-h(s)|<\frac{1}{n}\right\\}>0,$

which implies in the language of linear dynamics that

$\liminf_{T\to\infty}\frac{1}{T}\mathrm{meas}\left\\{\tau\in[0,T]:T_{\tau}\zeta(\cdot;\alpha)\in
U\right\\}>0.$

Since $U$ is arbitrary and $\zeta(\cdot;\alpha)$ is an element of
$H(\mathcal{D})$, we get that
$\zeta(\cdot;\alpha)\in\mathrm{FHC}(\mathcal{T})$. In view of the Conejero-
Müller-Peris theorem it follows that also
$\zeta(\cdot;\alpha)\in\mathrm{FHC}(T_{h})$.

Let now $(K,f,\varepsilon)$ be admissible. By Mergelyan’s theorem there is a
polynomial $P(s)$ with

$\max_{s\in K}|P(s)-f(s)|<\frac{\varepsilon}{2}.$

On the other hand

$W:=\left\\{g\in H(\mathcal{D}):\max_{s\in
K}|g(s)-P(s)|<\frac{\varepsilon}{2}\right\\}$

is an open subset of $H(\mathcal{D})$. Since
$\zeta(\cdot;\alpha)\in\mathrm{FHC}(T_{h})$, we have that

$\liminf_{N\to\infty}\frac{1}{N}\\#\left\\{n\leq
N:T^{n}_{h}\zeta(\cdot;\alpha)\in W\right\\}.$

Therefore, by the triangle inequality and the equation $T^{n}_{h}=T_{hn}$ we
conclude that

$\liminf_{N\to\infty}\frac{1}{N}\\#\left\\{n\leq N:\max_{s\in
K}|\zeta(s+ihn;\alpha)-f(s)|<\varepsilon\right\\}>0.$

Hence, $\zeta(s;\alpha)$ is $h$-discrete strongly universal as well.

Now we assume that the converse statement is true, i.e. the Hurwitz zeta-
function is $h$-discrete strongly universal. If $U\subseteq H(\mathcal{D})$ is
open with $\zeta(\cdot,\alpha)\in U$, then by assumption

$\liminf_{N\to\infty}\frac{1}{N}\left\\{n\leq
N:T_{h}^{n}\zeta(\cdot;\alpha)\in U\right\\}.$

Hence, $\zeta(\cdot;\alpha)$ is strongly recurrent for the operator $T_{h}$
and, consequently, for the family $\mathcal{T}$ as can be seen by the
Gottshalk-Hedlund theorem.

If $(K,f,\varepsilon)$ is admissible, then the $h$-discrete strong
universality implies that there is integer $N$ such that

(3.1) $\displaystyle\max_{s\in
K}|\zeta(s+ihN;\alpha)-f(s)|<\frac{\varepsilon}{2}.$

Since $\zeta(\cdot;\alpha)$ is strongly recurrent for $\mathcal{T}$, we know
that

$\limsup_{T\to\infty}\frac{1}{T}\mathrm{meas}\left\\{\tau\in[0,T]:\max_{s\in
ihN+K}|\zeta(s+i\tau;\alpha)-\zeta(s;\alpha)|<\frac{\varepsilon}{2}\right\\}>0.$

From the triangle inequality and (3.1), we obtain now the second statement of
the theorem. ∎

###### Proof of Theorem 1.2.

Let $h>0$. It should be noted that if $(K,f,\varepsilon)$ is admissible ($f$
may also have zeros), then

(3.2)
$\displaystyle\liminf_{T\to\infty}\frac{1}{T}\mathrm{meas}\left\\{\tau\in[0,T]:\max_{s\in
K}|\log\zeta(s+i\tau)-f(s)|<\varepsilon\right\\}.$

For, we know that hypothetical zeros of $\zeta(s)$ off the vertical line
$1/2+i\mathbb{R}$ are distributed sparser as we move higher in the strip
$\mathcal{D}$. Therefore, for any compact set $K$, it is possible to show that
the measure of those $\tau\in[0,T]$ such that $i\tau+K$ does not contain any
zeros of $\zeta(s)$, is asymptotically equal to $T$. On the other hand,
Voronin’s theorem implies that the set of $\tau$ such that $\zeta(s+i\tau)$ is
close to $e^{f(s)}$ has positive lower density. Relation (3.2) follows by
combining these two facts.

It is only now that we have to assume the Riemann hypothesis in order to
ensure that $\log\zeta\in H(\mathcal{D})$. We then have the same setting as
for the Hurwitz zeta-function in the previous theorem. The continuous
universality of $\zeta(s)$ implies the continuous strong universality of
$\log\zeta(s)$ which in turn (by the Conejero-Müller-Peris theorem) implies
the $h$-discrete strong universality of $\log\zeta(s)$ and by exponentiation
the $h$-discrete universality of $\zeta(s)$.

For the converse statement however, we employ additionally Bagchi’s theorem
after applying the Gottshalk-Hedlund theorem. Of course it is again essential
to ensure that $\log\zeta\in H(\mathcal{D})$ as follows from the Riemann
hypothesis. By repeating now the same steps as in the previous proof but
moving from $\zeta(s)$ to its logarithm and preserving the $\liminf$ notation,
we obtain that the $h$-discrete universality of $\zeta(s)$ implies its
continuous universality. ∎

######  Remark.

One of the main arguments in the proof of the Conejero- Müller-Peris theorem
is that the (frequently) hypercyclic vector can approximate itself in the
space $X$. This may not be possible in our case unless we assume the Riemann
hypothesis in which case Voronin’s theorem is applicable. Another approach
relies on working in a slit half-plane $\Omega$ which is defined as the whole
$\mathcal{D}$ without the segments $(1/2+i\gamma,\beta+i\gamma]$ for any zero
$\rho=\beta+i\gamma$ of $\zeta(s)$. Since $\zeta(1+it)\neq 0$,
$t\in\mathbb{R}$, $\Omega$ is simply connected and we can show as in the case
of $H(\mathcal{D})$, that $H(\Omega)$ is a Fréchet space with the induced
topology. The disadvantage of this approach is that the family $\mathcal{T}$
of vertical shifts in not anymore well-defined in $H(\Omega)$. Nevertheless,
if we leave aside the notion of operators then Voronin’s theorem implies the
strong recurrence of $\zeta(s)$ in the space $H(\Omega)$ (in the form given by
Bagchi). However, later in the proof of the Conejero-Müller-Peris theorem, a
certain continuity argument is needed that involves the elements $x+\lambda
T_{\tau}x$, $x\in HC(\mathcal{T})$, $\lambda\in\mathbb{C}$ and $\tau$ from
some suitable interval. This argument does not seem that can be adjusted to
our case if we drop some defining properties of a $C_{0}$-semigroup. Instead,
to prove the weaker statement of Theorem 1.3, we modify the proof of [9,
Theorem 7.22], where no self-approximation is needed.

###### Proof of Theorem 1.3.

Let $U_{m}$, $m\geq 1$, be an enumeration of the sets

$\left\\{f\in H^{*}(\mathcal{D}):\max_{s\in
K_{N}}|f(s)-e^{P(s)}|<\frac{1}{N}\right\\},\quad N\geq 1,\,P\in\mathbb{Q}[X],$

which form a countable base of $H^{*}(\mathcal{D})$ and for each $m\geq 1$
define

$\displaystyle J_{m}=\left\\{\tau\in(0,+\infty):\exists n\in\mathbb{N}\text{
with }\max_{s\in K_{N}}|\zeta(s+in\tau)-e^{P(s)}|<\frac{1}{N}\right\\},$

which is an open subset of $(0,+\infty)$.

By Voronin’s theorem it follows that $J_{m}$ is dense. For, if
$0<a<b<+\infty$, then there is $n_{0}\in\mathbb{N}$ such that
$n_{0}b>(n_{0}+1)a$ and, thus, $(n_{0}a,+\infty)\subseteq\cup_{n\geq
n_{0}}(na,nb)$. The universality theorem implies that $T_{s}\zeta\in U_{m}$
for (infinitely many) $s\geq n_{0}$. Hence, $s\in(na,nb)$ for some $n\geq
n_{0}$ and if we set $t_{0}=s/n$, then $t_{0}\in J_{m}\cap(a,b)$.

Therefore, the Baire category theorem yields that the set

$J:=\bigcap_{m\geq 1}J_{m}$

is a dense $G_{\delta}$-set in $(0,+\infty)$ whose elements satisfy the
desired property of $\zeta(s)$. ∎

##  4\. Multidimensional case

There is no real advantage on considering only $\zeta(s)$ or $\zeta(s;\alpha)$
since any other function defined in a similar space as $H(\mathcal{D})$ could
take their place. In fact, we introduce the following generalization, which
has also been realized by Bagchi [3]:

Let $N\in\mathbb{N}$, $\mathbf{h}:=(h_{1},\dots,h_{N})$ be a vector of
positive real numbers and $\sigma_{1n}<\sigma_{2n}$, $n\leq N$. If
$\mathcal{D}_{n}:=\left\\{s\in\mathbb{C}:\sigma_{1n}<\sigma<\sigma_{2n}\right\\}$,
$n\leq N$, and $\mathcal{C}:=\prod_{n\leq N}\mathcal{D}_{n}$ is their
Cartesian product, then $H(\mathcal{C})$ is a separable Fréchet space (with
the product topology) and the family of operators
$\mathcal{T}_{\mathbf{h}}=(T_{\tau})_{\tau\geq 0}$ defined by

$T_{\tau}(f_{1},\dots,f_{N})=(f_{1}(\cdot+ih_{1}\tau),\dots,f_{N}(\cdot+ih_{N}\tau)),\quad(f_{1},\dots,f_{N})\in
H(\mathcal{C}),\quad\tau\geq 0,$

is a well-defined $C_{0}$-semigroup. Lastly, $H^{*}(\mathcal{C})\subseteq
H(\mathcal{C})$ will consist of the vectors whose entries are zero-free
functions.

A vector of zeta-functions $(\zeta_{1},\dots,\zeta_{N})\in H(\mathcal{C})$
will be called:

  1. (1)

continuous jointly universal if for any admissible
$(K_{n},f_{n},\varepsilon)^{*}$, $n\leq N$,

(4.1)
$\displaystyle\liminf_{T\to\infty}\frac{1}{T}\mathrm{meas}\left\\{\tau\in[0,T]:\max_{n\leq
N}\max_{s\in K_{i}}|\zeta_{n}(s+ih_{n}\tau)-f_{n}(s)|<\varepsilon\right\\}>0;$

  2. (2)

continuous joint strongly universal if for any admissible
$(K_{n},f_{n},\varepsilon)$, $n\leq N$, relation (4.1) holds;

  3. (3)

$h$-discrete jointly universal/joint strongly universal if in (4.1) we
substitute the continuous variable $\tau\in[0,T]$ with a discrete variable
$hm$, $m\in[0,T]\cap\mathbb{N}$, and the Lebesgue measure notation
$\mathrm{meas}$ with the notation of the cardinality of a set $\\#$.

With the above notations, we can adjust the proofs from the previous sections
to obtain similar results for the multidimensional case.

######  Theorem 4.1.

If $(\zeta_{1},\dots,\zeta_{N})\in H(\mathcal{C})$ is continuous joint
strongly universal, then it is $h$-discrete joint strongly universal for every
$h>0$. If $(\zeta_{1},\dots,\zeta_{N})\in H^{*}(\mathcal{C})$ is continuous
jointly universal, then it is $h$-discrete joint universal for every $h>0$. If
$(\zeta_{1},\dots,\zeta_{N})\in H(\mathcal{C})$ is continuous jointly
universal, then there is a dense $G_{\delta}$-set $J\subseteq(0,+\infty)$ such
that if $t_{0}\in J$, then for any admissible tuple
$(K_{n},f_{n},\varepsilon)^{*}$, $n\leq N$, there is a sequence
$(n_{k})_{k\geq 1}\subseteq\mathbb{N}$ such that

$\max_{n\leq N}\max_{s\in
K_{n}}|\zeta_{n}(s+it_{0}n_{k})-f_{n}(s)|<\varepsilon,\quad k\geq 1.$

##  5\. Zeta-functions

The reason we highlighted the term “zeta-functions” is because in analytic
number theory there is no rigorous definition of what a zeta- or an
$L$-function should look like. They are usually considered as Dirichlet series

$L(s)=\sum_{n\geq 1}\frac{a_{n}}{e^{\lambda_{n}s}},\quad\sigma>\sigma_{0},$

where $(a_{n})_{n\geq 1}\subseteq\mathbb{C}$ and $(\lambda_{n})_{n\geq
1}\subseteq\mathbb{R}$ are sequences of number-theoretic interest (for example
$\lambda_{n}=\log n$ and $a_{n}=1$) and $\sigma_{0}<\infty$ is the abscissa of
absolute convergence. Naturally, $L(s)$ can not be universal in the half-plane
$\sigma>\sigma_{0}$. If it can, however, be analytically continued to a
vertical strip $\sigma_{1}<\sigma<\sigma_{0}$ with the exception of finitely
many poles, then it will most likely be universal as well. Here we can make
two distinctions. If $L(s)$ has also an Euler product representation

$L(s)=\prod_{n\geq 1}\left\lparen
1-\frac{b_{n}}{e^{\mu_{n}s}}\right\rparen^{-1},\quad\sigma>\sigma_{0},$

for some $(b_{n})_{n\geq 1}\subseteq\mathbb{C}$ and $(\mu_{n})_{n\geq
1}\subseteq\mathbb{R}$, then similar zero-density estimates as in the case of
$\zeta(s)$ could possibly be attained, allowing us to say that $L(s)$ can not
be strongly universal. If, on the other hand, such representation does not
exist, then $L(s)$ will be strongly universal.

A good candidate of a zeta-function having an Euler product representation are
elements from the so-called Selberg class introduced by Selberg [22]. For
instance, the Riemann zeta-function, Dirichlet $L$-functions, Dedekind zeta-
functions and Hecke $L$-functions belong to this class. For a detailed survey
we refer to [24], while sufficient conditions for an $L(s)$ from this class to
be universal are given in [17]. If additionally we assume some sort of
independence between elements $L_{1},\dots,L_{N}$ of the Selberg class, then
we can also have joint universality. For example if $\chi_{1},\dots,\chi_{N}$
are Dirichlet characters that are pairwise nonequivalent, then the associated
Dirichlet $L$-functions $(L(s,\chi_{1}),\dots,L(s,\chi_{N}))$ are jointly
universal. This was proved independently by Bagchi [1, 2], Gonek [7] and
Voronin [27]. A more general framework in the context of the Selberg class is
given in [15].

Zeta-functions without an Euler product are usually occurring when
$\lambda_{n}=\log\kappa_{n}$ with
$\kappa_{n}\in\mathbb{R}_{+}\setminus\mathbb{N}$ or when they can be expressed
as a linear combination of two or more zeta-functions which have an Euler
product. A classic example of the first case is the Lerch zeta-function [11]
which is a generalization of the Hurwitz zeta-function, while an example of
the second case are Dirichlet series with periodic coefficients [23]. In both
cases we have strong universality while in [4, 13] a more general framework is
given. If a tuple of such zeta-functions has some sort of independence between
them, then they will also be joint strongly universal [10, 14].

We only presented a selection of results. Their discrete analogues can also be
found in the literature. On the other hand, Theorem 4.1 implies in a strong or
a weaker sense that studying the continuous universality may suffice.

## References

  * Bagchi [1981] B. Bagchi.  _Statistical behaviour and universality properties of the Riemann zeta function and other allied Dirichlet series_.  PhD thesis, Indian Statistical Institute-Kolkata, 1981.
  * Bagchi [1982] B. Bagchi.  A joint universality theorem for Dirichlet L-functions.  _Math. Z._ , 181: 319–334, 1982.  doi: 10.1007/BF01161980.
  * Bagchi [1987] B. Bagchi.  Recurrence in topological dynamics and the Riemann hypothesis.  _Acta Math. Hung._ , 50: 227–240, 1987.  doi: 10.1007/BF01903937.
  * Bayart [2023] F. Bayart.  Universality of general Dirichlet series with respect to translations and rearrangements.  _Ark. Mat._ , 61(1): 19–39, 2023.  doi: 10.4310/ARKIV.2023.v61.n1.a2.
  * Bayart and Matheron [2009] F. Bayart and É. Matheron.  _Dynamics of linear operators_ , volume 179 of _Camb. Tracts Math._ Cambridge: Cambridge University Press, 2009.
  * Conejero et al. [2007] J. A. Conejero, V. Müller, and A. Peris.  Hypercyclic behaviour of operators in a hypercyclic $C_{0}$-semigroup.  _J. Funct. Anal._ , 244(1): 342–348, 2007\.  doi: 10.1016/j.jfa.2006.12.008.
  * Gonek [1979] S. M. Gonek.  _Analytic properties of zeta and $L$-functions_.  PhD thesis, 1979.
  * Gottschalk and Hedlund [1946] W. H. Gottschalk and Gustav A. Hedlund.  Recursive properties of transformation groups.  _Bull. Am. Math. Soc._ , 52:637–641, 1946.  doi: 10.1090/S0002-9904-1946-08612-7.
  * Grosse-Erdmann and P. Manguillot [2011] K.-G. Grosse-Erdmann and A. P. Manguillot.  _Linear chaos_.  Universitext. Berlin: Springer, 2011.  doi: 10.1007/978-1-4471-2170-1.
  * Javtokas and Laurinčikas [2008] A. Javtokas and A. Laurinčikas.  A joint universality theorem for periodic Hurwitz zeta-functions.  _Bull. Aust. Math. Soc._ , 78(1): 13–33, 2008.  doi: 10.1017/S0004972708000300.
  * Laurinčikas [1995] A. Laurinčikas.  _Limit theorems for the Riemann zeta-function_ , volume 352 of _Math. Appl., Dordr._ Dordrecht: Kluwer Academic Publishers, 1995.
  * Laurinčikas and Macaitienė [2009] A. Laurinčikas and R. Macaitienė.  The discrete universality of the periodic Hurwitz zeta function.  _Integral Transforms Spec. Funct._ , 20(9-10): 673–686, 2009.  doi: 10.1080/10652460902742788.
  * Laurinčikas et al. [2003] A. Laurinčikas, W. Schwarz, and J. Steuding.  The universality of general Dirichlet series.  _Analysis, München_ , 23(1): 13–26, 2003.
  * Lee et al. [2017a] Y. Lee, T. Nakamura, and Ł. Pańkowski.  Joint universality for Lerch zeta-functions.  _J. Math. Soc. Japan_ , 69(1): 153–161, 2017a.  doi: 10.2969/jmsj/06910153.
  * Lee et al. [2017b] Y. Lee, T. Nakamura, and Ł. Pańkowski.  Selberg’s orthonormality conjecture and joint universality of $L$-functions.  _Math. Z._ , 286(1-2):1–18, 2017b.  doi: 10.1007/s00209-016-1754-2.
  * Matsumoto [2015] K. Matsumoto.  A survey on the theory of universality for zeta and $L$-functions.  In _Number theory. Plowing and starring through high wave forms. Proceedings of the 7th China-Japan Seminar, Fukuoka, Japan, October 28 – November 1, 2013_ , pages 95–144. Hackensack, NJ: World Scientific, 2015.  doi: 10.1142/9789814644938_0004.
  * Nagoshi and Steuding [2010] H. Nagoshi and J. Steuding.  Universality for $L$-functions in the Selberg class.  _Lith. Math. J._ , 50(3): 293–311, 2010\.  doi: 10.1007/s10986-010-9087-z.
  * Oxtoby and Ulam [1941] J. C. Oxtoby and S. M. Ulam.  Measure-preserving homeomorphisms and metrical transitivity.  _Ann. Math. (2)_ , 42: 874–920, 1941.  doi: 10.2307/1968772.
  * Queffelec and Queffelec [2020] H. Queffelec and M. Queffelec.  _Diophantine approximation and Dirichlet series_ , volume 80 of _Texts Read. Math._ New Delhi: Hindustan Book Agency; Singapore: Springer, 2nd extended edition edition, 2020.  doi: 10.1007/978-981-15-9351-2.
  * Reich [1980] A. Reich.  Werteverteilung von Zetafunktionen.  _Arch. Math._ , 34: 440–451, 1980.  doi: 10.1007/BF01224983.
  * Riemann [2017] B. Riemann.  _The collected works of Bernhard Riemann. The complete German texts. With an English introduction by Hans Lewy_.  Mineola, NY: Dover Publications, reprint of the 1953 Dover republication of the 2nd edition of Bernhard Riemann’s ‘Gesammelte Mathematische Werke’ published in 1892 and the Supplement (Nachträge) published 1902 edition, 2017.  ISBN 978-0-486-81243-4.
  * Selberg [1992] A. Selberg.  Old and new conjectures and results about a class of dirichlet series.  In _Proceedings of the Amalfi Conference on Analytic Number Theory (Maiori, 1989)_ , volume 2, pages 47–63, 1992.
  * Steuding [2002] J. Steuding.  On Dirichlet series with periodic coefficients.  _Ramanujan J._ , 6(3): 295–306, 2002.  doi: 10.1023/A:1019797315282.
  * Steuding [2007] J. Steuding.  _Value distribution of $L$-functions_, volume 1877 of _Lect. Notes Math._ Berlin: Springer, 2007.  doi: 10.1007/978-3-540-44822-8.
  * Titchmarsh [1986] E. C. Titchmarsh.  _The theory of the Riemann zeta-function. 2nd ed., rev. by D. R. Heath-Brown_.  1986\.
  * Voronin [1975] S. M. Voronin.  Theorem on the ‘universality’ of the Riemann zeta-function.  _Izv. Akad. Nauk SSSR, Ser. Mat._ , 39: 475–486, 1975\.
  * Voronin [1978] S. M. Voronin.  _Analytic properties of Dirichlet generating functions of arithmetic objects_.  PhD thesis, 1978.