# Towards the essence of Šoltés’ problem

Stijn Cambie Department of Computer Science, KU Leuven Campus Kulak-Kortrijk,
8500 Kortrijk, Belgium. Supported by a postdoctoral fellowship by the Research
Foundation Flanders (FWO) with grant number 1225224N.

###### Abstract

We explore the question asking for graphs $G$ for which the total distance
decreases, possibly by a fixed constant $k$, upon the removal of any of its
vertices. We obtain results leading to intuition and doubts for the Šoltés’
problem ($k=0$) and its conjectures.

##  1 Introduction

In 1991, Šoltés [14] observed that if one removes a vertex of a cycle
$C_{11}$, the total distance does not change, and asked whether there are
other such graphs $G$ (nowadays called Šoltés’ graphs). It is one of the most
elementary questions one can pose [10] related to $W(G)$, the total distance
of $G$. Infinitely many examples were given by Spiro [15] and Cambie [5] for
the relaxation of Šoltés’ problem to signed graphs and hypergraphs
respectively.

Meanwhile, there are numerous open conjectures (weaker to stronger forms),
conjecturing that Šoltés’ graphs are e.g. regular or vertex-transitive, and
that $C_{11}$ is the only Šoltés’ graph. See [10, conj. 47, 48, 51]. One of
the arguments, as can be seen in the conclusion of [2], was that no other
examples were found among the $>10^{8}$ vertex-transitive graphs in the census
by Holt and Royle [9]. We will give intuition why all of these (different from
the cycles) satisfy $W(G)>W(G\setminus v)$ for $v\in V(G)$.

In Section 2, we prove that if $W(G)\leq W(G\setminus v)$ for every $v\in
V(G),$ the diameter cannot be too small, and if the value $W(G)-W(G\setminus
v)$ is independent of the vertex $v\in v(G),$ then $G$ is a cycle or the
minimum degree of $G$ is at least $3.$

In Section 3 (and Appendix A), we present eight graphs $G$ for which two third
of the vertices $v$ satisfy $W(G\setminus v)=W(G)$ (these are Šoltés’
vertices), and give conditional examples of graphs for which an even higher
fraction of the vertices satisfy the inequality.

In [1, Prob. 3] (and [10, Prob. 44]), the authors mentioned that arguments to
solve Šoltés’ problem may also work for the following generalisation.

######  Problem 1.

For a fixed $z\in\mathbb{Z}$, find all graphs $G$ for which the equality
$W(G)-W(G-v)=z$ holds for all vertices $v$.

As a first thing, we want to convince the reader that this problem is nearly
impossible to solve in general111For fixed $z$, it might be possible to reduce
to a finite number of candidates. and by the reasoning of the authors, solving
the Šoltés’ problem may be hard or impossible as well.

Of course, for every $z>0$, the graph $K_{z+1}$ is a solution, but there are
values of $z$ for which there are many solutions. By an immediate argument
using the pigeon hole principe on the number of cubic vertex-transitive graphs
(which is of the form $n^{\Theta(\log n)}$ as estimated in [13]), the number
of solutions can be arbitrary large. For a concrete indication, the census by
Holt and Royle [9] in https://zenodo.org/records/4010122 contains more than
$10^{8}$ vertex-transitive graphs with diameter bounded by $3$, each
corresponding to a value $0<z<141$.

By focusing on a subfamily (defined later), for which the plausible values of
$z$ can be both negative or positive, we can expect that also $z=0$ might have
multiple solutions. We conjecture this is the case if there are e.g.
infinitely many vertex-transitive graphs (different from cycles) for which
$W(G)<W(G\setminus v)$ for all $v\in V(G).$

We add more doubts and remarks on the circulating conjectures in Section 4,
giving evidence why these conjectures may be false.

In Section 5, we give our conclusions and state our core question, which would
lead to the essence behind Šoltés’ problem. Calling a graph $G$ satisfying 1
for a $z\leq 0$ a negative-Šoltés’ graph (these are far from vertex-robust for
distances), we can summarize that the essential question is whether there are
infinitely many negative-Šoltés’ graphs which are not cycles.

###  1.1 Notation and Terminology

We only consider simple connected graphs $G=(V,E).$ The degree of a vertex
$v$, denoted by $\deg(v)$, is the number of edges containing $v$. The minimum
and maximum degree, $\delta$ and $\Delta$, represent the smallest and largest
degrees. When removing the vertex $v$ and its incident edges from $G$, we
obtain $G\setminus v$.

The distance $d_{G}(u,v)$ or $d(u,v)$ between two vertices $u$ and $v$ is
equal to the length of the shortest path between them. The diameter,
$diam(G)$, is the largest among all possible distances and the total distance
(or Wiener index), $W(G)$, the sum over all of them; $W(G)=\sum_{u,v\in
V}d(u,v)$. The radius $rad(G)=\min_{u\in V}\max_{v\in V}d(u,v)$ gives the
maximum distance from a central vertex. The transmission of a vertex $v$,
$\sigma(v)=\sum_{u\in V}d(u,v)$, is the sum of distances between $v$ and the
other vertices. We also define the arc-graph of $G$.

######  Definition 2.

Let $G=(V(G),E(G))$ be a graph. Let $A(G)$ be the arcs of $G$, i.e., the
ordered pairs of neighbouring vertices. Note that $\left\lvert
A(G)\right\rvert=2\left\lvert E(G)\right\rvert.$ The arc-graph $H$ of $G$ has
vertex set $A(G)$, with two arcs being adjacent if

  * •

they correspond to the same edge, i.e., $(u,v)$ is adjacent to $(v,u)$ when
$uv\in E(G),$

  * •

the arcs have the same root, i.e., $(v,u)$ and $(v,w)$ are adjacent in $H$.

Equivalently, $H$ is equal to the line-graph of the subdivision of $G.$

Essentially, ranging over all vertices, a vertex $v$ of degree $d$ is replaced
by a clique $K_{d}$ whose endvertices are connected with one initial neighbour
of $v$ each. It has been introduced before as the subdivided-line graph in
[8], and for cubic graphs, as the truncation of the graph [2]. An example,
$A(K_{4})$, and a sketch of the local replacement (for $d=7$) is shown in Fig.
1.

Figure 1: Arc-graph of $K_{4}$ (left) and local modification of a degree $7$
vertex (middle and right)

##  2 Necessary condition for Šoltés’ graphs

Forbidding an isolated vertex as a Šoltés’ graph, and remarking that if $u$ is
a pendent vertex of a connected graph $G$, we have $W(G\setminus u)<W(G)$, we
know that the minimum degree ($\delta$) of a Šoltés’ graph is at least $2$.
Here we prove that if $G\not=C_{11}$ is a Šoltés’ graph, then $\delta(G)\geq
3.$ This is a stronger version of a result by Dragan Stevanović (private
communication), that a Šoltes’ graph different from $C_{11}$ cannot have
internal paths with $3$ consecutive degree-$2$-vertices. In the proofs, we
denote $G_{v}$ for the graph $G\setminus v$.

######  Proposition 3.

A graph for which $\delta(G)=2$ and $W(G\setminus v)$ is constant for all
$v\in V(G),$ is a cycle.

###### Proof.

Let $G=(V,E)$ be such a graph with $\delta(G)=2$, let $p$ be a vertex with
degree $2$ and $a,b$ be its two neighbours. We need
$W(G)=W(G_{a})=W(G_{p})=W(G_{b}).$ Let $X=V\setminus\\{a,p,b\\}.$ Let
$H_{a}=G[X\cup a]$ and $H_{b}=G[X\cup b].$ Let $\sigma(a)=\sum_{w\in
X}d_{H_{a}}(a,w)$ and $\sigma(b)=\sum_{w\in X}d_{H_{b}}(b,w).$

We are now ready to compare $W(G_{a}),W(G_{p})$ and $W(G_{b}).$ For this, we
split these total distances in multiple parts. First observe that
$d_{G_{p}}(a,b)\leq\lvert X\rvert+1$ with equality if and only if $G=C_{n},$
while $d_{G_{a}}(b,p)=d_{G_{b}}(a,p)=1.$ Next, we note that for every choice
of $x,y\in X$,

$d_{G_{p}}(x,y)\leq d_{G_{a}}(x,y),d_{G_{b}}(x,y).$

Finally, since $H_{a},H_{b}\subset G_{p}$ we note that

$\sum_{w\in
X}\left(d_{G_{p}}(a,w)+d_{G_{p}}(b,w)\right)\leq\sigma(a)+\sigma(b)$
$\sum_{w\in X}\left(d_{G_{a}}(p,w)+d_{G_{a}}(b,w)\right)=2\sigma(b)+\lvert
X\rvert$ $\sum_{w\in
X}\left(d_{G_{b}}(a,w)+d_{G_{b}}(p,w)\right)=2\sigma(a)+\lvert X\rvert.$

Using these observations, we conclude that

$\displaystyle 0=$ $\displaystyle 2W(G_{p})-W(G_{a})-W(G_{b})$
$\displaystyle=$ $\displaystyle
2d_{G_{p}}(a,b)-d_{G_{a}}(p,b)-d_{G_{b}}(a,p)+\sum_{x,y\in
X}\left(2d_{G_{p}}(x,y)-d_{G_{a}}(x,y)-d_{G_{b}}(x,y)\right)$
$\displaystyle+\sum_{w\in
X}\left(2d_{G_{p}}(a,w)+2d_{G_{p}}(b,w)-d_{G_{a}}(p,w)-d_{G_{a}}(b,w)-d_{G_{b}}(a,w)-d_{G_{b}}(p,w)\right)$
$\displaystyle\leq$ $\displaystyle 2d_{G_{p}}(a,b)-2-2\lvert X\rvert$
$\displaystyle\leq$ $\displaystyle 0.$

Since equality need to be attained in every step, we have
$d_{G_{p}}(a,b)=1+\lvert X\rvert,$ which implies that $G_{p}$ is a path from
$a$ to $b$, and thus $G$ is a cycle. ∎

######  Proposition 4.

A graph $G$ of order $n>1$ with $diam(G)\leq 2$ has at least one vertex $v$
for which either $G\setminus v$ is disconnected, or $W(G\setminus v)<W(G).$

###### Proof.

This is obvious for a clique (diameter $1$ graph). So now assume $diam(G)=2.$
First we observe that $G$ cannot have a universal vertex $v$, since for a
vertex $u\not=v$ $W(G)=2\binom{n}{2}-m>2\binom{n-1}{2}-m+\deg(u)=W(G_{u}).$ So
$rad(G)>1$, i.e. for every $v\in V$ its closed neighbourhood $N[v]$ is not
equal to $V.$ The only pairs of vertices $u,u^{\prime}\in V(G_{v})$ for which
$d_{G_{v}}(u,u^{\prime})>d_{G}(u,u^{\prime}),$ have to be both neighbours of
$v$ in $G$ (and have no other common neighbour).

Note that for every $u\in N(v)$ and $w\not\in N[v]$,
$d_{G_{v}}(u,w)=d_{G}(u,w)\leq 2.$ This implies that
$d_{G_{v}}(u,u^{\prime})\leq d_{G_{v}}(u,w)+d_{G_{v}}(w,u^{\prime})\leq 4$ and
thus $d_{G_{v}}(u,u^{\prime})-d_{G}(u,u^{\prime})\leq 2.$

Since $\sum_{u\in V\setminus v}d(u,v)=2(n-1)-\deg(v)\geq n$, has to be lower
bounded by $\sum_{u,u^{\prime}\in V\setminus
v}\left(d_{G_{v}}(u,u^{\prime})-d_{G}(u,u^{\prime})\right),$ there are at
least $\frac{n}{2}$ pairs of vertices $(u,u^{\prime})$ for which the unique
shortest path uses $v$.

Summing over all $v\in V$, this implies that there are at least
$\frac{n^{2}}{2}>\binom{n}{2}$ pairs of vertices at distance $2$ in $G$, which
is a contradiction. ∎

For self-centric graphs (graphs with $diam=rad$), e.g. vertex-transitive
graphs, one can also exclude the diameter to be $3.$

######  Proposition 5.

A graph $G$ of order $n>1$ with $diam(G)=rad(G)=3$ has at least one vertex $v$
for which either $G\setminus v$ is disconnected, or $W(G\setminus v)<W(G).$

###### Proof.

Assume $G$ has connectivity at least two, i.e., $G\setminus v$ is connected
for every $v\in V(G)$.

Let $v\in V(G)$ and let $v^{\prime}$ be an antipodal vertex, that is,
$d(v,v^{\prime})=3.$ If $a,b$ are two vertices with $d(a,b)=d(a,v)+d(v,b)=2$,
we note that $d_{G_{v}}(a,b)\leq
d_{G_{v}}(a,v^{\prime})+d_{G_{v}}(b,v^{\prime})\leq 2\cdot 3=6.$

If $a,b$ are two vertices with $d(a,b)=3$, $d(a,v)=1$ and $d(v,b)=2$, we can
consider a shortest path between $a$ and $v^{\prime}$ and let $w$ be the
neighbour herein of $v^{\prime}.$ Then $d_{G_{v}}(a,b)\leq
d_{G_{v}}(a,w)+d_{G_{v}}(b,w)\leq 2+3=5.$

Assume there are $x$ pairs of vertices at distance $2$, and $y$ pairs of
vertices at distance $3$. If $d(a,b)=2,$ there is at most one vertex $v$ for
which $d_{G_{v}}(a,b)>d(a,b)$ and the increase is at most $6-2=4$. If
$d(a,b)=3,$ there are at most two vertices whose removal increase the distance
between $a$ and $b$, hereby the increase is bounded by $5-3=2.$ The total
increase, $\sum_{u,u^{\prime}\in V\setminus
v}\left(d_{G_{v}}(u,u^{\prime})-d_{G}(u,u^{\prime})\right),$ is thus bounded
by $4(x+y).$ On the other hand, the sum of the transmissions over all
vertices, which equals $2W(G)$, is strictly above $2(2x+3y).$ As such, there
is a vertex $v$ for which $W(G\setminus v)<W(G).$ ∎

######  Proposition 6.

A graph $G$ for which $W(G)\leq W(G_{v})$ for every $v\in V(G)$ is twin-free.
More generally, there are no $v,v^{\prime}\in G$ for which $N(v)\subseteq
N(v^{\prime}).$

###### Proof.

If not, for every $2$ vertices $x,y\in G_{v}=G\setminus v$ for which there
exists a shortest path in $G$ using $v$, there is also one which uses
$v^{\prime}.$ Thus $d_{G}(x,y)=d_{G_{v}}(x,y)$ for every $x,y\in G_{v}$,
implying that $W(G)>W(G_{v})$. ∎

##  3 A conditional construction for partial Šoltés’ graphs

An $\alpha$-Šoltés’ graph, is a graph for which at least an $\alpha$-fraction
of its vertices are Šoltés’ vertices. In [2, abstract] and [10, Sec. 6], it is
mentioned that the only known $\frac{1}{3}$-Šoltés’ graphs were truncated
cubic graphs at that point (neglecting the quartic example from [2] obtained
by taking the line graph of a certain cubic graph). Meanwhile, by [1, 6] more
examples are known. In this section, we give some other (conditional)
examples. We start by the following explicit example, which will be
informative for a conditional construction with larger $\alpha$.

######  Example 7.

There exists a modified quartic ($4$-regular) $\alpha$-Šoltés’ graph for
$\alpha=\frac{27}{56}=\frac{1}{2}-\frac{1}{56}.$

###### Proof.

For this, we take the arc-graph $G$ of the Moore graph $M$ with degree/
valency $4$ and girth $12$/ diameter $6$. Note that the order of $M$ is
$n(M)=2\sum_{i=0}^{5}3^{i}=3^{6}-1=728$ and $n(G)=4(3^{6}-1)=2912.$ For a
fixed edge $e\in G,$ we have that there are $2\cdot 3^{5}\cdot 3=2\cdot
3^{6}=1458$ many vertices at distance $11$ from $e.$ For every $v\in V(G),$
$W(G)-W(G\setminus v)=29896-37356=-7460.$ Noting that
$7460=23+\sum_{k=12}^{122}k,$ we finally construct a graph $Q$ by connecting
an end vertex $v_{12}$ of a $P_{111}$ (with vertices $v_{k},12\leq k\leq 122$)
to both endvertices of an edge $e$ of $G$, and finally add a pendent vertex
$u_{23}$ to $v_{22}.$ Then $n(Q)=2912+112=3024$ and $W(Q)-W(Q\setminus v)=0$
for every $v\in V(G)\subset V(Q)$ which is at distance $11$ from $e.$ This
gives a $\frac{1458}{3024}=\frac{27}{56}$ ratio of vertices of $Q$ which are
Šoltes’ vertices. ∎

The following proposition gives some intuition that one can expect that a
large graph exists of which more than a $\frac{2}{3}$-fraction of its vertices
are Šoltés’ vertices, which would answer [6, Prob. 1]. Nevertheless, it is
related with the very hard open problem on estimating the minimum order of a
cage. Note that in [7] a lower bound on the difference has been shown that is
negligible towards our aims, but no good upper bound is known either [11].

The underlying idea is broader; if there is a large proportion of the vertices
for which $W(G\setminus v)-W(G)$ equals the same positive constant, and we can
add a little substructure to compensate evenly over them, then there is a
graph with a large proportion of Šoltés’ vertices.

######  Proposition 8.

If there exists a $7$-regular graph with even girth $g\geq 58$ which is arc-
transitive and has roughly the Moore bound $N(7,g)$ many vertices, e.g. order
no more than $1.0005N(7,g)$, then there are graphs with roughly a
$\frac{5}{7}$222The exact value depends on how well the Moore bound is
approximated fraction Šoltés’ vertices.

###### Proof.

Assume such a graph $G$ exists, for girth $g=2k$. Remember that
$N(7,g)=2\sum_{i=0}^{k-1}6^{i}=2\frac{6^{k}-1}{6-1}=2\frac{6^{k}-1}{5}.$ Let
$uv$ be an edge of $G$. Note that the edges at distance at most $k-1$ from
either $uv$ in the line graph of $G$ span a tree $T$ (in $G$, with internal
vertices having degree $7$).

Let $G^{\prime}=A(G)$ be the arc-graph of $G.$ This graph is vertex-
transitive, since $G$ was arc-transitive.

Due to the girth condition of $G$, every cycle in $G^{\prime}$ that is not
part of a $K_{7}$, has length at least $2g.$ For every $2$ vertices
$w_{1},w_{2}$ in $G^{\prime}$ for which the shortest path (which has length
$i$) between them uses a vertex $v^{\prime}\in V(G^{\prime})$, the shortest
path between them in $G\setminus v^{\prime}$ has length at least $2g-i.$ If
$i\leq g-1,$ we know that this was initially the unique shortest path. Thus
the difference of distances changed by at least $(2g-i)-i=2(g-i)$. Let
$u^{\prime}$ be the unique neighbour of $v^{\prime}$ which is not part of the
same $K_{7}$. Now we can compute a lower bound for

$diff(G^{\prime},v^{\prime})=\sum_{w_{1},w_{2}\in G^{\prime}\setminus
v^{\prime}}d_{G^{\prime}\setminus
v^{\prime}}(w_{1},w_{2})-d_{G^{\prime}}(w_{1},w_{2})$

by counting the number of pairs of vertices whose shortest paths use
$v^{\prime}$ and are at distance less than $g$ initially. Let $N_{u^{\prime}}$
be the set of vertices which are closer to $u^{\prime}$ than to $v^{\prime}$,
and similarly $N_{v^{\prime}}=\\{w\in V(G^{\prime})\colon
d_{G^{\prime}}(w,v^{\prime})<d_{G^{\prime}}(w,u^{\prime})\\}.$ Let
$N_{v^{\prime}}^{i}=\\{w\in N_{v^{\prime}}\colon d(v^{\prime},w)=i\\}$ and
define $N_{u^{\prime}}^{i}$ analogously. Note that $\left\lvert
N_{v^{\prime}}^{j}\right\rvert=6^{\mathopen{}\left\lceil\frac{j}{2}\right\rceil\mathclose{}}$
for every $0\leq j\leq g.$ The number of pairs of vertices at even distance,
$2i+2<g$, whose shortest path between them uses $v^{\prime}$, is now equal to

$\sum_{j=0}^{2i}\left\lvert N_{u^{\prime}}^{j}\right\rvert\left\lvert
N_{v^{\prime}}^{2i+1-j}\right\rvert=(2i+1)\cdot 6^{i+1}.$

Similarly, for odd distance $2i+1$, we get

$\sum_{j=0}^{2i-1}\left\lvert N_{u^{\prime}}^{j}\right\rvert\left\lvert
N_{v^{\prime}}^{2i-j}\right\rvert=i\cdot(6^{i}+6^{i+1})=7i\cdot 6^{i}.$

This results in

$\displaystyle diff(G^{\prime},v^{\prime})$ $\displaystyle\geq
2\sum_{i=0}^{k-2}(2i+1)\cdot 6^{i+1}\cdot(g-(2i+2))+2\sum_{i=1}^{k-1}7i\cdot
6^{i}\cdot(g-(2i+1))$ $\displaystyle=2\frac{6^{k}(365k-606)+840k+606}{125}$

Let $N:=N(7,g)$. Note that $G$ has diameter bounded by $g$ (if not, take two
edges at maximum distance and consider the two neighbourhoods of them, up to
distance $k-1$). Hence $diam(G^{\prime})\leq 2g=4k.$ For any $v^{\prime}\in
V(G^{\prime})$, we can approximate that

$\displaystyle\sigma(v^{\prime})=\sum_{w\in G^{\prime}}d(w,v^{\prime})$
$\displaystyle\leq 2g\cdot 7\cdot 0.0005N+\sum_{i=0}^{g-1}\left(\left\lvert
N_{u^{\prime}}^{i}\right\rvert(i+1)+i\left\lvert
N_{v^{\prime}}^{i}\right\rvert\right)$
$\displaystyle=0.007gN+1+\sum_{i=1}^{k-1}(6^{i}\cdot 8i)+6^{k}\cdot(4k-1)$
$\displaystyle=0.014kN+\frac{8}{25}\left((5k-6)6^{k}+6)\right)+6^{k}(4k-1)$
$\displaystyle<\frac{0.14k6^{k}}{25}+\frac{6^{k}(140k-73)+73}{25}$
$\displaystyle=\frac{6^{k}(700.7k-365)+365}{125}$

Here we have used that $\left\lvert
N_{u^{\prime}}^{2i-1}\right\rvert=\left\lvert
N_{u^{\prime}}^{2i}\right\rvert=\left\lvert
N_{v^{\prime}}^{2i-1}\right\rvert=\left\lvert
N_{v^{\prime}}^{2i}\right\rvert=6^{i}$ and $(2i-1)+2\cdot 2i+(2i+1)=8i$ when
$1\leq i\leq k-1.$

Finally, we notice that
$diff(G^{\prime},v^{\prime})-\sigma(v^{\prime})>10^{3}k^{2}$ since
$(29.3k-847)6^{k}-1680k-847>10^{6}k^{2}$ for $k\geq 29$ and that
$W(G^{\prime}\setminus
v^{\prime})-W(G^{\prime})=diff(G^{\prime},v^{\prime})-\sigma(v^{\prime}).$

The proof will now be essentially finished by the following claim.

######  Claim 9.

Let $G^{\prime}$ be a vertex-transitive graph and satisfy
$W(G^{\prime}\setminus v^{\prime})-W(G^{\prime})=x>16k^{2}$ for some
$k\in\mathbb{N}.$ Then we can append a tree to $u^{\prime}v^{\prime}$ of order
bounded by $\sqrt{2x}$ to form a graph $H$ satisfying $W(H\setminus w)-W(H)=0$
for every $w\in V(G^{\prime})$ for which
$d_{G^{\prime}}(u^{\prime}v^{\prime},w)=2k-1$.

###### Proof.

Choose the largest $\ell$ such that $\binom{\ell}{2}-\binom{2k}{2}\leq x.$
Note that $\ell\geq 4k.$ Let $y=x+\binom{2k}{2}-\binom{\ell}{2}.$ If $y=0$ or
$2k+1\leq y,$ we append a path $P_{\ell}$ to $G^{\prime}$ by connecting one
end vertex of the path to both $u^{\prime}$ and $v^{\prime}$ and connect an
additional pendent vertex to the path, such that its distance to $u^{\prime}$
and $v^{\prime}$ equals $y-(2k-1).$ If $0<y<2k+1,$ append a path $P_{\ell-1}$
to $G^{\prime}$ as before, and add two vertices such that the sum of their
distances to $u^{\prime}$ and $v^{\prime}$ equals $\ell-1+y-2(2k-1).$ Let the
added tree be denoted with $T$. Now for every $w\in V(G^{\prime})$ with
$d_{G^{\prime}}(u^{\prime}v^{\prime},w)=2k-1$,

$W(H\setminus w)-W(H)=W(G^{\prime}\setminus w)-W(G^{\prime})-\sum_{z\in
V(T)}d_{H}(w,z)=0.\qed$

Since $x$ is clearly bounded by
$\sigma_{G^{\prime}}(w)=\sigma(w^{\prime})<2g\cdot 8N,$ the number of vertices
in $T$ is small.

There are $2\cdot 6^{k}$ vertices $w$ in $G^{\prime}$ for which
$d_{G^{\prime}}(u^{\prime}v^{\prime},w)=2k-1$. Now $\frac{2\cdot
6^{k}}{\left\lvert V(H)\right\rvert}\geq\frac{2\cdot
6^{k}}{7.0035N(7,g)+\left\lvert V(T)\right\rvert}\sim\frac{5}{7.0035}.$ ∎

So far, $8$ explicit examples of $\frac{2}{3}$\- Šoltes’ graphs have been
found after performing multiple searches. They are listed and verified in [4,
doc. 2_3_Soltesgraphs].

They contain the example on $12$ vertices in Fig. 2 (left) mentioned in [1,
6], an example Fig. 5 on $69$ vertices first discovered by Kurt Klement
Gottwald and Snježana Majstorović Ergotić (some years ago) and an example Fig.
4 on $60$ vertices found by Jorik Jooken.

The ones of order $69$ and $384$ are derived from subdiving some edges of
vertex-transitive graphs. The ones of order $60,90,180,300$ by adding new
vertices which are connected to the end vertices of a perfect matching (an
edge orbit) of the cubic vertex-transitive graphs which can be found on
https://houseofgraphs.org/graphs by their graph Id’s $36462,36702,38064$ and
$41433$.

##  4 Counterarguments to the present conjectures on Šoltés’ graphs

When [2, conj. 4.2] suggested that $C_{11}$ may be the only Šoltés’ graph,
they did so based on the limited progress on fractional Šoltés’ graphs. In [1]
and [6], there has been proven that there are infinitely many graphs for which
roughly half of the vertices are Šoltés’ vertices. This seems the best one can
do when aiming for an infinite family of graphs for which the Šoltés’ vertices
span a $2$-regular graph and the graph has an analogous simple structure. A
few examples of $\frac{2}{3}$ and plausibly higher (conditional proof with the
conditions being related to the hard problem on determining the order of
cages, see e.g. [7]) were given in Section 3. See Fig. 2 for the only two
graphs of order bounded by $12$ different from $C_{11}$, with at least half of
the vertices being Šoltés’ vertices. Depending on the beliefs of the behaviour
for large order, one may even expect that there also graphs with a
$\frac{8}{9}$-fraction of the vertices being Šoltés’ vertices (considering the
arc-graph of an arc-transitive $8$-regular graph and connect the vertices of
each $K_{8}$ with a new vertex).

Figure 2: The unique graphs on 12 vertices with 8 and 6 Šoltés’ vertices,
respectively.

The other argument in [2] was the verification of some small vertex-transitive
graphs, none of them being a Šoltés’ graph. Noting that $W(C_{n})=W(P_{n-1})$
implies $n=11$, one can focus on the graphs with minimum degree at least $3.$
The following (near-)corollary of 5 and 4 indicates that the transmission of a
vertex is larger than the sum of few additional detours among the other pairs
for the dense graphs.

######  Corollary 10.

There is no vertex-transitive graph $G$ of order $n\leq 47$ and $\delta(G)\geq
3$ for which $W(G)\leq W(G\setminus v)$ for $v\in V(G).$

###### Proof.

By 5 and 4, we can exclude the examples with diameter bounded by $3.$ The
remaining examples (around $17000$) from the census [9] can be verified as
well by direct verification. Since the vertex-connectivity of a $d$-regular
vertex-transitive graph is at least $\frac{2}{3}(d+1)$ (see proof of [16, Thm.
3]) and thus $n\geq\sum_{1\leq i\leq 4}\left\lvert N_{i}\right\rvert\geq
2(d+1)+\frac{2}{3}(d+1),$ also the diameter did not have to be checked for all
graphs of the census to deduce the list of the graphs with diameter at least
$4.$ This is done in [4, doc. VT47]. ∎

By [4, doc. arcgraph10000], we know meanwhile that there are many vertex-
transitive graphs for which $\delta(G)>2$ and $W(G)\leq W(G\setminus v)$ and
the argument of 10 thus does not extend.

Next, we prove that there are counterexamples to some of the most natural
conjectures for the variant of 1, by giving two families of non-regular graphs
(which are thus not vertex-transitive nor a Cayley graph) for certain $z.$

######  Proposition 11.

There are non-regular graphs $G$ and values $z$ satisfying $W(G)-W(G\setminus
v)=z$ for every $v\in V(G).$ Hereby the number of orbits or $\Delta-\delta$
can be unbounded.

###### Proof.

Our first example consists of a circular ladder $CL_{2k+4}$ (two cycles
$C_{2k+4}$ connected with a perfect matching), for which we add replace two
opposite $C_{4}$s by $K_{4}$s (i.e., add $4$ additional edges). An example for
$k=1$ is depicted in Fig. 3 (left). This graph has
$\mathopen{}\left\lceil\frac{k}{2}\right\rceil\mathclose{}+1$ many vertex
orbits. The initial circular ladder is a planar graph, which can be drawn with
an inner- and outer cycle $C_{2k+4}$. Removing the edges of the two $K_{4}$s,
we would obtain two components. We call the vertices of these components the
left and the right vertices. The transmission for all vertices is the same.
For any left vertex of the outer cycle, the sum towards the other vertices on
the outer cycle, is fixed (no shortest paths use vertices at the inner cycle).
The ones to the inner cycle are within the same distance as their copies on
the outer cycle, except that for the left ones the distance is one larger.
Thus
$\sigma(v)=\mathopen{}\left\lfloor\frac{(2k+4)^{2}}{4}\right\rfloor\mathclose{}+(k+2).$
Let the outer left vertices be $v_{0}$ (a $4$-vertex) up to $v_{k+1}.$ Let the
outer right vertices be $w_{0}\ldots w_{k+1}$ in a symmetric way. Let
$v^{\prime}_{i}$ and $w^{\prime}_{i}$ denote the inner vertices. Now removing
the vertex $v_{i}$, implies that the distance between $v_{j}$ and $v_{m}$
where $0\leq j<i<m\leq k+1$ increases by two. The distance between $v_{j}$ and
$w_{m}$ (or $w^{\prime}_{m}$) increases by one, if $j+m>k+1$ and $j<i$.
Analogously for $v_{m}$ and $w_{j}$ when $m>i.$ This implies that the sum of
increases in the distance equals

$2i(k+1-i)+2\sum_{j=1}^{i-1}j+2\sum_{j=1}^{k-i}=k^{2}+k.$

Since both the transmission and difference in distances is independent of $i$,
and by symmetry between left and right, as well as inner and outer, we
conclude.

Now we consider a second family, where the irregularity can be arbirarily
large, i.e. $\Delta(G)-\delta(G)=k$ for every $k>0.$ Let $n=2k+2$. Let $A_{0}$
and $A_{3}$ be sets of $k$ vertices, $B_{1}$ and $B_{2}$ be both sets of order
$3n$ spanning $n$ triangles. Let $G[A_{0},B_{1}]$ and $G[A_{3},B_{2}]$ be
complete bipartite. Here $G[U,V]$ denotes the subgraph of $G$ spanned by
$U\cup V$ with only edges $uv$, where $u\in U,v\in V$, present. For every pair
of a triangle $T_{1}$ in $B_{1}$ and a triangle $T_{2}$ in $B_{2}$, add a
$C_{6}$ in between (i.e., let $G[T_{1},T_{2}]\cong C_{6}$). It is easy to see
that every $2$ vertices have at least two disjoint shortest paths in between
them. To conclude, we only need to prove that the transmission of every vertex
$v$, $\sigma(v)=\sum_{u\in V}d(v,u)$, is equal. For a vertex $v$ in
$A_{0},A_{3}$, since it has eccentricity $3$, we easily compute that
$\sigma(v)=\sum_{i=1}^{3}i\cdot\left\lvert
N_{i}(v)\right\rvert=3n+2\cdot(3n+k-1)+3\cdot k=9n+5k-2.$ Here
$N_{i}(v)=\\{u\in V\mid d(u,v)=i\\}.$ Every vertex in $B_{1}\cup B_{2}$ has
eccentricity $2$ and degree $k+2+2n=3n-k.$ Its transmission thus equals
$2(6n+2k-1)-(3n-k)=9n+5k-2=23k+16.$ An example for $k=1$ is depicted in Fig. 3
(right). ∎

Figure 3: Non-regular graphs on $12$ and $26$ vertices resp. for which
$W(G)-W(G\setminus v)$ is independent of $v$

Nevertheless, these examples are constructed in such a way that the distances
in $G\setminus v$ barely change, which implies that $W(G)-W(G\setminus v)$ is
large. We give an example of a non-vertex-transitive graphs for which
$W(G)-W(G\setminus v)$ is fixed and small compared with its order.

######  Example 12.

The arc-graph of https://houseofgraphs.org/graphs/19281 has order $320$ is
non-vertex-transitive graphs and satisfies $W(G)-W(G\setminus v)=40$ for every
$v\in V(G).$ This is verified in [4, doc. Nonvertex-transitive].

Checking graphs with two orbits, there are many for which $W(G)-W(G\setminus
v)$ is independent of $v$. Almost all connected large graphs with few orbits
are at least $2$-connected. If there is no restriction on the sign of
$W(G)-W(G\setminus v)$, as this difference is bounded by $-n^{3}$ and $n^{3}$,
one may expect that there are both vertex-transitive and non-vertex-transitive
(and thus not Cayley graphs) Šoltés’ graphs. The latter is the case if there
are $d$-regular (for $3\leq d\leq 7$) arc-transitive graphs with large girth
$g$ near the Moore bound $N(d,g)$.

##  5 Conclusion

The problem of Šoltés, due to its charming simplicity, has intrigued many
people and resulted in over a $100$ citing papers in the past. In this paper,
we gave indications why some of the current conjectures were not well-founded
and may be false. Furthermore, the research lead to the following key
question.

######  Question 13.

Are there infinitely many negative-Šoltés’ graphs?

We conjecture that if this question has an affirmative answer , for every
$z\in\mathbb{Z},$ there are infinitely many graphs $G$ for which
$W(G)-W(G\setminus v)=z$ for every $v\in V(G)$ and among them, there are also
non-vertex-transitive ones. As an analogy, we refer to the conjecture of
Heath-Brown on solutions of the Diophantine equation $x^{3}+y^{3}+z^{3}=k$,
which says that there are infinitely many solutions whenever $k\not\equiv\pm
4\pmod{9}$ (i.e., when there is no simple reason of non-existence). Also for
this somewhat computationally simpler question, it has taken a while to find
large solutions $(x,y,z)\in\mathbb{Z}^{3}$ for some values $k$, see e.g. [3].

If there is a value $n_{0}$ such that every graph $G$ of order $n\geq n_{0}$
satisfies $W(G)>W(G\setminus v)$ for $v\in V(G)$, (no negative-Šoltés’ graph
exists with order at least $n_{0}$), we know that $n_{0}$ is much larger than
$10^{4}$ by [4, doc. arcgraph10000]. Under the existence of $n_{0}$,
addressing the problem of Šoltés will need ideas to determine or exclude the
Šoltés’ graphs with order bounded by $n_{0}.$ When 13 has a negative answer,
the number of solutions for 1 may be approximately increasing over positive
$z$.

Related to 13, one can also ask the extremal question on a good lower bound
for $W(G)-W(G\setminus v)$ for vertex-transitive graphs of order $n$ and
degree $d$. Checking the census on cubic vertex-transitive graphs up to $1280$
vertices [12], we note that there are only a few dozens of negative-Šoltés’
graph among them and all of these are arc-graphs, giving a direction for the
extremal question. Hereby we formulate the following related question for
general graphs.

######  Question 14.

A graph $G$ for which $W(G)\leq W(G\setminus v)$ for all $v\in V(G)$ has
minimum degree upper bounded by $7?$

## Acknowledgments

The author thanks Marston Conder, Jorik Jooken, Snježana Majstorović Ergotić
and Dragan Stevanović for discussions and informing on references and state-
of-the-art results.

## References

  * [1] M. Akhmejanova, K. Olmezov, A. Volostnov, I. Vorobyev, K. Vorob’ev, and Y. Yarovikov.  Wiener index and graphs, almost half of whose vertices satisfy šoltés property.  Discrete Appl. Math., 325:37–42, 2023.
  * [2] N. Bašić, M. Knor, and R. Škrekovski.  On regular graphs with Šoltés vertices.  Ars Mathematica Contemporanea.
  * [3] A. R. Booker and A. V. Sutherland.  On a question of mordell.  Proceedings of the National Academy of Sciences, 118(11):e2022377118, 2021.
  * [4] S. Cambie.  Code and data for the paper “towards the essence of šoltés’ problem”.  https://github.com/StijnCambie/Soltes/tree/main/SoltesGraphs, 2024.
  * [5] S. Cambie.  Šoltés’ hypergraphs.  arXiv e-prints, page arXiv:2406.01504, June 2024.
  * [6] A. A. Dobrynin and K. V. Vorob’ev.  Some results on the Wiener index related to the šoltés problem of graphs.  Discrete Appl. Math., 344:154–160, 2024.
  * [7] G. Exoo, R. Jajcay, M. Mačaj, and J. Širáň.  On the defect of vertex-transitive graphs of given degree and diameter.  J. Combin. Theory Ser. B, 134:322–340, 2019.
  * [8] T. Hasunuma.  Structural properties of subdivided-line graphs.  J. Discrete Algorithms, 31:69–86, 2015.
  * [9] D. Holt and G. Royle.  A census of small transitive groups and vertex-transitive graphs.  J. Symb. Comput., 101:51–60, 2020.
  * [10] M. Knor, R. Škrekovski, and A. Tepeh.  Selected topics on wiener index, 2023.
  * [11] F. Lazebnik, V. A. Ustimenko, and A. J. Woldar.  New upper bounds on the order of cages.  Electron. J. Comb., 4(2):research paper r13, 11, 1997.
  * [12] P. Potočnik, P. Spiga, and G. Verret.  Cubic vertex-transitive graphs on up to 1280 vertices.  J. Symb. Comput., 50:465–477, 2013.
  * [13] P. Potočnik, P. Spiga, and G. Verret.  Asymptotic enumeration of vertex-transitive graphs of fixed valency.  J. Combin. Theory Ser. B, 122:221–240, 2017.
  * [14] L. Šoltés.  Transmission in graphs: a bound and vertex removing.  Mathematica Slovaca, 41(1):11–16, 1991.
  * [15] S. Spiro.  The Wiener index of signed graphs.  Appl. Math. Comput., 416:10, 2022.  Id/No 126755.
  * [16] M. E. Watkins.  Connectivity of transitive graphs.  J. Combinatorial Theory, 8:23–29, 1970.

##  Appendix A Presentation of examples of $\frac{2}{3}$-Šoltés’ hypergraphs

The smallest new example is a graph formed by a $C_{40}$ on $[40]$, with
additional edges between $i$ and $i+11$ if $i\equiv 1\pmod{4}$ and between $i$
and $i+9$ if $i\equiv 2\pmod{4}$, together with an additional vertex connected
to $i$ and $i+1$ for $2\mid i.$ Here indices are considered modulo $40$.

Figure 4: A graph of order $60$ with $40$ Šoltés’ vertices

Figure 5: A graph of order $69$ with $46$ Šoltés’ vertices ($2$
representations) Figure 6: A graph of order $90$ with $60$ Šoltés’ vertices


# A Generalisation of Euler’s Totient Function

Vlad Robu  Faculty of Mathematics and Informatics
University of Bucharest, Academiei st. 14, Bucharest, Romania
<EMAIL_ADDRESS>
###### Abstract.

Euler’s totient function, $\varphi(n)$, which counts how many of
$0,1,\dots,n-1$ are coprime to $n$, has an explicit asymptotic lower bound of
$n/\log\log n$, modulo some constant. In this note, we generalise $\varphi$;
given an irreducible integer polynomial $P$, we define the arithmetic function
$\varphi_{P}(n)$ that counts the amount of numbers among
$P(0),P(1),\dots,P(n-1)$ that are coprime to $n$. We also provide an
asymptotic lower bound for $\varphi_{P}(n)$.

###### Key words and phrases:

Euler’s totient function, Mertens’ third theorem, irreducible integer
polynomial, asymptotic lower bound, Frobenius density theorem,
natural/Dirichlet density

###### 2020 Mathematics Subject Classification:

11C08, 11N37

##  1\. Introduction and Preliminary Remarks

Throughout the entire text, $p$ is intended to be a prime number. For
functions $f,g:\mathbb{R}\to\mathbb{R}_{>0}$, we say that $f\sim g$ if
$\displaystyle\lim_{x\to\infty}f(x)/g(x)=1$.

We start by recalling the following result, which is due to Mertens:

######  Theorem 1.1 (Mertens’ third theorem).

We have that

$\prod_{\begin{subarray}{c}p\leq
x\end{subarray}}\left(1-\frac{1}{p}\right)\sim\frac{e^{-\gamma}}{\log x},$

where $\gamma$ is the Euler-Mascheroni constant,
$\gamma=\displaystyle\lim_{n\to\infty}\left(H_{n}-\log n\right)$.

Based on this, a quick lower bound for $\varphi(n)$ can be established
asymptotically, where $\varphi$ indicates the Euler totient function. Indeed,
we know that [1]

$\frac{\varphi(n)}{n}=\prod_{p\mid
n}\left(1-\frac{1}{p}\right)=\prod_{\begin{subarray}{c}p\mid n\\\ p\leq\log
n\end{subarray}}\left(1-\frac{1}{p}\right)\prod_{\begin{subarray}{c}p\mid n\\\
p>\log n\end{subarray}}\left(1-\frac{1}{p}\right).$

The second product cannot have more than $\log n/\log\log n$ factors. Thus it
is bounded below by $\displaystyle\left(1-\frac{1}{\log n}\right)^{\log
n/\log\log n}$, which goes to $1$ (from below) as $n$ goes to infinity. The
first product is bounded below by $\displaystyle\prod_{p\leq\log
n}\left(1-\frac{1}{p}\right)\sim\frac{e^{-\gamma}}{\log\log n}$. Overall, we
obtain that $\displaystyle\varphi(n)$ is bounded below by a quantity
asymptotically similar to $\displaystyle e^{-\gamma}\cdot\frac{n}{\log\log
n}$. In this note, we are going to generalise $\varphi$ and also provide a
lower bound for the generalised version; however, by contrast to the case of
the usual $\varphi$, the constants that appear in front will not be explicit.

Mertens’ third theorem can be rapidly generalised. Let us take a look at the
asymptotics of the quantity $\displaystyle\prod_{d<p\leq
x}\left(1-\frac{d}{p}\right)$ in terms of $x$, where $d$ is a fixed positive
integer. The whole trick is that it can be connected to the product in
Mertens’ third theorem via the convergent product [2]

$\mathcal{G}_{d}=\prod_{p>d}\left(1-\frac{d}{p}\right)\left(1-\frac{1}{p}\right)^{-d}.$

Indeed, $\mathcal{G}_{d}$ converges, because we can write
$\displaystyle\log\mathcal{G}_{d}=\sum_{p>d}\left(\log\left(1-\frac{d}{p}\right)-d\log\left(1-\frac{1}{p}\right)\right)$.
As $\log(1-x)=-x+O(x^{2})$, we get that
$\displaystyle\log\left(1-\frac{d}{p}\right)-d\log\left(1-\frac{1}{p}\right)=O\left(\frac{1}{p^{2}}\right)$,
so the fact that $\displaystyle\sum_{p}\frac{1}{p^{2}}<\infty$ finishes it.
With this,

$\displaystyle\prod_{d<p\leq x}\left(1-\frac{d}{p}\right)$
$\displaystyle=\prod_{p\leq d}\left(1-\frac{1}{p}\right)^{-d}\cdot\prod_{p\leq
x}\left(1-\frac{1}{p}\right)^{d}\cdot\prod_{d<p\leq
x}\left(1-\frac{d}{p}\right)\left(1-\frac{1}{p}\right)^{-d}\sim$
$\displaystyle\sim\prod_{p\leq
d}\left(1-\frac{1}{p}\right)^{-d}\cdot\frac{e^{-d\gamma}}{(\log
x)^{d}}\cdot\mathcal{G}_{d}.$

Let us continue with some notes on Galois theory. Consider an irreducible
polynomial $f$ with integer coefficients, with splitting field $K$ and Galois
group $G$; also, let $n=\deg f$ be the degree of $f$. We view $G$ in the usual
manner, as a group of permutations on the roots of $f$, embedded in $S_{n}$.

The following two results establish a strong connection between the cycle
decomposition of permutations in $G$ and the way $f$ decomposes modulo primes
$p$.

######  Theorem 1.2 (Dedekind).

(see e.g. [3] or theorem 8.23 from [4]) Consider a prime $p$ that does not
divide the discriminant of $K$. If $f$ decomposes in $\mathbb{Z}_{p}[X]$ as
$\displaystyle f=\prod_{i=1}^{t}f_{i}$, then $G$ contains at least one
permutation which is the product of $t$ disjoint cycles of lengths
$n_{1},\dots,n_{t}$, where $n_{i}$ is the degree of $f_{i}$.

######  Theorem 1.3 (Frobenius density theorem).

(see e.g. [3] or [5], p. 11) If $G$ contains a permutation $\sigma$ which is
the product of disjoint cycles of length $n_{1},\dots,n_{t}$, then there
exists an infinite set $P_{\sigma}$ of primes such that for any $p\in
P_{\sigma}$, the decomposition of $f$ modulo $p$ has the following structure:
$\displaystyle f=\prod_{i=1}^{t}f_{i}$, where $f_{i}$ is a polynomial in
$\mathbb{Z}_{p}[X]$ of degree $n_{i}$, for all $i\in\\{1,2,\dots,t\\}$.

Moreover, the set $P_{\sigma}$ has natural density equal to $1/\left\lvert
G\right\rvert$ times the number of permutations $\sigma$ of $G$ with cycle
decomposition type $(n_{1},\dots,n_{t})$.

We will be especially interested in the latter, as it will allow us to find
the exact asymptotics of some products along the way.

Before finally moving to the main stage, let us recall the following

######  Proposition 1.4.

$G$ acts transitively on the set of roots of $f$, since $f$ is irreducible.
Therefore, the number of automorphisms of $G$ that fix a given root of $f$ is
the same for all roots of $f$.

##  2\. Main Result

######  Theorem 2.1.

Consider a nonconstant irreducible polynomial $P\in\mathbb{Z}[X]$ of degree
$d=\deg P$ and define $\delta=\displaystyle\gcd_{k\geq 0}P(k)$. Let
$G\hookrightarrow S_{d}$ be the Galois group of $P$ over $\mathbb{Q}$ and also
let $q$ be the proportion of permutations in $G$ that fix a given root of $P$.
Then there exists a constant $c>0$, such that for all $\varepsilon>0$ and all
$n\in\mathbb{Z}_{\geq 2}$ with $\gcd(n,\delta)=1$ that are greater than some
$n(\varepsilon)$, among

$P(0),P(1),P(2),\dots,P(n-1)$

there are at least $cn\cdot\left(\log\log n\right)^{-qd-\varepsilon}$ numbers
relatively prime to $n$.

###### Proof of Theorem 2.1.

Denote by $\varphi_{P}(n)$ as the number of integers among $P(0)$, $P(1)$,
$P(2)$, $\dots$, $P(n-1)$ which are relatively prime to $n$, for all
$n\in\mathbb{Z}_{\geq 2}$. Also, define by $f(n)$ the number of multiples of
$n$ among $P(0)$, $P(1)$, $P(2)$, $\dots$, $P(n-1)$, for all
$n\in\mathbb{Z}_{\geq 2}$. We have the following

######  Lemma.

With the above mentioned notations,

$\varphi_{P}(n)=n\prod_{\begin{subarray}{c}p|n\end{subarray}}\left(1-\frac{f(p)}{p}\right).$

For a proof of the lemma, see e.g. [6], pp. 404-405. So we have to work on the
product

$\frac{\varphi_{P}(n)}{n}=\prod_{\begin{subarray}{c}p\mid
n\end{subarray}}\left(1-\frac{f(p)}{p}\right).$

Let $d=\deg P$ and consider from now on only positive integers $n>e^{d+1}$.
Also, fix some small $\varepsilon>0$. Then we can split our product into $3$
parts:

$\displaystyle\frac{\varphi_{P}(n)}{n}$
$\displaystyle=\prod_{\begin{subarray}{c}p\mid n\\\ p\leq
d\end{subarray}}\left(1-\frac{f(p)}{p}\right)\cdot\prod_{\begin{subarray}{c}p\mid
n\\\ d+1\leq p<\log
n\end{subarray}}\left(1-\frac{f(p)}{p}\right)\cdot\prod_{\begin{subarray}{c}p\mid
n\\\ p\geq\log n\end{subarray}}\left(1-\frac{f(p)}{p}\right)=$
$\displaystyle=\Pi_{1}\Pi_{2}\Pi_{3}.$

For $p\leq d$ that divides $n$, since $\gcd(\delta,n)=1$, it follows that not
all of the numbers $P(i)$, $i=\overline{0,p-1}$, are divisible by $p$, hence
$f(p)\leq p-1$. Consequently, $\displaystyle\Pi_{1}\geq\prod_{p\leq
d}\frac{1}{p}$.

If $p\geq d+1$, then the equation $P(k)=0$ cannot have more than $\deg P=d$
solutions modulo $p$. Consequently, $f(p)\leq d$.

In the prime decomposition of $n$, if $k$ is the number of distinct prime
factors exceeding $\log n$, then $n\geq(\log n)^{k}$, so
$k\leq\displaystyle\frac{\log n}{\log\log n}$. It follows that
$\Pi_{3}\geq\displaystyle\prod_{\begin{subarray}{c}p\mid n\\\ p\geq\log
n\end{subarray}}\left(1-\frac{d}{p}\right)\geq\left(1-\frac{d}{\log
n}\right)^{\frac{\log n}{\log\log n}}\sim e^{-\frac{d}{\log\log n}}\geq 0.99$
for all sufficiently large positive integers $n$.

For $\Pi_{2}$, we need to be a bit more careful when dealing with the
$f(p)$’s. If we define $g(p)$ the number of roots $P$ has modulo $p$, we
obviously have $f(p)\leq g(p)$, as $f(p)$ counts only the number of distinct
roots modulo $p$. For each $k\in\\{0,1,\dots,d\\}$, define $P_{k}=g^{-1}(k)$
to be the set of those primes $p>d$ such that $g(p)=k$. Then, by writing
$x=\log n$, we more generally look at the quantity

$\Pi_{2}\geq\Pi_{2}^{\prime}=\prod_{k=0}^{d}\prod_{\begin{subarray}{c}d<p\leq
x\\\ p\in P_{k}\end{subarray}}\left(1-\frac{k}{p}\right).$

Now, if we define
$\displaystyle\mathcal{G}_{d,k}=\prod_{\begin{subarray}{c}p>d\\\ p\in
P_{k}\end{subarray}}\left(1-\frac{k}{p}\right)\left(1-\frac{1}{p}\right)^{-k}$,
in a similar manner to establishing the convergence of $\mathcal{G}_{d}$, we
get that $\mathcal{G}_{d,k}$ is convergent too, for all
$k\in\\{0,1,\dots,d\\}$. Consequently,

$\displaystyle\Pi_{2}^{\prime}$
$\displaystyle=\prod_{k=0}^{d}\prod_{\begin{subarray}{c}d<p\leq x\\\ p\in
P_{k}\end{subarray}}\left(1-\frac{k}{p}\right)=$
$\displaystyle=\prod_{k=0}^{d}\left(\prod_{\begin{subarray}{c}d<p\leq x\\\
p\in
P_{k}\end{subarray}}\left(1-\frac{k}{p}\right)\left(1-\frac{1}{p}\right)^{-k}\right)\cdot\prod_{k=0}^{d}\left(\prod_{\begin{subarray}{c}d<p\leq
x\\\ p\in P_{k}\end{subarray}}\left(1-\frac{1}{p}\right)\right)^{k}\sim$
$\displaystyle\sim\prod_{k=0}^{d}\left(\mathcal{G}_{d,k}\cdot\prod_{p\leq
d}\left(1-\frac{1}{p}\right)^{-k}\right)\cdot\prod_{k=0}^{d}\left(\prod_{\begin{subarray}{c}p\leq
x\\\ p\in P_{k}\end{subarray}}\left(1-\frac{1}{p}\right)\right)^{k}.$

Therefore, we are interested in the asymptotics of
$\displaystyle\prod_{\begin{subarray}{c}p\leq x\\\ p\in
P_{k}\end{subarray}}\left(1-\frac{1}{p}\right)$. For $p\in P_{k}$, $g(p)=k$
means that the polynomial $P$ has exactly $k$ roots modulo $p$, counted with
multiplicity. By Frobenius’ Density Theorem, we know that $P_{k}$ has natural
density $\alpha_{k}=\beta_{k}/\left\lvert G\right\rvert$, where $\beta_{k}$
counts the number of permutations in $G$ that have exactly $k$ fixed points.
This implies that

$\lim_{x\to\infty}\frac{\sum_{\begin{subarray}{c}p\in P_{k},~{}p\leq
x\end{subarray}}1/p}{\sum_{p\leq x}1/p}=\alpha_{k}.$

So, for all sufficiently large $x$, we have that $\displaystyle\sum_{p\leq
x,~{}p\in P_{k}}1/p<(\alpha_{k}+\varepsilon/kd)\log\log x$. It follows that
$\displaystyle\sum_{\begin{subarray}{c}p\leq x\\\ p\in
P_{k}\end{subarray}}\log\left(1-\frac{1}{p}\right)=-\sum_{\begin{subarray}{c}p\leq
x\\\ p\in
P_{k}\end{subarray}}\frac{1}{p}+O(1)\geq-(\alpha_{k}+\varepsilon/kd)\log\log
x+O(1)$, so $\displaystyle\prod_{\begin{subarray}{c}p\leq x\\\ p\in
P_{k}\end{subarray}}\left(1-\frac{1}{p}\right)\geq c_{k}\cdot(\log
x)^{-\alpha_{k}-\varepsilon/kd}$, where $c_{k}$ is a constant that does not
depend on $\varepsilon$. Consequently,

$\Pi_{2}^{\prime}\sim C\cdot(\log
x)^{-\alpha_{1}-2\alpha_{2}-\dots-d\alpha_{d}-\varepsilon},$

where $C$ is a constant independent of $\varepsilon$, so we are left with
taking one more careful look at the quantity $\left\lvert
G\right\rvert(\alpha_{1}+2\alpha_{2}+\dots+d\alpha_{d})=\beta_{1}+2\beta_{2}+\dots+d\beta_{d}$.
Now, this sum counts the number of pairs $(\sigma,y)$, where $\sigma$ is an
element of the Galois group $G$ and $y$ is a fixed point of $\sigma$, by first
considering permutations of $G$. If we consider first the roots $y$ of $P$, we
see that we need to count how many automorphisms of $G$ fix $y$. As
established in 1.4, this number is the same for all roots. Therefore, the
exponent we just obtained can be put in the shape $-qd-\varepsilon$.

Finally, putting $\Pi_{1}$, $\Pi_{2}$ and $\Pi_{3}$ together, we obtain that
$\varphi_{P}(n)$ is bounded below by $cn\cdot(\log\log n)^{-qd-\varepsilon}$,
for all $n$ that are greater than some $n(\varepsilon)$. Moreover, we see that
the constant $\displaystyle c=C\cdot 0.99\cdot\prod_{p\leq d}\frac{1}{p}$
depends on $d=\deg P$ only, and it has nothing to do with $\varepsilon$. ∎

##  3\. Final Remarks

The extra $-\varepsilon$ that appears at the exponent of the lower bound comes
from the fact that we do not know how to express the sum
$\displaystyle\sum_{\begin{subarray}{c}p\in P_{k}\\\ p\leq
x\end{subarray}}\frac{1}{p}$ clean in terms of $\log\log x$. Dirichlet density
(which is implied by natural density) only goes this far.

A way to avoid $-\varepsilon$ is by directly using the bound $f(p)\leq d$ for
all large primes $p$. This way, the final lower bound would even have an
explicit constant, however the exponent would only be $-d$, which is weaker
than the result here.

A final question might arise, and that is: what if $q=1$? In that case, the
lower bound here would be even smaller than the safer one, with $-d$ as an
exponent.

If $q=1$ i.e. all automorphisms of $G$ fix all roots of $f$, then $G$ consists
only of the identity automorphism, meaning $K=\mathbb{Q}$. In that case, as
$P$ is irreducible, we would obtain that $P$ is of degree $1$. However, this
situation is very similar to the analysis of $\varphi(n)$ and consequently
gives the same lower bound as the one for $\varphi(n)$, since all the trouble
regarding the degree $d$ of $P$ is gone.

So the result presented here is especially relevant for $\deg P\geq 2$ as,
again, $\deg P=1$ could instead be put in the same situation as the classic
$\varphi$.

## References

  * [1] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, pp. 216-219, Archiv d. Math. u. Phys., 1909\.
  * [2] Y. Lagrida, The $k$-tuple conjecture, pp. 3-4, Hal open science, 2020\.
  * [3] R. Brandl, Integer Polynomials that are Reducible Modulo all Primes, pp. 286-288, The American Mathematical Monthly, 1986\.
  * [4] J. S. Milne, Algebraic Number Theory (v3.08), available at www.jmilne.org/math/, 2020\.
  * [5] P. Stevenhagen, H. W. Lenstra, Jr., Chebotarev and his density theorem, p. 11.
  * [6] T. Andreescu, C. Pohoață, O. Mushkarov, Number Theory: Concepts And Problems, XYZ Press, 2017\.


# REAL-TIME VISUALISATION OF FUGUE PLAYED BY A STRING QUARTET

###### Abstract

We present a new system for real-time visualisation of music performance,
focused for the moment on a fugue played by a string quartet. The basic
principle is to offer a visual guide to better understand music using
strategies that should be as engaging, accessible and effective as possible.
The pitch curves related to the separate voices are drawn on a space whose
temporal axis is normalised with respect to metrical positions, and aligned
vertically with respect to their thematic and motivic classification. Aspects
related to tonality are represented as well. We describe the underlying
technologies we have developed and the technical setting. In particular, the
rhythmical and structural representation of the piece relies on real-time
polyphonic audio-to-score alignment using online dynamic time warping. The
visualisation will be presented at a concert of the Danish String Quartet,
performing the last piece of _The Art of Fugue_ by Johann Sebastian Bach.

##  1 Introduction

In this article, we present a new project of real-time visualisation of music
performance. It is part of a broad objective, by the first author and
especially within the context of his _MIRAGE_
project111https://www.uio.no/ritmo/english/projects/mirage, to design tools to
make music more easy to understand and more engaging, especially for non-
expert listeners.

The presented project is focused on a String Quartet interpretation of the
last piece of _The Art of Fugue_ by Johann Sebastian Bach. In order to provide
a very rich musicological visualisation of the piece, we decided to prepare
the analysis in advance and to synchronise the live performance with the help
of score-following technologies.

The paper is organised as follows. Section 2 gives a brief overview of
previous works, including ours. Section 3 formalises the underlying principles
founding our proposed approach. Section 4 describes what the visualisation is
about, concretely. Section 5 details the underlying technical aspects and
especially the score-following approach.

In the following, a distinction needs to be made between pitch tra _ck_ ing
(detecting pitch height from audio, frame by frame, as described in Section
5.1) and pitch tra _c_ ing (drawing the pitch line in the visualisation, as
described in Section 4.1).

##  2 Previous Works in Music Visualisation

###  2.1 Brief State of the Art

There is a very large number of approaches that have been proposed for video
visualisation of music as it evolves along time. For instance, there has been
discussion about the application of music-colour synaesthetic mappings in live
ensemble performance [1]. A system architecture has been proposed to build
real-time music visualisations rapidly, with the view to provide a sense of
musical experience to the users [2].

###  2.2 Our Previous Works in Music Visualisation

This interest in music visualisation stems from the first author’s work in
audio and music feature extraction and especially the design of _MIRtoolbox_
[3]. This toolbox was initially conceived with the initial aim to better
understand the affective and emotional impact of music [4]. First video
visualisations were made in
2012222https://www.youtube.com/watch?v=H_SpFh2SPmg, so far focusing on timbral
and dynamical aspects of audio recordings. Another
visualisation333https://www.youtube.com/watch?v=8S7LyEkzWGE was aimed at
highlighting audio and musical features contributing to emotions dynamically
expressed by music [5]. Recently, we designed a new type of visualisation with
transformation of video shootings based on audio analysis, and applied to the
production of a music video444https://www.youtube.com/watch?v=L1FaxT74hTk.

##  3 General Philosophy

This visualisation project is guided by a few general desiderata, presented
below, that may look incompatible at first sight, due to conflicting
constraints. An additional principle addresses this conundrum.

###  3.1 Desiderata

####  3.1.1 Accessible and Self-Explanatory

The visuals should be understandable by a largest public. Hence no music
expertise should be required. In particular, music score representations
should not be displayed. The visuals should also be self-explanatory. No
verbal or text explanation should be necessary for the viewers to grasp the
logic.

####  3.1.2 Expressive while Thrifty

The visuals should be as impactful as possible while at the same time being
minimalist with regard to the use of visual strategies. For instance, there is
no need to use colors, forms or textures if they are not motivated by a
particular need to convey a particular musical characteristic.

####  3.1.3 Conveying the Richness of Music

One aspiration is to offer a visual equivalent of the way listeners — and
especially experienced music lovers — perceive, grasp and appreciate music
through their ears. Music is generally a rich experience consisting of a flow
of events appearing together or successively and building rich interactions.
Listeners are immersed by this flow of information, inciting to participate
and move with the music. One objective is to convey this experience visually.

###  3.2 Addressing Conflicts in the Desiderata

####  3.2.1 A Visual Complexity Assimilable Gradually

Clearly, describing the whole musical experience visually may lead to a very
complex representation that might be unfathomable at first sight. Although
complex stimuli might appeal to the spectators’ interest, in order to
correctly address desideratum 3.1.1, there should be a guiding thread within
the flow of stimuli that the spectator can rely on to progressively grasp what
is happening and discover little by little the logic of the whole
visualisation.

##  4 Visualisation scenario

The proposed scenario exploits the particular characteristics of string
quartet fugues , where each of the four instruments plays a monody and where
the subtle changes in pitch, dynamics and timbre play an important role. In a
fugue, a _subject_ — a musical theme — is introduced at the beginning in
imitation — i.e., repeated successively on each voice at different registers —
and reappears frequently in the course of the composition. The particular
piece under study, _Contrapunctus XIV_ , is actually structured into three
sections, each introducing a new subject.

###  4.1 Polyphonic Pitch Tra _c_ ing

Each instrument plays a single monodic line where successive notes are clearly
separated. The slow tempo and the rare use of small rhythmic values such as
sixteenth notes also contribute to the clarity of the melodic lines, and to a
focus on pitch, dynamic and timbral shaping of each successive notes. As such,
it seemed relevant to simply display pitch curves, resulting directly from the
temporal tracking of the fundamental frequency. The pitch curves are
progressively drawn from left ro right as time goes by. Each instrument
generates its own pitch curve.

####  4.1.1 Rhythm Quantisation

As we will see in Section 4.2, the pitch curves will be superposed so that
similar motives could be compared. For that reason, in order to allow their
temporal alignments, the horizontal axis directing the pitch curves needs to
be temporally quantised, in the sense that it should be graduated in rhythmic
values, as indicated in the score. The rhythmic quantisation of the live
performance is made possible thanks to score following capabilities, described
in section 5.2.

The fact that the tempo is not constant — and actually fluctuates a lot
throughout the piece — raises a technical issue: How to progressively draw a
pitch curve along this quantised axis if there is uncertainty concerning the
quantised position of each successive instant?

For each note, a hypothetical tempo — i.e. a duration in seconds for that note
— is inferred. In one strategy, $S_{1}$, the tempo is assumed to be constant,
and the hypothetical tempo is identified with the tempo related to the
previous note.

Another strategy, not considered here, would consist in measuring the tempo
variation throughout the piece for different performances of the same
musicians and use it as a guide for the tempo change expectation. If the tempo
changes are guessed correctly, they would first appear in the visualisation,
and it would look as if the performers follow the visuals, and in the other
case, the behavior of the visualisation might appear random, which might be
undesirable.

Let $t$ be the performance time and $x$ the time axis in the visualisation.
Let’s consider a note starting at time $t_{i}$ and ending at time $t_{i+1}$,
corresponding to the metrical positions located in abscissae $x_{i}$ and
$x_{i+1}$ . Let’s suppose that the chosen tempo for the visualisation is such
that the note is expected to end at time $t^{\prime}_{i+1}$. Three cases need
to be considered:

  * •

If the expected tempo is exact — i.e., $t^{\prime}_{i+1}=t_{i+1}$ —, the curve
is drawn in a simple way, by using the simple mapping $m_{t}$ defined, for
$t\in[t_{i},t_{i+1}]$ as

$m_{t}:\theta\in[t_{i},t]\mapsto x_{i}+\frac{\theta-
t_{i}}{t^{\prime}_{i+1}-t_{i}}(x_{i+1}-x_{i}),$ (1)

which means that the part of the curve already drawn does not modify along
time afterwards. It remains constant afterward, i.e., for $t\geq t_{i+1}$,

$m^{\prime}_{t}:\theta\in[t_{i},t_{i+1}]\mapsto x_{i}+\frac{\theta-
t_{i}}{t_{i+1}-t_{i}}(x_{i+1}-x_{i}),$ (2)

  * •

If the actual tempo is slower — i.e., $t^{\prime}_{i+1}<t_{i+1}$ —, the curve
is drawn in the same way until reaching the expected end of note
$t^{\prime}_{i+1}$, so equation 1 is valid for $t\in[t_{i},t^{\prime}_{i+1}]$.
On the other hand, once point $x_{i+1}$ has been reached, the mapping $m_{t}$
for $t\in[t^{\prime}_{i+1},t_{i+1}]$ becomes

$m^{\prime\prime}_{t}:\theta\in[t_{i},t]\mapsto x_{i}+\frac{\theta-
t_{i}}{t-t_{i}}(x_{i+1}-x_{i}),$ (3)

which means that curve is compressed to accommodate the rest of the note in
the same visual space. Once time $t_{i+1}$ is reached, the mapping stabilises
to equation 2.

  * •

If on the contrary the actual tempo is faster — i.e.,
$t^{\prime}_{i+1}>t_{i+1}$ —, the curve is drawn in the same way until
reaching the unexpected end of note $t_{i+1}$, so equation 1 is valid for
$t\in[t_{i},t_{i+1}[$. But as soon as the note is ended, the mapping is
corrected and from that point the mapping switches to equation 2. For the sake
of clarity following desideratum 3.1.1 and in order to avoid emphasizing
excessively this disruption, an abrupt change in the graphical representation
should be avoided, and the transition between mappings $m_{t}$ and
$m^{\prime}_{t}$ is shown progressively, in accordance with “fluid” design
principles.

####  4.1.2 Pitch Height Ordering

The disposition of pitch curves on the Y-axis is less of a problem, as a
simple conversion of frequencies on a logarithmic scale gives an adequate
representation. Besides, accurately representing the relative location in
pitch of each instrument enables to convey the registral differences.
Moreover, the rare cases of swapping of register order between voices (the
second violin crossing for instance the first violin and playing the highest
pitch for a few notes) can be immediately noticed in the visualisation. By
associating a different color with each instrument (for instance red for
cello, black for alto, blue for the second violin and orange for the first
violin), this makes this rare disruption in the natural ordering in pitch more
noticeable.

Vibrato, portamento and any other form of pitch deviation related to
performance are directly exhibited by the pitch curve, and additional
treatment to make them accessible to the viewers do not seem necessary in our
case.

The actual set of pitch heights used as implicit reference for the pitch space
defines both diatonic and chromatic scales. This would lead in theory to a
graduation of the pitch axis through a large set of horizontal lines.
Following desiderata 3.1.1, the display of the whole diatonic or chromatic
scale is avoided. Only pitches that are actualized are indicated with
horizontal lines. The tonal structuration of this set of lines is further
discussed in section 4.3.

####  4.1.3 Dynamics and Timbre

Amplitude for each pitch curve is represented by controlling the width of the
curve. Timbral aspects will also be depicted in future works.

###  4.2 Dynamic Paradigmatic Analysis

So far the position of the pitch curves on the time axis (as discussed in
section 4.1.1) was expressed with respect to the metrical grid given by the
notated music. It was implicitly assumed that the X-axis in the visualisation
represented the overall temporal evolution of the piece of music from
beginning to end.

Yet such strategy would only show how the music sounds like at each individual
instant, without any structured reference with what has been played, apart
from the mere display of the left part of the curve before the given time.
Music listening is a lot about inferring associations from what we are
currently hearing and we previously heard. This leads to the inference of a
structural understanding of the piece, and in particular of a thematic and
motivic lexicon, where music sequences of various sizes are considered as
repetitions of themes and motives. Following desideratum 3.1.3, this
structural information should be depicted in the visualisation.

One solution commonly used in music analysis is to add annotations on top of
the score — or in our case, the pitch curve —, such as boxes around sequences
of notes that are repeated. Boxes would be distinguished with respect to
color, width, line style, etc., in order to denotate particular theme or
motive. Figure 1 gives an idea of the type of motivic structure that can be
found in the beginning of _Contrapunctus XIV_.

Figure 1: Motivic analysis of the beginning of _Contrapunctus XIV_. The first
subject is shown in red and its corresponding countersubject in blue.

The problem with that formalisation is that it makes the visualisation more
complicated, more technical, and would demand a lot of additional attention
from the spectators, which would contradict desideratum 3.1.2. In particular,
they would need to find by themselves the position in the score (or the
overall set of pitch lines) of each type of boxes, which would quickly become
tedious. Besides, it does not seem feasible to display the whole pitch curve
on one single screen.

A fruitful solution to this problem can be found in the notion of paradigmatic
analysis. It was initially a method designed by Levi-Strauss in order to
structure texts, and it has then been introduced in music analysis by Nicolas
Ruwet [6] (cf. an example in Figure 2), and used extensively in music
semiotics [7]. The idea is simply to align vertically musical sequences that
share a same motivic or thematic identity. By compiling the successive
occurrences one below each other, the whole score can be read from left to
right and from top to bottom.

Figure 2: Paradigmatic analysis of a _Geisslerlied_ [6].

We partly follow this strategy by cutting the pitch lines into segments and
aligning those corresponding to repetitions of a same motif or theme
vertically. Contrary to the paradigmatic analysis, however, we do not use the
vertical axis as a way to distribute the sequences over time, because the
Y-axis is already used for representing the whole 4-voice polyphony.

Since our visualisation is dynamic, evolving over time, we do not need to care
about the readability of the whole representation once everything is drawn,
but only about the understandability of the dynamic progression of the
visualisation. As such, it is not a problem to superpose the repetitions of a
same pattern one on top of each other. If they are transposed (which is
generally the case in fugues), the corresponding vertical translation will be
clearly shown. Besides, the music operation of inversion (very typical to
fugues as well) will lead to the vertical inversion of particular occurrences
as well.

Since the pitch curves are not drawn simply from left to right anymore but may
appear at any place in the screen, the part of the curve being extended at a
given time should be clearly visible. For that purpose, we use the parameter
of line width to also control the recency of each part of the pitch curves.
The part of the curve most recently appears thicker while the older sections
become thinner and thinner. Besides, the rightmost point of the pitch curve
corresponding to the current instant is highlighted with a clearly visible
pointer, which has the color related to the instrument, as mentioned in
section 4.1.2.

Figure 3 presents the progressive construction of the paradigmatic
visualisation of the beginning of _Contrapunctus XIV_. The first 5 bars
correspond to the first subject, while the rest of the excerpt corresponds to
its counter-subject. Only the first occurrence of the counter-subject is shown
here. We notice that the successive 1-bar repetition in the bass line in bars
8—9 and 9—10 (purple box in figure 1) is folded, the second occurrence on top
of the first one. Similarly, for the tenor part, bar 12 is an extra bar
extending further bar 11, and is therefore folded in the visualisation.

Figure 3: Screenshots of the current version of the visualisation showing
various moments at the beginning of _Contrapunctus XIV_. On the top right of
each image is added the circular tonal representation, with the main triad
D-F-A. Successively from top to down, left to right: end of bars 7, 8, middle
of bar 9, end of bar 10 and middle and end of bar 12.

###  4.3 Tonal Analysis

Concerning the tonal dimension of the music, it is necessary to highlight
hierarchies between pitches. As the key of the piece is D minor, it seems
reasonable to highlight the main triad D-F-A, which is shown in the
visualisation in the form of a horizontal grid. All the lines corresponding to
a same pitch class are displayed with a same color (for instance555Examples of
colors are indicated in this paper. They will be tweaked so as to optimise the
clarity of the representation and the hierarchy of importance., red for D,
cyan for F and green for A). Only lines corresponding to pitches that have
been actually played are shown, so they progressively “light up” as the music
goes.

Attentive spectators will notice that while many entries of the fugue’s first
subject go from D (red) to A (green) and back to D, other entries go from A to
D and back to A, which has a slight shorter ambitus (fourth instead of fifth,
shown respectively by the red and black lines in Figure 3.). The visualisation
thus explicitly reveals the dichotomy between _subject_ and _answer_ in a
fugue.

To make explicit the concept of pitch classes, which plays an important role
in tonal analysis, as we will discuss in the next paragraphs, a circular
representation of pitch classes is shown in addition to the pitch curve
representation. This is illustrated in Figure 3666The tonal visualization has
not been implemented yet, and is therefore manually superimposed onto the
screenshots.. When the pitch classes D, A and F successively appear at the
very beginning of the fugue, they appear at the same time in the circle, using
the same color code as previously defined. Here also, this core triad defining
the main key of the piece will remain displayed during the whole piece.

One core characteristic of tonality is that the music can be considered as a
succession of triads (simple triads or seventh chords). These successive
triads are shown as triangles on the circle. Only the current triad is shown.
Seventh chords are shown with a triangle representing the main triad, plus a
second little triangle between the fifth, seventh and root, as shown in Figure
3, panels 1, 2 and 4.

For any given triad, if the root does not belong to the D-F-A triad, it is
indicated in orange both in the circle and as a horizontal line. Same for the
fifth but with a distinction: it is shown in dark green if it is a perfect
fifth, and grey in the other cases (not illustrated in the figure). The colors
is also used for the side of the triangle linking the root and the fifth.
Similar principles are used for the third, but with a distinction between
major and minor thirds. Similar principles are defined for the seventh degree.

As soon as the triad has been replaced by a subsequent one, the previous triad
is not displayed anymore, neither in the circle, nor as horizontal lines.

The last concept of importance that is visualised is the descending fifth
transition, so important in tonal music for its role in cadences but more
generally in the “circle of progression”. Descending-fifth transitions are
shown through an actual rotation of the triangle in the circle. At the same
time, pitch classes that remain constant through the transition are
highlighted as such, while voice leading movements are shown through
translations, leading tone going one degree up and the seventh one degree
down. Finally, when the descending fifth corresponds to a cadence, arriving to
an important tonic chord, the rotation ends with a slightly flamboyant
animation.

These tonal considerations will surely appear very arcane at first sight for a
non-expert spectator. Following principle 3.2.1, these more complex
consideration should be displayed in a rather unobtrusive way, available to
curious viewers who already understand the rest of the visualisation.

###  4.4 General Structure of the Piece

_Contrapunctus XIV_ , is a fugue with three different subjects, defining three
successive parts, each starting when the corresponding subject first appears.
It should be noted that when the second, or third, subject appears, the
previous one(s) can still occur from time to time.

At the beginning, the cello ($c$) plays the first subject $A$ alone, which is
displayed on the leftmost part of the screen. Then the alto ($a$) plays the
second entry ($A_{2}$) of $A$ while $c$ plays the countersubject of $A$. It
should be noted that in this fugue the countersubjects are not exact
repetitions of each other, but can be rather characterised as looser passages
structured by specific motivic cells. Hence these countersubjects are not
represented as single curves but as a succession of segments related to the
different motivic cells. For instance in this first countersubject, related to
$A_{1}$, there is a successive repetition of a small pattern with
transposition, which is shown on the right of panel 4 of Figure 3.

The first section continues similarly with the successive entries $A_{i}$ of
$A$ while the other voices continue their entries and develop new motivic
materials. All entries of subjects remain visible (while still being
progressively dimmed as indicated in section 4.2). On the contrary, to
simplify the visualisation, some of the entries’ continuations and
developments completely fade away after some point if they are not deeply
related to parts that will appear later in the piece.

The first entry by the second violon ($v_{2}$) of the second subject $B$
appears, at measure 114, as one of the many developments within the dense
network related to subject A. But as $v_{2}$ continues its long entry solo, it
progressively occupies the middle part of the screen, and all the material
related to $A$ fades away, so that this new $B$ entry suddenly becomes alone.

It should be noted that $B$ is far longer than the other two subjects, but
includes internal motivic repetitions, which are represented as such, through
vertical superposition of small lines.

Then the first violin ($v_{1}$) plays $B_{2}$ while $v_{2}$ plays the
countersubject of $B_{1}$, and so on. Then at measure 149, $c$ plays a new
entry of $A$ (leading to a progressive visual reactivation of the network of
lines related to $A$) while $v_{1}$ plays an entry of $B$ and so on.

There are also rare cases of multiple-voice patterns, where several voices
play a pattern that is repeated several times successively. This is a rare
case where several pitch curves are superposed not because of their thematic
identity but because of their simultaneity.

At measure 193, the third subject $C$ is introduced by $a$. This theme,
displayed on the right part of the screen, is known as the “BACH” theme as it
starts with B$\flat$, A, C and B$\natural$. So those letters are displayed
next to the pitch curve (as well as on the pitch class circle), which also
gives some dramatic effect to the visual.

In measure 233, $v_{2}$ plays a final entry of $B$ while $c$ starts a final
entry of $A$. These two final entries are particularly highlighted in the
visualisation. On measure 239, $v_{2}$ and $c$ end abruptly, while $a$
continues a short imitation of the ending of $B$ by $v_{2}$ for just one more
measure, and everything stops abruptly, as the composition of the piece is
unfinished.

The whole visualisation then fades away with only the four letters B A C H
remaining.

##  5 Technical Solution

The data-flow diagram of the proposed solution developed for this project is
shown in Figure 4.

Figure 4: Overall architecture of the proposed solution.

Each of the four instruments is captured using one of four DPA 4060 close-up
microphones. The audio is digitized and mixed into a single 4-channel audio
stream using a Behringer UMC404HD audio interface (to be confirmed), which is
plugged via USB to a MacBook Pro.

The software part is integrated into a single Mac app developed in Swift. Each
of the four channel is fed to a Pitch Tracking module, which sends information
about pitch, amplitude and timbre for each successive frame in each instrument
to the Visualisation module. In parallel, the four-channel audio stream is
also summed into one mono channel and fed to the Score Following module, which
sends information about the current position in the score to the Visualisation
module as well.

###  5.1 Pitch Tra _ck_ ing

The audio signal is decomposed into successive frames of length 50 ms and of
hop 25 ms. For each successive audio frame, pitch has been so far estimated by
computing the autocorrelation function. To speed up the computation,
autocorrelation function is computed using Fast Fourier Transform (FFT), using
the vDSP library of Apple’s _Accelerate_ framework. The frequency
corresponding to the global maximum of the autocorrelation function is
selected as the fundamental frequency.

In the first prototype, the analysis is carried out on synthesized rendering
of MIDI files. Future works will focus on the particular characteristics of
string instruments. Mechanisms will also be developed to avoid incorrect pitch
detection due to leakage between instruments.

Other signal processing processes are under consideration to extract timbral
descriptions of the sound.

###  5.2 Score Following

Score following refers to the task and technologies for aligning performances
of musical pieces to their score in real-time [8, 9]. The _dynamic time
warping_ (DTW) algorithm is the method of choice for performing audio-to-audio
alignments [10]. DTW is a general dynamic programming technique for finding
the best alignment between two sequences of observations. For the system
presented in this paper, we use the _on-line time warping_ (OLTW) algorithm
[11, 9]. This algorithm adapts DTW to be used in real-time scenarios by
computing the alignment incrementally.

We perform audio-to-score alignment by (manually) annotating a live recording
of _Contrapunctus XIV_ performed by DSQ, which we will refer to in the
following as the _reference_. For this recording, the positions of the beats
were annotated using Sonic Visualiser777https://sonicvisualiser.org by two
annotators with 10+ years of formal musical education. These beat annotations
are then averaged across annotators. As spectral features to compute the input
and reference sequences we used the modified MFCC features described in [10].
These features have been successful in aligning opera in real time [12].

The score follower works as follows:

  1. 1.

Before the beginning of the performance: Extract spectral features for the
annotated reference recording and set the current position of the score
follower to 0.

  2. 2.

During the performance:

    1. (a)

Mix the the individual tracks into a single (mono) track.

    2. (b)

For each new audio frame from the mixed input stream, compute the spectral
features.

    3. (c)

Update the current position of the score follower using OLTW.

###  5.3 Visualizer

The module draws the pitch curves — and their transformations based on
amplitude and timbre — related to each instrument into successive segments,
and places them in the screen to form the paradigmatic analysis, as discussed
in section 4.2. Under the pitch curves are also displayed horizontal lines
corresponding to important pitch levels related to the tonal analysis, as
explained in section 4.3. The module also draws the tonal circle and the
successions of triads and seventh chords. It also displays some particular
events such as the pitches B A C H and the particular emphasis on the last
entry of subjects $A$ and $B$.

Before the real-time process, the paradigmatic analysis is loaded into a
particular data structure, containing for each voice (i.e., each instrument)
the list of successive segments.

Each segment is represented by a triplet $(t_{1},t_{2},x_{1})$, where:

  * •

$t_{1}$ and $t_{2}$ are the time positions of the start and end of the
segment, expressed as positions in the score, and

  * •

$x_{1}$ is the abscissa of the start of the segment in the visual
representation.

The tonal analysis is loaded into another data structure, containing the list
of successive chords, with also indications of the falls of fifths. Another
list indicates when each horizontal lines corresponding to a pitch from the
main triad D, F and A lights up.

###  5.4 Control Interface

A user’s interface is also being designed to allow external control of the
system. This will enable to control a number of parameters before and during
the concert, related in particular to the amplitude of the input signals or
the tuning. This will also allow to manually assign the position in the score
in case of problems with the score following or of unplanned performance
issues from the musicians’ side.

##  6 Future Works

The system is currently under development. The visualisation will be premiered
at a Danish String Quartet concert, which had to be been postponed to May 22,
2021, at the Concert Hall of the Royal Danish Academy of Music in
Frederiksberg. This leaves a comfortable amount of time to improve the
visualisation, in particular related to pitch tracking, and to improve
clarity, richness and aesthetic appeal.

The audience will be invited to fill out a questionnaire, to evaluate the
fulfillment of desideratum 3.1.1, i.e., that the visualisation should be
accessible and self-explanatory to a largest public. The visualisation will
also be published online, with a corresponding online questionnaire.

In future works, we plan to generalise the system to broader musical contexts,
through the integration of polyphony, of various musical forms. We plan also
to integrate a polyphonic pitch tracker that would not require the use of
multi-channel instrument pickups, but simply a single mono or stereo pickup.
The score following might be used as a guiding point for the pitch tracking.

The musicological analysis, here the paradigmatic and tonal analyses, are for
the moment performed manually. In longer term we plan to integrate our systems
of automated motivic and structural analysis. By integrating also automated
transcription systems, the whole process could be carried out without the need
of a score and therefore of a score follower.

Acknowledgments
This work was partially supported by the Research Council of Norway through
its Centers of Excellence scheme, project number 262762 and the MIRAGE
project, grant number 287152; the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme under grant
agreement No. 670035 (project “Con Espressione”); and the Marie Skłodowsa-
Curie grant agreement number 765068, MIP-Frontiers.

This visualisation project is part of a larger project, the MusicLab5
Copenhagen 2020 event, under the initiative of Simon Høffding, which has been
postponed to 2021. We would like to warmly thank the musicians of the Danish
String Quartet and Simon Høffding for offering us this fantastic opportunity
to carry out this project.

The score in Figure 1 was initially typset by Tim Knigge, and made available
through the Mutopia project888http://www.mutopia.org..

## References

  * [1] K. Ng, J. Armitage, and A. McLean, “The colour of music: Real-time music visualisation with synaesthetic sound-colour mapping,” in _Proceedings of the Electronic Visualisation and the Arts (EVA)_ , 2014.
  * [2] S. C. Nanayakkara, E. Taylor, L. Wyse, and S. Ong, “Towards building an experiential music visualizer,” in _Proceedings of the 6th International Conference on Information, Communications & Signal Processing_, 2007.
  * [3] O. Lartillot and P. Toiviainen, “A Matlab toolbox for musical feature extraction from audio,” in _International conference on digital audio effects (DAFx)_ , 2007.
  * [4] T. Eerola, O. Lartillot, and P. Toiviainen, “Prediction of multidimensional emotional ratings in music from audio using multivariate regression models.” in _Proceedings of the 10th International Society for Music Information Retrieval Conference (ISMIR)_ , 2009.
  * [5] O. Lartillot, K. Eliard, D. Cereghetti, and D. Grandjean, “Video visualization of predictors of emotions dynamically expressed by music,” in _Proceedings of the 5th Humaine Association Conference on Affective Computing and Intelligent Interaction_ , 2013.
  * [6] N. Ruwet, “Methods of analysis in musicology,” _Music Analysis_ , vol. 6, no. 1-2, pp. 4–39, 1987, translated from « Méthodes d’analyse en musicologie », Revue belge de musicologie, 20, pp. 65-90, 1966.
  * [7] J.-J. Nattiez, _Music and Discourse: Towards a Semiology of Music_. Princeton University Press, 1990\.
  * [8] Müller, Meinard, _Fundamentals of Music Processing_. Heidelberg: Springer International Publishing Switzerland, 2015.
  * [9] A. Arzt, “Flexible and Robust Music Tracking,” Ph.D. dissertation, Johannes Kepler University Linz, Linz, Austria, November 2016.
  * [10] T. Gadermaier and G. Widmer, “A Study of Annotation and Alignment Accuracy for Performance Comparison in Complex Orchestral Music,” in _Proceedings of the 20th International Society for Music Information Retrieval Conference (ISMIR)_ , Delft, The Netherlands, 2019.
  * [11] S. Dixon, “Live Tracking of Musical Performances using On-line Time Warping,” in _Proceedings of the 8th International Conference on Digital Audio Effects (DAFx’05)_ , Madrid, Spain, 2005.
  * [12] C. Brazier and G. Widmer, “Towards Reliable Real-time Opera Tracking: Combining Alignment with Audio Event Detectors to Increase Robustness,” in _Proceedings of the 17th Sound and Music Computing Conference (SMC)_ , Torino, Italy, 2020.