# Classification of UHF Partial Discharge Signals in Gas-Insulated HVDC
Systems Using Neural Networks

Steffen Seitz, Thomas Götz, Christopher Lindenberg, Ronald Tetzlaff and
Stephan Schlegel Steffen Seitz, Christopher Lindenberg and Ronald Tetzlaff are
with the Department of Electrical and Computer Engineering, Technische
Universität Dresden, 01062 Dresden, Germany. Thomas Götz and Stephan Schlegel
are with the Department Electrical Power Systems and High Voltage Engineering,
Technische Universität Dresden, E-mail<EMAIL_ADDRESS>
# Generalizable Classification of UHF Partial Discharge Signals in Gas-
Insulated HVDC Systems Using Neural Networks

Steffen Seitz, Thomas Götz, Christopher Lindenberg, Ronald Tetzlaff and
Stephan Schlegel Steffen Seitz, Christopher Lindenberg and Ronald Tetzlaff are
with the Department of Electrical and Computer Engineering, Technische
Universität Dresden, 01062 Dresden, Germany. Thomas Götz and Stephan Schlegel
are with the Department Electrical Power Systems and High Voltage Engineering,
Technische Universität Dresden, E-mail<EMAIL_ADDRESS>
###### Abstract

Undetected partial discharges (PDs) are a safety critical issue in high
voltage (HV) gas insulated systems (GIS). While the diagnosis of PDs under AC
voltage is well-established, the analysis of PDs under DC voltage remains an
active research field. A key focus of these investigations is the
classification of different PD sources to enable subsequent sophisticated
analysis.

In this paper, we propose and analyze a neural network-based approach for
classifying PD signals caused by metallic protrusions and conductive particles
on the insulator of HVDC GIS, without relying on pulse sequence analysis
features. In contrast to previous approaches, our proposed model can
discriminate the studied PD signals obtained at negative and positive
potentials, while also generalizing to unseen operating voltage multiples.
Additionally, we compare the performance of time- and frequency-domain input
signals and explore the impact of different normalization schemes to mitigate
the influence of free-space path loss between the sensor and defect location.

###### Index Terms:

Fault diagnosis, HVDC, partial discharge, neural networks, machine learning.

##  I Introduction

The increasing integration of renewable energy sources into the existing high-
voltage grid requires the use of high-voltage direct current (HVDC) systems.
This technology is superior to conventional AC technology for transmitting
large amounts of power over long distances because of lower losses, and the
elimination of reactive power. Apart from high efficiency, the compact
installation of high-voltage equipment is also a critical consideration. Both
requirements, high-efficiency power transmission and space-saving
installation, are met by gas-insulated systems (GIS), which have been
developed for use in transmission systems under AC voltage stress since the
1960s.

A crucial aspect of ensuring fault-free operation in HVDC GIS is the automatic
classification of PD-generating defects prior to interpreting the results in
terms of fault-free operation [1].

Figure 1: Schematic representation of a HVDC gas-insulated system and related
typical partial discharges generating faults. The presented work aims to
classificate UHF PD signals caused by particle-  and protrusion-based
defects. [2]

Figure 1 provides a visual representation of an HVDC GIS and illustrates
common sources of PDs, including solid metallic particles on the insulation,
on free potential or freely moving in the insulating gas, and conducting
protrusions on the encapsulation or conductor [2]. In contrast to conventional
AC GIS, the number of these devices in operation under DC stress is rather
low. Thus, the measurement [3], classification [4], and physical
interpretation [5] of DC PDs continue to be active areas of research.
Recently, studies investigating PD development in HVDC GIS indicate that the
physical processes responsible for PD formation are the same as compared to
those observed under AC voltage stress [6]. However, due to the constant
electric field, continuous directed movement of charge carriers, and the
generation of space and surface charges, the behavior of DC PDs events, such
as amplitude and repetition rate, differs significantly from AC PDs [2].

As a result, the methods and findings related to AC PD classification cannot
be directly applied to HVDC GIS. For example, the well-established AC GIS PD
detection method, which relies on measurements in the ultra-high frequency
(UHF) range and human expert evaluation of phase-resolved partial discharge
(PRPD) plots [7, 8], is not suitable for distinguishing DC PD source signals
due to the lack of necessary phase information. Consequently, the development
and testing of novel DC-specific PD classification methods are essential for
ensuring the safety of HVDC GIS.

The most advanced technique for evaluating and identifying PDs under DC
voltage stress is pulse sequence analysis (PSA) followed by the assessment of
patterns by human experts [9]. This method leverages the amplitude and time
information of individual PD events in the UHF signal to identify the
underlying defect [10]. However, this approach relies on time-consuming human
judgment and it is limited to scenarios with a single PD source. In situations
where multiple sources are active, the PD signals overlap, hindering clear
identification and necessitating the use of complex techniques for source
separation [11, 12].

To circumvent the time-intensive process of human evaluation, Schober and
Schichler [13] proposed a machine learning-based approach for autonomously
classifying DC PD signals in GIS. Their novel approach employed Support Vector
Machines and MLP to assess PSA features derived from UHF measurements. Despite
its promising results, this method inherits the limitations associated with
hand-crafted PSA features, such as challenges in classifying signals of
multiple active PD sources.

Figure 2: Picture of the experimental setup (top) and three-dimensional
schematics of the electrode arrangements used for the emulation of DC-PD at
the gas-solid interface (bottom, left) and at a fixed metallic protrusion
(bottom, right) [2].

Furthermore, evaluation methods based on neural networks have shown promising
results in effectively distinguishing multiple active signal sources in
similar domains, when directly applied to time-domain measurements [14, 15].
Consequently, when these techniques are used for DC GIS PD classification,
they could potentially eliminate the need for PSA feature evaluation and
source separation techniques.

Recently, Beura et al. [16] introduced a first neural network-based method for
autonomous feature extraction from UHF time-domain measurements. Their study
showed results comparable to the pre-existing PSA methods [13], proving the
efficiency of this new approach. However, several critical questions that are
essential for the practical application of this method remain open.

First, as already illustrated in Figure 1, DC PDs in GIS originate from
multiple sources. Among these source types, PDs generated by particles on the
insulator surface are particularly significant [10]. However, the existing
literature on PD classification using neural networks based on UHF
measurements does not provide sufficient evidence regarding the capability to
classify this specific fault type. Moreover, there is a lack of information
regarding the classification accuracy of UHF signal-based neural network
models specifically for protrusions and insulator particles at both negative
and positive polarities of the inception voltage. This information is crucial
for a risk assessment of the asset and a successful transfer of the laboratory
experiment results to on-site installations [2].

In addition, previous studies under AC stress have demonstrated that utilizing
fast Fourier transform (FFT) coefficients extracted from UHF signals as
training data yields improved classification results in similar AC
classification tasks [17]. Therefore, it would be advantageous to explore the
transferability of these findings to the domain of DC PD classification.

Furthermore, all typical defects of HVDC GIS can experience stress from
various multiples of the inception voltage $U_{\mathrm{i}}$. These individual
voltages lead to slightly different discharge patterns [2]. However, the
specific $U_{\mathrm{i}}$ at the on-site GIS is not known in practice and
creating a suitable amount of data for every combination of the defect type
and $U_{\mathrm{i}}$ multiple is impractical for experts. Thus, it is
essential to investigate the ability of possible DC PD classification models
to generalize from laboratory-based signals to measurements based on unseen
$U_{\mathrm{i}}$ multiples of the GIS.

Another challenge in HVDC GIS arises from the amplitude of UHF PD signals,
which is influenced by free-space path loss, particularly when the signal has
to cross barrier insulators. Thus, the amplitude is proportional to the
distance between the defect location and the sensor. As this distance varies
in applications outside laboratory tests, it might be advantageous to
generally exclude amplitude-related information during model training by
applying different normalization methods. In summary, this study contributes
to the HVDC GIS PD classification in three significant aspects:

  * •

First, we extend the approach of Beura et al. [16] by providing the missing
evidence that a neural network-based architecture can effectively classify DC
PD time-domain UHF signals originating from particles on an insulator and
fixed metallic protrusions at both negative and positive DC voltage stress.
Furthermore, we aim to improve the classification performance by incorporating
frequency-domain signals and exploring different layer configurations,
including the number, ordering, and hyperparameters (stride, kernel size) of
our network.

  * •

Second, we present the first investigation of an HVDC PD classification model
in terms of its ability to classify measurements obtained at multiples of the
inception voltage $U_{\mathrm{i}}$ that have never been included in the model
training. By doing so, we seek to gain insights into the transfer learning
capabilities of the model, allowing for generalization from laboratory data to
on-site installations under unknown DC voltage stress levels.

  * •

Third, we analyze the impact of different normalization methods on the
performance of an HVDC PD classification model to mitigate potential
influences of free-space path losses between the sensor and defect locations.
This analysis aims to enhance the robustness of the model in real-world
scenarios where the distance between the sensor and defect location may vary.

##  II Experimental Setup & Methods

This study is conducted using UHF DC-PD signals measured under DC voltage
stress, as documented in Götz [2] and Götz et al. [6]. The measurements were
performed in a gas-insulated test setup shown in Figure 2 (top). Similar to
Beura et al. [16], model electrode arrays are installed inside a test vessel
to simulate the typical behaviour of the defects. The tests were performed
using sulfur-hexafluoride (SF6) as the insulation gas at an absolute pressure
of 0.5 MPa.

In the protrusion arrangement (Figure 2; bottom, right), the metallic
protruding needle has a length of 5 mm and the needle tip is installed at a
distance of $55$ mm from the opposing high-voltage electrode. To simulate PD
at the gas-solid interface (Figure 2; bottom, left), a $13$ mm needle is
placed on the surface of an epoxy insulator, typically used in gas-insulated
systems. The distance between the needle tip and the opposing high-voltage
electrode is 26.7 mm. The high DC voltage with positive and negative polarity
up to voltages of 250 kV is applied via the air-SF6 bushing installed in the
centre of the test vessel. PD signals are detected using a standard UHF sensor
[18] installed in the test vessel. A 30 dB amplifier is used to increase the
signal-to-noise ratio.

The time-dependent PD signals are sampled at $10$ GS/s using a Teledyne LeCroy
WavePro 735 ZiA digital oscilloscope. Each $i$-th measurement
$M_{j}=\\{s_{j,1},...,s_{j,u},...,s_{j,l_{s}}\\},j\in\\{1,\ldots,N\\}$ has a
length of $l_{\mathrm{s}}=20002$ individual samples $s_{j,u}|s\in\mathbb{R}$,
sampled at time step $u$. The resulting data set contains a total of $N=33000$
individual PD measurements taken at different multiples of the inception
voltage $U_{\mathrm{i}}$.

Figure 3: Time-domain signal examples of the considered defects. Each PD
measurement is based on either particles at the gas-solid interface (Pa-, Pa+)
or protrusions (Pr-, Pr+) at negative and positive potential of the needle
electrode.

A so-called source class label is assigned to each $M_{j}$ based on the defect
type, the polarity of the needle and the $U_{\mathrm{i}}$ multiple. Note that
the $U_{\mathrm{i}}$-information is only utilized to investigate the
generalization capability of the model (Section III-B). In the classification
task the model discards this information and learns to predict the so-called
output class labels depicted in Figure 3 based on the given source class
measurement. Thus, the output class labels are based only on the defect type
and needle polarity. The number of available source class measurements is
shown in Table I.

Table I: Number of available measurements $M_{j}$ of each source class in the dataset of [2].  | Negative Polarity | Positive Polarity
---|---|---
| $\overbrace{\hskip 120.55518pt}$ | $\overbrace{\hskip 129.16626pt}$
Particle {41mm | Pa${}^{-}_{1\cdot U_{\mathrm{i}}}$ | Pa${}^{-}_{1.5\cdot U_{\mathrm{i}}}$ | Pa${}^{-}_{3\cdot U_{\mathrm{i}}}$ | Pa${}^{+}_{1\cdot U_{\mathrm{i}}}$ | Pa${}^{+}_{1.25\cdot U_{\mathrm{i}}}$ | Pa${}^{+}_{1.5\cdot U_{\mathrm{i}}}$
|  |  |  |  |
3500 | 3500 | 3500  | 3500 | 3500 | 3500
|  |  |  |  |
Protrusion {41mm | Pr${}^{-}_{2\cdot U_{\mathrm{i}}}$ | Pr${}^{-}_{3\cdot U_{\mathrm{i}}}$ | \-  | Pr${}^{+}_{2\cdot U_{\mathrm{i}}}$ | - | -
|  |  |  |  |
4000 | 4000 | \-  | 4000 | - | -
|  |  |  |  |  |

In each of our experiments, the data is randomly drawn from these recorded
measurements and divided into a training and a test set by allocating 80 % of
the measurements of each class to the training set $D_{\mathrm{train}}$ and
the remaining 20 % to the test set $D_{\mathrm{test}}$ which are normalized
using three different methods.

(a)  Figure 4: The proposed model consists of five consecutive 1D-CNN layers
with ReLU activation, followed by an average pooling- and a flatten layer. The
features are fed into a fully connected multi-layer perceptron. This network
has 512 ReLU neurons in the input layer and four output neurons with a softmax
activation to assign one of the output classes (Pa-, Pa+, Pr-, Pr+).

###  II-A Normalization methods

The objective of data normalization or min-max scaling is to standardize
features to a consistent scale. This typically leads to improved performance
and training stability of the model. However, dependent on the choice of the
method, its application may affect the information contained in the signal.
Normalization can be applied in three different ways:

####  II-A1 Trainset normalization (Tr)

In trainset normalization, every sample in each measurement $M_{j}$ within
$D_{\mathrm{train}}$ and $D_{\mathrm{test}}$ is normalized between $-1$ and
$+1$ according to:

$\bar{s}_{j,u}=\frac{s_{j,u}-\text{Min}(D_{\mathrm{train}})}{\text{Max}(D_{\mathrm{train}})-\text{Min}(D_{\mathrm{train}})}.$
(1)

Min/Max$(\cdot)$ are operations that return the min-/maximum value of any
individual measurement within the dataset. As shown in equation (1), trainset
normalization scales each sample in each measurement with respect to the
maximum and minimum sample value of all individual measurements across all
classes in the dataset. Thus, this method preserves the amplitude information
for each measurement in the dataset. However, due to the previously stated
free-space path loss problem, it might be advantageous to generally exclude
amplitude-related information during model training.

####  II-A2 Class normalization (Cl)

Class normalization scales each sample within a measurement relative to the
maximum and minimum sample values of all measurements belonging to the
corresponding source class from Table I. In this method, the amplitude-related
information is preserved within samples of one class, while it is hidden
between measurements of different classes.

####  II-A3 Measurement normalization (Me)

In measurement normalization, each sample in a measurement $M_{j}$ is scaled
based on the maximum and minimum sample values within that specific
measurement period in the dataset. In this case, the model can no longer rely
on amplitude-related features to classify different samples of class in the
dataset.

###  II-B Classification model

In our experiments, the normalized UHF amplitude signal measurements and their
respective FFT coefficients are separately used to train the neural networks-
based model as depicted in Figure 4. These networks use sample measurements
and their assigned output class labels in $D_{\mathrm{train}}$ to learn their
weighting and bias parameters and ultimately predict the correct output class
label.

The architecture in our work is based on 1D-convolutional [19] and perceptron
layers [20]. We tested different numbers and arrangements of these layer types
in conjunction with different activation functions such as ReLU, Sigmoid, and
Tanh to achieve an improved classification result. For brevity, only the final
model structure is given. This structure and the corresponding activation
functions were empirically determined with respect to maximizing
classification performance. In the final architecture, the 1D-convolutional
layers perform sequential, discrete convolutions between a filter kernel and
the data. The extracted features are processed by a ReLU activation function
after each layer followed by an average pooling layer and a flattening layer.
The data is further processed by the perceptron layer with 512 neurons and a
ReLU activation function, which maps the extracted information to the output
classes depicted in Figure 3.

The model parameter adjustment is performed using backpropagation and the
optimal parameter set is determined by optimizing a cross-entropy loss using
ADAM optimization [21]. The initial learning rate of 0.0001 and a batch size
of 64 were determined through a random search. In each of our experiments, the
network is initialized with 15 different weight initialization seeds to
account for the effects of a non-optimal start to the optimization process.
The number of individual seeds was chosen to represent a reasonable trade-off
between the statistical robustness of the result and the computational time of
the model.  The performance of each trained model is evaluated using unseen
data from $D_{\mathrm{test}}$. In addition, similar to k-fold cross-
validation, a different set of measurements from the limited experimental data
are randomly assigned to $D_{\mathrm{train}}$ and $D_{\mathrm{test}}$ in each
of the 15 training and testing procedures. The obtained classification results
are averaged to determine a more reliable true positive rate $A$ of the
proposed architecture for each defect class. Similarly, the true negative,
false negative and false positive rates of the model are determined for all
other output classes.

##  III Experiments & Results

###  III-A Time- and frequency-domain classification results

In this section, we analyze the capability of the proposed architecture to
classify unseen measurements of PD generated by a fixed protrusion or a
particle adhering to the gas-solid interface. To accomplish this, we utilize
UHF signals measured in either the time-domain or frequency-domain at a
specific $U_{\mathrm{i}}$ multiple for each output class. In this initial
experiment, the baseline dataset D comprises measurements of Pa${}^{-}_{1\cdot
U_{\mathrm{i}}}$, Pa${}^{+}_{1\cdot U_{\mathrm{i}}}$, Pr${}^{-}_{2\cdot
U_{\mathrm{i}}}$, and Pr${}^{+}_{2\cdot U_{\mathrm{i}}}$, which are then
divided into $D_{\mathrm{train}}$ and $D_{\mathrm{test}}$. However, while it
would be beneficial to classify the output class based on data measured at the
same constant multiple of $U_{\mathrm{i}}$, for technical reasons the
available dataset only contained an unbalanced measurement distribution [2].
As a result, there is an unequal distribution of measurements recorded at the
same $U_{\mathrm{i}}$ multiples for each output class, as shown in Table I.

Figure 5: Model confusion matrix ($\bar{A}_{\text{trainset}}=0.9653$) obtained
by utilizing Pa${}^{-}_{1\cdot U_{\mathrm{i}}}$, Pa${}^{+}_{1\cdot
U_{\mathrm{i}}}$, Pr${}^{-}_{2\cdot U_{\mathrm{i}}}$ and Pr${}^{+}_{2\cdot
U_{\mathrm{i}}}$ time-domain measurements, preprocessed by trainset
normalization.

Figure 5 illustrates the confusion matrix of the experiment involving the
proposed output classes Pa${}^{-}_{1\cdot U_{\mathrm{i}}}$, Pa${}^{+}_{1\cdot
U_{\mathrm{i}}}$, Pr${}^{-}_{2\cdot U_{\mathrm{i}}}$ and Pr${}^{+}_{2\cdot
U_{\mathrm{i}}}$. The model achieves a near-perfect true positive rate $A$ for
UHF signals resulting from positive particle (Pa+) or positive protrusion
(Pr+) defects. For the remaining two output classes, the model obtains only a
slightly worse result. In particular, it exhibits a nearly symmetrical
confusion between measurements associated with negative particles (Pa-) and
negative protrusions (Pr-). As mentioned in Section II-B, the model in this
experiment was trained separately with 15 different weight initialization
seeds. Thus, the presented classification rates of each class in the confusion
matrix are the average across all individual runs. The overall performance of
the architecture is represented by the average true positive rate $\bar{A}$.
It is determined by averaging the individual true positives of all output
classes in the confusion matrix. In Figure 5, these values are indicated by
the diagonal elements of the matrix, representing the true positive rate of
correctly classified PD samples for each class, while the non-diagonal
elements represent the false positive and true negative rates when comparing
the predicted class against the ground truth.

Table II: Average true positive classification rates $\bar{A}$ for different normalization strategies and input datatype.  Input | Normalization Method
---|---
Datatype | Measurement (Me) | Class (Cl) | Trainset (Tr)
Time-Domain (TD) | 0.9977 | 0.9932 | 0.9653
Freq.-Domain (FFT) | 0.9983 | 0.9975 | 0.8048

As summarized in Table II, the trained model achieves an
$\bar{A}_{\text{Tr}}=0.9653$ on the trainset normalized measurements in
$D_{\mathrm{test}}$. The performance on time-domain test data is generally
better if the amplitude information is at least partially-
($\bar{A}_{\text{Cl, TD}}=0.9932$), or completely- $(\bar{A}_{\text{Me,
TD}}=0.9977$) hidden after normalization. If the time-domain input data is
converted to the frequency-domain instead, the classification rate based on
the trainset normalized FFT coefficients only achieves an average of
$\bar{A}_{\text{Tr, FFT}}=0.8048$. Thus, if trainset normalization is selected
and the model generalization to unseen $U_{\mathrm{i}}$ multiples is not
required, time-domain data should be used to train the classifier. Analog to
the time-domain signal, the FFT-based true positive rate is higher for class-
and measurement normalization. Classifying PDs from the FFT coefficiants of
the UHF signal resulted in the highest classification performance in our
experiments, with $\bar{A}_{\text{Me, FFT}}=0.9983$. Therefore, the minor
difference in performance compared to using the time-domain data hardly
justifies the computational cost of converting every measurement to the
frequency-domain. Thus, the following experiment relies solely on the time-
domain data.

###  III-B Transfer learning experiment results (generalization to an unseen
multiple of $U_{\mathrm{i}}$)

As previously mentioned in Section 1, it is important to examine PD
classification models in terms of their generalization to measurements of
defects recorded at unknown multiples of the GIS inception voltage
($U_{\mathrm{i}}$). Therefore, each PD measurement is assigned a source class
based on the defect type and the inception voltage determined at the time of
recording. Note that the exact value of $U_{\mathrm{i}}$ does not need to be
further specified, since the approach of this work is centered around the idea
of using laboratory data at specific $U_{\mathrm{i}}$ multiples to train a
model that generalizes to data from unknown $U_{\mathrm{i}}$ multiples at the
on-site GIS.

In the first part of our experiment, we evaluate the generalization
performance based on a transfer learning framework, where we pre-train our
model based on the data of the same source classes used in Section III-A
(Pa${}^{-}_{1\cdot U_{\mathrm{i}}}$, Pa${}^{+}_{1\cdot U_{\mathrm{i}}}$,
Pr${}^{-}_{2\cdot U_{\mathrm{i}}}$ and Pr${}^{+}_{2\cdot U_{\mathrm{i}}}$), to
create a baseline for our further studies. Note, that analog to the previous
experiment, any measurement is normalized by either trainset-, class- or
measurement normalization. After the training process, the generalization
performance of the baseline model is assessed by monitoring the model
generalization rate $G$, which is equal to the true positive rate of the model
on the untrained Pa${}^{+}_{1.5\cdot U_{\mathrm{i}}}$ measurements in the test
set, i.e. $G:=A(\text{Pa}^{+}_{1.5\cdot U_{\mathrm{i}}}$). Note, that the data
of Pa${}^{+}_{1.5\cdot U_{\mathrm{i}}}$ is explicitly excluded from the
training set in any of the further experiments. herefore, the described
measurements are used only at inference time to test the model’s
generalization to an unseen source class. In this setting, the model can only
rely on the knowledge learned from the source class data available in
$D_{\mathrm{train}}$ to classify any of the Pa${}^{+}_{1.5\cdot
U_{\mathrm{i}}}$ measurements in $D_{\mathrm{test}}$.

When trainset normalization (Tr) is used to normalize the baseline dataset
(Base), the model achieved a generalization rate of
$G_{\mathrm{Tr,Base}}=0.6801$. With class normalization (Cl), the model
achieved a significantly lower result of $G_{\mathrm{Cl,Base}}=0.4010$, while
with measurement normalization, the generalization rate of
$G_{\mathrm{Me,Base}}=0.2085$ did not outperform a random classifier in
classifying our four output classes ($G_{\mathrm{r}}=0.25$). A possible
explanation could be the lack of amplitude-related information after data
preprocessing with these normalization methods. To investigate this issue
further, we refine our basic model by gradually adding measurement data from a
previously withheld source class to the trainset $D_{\mathrm{train}}$. The
extended training set is used to train the model from scratch. In parallel,
the generalization rate of the model is determined after each addition,
analogous to the baseline experiment. The sequential training was performed
for two different consecutive sequence orders ("Order 1" and "Order 2") to
rule out any effects of adding a single record to $D_{\mathrm{train}}$.

Figure 6: Model generalization rate $G$ on the untrained $U_{\mathrm{i}}$
multiplier Pa${}^{+}_{1.5\cdot U_{\mathrm{i}}}$ when additional data from a
specific previously withheld source classes is included in the
$D_{\mathrm{train}}$. The issue is investigated for trainset (Tr), class (Cl),
and measurement (Me) normalization and two different sequential training
orders.

The results of this experiment shown in Figure 6 indicate, that the model
achieves a generalization rate that is reliably above the baseline results,
regardless of the normalization type and sequential ordering, after data from
the first additional $U_{\mathrm{i}}$ multiple is added to the baseline
dataset. After training the model with data from all available source classes
in Table I (except for the $\text{Pa}^{+}_{1.5\cdot U_{\mathrm{i}}}$ data), a
generalization performance is achieved that far exceeds random guessing.
Analog to training with a single additional source class, this result is
independent of the type of normalization and the sequential order. In contrast
to the previous experiment from Table II, trainset normalization performs best
in this transfer learning setting. The highest generalization rate with
trainset normalization was achieved after training with order 1 (O1),
resulting in $G_{\text{Tr, O1}}=0.9982$. In comparison, the highest
generalization rate of class normalization at the end of order 2 (O2) achieved
$G_{\text{Cl, O2}}=0.9578$. The highest measurement normalization based
approach only achieves $G_{\text{Me, O1}}=0.8672$ at the end of order 1. As
for the baseline dataset, a possible explanation could be the lack of
amplitude-related information after data preprocessing with these
normalization methods. In practice, the model is expected to generalize from
laboratory measurements to data of a monitored GIS with an unknown
$U_{\mathrm{i}}$ multiple. Therefore, assuming negligible effects of free-
space path loss, it is recommended to select normalization methods that
preserve the amplitude information in the data.

Figure 7: Confusion matrix and generalization rate $G_{\mathrm{Full}}$ (red)
of the proposed model. The network was trained using the full trainset-
normalized measurements of all available classes from Table I (except
$\text{Pa}^{+}_{1.5\cdot U_{\mathrm{i}}}$), using the train sequence of order
1.

Similar to Section III-A, it is crucial to evaluate model performance
concerning the remaining source class measurements from Table I while
assessing generalization on the withheld $\text{Pa}^{+}_{1.5\cdot
U_{\mathrm{i}}}$ data. When measurements of all source classes from Table I
(exept $\text{Pa}^{+}_{1.5\cdot U_{\mathrm{i}}}$) are included in
$D_{\mathrm{train}}$, the model classifies almost all test set measurements
correctly. This is illustrated by the confusion matrix in Figure 7. For the
sake of brevity, all combinations of normalization methods and training
routines are not shown, as they achieved comparable results. In the depicted
configuration, the average true positive rate over the available classes in
the training set is $\bar{A}_{\text{Tr, O1}}=0.9979$. When this score is
averaged with the associated generalization rate $(G_{\text{Tr, O1}}=0.9982)$,
the model attains an average final true positive rate of $\tilde{A}_{\text{Tr,
O1}}=0.9977$ for all measurements across all classes in our experiment.

###  III-C Comparison to other methods

Compared to other methods, our model classifies HVDC PDs originating from
metallic particles on the gas-solid interface (insulator) (Pa) of a GIS with
an average accuracy of 99.67%, which has not been reported in any other non-
PSA-based DC PD classification study. In addition, our refined CNN/MLP-based
architecture achieves an 1.29% higher average performance than the previous
best model in the protrusion (Pr) detection task [16]. The study of Schober
and Schichler [13] previously studied Pr and Pa classification, however their
PSA-based method did not report individual classification rates for these PD
types. In addition, the number of measurements available for each class is
very limited, making any comparative analysis on their work even more
difficult. Furthermore, our model is the first to differentiate between
negative and positive polarities of $\text{Pr}^{\pm}$ and $\text{Pa}^{\pm}$
measurements, while achieving previously unreported generalization
capabilities to untrained $U_{\mathrm{i}}$ multiples. Moreover, we are the
first to investigate the effect of normalization on the classification
performance. The main contributions of our work to the field are summarized in
Table III.

Table III: Comparison of the presented work to related non-expert-based PD classification approaches in HVDC GIS. Category | Our work | [16] | [13] |
---|---|---|---|---
Pr classification accuracy: | 99.99% | 98.23% |  not reported |
Pa classification accuracy: | 99.67% |  not inves- tigated (n.i.) |  not reported |
Average per class test set size: | 733 | 461 | 83 |
No PSA features required: |  |  | ✗ |
Defect polarity studied on: |  protrusion & solid particle on insulator |  particle on free potential | n.i. |
Normalization influence |  | n.i. | n.i. |
Generalization to $U_{\mathrm{i}}$ multiples: |  |  n.i. |  n.i. |

Note that we excluded approaches based on conventional PSA [9, 10] and PDs
under AC [22, 23, 24, 19] from this comparison, as they either depend on time
consuming human expert evaluation or rely on measurements of related but
different physical phenomena.

##  IV Conclusion

In this paper, we evaluate the performance and generalizability of a neural
network-based method for the classification of DC partial discharges (PDs) at
both negative and positive polarity. The ultra-high frequency (UHF) time- and
frequency-domain PD signals are generated by conductive protrusions and
particles on an insulator. Our study extends the literature on HVDC GIS PD
classification in multiple aspects:

  * •

First, we report the first classification of UHF signals originating from
particles adhering to the gas-solid interface (insulators) with an accuracy of
$99.67$%, without the need for pulse sequence analysis (PSA). Additionally,
our model outperforms all previously reported methods by $1.29$% on the UHF
protrusion signal classification task, achieving an accuracy of $99.99$%. The
use of frequency-domain signals achieved only a negligible average performance
advantage of $0.04$% compared to the UHF time-domain signal classification
model result which hardly justifies the computational cost of converting each
measurement to the frequency-domain.

  * •

Second, we are the first to investigate the transfer learning ability of a UHF
signal-based neural network PD classification model to generalize to
measurements recorded under unknown DC voltage stress levels. Regardless of
the training order, our model correctly classifies $99.87$% of the
$U_{\mathrm{i}}$ multiple signals not included in the train set as well as
$99.77$% of all available PD test set measurements.

  * •

Third, we analyze the effect of preprocessing, including sample-, class-, and
training set normalization on the performance of a PD classification model in
HVDC GIS to mitigate the possible influence of free-space path losses between
the sensor- and defect location. Our results show that methods partially
eliminating amplitude information perform better in PD classification
experiments, while amplitude-preserving methods slightly outperform in the
$U_{\mathrm{i}}$ multiple transfer learning task.

In future work, the proposed approach should be applied to measurements of the
remaining PD types in HVDC GIS such as insulator cavitys, free-moving
particles, and material on free potential. We also suggest considering
different sensor positions, electrode geometries, and spacing to enhance the
methodology. Furthermore, it would be important to study the transfer learning
capability on data from additional operating voltages to facilitate the
practical application of the method.

## Acknowledgments

This research was partly funded by the German Research Foundation (DFG,
project number 379542208) and the German Federal Ministry of Economic Affairs
and Climate Action (BMWK, reference: KK5056101KA0). The authors acknowledge
the computing time through the ZIH at TU Dresden and the feedback from Thomas
Linde and Carsten Knoll.

## References

  * Davies and Jones [2008] N. Davies and D. Jones, “Testing distribution switchgear for partial discharge in the laboratory and the field,” in _Conference Record of the 2008 IEEE International Symposium on Electrical Insulation_ , 2008, pp. 716–719.
  * [2] T. Götz, “Partial discharge behaviour of gas-solid insulation systems under DC voltage stress,” Dissertation, Technical University Dresden, 2022.
  * Abbasi et al. [Janpath / New Delhi, 2019] A. Abbasi, J. Castellon, A. Cavallini, F. Esterl, and T. Götz, “Progress on partial discharge detection under DC voltage stress,” in _CIGRE Joint Colloquium - SCA2/SCB2/SCD1_ , Janpath / New Delhi, 2019.
  * Pirker, A. and Schichler, U. [2016] Pirker, A. and Schichler, U., “Partial discharges at DC voltage - measurement and pattern recognition,” in _2016 International Conference on Condition Monitoring and Diagnosis_ , 2016, pp. 287–290.
  * [5] A. Mor, L. Heredia, F. Muñoz, U. Richert, M. Gatzsche, H. He, N. Belda, T. Vu, C. Toigo, and M. Tuczek, “Promotion: Progress on meshed HVDC offshore transmission network - report on diagnostic analysis and condition assessment (D15.5).” [Online]. Available: https://www.promotion-offshore.net/fileadmin/PDFs2/D15.5_final_report.pdf
  * Götz et al. [2020] T. Götz, H. Kirchner, and K. Backhaus, “Partial discharge behaviour of a protrusion in gas-insulated systems under DC voltage stress,” _Energies_ , vol. 13, no. 12, 2020.
  * Achatz et al. [2005] N. Achatz, J. Gorablenkow, U. Schichler, B. Hampton, and J. Pearson, “Features and benefits of UHF partial discharge monitoring systems for GIS,” in _Proceedings of 2005 International Symposium on Electrical Insulating Materials, 2005. (ISEIM 2005)._ , vol. 3, 2005, pp. 722–725 Vol. 3.
  * Hoshino et al. [2006] T. Hoshino, H. Koyama, S. Maruyama, and M. Hanai, “Comparison of sensitivity between UHF method and IEC 60270 for onsite calibration in various GIS,” _IEEE Transactions on Power Delivery_ , vol. 21, no. 4, pp. 1948–1953, 2006.
  * Pirker and Schichler [2018] A. Pirker and U. Schichler, “Partial discharge measurement at DC voltage — Evaluation and characterization by NoDi pattern,” _IEEE Transactions on Dielectrics and Electrical Insulation_ , vol. 25, no. 3, pp. 883–891, 2018.
  * Pirker and Schichler [2019] ——, “Application of NoDi* pattern for UHF PD measurement on HVDC GIS/GIL,” Sep. 2019, international Conference on Condition Monitoring, Diagnosis and Maintenance, CMDM 2019 ; Conference date: 09-09-2019 Through 11-09-2019.
  * Hochbrückner et al. [2020] B. Hochbrückner, M. Spiertz, A. Küchler, M. H. Zink, T. Steiner, E. Winkelmann, and K. Backhaus, “Digital filtering methods for interferences on partial discharges under dc voltage,” in _Proceedings of the 21st International Symposium on High Voltage Engineering_. Springer International Publishing, 2020, pp. 560–571.
  * Hochbrückner et al. [2019] B. Hochbrückner, M. Spiertz, M. H. Zink, A. Küchler, and K. Backhaus, “Comparison of algorithms for clustering of partial discharge signals under DC voltage,” in _2019 2nd International Conference on High Voltage Engineering and Power Systems_ , 2019, pp. 041–046.
  * Schober and Schichler [2022] B. Schober and U. Schichler, “HVDC GIS/GIL - Machine learning algorithms for online PD classification at DC voltage,” in _2022 9th International Conference on Condition Monitoring and Diagnosis (CMD)_ , 2022, pp. 225–230.
  * Adam and Tenbohlen [2018] B. Adam and S. Tenbohlen, “Classification of multiple PD sources by signal features and LSTM networks,” in _2018 IEEE International Conference on High Voltage Engineering and Application (ICHVE)_ , 2018, pp. 1–4.
  * Adavanne et al. [2019] S. Adavanne, A. Politis, J. Nikunen, and T. Virtanen, “Sound event localization and detection of overlapping sources using convolutional recurrent neural networks,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 13, no. 1, pp. 34–48, 2019.
  * Beura et al. [2022] C. P. Beura, P. Wenger, E. Tozan, M. Beltle, and S. Tenbohlen, “Classification of partial discharge sources in HVDC gas insulated switchgear using neural networks,” in _VDE High Voltage Technology; 4. ETG-Symposium_ , 2022.
  * Li et al. [2018] G. Li, X. Wang, X. Li, A. Yang, and M. Rong, “Partial discharge recognition with a multi-resolution Convolutional Neural Network,” _Sensors_ , vol. 18, no. 10, 2018.
  * Tröger et al. [2010] A. Tröger, U. Riechert, S. Burow, and S. Tenbohlen, “Sensitivity evaluation of different types of PD sensors for UHF-PD-measurements,” in _Proceedings of the International Conference on Condition Monitoring and Diagnosis_ , 2010.
  * Seitz et al. [2017] S. Seitz, J. Müller, R. Tetzlaff, and P. Holstein, “Neural networks for the classification of electrical discharges,” in _Advances in Acoustics; German Acoustical Society_ , 2017, pp. 1019–1021.
  * Mieruch et al. [2021] S. Mieruch, S. Demirel, S. Simoncelli, R. Schlitzer, and S. Seitz, “SalaciaML: A deep learning approach for supporting ocean data quality control,” _Frontiers in Marine Science_ , vol. 8, 2021.
  * Kingma and Ba [2014] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _CoRR_ , vol. abs/1412.6980, 2014.
  * Wang and Yu [2020] W. Wang and N. Yu, “Partial discharge detection with Convolutional Neural Networks,” in _2020 International Conference on Probabilistic Methods Applied to Power Systems_ , 2020, pp. 1–6.
  * Tuyet-Doan et al. [2021] V.-N. Tuyet-Doan, H.-A. Pho, B. Lee, and Y.-H. Kim, “Deep ensemble model for unknown partial discharge diagnosis in gas-insulated switchgears using Convolutional Neural Networks,” _IEEE Access_ , vol. 9, pp. 80 524–80 534, 2021.
  * Gulski and Krivda [1993] E. Gulski and A. Krivda, “Neural networks as a tool for recognition of partial discharges,” _IEEE Transactions on Electrical Insulation_ , vol. 28, no. 6, pp. 984–1001, 1993.

|  Steffen Seitz received his Diploma (Dipl.-Ing.) degree in electrical
engineering from the Technische Universität Dresden in Germany in 2016. He is
currently advancing his academic career as a Ph.D. candidate and research
associate at the Chair of Fundamentals of Electrical Engineering, under the
guidance of Ronald Tetzlaff. His interests include neural network-based
condition monitoring and explainable artificial intelligence and explainable
artificial intelligence, with a specific focus on enhancing the
understandability of model reasoning in predictive maintenance.

---|---
|  Thomas Götz received the Diploma degree in electrical engineering in 2015
and the Ph.D. degree in high voltage engineering in 2022 from the Technische
Universität Dresden. From 2015 to 2022 he was a research associate at the
Chair of High Voltage and High Current Engineering, where he headed the
research group High Voltage Engineering in 2022 and 2023. He is a member of
the CIGRE WG D1.63 “Partial discharge detection under DC voltage stress”. One
of his journal publications was awarded a national literature award.
---|---
|  Christopher Lindenberg is currently pursuing his B.Sc. degree in Computer
Science together with Steffen Seitz and Ronald Tetzlaff at the Technische
Universität Dresden in Germany. He is recently researching neural network-
based failure diagnosis and condition monitoring at the Chair of Fundamentals
of Electrical Engineering.
---|---
|  Ronald Tetzlaff (Senior Member, IEEE) is the Head of the Chair of
Fundamentals of Electrical Engineering, Technische Universität Dresden,
Germany. Since August 2020, he is also the Chief Officer of Technology
Transfer and Internationalization at the Technische Universität Dresden. His
scientific interests include problems in signal and system theory, medical
signal processing, stochastic processes, system modeling, system
identification, machine learning, mem-elements, memristive systems, Volterra
systems, physical fluctuation phenomena, and Cellular Nonlinear Networks.
---|---
|  Stephan Schlegel received the doctoral and the habilitation degree in
electrical engineering at the Technische Universität Dresden in 2011 and 2019.
He led the research group “Electrical Contacts and Connection” between 2011
and 2020. Since 2020, he is provisional holder of the Chair of High Voltage
and High Current Engineering at the TU Dresden. His research focus is in the
fields of the fundamentals of the electrical-mechanical-thermal contact
behavior as well as the aging mechanisms and long-term behavior of electrical
contacts and connections.
---|---


We provide examples of finitely presented groups with transcendental spectral radius. The proofs relies on links between decidability of the Word Problem and semi-computability of the spectral radius, and on small-cancellation theory.

Throughout the paper, we consider marked groups, that is, pairs $(G,S)$ with $G$ a finitely generated group and $S$ a finite symmetric generating set (i.e., $S=S^{-1}$). We consider the simple random walk $(X_n)_{n\ge 0}$ on $\Cay(G,S)$, starting at $X_0=e_G$, and define

\[ p_{G,S}(g;n) = \PP[X_n=g].\]

Equivalently $p_{G,S}(g;n)=\frac1{\abs{S}^n}\, \#\{w\in S^n\mid \bar w=g\}$[Most of the time, $G$ and $S$ are clear from the context and $g=e_G$, hence we only write $p(n)$]. The spectral radius is defined as

\[ \rho(G,S) = \limsup_{n\to\infty} \sqrt[n]{p_{G,S}(e;n)}. \vspace*{-3mm} \]

Our main result is the following:

There exists a finitely presented group $G$ such that the spectral radius $\rho(G,S)$ is transcendental for all finite symmetric generating sets $S$.

This answers a question of Kassabov and Pak <cit.>. In Section <ref>, Theorem <ref>thm:main is extended to the exponential growth rate and the asymptotic entropy.

As the proof for Theorem <ref>thm:main uses crucially that $G$ has undecidable Word Problem, we propose another result of the same flavor:

There exists a finitely generated group $G$ with decidable Word Problem such that the spectral radius $\rho(G,S)$ is transcendental for a specific generating set $S$.

The construction uses classical $C'(1/6)$ small-cancellation theory. As a key ingredient, we use that these groups satisfy the Rapid Decay property (uniformly).

Acknowledgments. I'm grateful to Anna Erschler, Tatiana Nagnibeda and Igor Pak for comments and encouragements, to Denis Osin for sharing some ideas for <ref>, and to Carl-Fredrik Nyberg-Brodda for sparing a few generators and relators in the last construction of <ref>. The author was supported by the Swiss NSF grant 200020-200400.

§ SEMI-COMPUTABLE NUMBERS

The first ingredient in our proof is the following definition:

A number $x\in\R$ is lower (resp. upper) semi-computable if there exists an algorithm enumerating an increasing (resp. decreasing) sequence $(x_k)$ of real algebraic numbers[Real algebraic numbers $x_k$ can be specified as triplets $(P_k(X),a_k,b_k)\in\Q[X]\times\Q\times\Q$ such that $x_k$ is the only root of $P_k(X)$ in the interval $[a_k,b_k]$.] such that $x_k\to x$.

§.§ Lower bounds
We first observe that spectral radius are lower semi-computable in a very general setting, namely for all recursively presented groups:

Let $G$ be a recursively presented group, then $\rho(G,S)$ is lower semi-computable. Moreover, the result is effective: there exists an algorithm with

Input: A recursively presented marked group $(G,S)$, specified via a finite set $S$ and an algorithm enumerating a set of defining relations.

Output: An algorithm enumerating an increasing sequence of real algebraic numbers $(x_k)$ such that $x_k\to \rho(G,S)$.

Note that $p(m+n)\ge p(m)\cdot p(n)$, therefore Fekete's lemma ensures that

\[ \rho(G,S) =  \sup_{n\ge 1} \sqrt[n]{p(n)}. \]

As $G$ is recursively presented, its Word Problem (i.e., the set of words $w\in S^*$ such that $\bar w=e_G$) is recursively enumerable. Let $(v_i)_{i\ge 1}\subseteq S^*$ be a computable enumeration of the Word Problem, and let us define

\[ p_k(n) = \frac1{\abs S^n} \cdot \#\{v_i : \ell(v_i)=n \text{ and } 1\le i\le k\}. \]

Observe that $p_k(n)\nearrow p(n)$ pointwise  as $k\to\infty$. In particular

\[ x_k = \max_{1\le n\le k}\sqrt[n]{p_k(n)}\]

is a computable increasing sequence such that $x_k\to \rho(G,S)$, as promised.

The analogous result for upper semi-computable doesn't hold, even under the additional assumption that the Word Problem is decidable (with a Word Problem algorithm as part of the input). Indeed, this would imply that amenability is a co-semi-decidable property, contradicting <cit.>.

As will become clear in the proof of Theorem <ref>thm:main, there exist finitely presented groups (with undecidable Word Problem) whose spectral radius is not upper semi-computable.

§.§ Upper bounds
We find upper approximations for $\rho(G,S)$. This requires control on the speed of convergence of $\sqrt[2n]{p(2n)}\to\rho(G,S)$ (and some way to compute $p(2n)$). This control is given to us by the Rapid Decay property:

Let $G$ be a group, with a word metric $d_S$. We say that $G$ has the Rapid Decay property if there exists a polynomial $P\in\R[X]$ such that

\[ \norm{f}_{\mathrm{op}} \le P(r)\cdot \norm{f}_2 \]

for all $f\in\C G$ supported on the ball $B_S(e,r)$.

(The polynomial depends on $S$, but the fact that $G$ satisfies the property does not.) The link with cogrowth is the following observation (taking $f(x)=p(x;n)$):
If $(G,S)$ has the Rapid Decay property for a given polynomial $P$, then

\[ \rho(G,S)^{2n} \le P(n)^2 \cdot p(2n).\]

Our main interest lies on groups given by presentations satisfying the classical small-cancellation condition $C'(1/6)$. These satisfy the Rapid Decay uniformly.

If $G=\la S\mid R\ra$ is a $C'(\frac16)$ presentation, then $G$ has the Rapid Decay property with $P(r)=(10r+1)^3$ (for the generating set $S$).

Let $G_i=\la S\mid R_i\ra$ be a sequence of $C'(1/6)$ presentations such that $(G_i,S)\to (G,S)$ in the space of marked groups, then $\rho(G_i,S) \to \rho(G,S)$.

Combining the previous results, we have

\begin{equation} \tag{$*$}
\rho(G_i,S)/\sqrt[n]{P(n)}\le \sqrt[2n]{p_{G_i,S}(2n)} \le \rho(G_i,S),
\end{equation}

in particular $\sqrt[2n]{p_{G_i,S}(2n)} \to \rho(G_i,S)$ uniformly. It follows that

\begin{align*}
\lim_{i\to\infty}\rho(G_i,S) & = \lim_{i\to\infty}\lim_{n\to\infty}\sqrt[2n]{p_{G_i,S}(2n)} \\
& \overset!= \lim_{n\to\infty}\lim_{i\to\infty}\sqrt[2n]{p_{G_i,S}(2n)} = \lim_{n\to\infty}\sqrt[2n]{p_{G,S}(2n)}=\rho(G,S). \qedhere
\end{align*}

If $G=\la S\mid R\ra$ is a recursive $C'(\frac16)$ presentation, then $\rho(G,S)$ is upper semi-computable (hence computable). Moreover, the result is effective.

Rewriting the equation $(*)$, we get that

\[ \sqrt[2n]{p(2n)} \le \rho(G,S) \le \sqrt[n]{P(n)} \sqrt[2n]{p(2n)}. \]

Moreover, the Word Problem is decidable (using Dehn's algorithm), hence $p(2n)$ is computable. This provides both upper and lower bounds.

§ FROM COMPUTABLE SPECTRAL RADIUS TO DECIDABLE WORD PROBLEM

Our main observation is the following:

Let $(G,S)$ be a recursively presented group such that the spectral radius $\rho(G,S)$ is upper semi-computable.
Consider a subset $W\subseteq S^*$ such that, for each $w\in W$, either $\bar w=e_G$ or the normal subgroup generated $\lla \bar w\rra_G$ is non-amenable. Then there exists an algorithm which, given a word $w\in W$, decides whether $\bar w=e_G$ or not.

(In particular, if $W=S^*$, then $G$ has decidable word problem.) This theorem relies crucially on a classical result due to Kesten.

Let $(G,S)$ be a marked group and $N\len G$ a non-amenable normal subgroup, then we have $\rho(G,S) < \rho(G/N,S)$.

Suppose that $G$ is presented as $\la S\mid R\ra$. Take $w\in W$, we run two parallel processes to decide whether $\bar w=e_G$ or not.

* As $G$ is recursively presented, we can enumerate all words $v\in S^*$ such that $\bar v=e_G$. If at any point $v=w$, we stop the algorithm and conclude that $\bar w=e_G$.

* The group $G_w=G/\lla \bar w\rra_G=\la S\mid R,w\ra$ is recursively presented, hence $\rho(G_w,S)$ is lower semi-computable. We can compute two sequences $(x_k)$ and $(y_k)$ such that

\[ x_k\searrow \rho(G,S) \quad\text{and}\quad  y_k\nearrow \rho(G_w,S). \]

As $x_k$ and $y_k$ are real algebraic, we can compare them. If at any point $x_k<y_k$, we stop the algorithm and conclude that $\bar w\ne e_G$. It should be noted that, if $\bar w\ne e_G$, then the inequality $x_k<y_k$ will hold eventually as $\lla \bar w\rra_G$ is non-amenable and therefore $\rho(G,S)<\rho(G/\!\lla \bar w\rra_G,S)=\rho(G_w,S)$.

In both cases, the algorithm finishes and decides correctly if $\bar w=e_G$ or not.

§ PROOF OF THEOREM <REF>THM:MAIN

We propose two different constructions, both relying on Theorem <ref>thm:comp_to_deci.

1. We recall a family of groups introduced by Higman <cit.>: for each $I\subseteq \Z$,

\[ H_I \coloneqq \la a,b,c,d \mid a^iba^{-i}=c^idc^{-i} \;\;(i\in I)\ra. \]

This is an amalgamated free product $A*_CB$ with $A=F(a,b)$, $B=F(c,d)$ and $C=F(\{g_i\}_{i\in I})$ (with injections $g_i\mapsto a^ib a^{-i}$ and $g_i\mapsto c^idc^{-i}$ respectively). We define

\[ w_i=a^iba^{-i}c^id^{-1}c^{-i}. \vspace*{-2mm}\]

If $i\notin I$, then $\lla \bar w_i\rra_{H_I}$ contains a non-abelian free group.

The subgroup $\la w_i,bw_ib^{-1}\ra$ is non-abelian free. This follows directly from the Normal Form Theorem for amalgamated free products, see eg. <cit.>.

Consider $I\subset\Z$ which is recursively enumerable (hence $H_I$ is recursively presented), but not recursive. Using Higman's embedding theorem <cit.>, we can embed $H_I$ into a finitely presented group $G$ (as Higman did). For any finite symmetric generating set $S$ of $G$, we consider a monoid homomorphism $\varphi\colon \{a^\pm,b^\pm,c^\pm,d^\pm\}^*\to S^*$ such that $\overline{\varphi(v)}=\bar v$ for all $v\in\{a^\pm,b^\pm,c^\pm,d^\pm\}$, and let $W=\{\varphi(w_i):i\in\Z\}\subset S^*$.

* Using the lemma, either $\bar w_i=e_G$ or $\lla \bar w_i\rra_G\ge \lla \bar w_i\rra_{H_I}$ is non-amenable.

* As $I$ is not recursive, there does not exist any algorithm which, given $\varphi(w_i)\in W$ (equivalently $i\in \Z$) decides whether $\bar w_i=e_G$ or not (equivalently $i\in I$ or not).

Therefore $\rho(G,S)$ cannot be upper semi-computable, hence cannot be algebraic.

Using Karrass-Solitar theorem on amalgamated free products <cit.>, one should be able to prove that $\lla g\rra_{H_I}$ contains a non-abelian free group for all $g\in H_I\setminus \{e\}$.

2. Start with $H=\la S_0\mid R\ra$ a finitely presented group with undecidable Word Problem, first constructed in <cit.>. We consider $G=H*\la t\ra$ and $W=S_0^*$. For each $w\in W$, either $\bar w$ is trivial, or the normal subgroup it generates satisfy

\[ \lla \bar w\rra_G \ge \la \bar w,\, t\bar wt^{-1},\, t^2\bar wt^{-2}\ra \simeq C_n * C_n * C_n \ge F_2 \]

where $n\in\{2,3,\ldots\}\cup\{\infty\}$ is the order of $\bar w$. Again, Theorem <ref>thm:comp_to_deci implies that $\rho(G,S)$ cannot be upper semi-computable, hence is transcendental.

Note that, combining the main result of <cit.> with <cit.>, we can find a group $H$ with undecidable Word Problem defined by $2$ generators and $12$ relators, and therefore $G$ defined by as little as $3$ generators and $12$ relators.

§ EXTENSION TO OTHER PARAMETERS

Similarly to <cit.>, the same ideas can be used to provide finitely presented groups for which the value of various parameters $f\colon\mathcal M\to\R$ (where $\mathcal M$ is the space of marked groups) are not computable. The key ingredients are the following:

* A recursively presented group $(G,S)$ and a subset $W\subseteq S^*$ such that

* the Word Problem restricted to $W$ is undecidable, and

* $f(G,S)<f(G/\!\lla \bar w\rra_G,S)$ for all $w\in W$ such that $\bar w\ne e_G$.

* For every recursively presented group $(Q,S)$, the value $f(Q,S)$ is lower semi-computable, and the result is effective in the sense of Lemma <ref>.

Under these conditions, we may conclude $f(G,S)$ is not upper semi-computable. In the following subsections, we check both conditions for the growth rate and the asymptotic entropy (up to a change of sign). In both cases, we may take $G = H*\Z$ where $H$ is any finitely presented group with undecidable Word Problem.

§.§ Growth rates
Let $d_S$ be the word metric on $G$, and $\beta_{G,S}(n) = \abs{B_{G,S}(e,n)}$ the volume of the ball of radius $n$. The growth rate of $(G,S)$ is defined as

\[ \omega(G,S) = \limsup_{n\to\infty}\sqrt[n]{\beta_{G,S}(n)}.\]

Anna Erschler constructed a continuum of (infinitely presented) marked groups with distinct growth rates <cit.>, in particular containing transcendental values. Once again, our recipe provides finitely presented examples of the form $G=H*\Z$.

Let $H$ be a non-trivial group, then $G=H*\Z$ is growth tight, that is, for every generating set $S$ and every $N\len G$ with $N\ne 1$, we have

\[ \omega(G/N,S)<\omega(G,S).\]

Let $(G,S)$ be a recursively presented group, then the growth rate $\omega(G,S)$ is upper semi-computable. Moreover, the result is effective.

The sequence $\beta_{G,S}(n)$ is sub-multiplicative, so Fekete's lemma implies that

\[ \omega(G,S) = \inf_{n\ge 1}\sqrt[n]{\beta_{G,S}(n)}. \]

Consider $\{(v_i,w_i)\}_{i\ge 1}$ a computable enumeration of

\[ \Delta(G,S) = \{(v,w)\in S^*\times S^*\mid \bar v=\bar w\}. \]

At time $k$, we define an equivalence relation $\sim_k$ on $S^*$, declaring $v_i\sim_k w_i$ for all $1\le i\le k$ (and then considering the reflexive, transitive closure). We define

\[ P^{\le n}_k=\faktor{S^{\le n}}{\sim_k} \quad\text{and}\quad \beta_k(n) = \abs{P^{\le n}_k} \]

Finally, let $y_k = \min\limits_{1\le n\le k} \sqrt[n]{\beta_k(n)}$. We have $\beta_k(n)\searrow \beta_{G,S}(n)$ hence $y_k\searrow \omega(G,S)$.

§.§ Asymptotic entropy
Let $(G,S)$ be a marked group. We consider the simple random walk $(X_n)_n$ on $\Cay(G,S)$. Recall that the Shannon entropy of $X_n$ is given by

\[ H(X_n) = -\sum_{g\in \supp X_n} p(g;n)\,\log\big(p(g;n)\big). \]

The asymptotic entropy of $(G,S)$ is defined as

\[ h(G,S)=\lim_{n\to\infty} \frac1n H(X_n). \]

Once again, both conditions are satisfied (for either construction of <ref>):

Let $(G,S)$ be a group and $N\len G$ non-amenable, then

\[ h(G/N,S)<h(G,S).\]

Let $(G,S)$ be a recursively presented group, then the asymptotic entropy $h(G,S)$ is upper semi-computable. Moreover, the result is effective.

As the sequence $H(X_n)$ is sub-additive, Fekete's lemma gives

\[ h(G,S)= \inf_{n\ge 1} \frac1n H(X_n). \]

Reusing the notations from Lemma <ref>, we define $P^n_k=\faktor{S^n}{\sim_k}$ and

\[ H_k^n = -\sum_{A\in P_k^n} \frac{\abs A\,}{\,\abs S^n}\log\left(\frac{\abs A\,}{\,\abs S^n}\right).\]

Observe that $H_k^n\searrow H(X_n)$ as $k\to\infty$. Finally, the sequence $x_k=\min_{1\le n\le k}\frac1n H_k^n$ provides upper approximations for $h(G,S)$.

§ PROOF OF THEOREM <REF>THM:MAIN2

More precisely, we prove the following result:

Let $X=\{x_n\}_{n\ge 1}$ be recursively enumerable set of computable reals, i.e., such that there exists an algorithm with specifications

Input: An index $n$.

Output: Two algorithms providing two monotonous sequences of rational numbers $(a_{m,n})_{m\ge 1}$ and $(b_{m,n})_{m\ge 1}$ such that $a_{m,n}\nearrow x_n$ and $b_{m,n}\searrow x_n$ as $m\to\infty$.

Then there exists a marked group $(G,S)$ with decidable Word Problem s.t. $\rho(G,S)\notin X$.

We combines small-cancellation theory and a diagonal argument. This combination of ideas already appears in <cit.>. The main additional difficulty is computability.

Fix an alphabet $S$, and consider an infinite sequence of cyclically reduced words $(r_i)_{i\in\N}\subset S^*$ satisfying the $C'(1/6)$ condition. For instance, we can take $S=\{a,b\}$ and $r_i=(a^ib^i)^7$ as in <cit.>.
For $I\subseteq\N$, we define $H_I = \la S\mid \{r_i\}_{i\in I}\ra$.

We define two sequences $(i_k)\subset\N$ and $(\varepsilon_i)\subset\Q_{>0}$, with $(i_k)$ increasing, such that

\[ \forall 1\le j\le k, \quad \abs{\rho(H_{I_k},S) - x_j}>\varepsilon_j, \]

where $I_k = \{i_1,\ldots,i_k\}$. Suppose that $(i_j)_{j\le k}$ and $(\varepsilon_j)_{j\le k}$ are fixed. Observe that

* $H_I=\la S\mid \{r_i\}_{i\in I}\ra$ is acylindrically hyperbolic <cit.>, hence every infinite normal subgroup is acylindrically hyperbolic <cit.>. This covers $\lla r_\ell\rra_{H_I}$ for $\ell\notin I$. ($r_\ell$ is not a power of $r_i$ for $i\in I$, hence $\la r_\ell\ra$ is infinite.) It follows that $\lla r_\ell\rra_{H_I}$ is not amenable hence

\[ \forall \ell\notin I,\quad \rho(H_I,S) < \rho(H_{I\cup\{\ell\}},S). \]

* Greendlinger's lemma implies that the Cayley graphs $\Cay(H_I,S)$ and $\Cay(H_J,S)$ coincide up to radius $\frac12\min_{i\in I\triangle J}\abs{r_i}$. In particular, we have $(H_{I\cup\{\ell\}},S)\to (H_I,S)$ in the space of marked groups. Corollary <ref> now implies that

\[ \lim_{\ell\to\infty}\rho(H_{I_k\cup\{\ell\}},S) = \rho(H_{I_k},S). \]

This implies that, for $\ell$ large enough, we have

\[ \forall 1\le j\le k, \quad \abs{\rho(H_{I_k\cup\{\ell\}},S) - x_j}>\varepsilon_j \quad\text{and}\quad \rho(H_{I_k\cup\{\ell\}},S)\ne x_{i+1}. \]

Therefore, we can estimate in parallel (dovetailing) all values $x_j$ for $1\le j\le k+1$ and $\rho(H_{I_k\cup\{\ell\}},S)$ for $\ell>i_k$ (Corollary <ref>), until we find a certificate that some $\ell$ satisfies the previous conditions. We take $i_{k+1}=\ell$ and $0<\varepsilon_{k+1}<\abs{\rho(H_{I_k\cup\{\ell\}},S)-x_{k+1}}$.

Finally, we consider $G=H_{\{i_1,i_2,\ldots\}}$. By construction, we have $\abs{\rho(G,S)-x_j}\ge \varepsilon_j$ for all $j$, hence $\rho(G,S)\notin X$. Moreover, $G$ is given by a recursive $C'(1/6)$ presentation and therefore has decidable Word Problem (using Dehn's algorithm).

Observations (1) and (2) prove that the family $(H_I)_{I\subseteq\N}$ satisfies the conclusions of <cit.>. In particular, this provides a family of $2$-generated groups for which the spectral radius $\rho(H_I,S)$ (or any other strictly monotone parameter) takes a continuum of values. Another family satisfying these conditions is Higman's family $(H_{\bar I})_{I\subseteq \Z}$ used in Section <ref>. We should note, however, that none of these families allows to reprove <cit.> (no isolated points).

We could replace the use of Corollary <ref> by <cit.>, which implies that $\rho(G/\!\lla w_\ell\rra,S)\to \rho(G,S)$ in probability, where $G$ is a fixed non-elementary torsionfree hyperbolic group and $w_\ell\in S^*$ is a random word of length $\ell$.

§ FURTHER REMARKS

§.§ An explicit example
The most natural question is the following:

Does there exist a finitely presented group $(G,S)$ with decidable Word Problem and transcendental spectral radius $\rho(G,S)$?

Sarnak asked if the spectral radius is transcendental for $G=\pi_1(\Sigma_2)$ the surface group <cit.>, and lots of effort has been done to approximate this value <cit.>. Of course, we expect $\rho(G,S)$ to be transcendent even in this case. However, we suggest looking at $G=\Z^d*\Z^d$ (with $d\ge 5$) might be a better try for transcendence.

We consider the cubical set $S_\cube=\{\pm 1\}^d$, which generates a group isomorphic to $\Z^d$. Recall the Green function is defined as

\[ G_{\Z^d,\cube}(z) = \sum_{n\ge 0} p(n)\cdot z^n = \sum_{n\ge 0} {2n\choose n}^d \left(\frac{z}{2^d}\right)^{2n}. \]

This function is a generalized hypergeometric function, specifically

\[ G_{\Z^d,\cube}(z) = \leftindex_{d+1}{F}_{d} \left(\frac12,\ldots,\frac12;1,\ldots,1;z\right).\]

For $d\ge 5$, Woess proves that $\rho(G,S)=1-\frac1{2\theta}$ where
$\theta = G_{\Z^d,\cube}(1)$ <cit.>. (Note that $\theta$ is the expected number of returns at $\mathbf 0$ of the simple random walk.) We are reduced to prove that a value of a G-function at $z=1$ is transcendental. Even though the transcendence of these specific values seems wide open, we fall into the realm of things mathematicians have thought about, and developed some machinery for. <cit.>

§.§ Computability of $\rho(G,S)$

Note that we cannot take $X=\{\text{computable reals}\}$ in Theorem <ref>. (Actually, by construction/Corollary <ref>, the spectral radius will be computable for our examples.) This begs the following question:

Does there exists a marked group $(G,S)$ with decidable Word Problem such that $\rho(G,S)$ is not computable? (Equivalently, not upper semi-computable.)

If we denote $p(2m)=\rho^{2m}/f(m)$ (with $f(m)\ge 1$ the sub-exponential correction). This would imply that there exists no computable function $N\colon \N\to\N$ such that

\[ \forall m\ge N(n),\quad  \frac1m\log\!\big(f(m)\big) \le \frac1n, \]

despite $\frac1m\log\!\big(f(m)\big)\to 0$. An approach in the spirit of Theorem <ref>thm:main could pass by a positive answer to the following question:

Does there exists a finitely generated group $G$ with decidable Word Problem such that, given as input a finite subset $T\subset G$, it is undecidable whether the normal subgroup generated $\lla T\rra_G$ is amenable or not?

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitleProceedings of the National Academy of Sciences
titleTHE WORD PROBLEM

journaltitleMath. notes of the Academy of Sciences of the USSR
titleSimple examples of groups with unsolvable word problem

journaltitleContemporary Mathematics
titleIntroduction to the Rapid Decay property

Berlin, New York

De Gruyter

booktitleProceedings of a Workshop at the Erwin Schrödinger Institute, Vienna, June 18 - July 13, 2001
titleGrowth rates of small cancellation groups

journaltitleCombinatorics, Probability and Computing
titleA Numerical Lower Bound for the Spectral Radius of Random Walks on Surface Groups

journaltitleJournal of Dynamical and Control Systems
titleOn problems related to growth, entropy, and spectrum in group theory

journaltitleAnnales de l'Institut Fourier
titleInfinitely presented graphical small cancellation groups are acylindrically hyperbolic

journaltitleProceedings of the Royal Society of London. Series A.
titleSubgroups of finitely presented groups

journaltitleJournal of the London Math. Society
titleEmbedding Theorems for Groups

journaltitleMonatshefte für Mathematik
titleThe Poisson Boundary of Amenable Extensions

American Mathematical Society

journaltitleTransactions of the American Mathematical Society
titleThe Subgroups of a Free Product of Two Groups with an Amalgamated Subgroup

notePreprint at <https://arxiv.org/abs/2404.10870>
titleMonotone parameters on Cayley graphs of finitely generated groups

American Mathematical Society

journaltitleTransactions of the American Mathematical Society
titleSymmetric Random Walks on Groups

Springer Berlin Heidelberg

seriesClassics in Mathematics
titleCombinatorial Group Theory

journaltitleJournal of Mathematical Sciences
titleAn estimate from above of spectral radii of random walks on surface groups

journaltitleTrudy Mat. Inst. Steklov.
titleOn the algorithmic unsolvability of the word problem in group theory

journaltitleAnnales de l’institut Fourier
titleCogrowth and spectral gap of generic groups

journaltitleTransactions of the American Mathematical Society
titleAcylindrically hyperbolic groups

notePreprint at <https://arxiv.org/abs/2111.01179>
titleComputable analysis on the space of marked groups

Editions de l'Ecole Polytechnique

booktitleActes des Journées X-UPS 2019 : Périodes et transcendance
titleE-fonctions et G-fonctions de Siegel

journaltitleAnnales scientifiques de l'École Normale Supérieure
titleGrowth tightness of free and amalgamated products

Cambridge University Press

seriesCambridge Tracts in Mathematics
titleRandom Walks on Infinite Graphs and Groups

notePreprint available at <https://arxiv.org/abs/1212.5280>
titleGeometry of infinitely presented small cancellation groups, Rapid Decay and quasi-homomorphisms

journaltitleGeometric & Functional Analysis GAFA
titleSome geometric groups with Rapid Decay

journaltitleJournal of Topology and Analysis
titleThe Rapid Decay property and centroids in groups

Springer Science & Business Media

booktitleSur les groupes hyperboliques d’apres Mikhael Gromov
titleSmall cancellation groups

§ PROPERTY (RD) FOR $C'(1/6)$ GROUPS,

BY CORENTIN BODART AND DENIS OSIN

We give a proof that $C'(1/6)$ groups satisfy the Rapid Decay property, uniformly. This is a simplification of the proof for $C'(1/10)$ groups due to Arzhantseva and Drutu <cit.>. A version of this proof, due to the second author, was first circulated in 2014.

Instead of proving property directly, we will show a sufficient condition due to Chatterji and Ruane <cit.> (see also <cit.>). We state it in the (quite restrictive) setting of groups acting on themselves:
[Property (CR)]A marked group $(G,S)$ has the property if there exists a $G$-equivariant map $C\colon G\times G\to\Pc(G)$ such that

* For all $x,y\in G$, we have $x\in C(x,y)$.

* For all $x,y,z\in G$, we have $C(x,y)\cap C(y,z)\cap C(z,x)\ne \emptyset$.

* There exists a polynomial $Q(r)$ such that, for all $x,y\in G$ and all $r\ge 0$,

\[ \abs{C(x,y)\cap B_S(x,r)}\le Q(r). \vspace*{-2mm}\]

* There exists a polynomial $R(r)$ such that, for all $x,y\in G$ satisfying $d_S(x,y)\le r$, the diameter of $C(x,y)$ is bounded by $R(r)$.

The specific polynomials $Q(r)$ and $R(r)$ depends on the choice of a finite generating set $S$, but their mere existence does not.

The link is made through the following result:

If $(G,S)$ has the property for $Q(r)$ and $R(r)$, then it satisfies the Rapid Decay property for $P(r)=Q(R(r))^\frac32$.

§.§ Strebel's description of geodesics in $C'(1/6)$ groups

Let us recall some geometric properties of Cayley graphs of $C'(1/6)$ presentations:

Consider a path labeled by $u$ with $uv\in R$.

* If $\abs{u}<\abs{v}$, then $u$ is the unique geodesic between its endpoints.

* If $\abs{u}=\abs{v}$, then $u$ and $v$ are the only two geodesics between their endpoints.

Let $\alpha$ be a geodesic segment in $\Cay(G,S)$, and let $\beta$ be a cycle labeled by a relation $r\in R$. Then $\alpha\cap \beta$ is either empty or connected.

Consider $p,q\in \alpha\cap\beta$. Using Lemma <ref>app:lem, any geodesic between $p$ and $q$ has to be one of the two arcs of $\beta$ delimited by $p$ and $q$. In particular, this holds for the segment of $\alpha$ between $p$ and $q$.

If $T$ is a simple[meaning the sides are disjoint] geodesic triangle, then any reduced van Kampen diagram it spans is of one of the following forms:

[xscale=.6, yscale=.85]
[circle, fill=black, inner sep=2pt] (x) at (0,0) ;
[circle, fill=black, inner sep=2pt] (y) at (6,0) ;
[circle, fill=black, inner sep=2pt] (z) at (3,3) ;

[inner sep=0] (xy1) at (1,0) ;
[inner sep=0] (xy2) at (2,0) ;
[inner sep=0] (xy3) at (3,0) ;
[inner sep=0] (xy4) at (4,0) ;
[inner sep=0] (xy5) at (5,0) ;
[inner sep=0] (xz1) at (.5,.5) ;
[inner sep=0] (xz2) at (1,1) ;
[inner sep=0] (xz3) at (1.5,1.5) ;
[inner sep=0] (xz4) at (2,2) ;
[inner sep=0] (xz5) at (2.5,2.5) ;

[very thick] (x) – (y) – (z) – (x);
[thick] 	(xy1) – (xz1)
(xy2) – (xz2)
(xy4) – (xz4)
(xy5) – (xz5);
at (3.3,-.66) Type $I_2$;
[rotate=30] at (2.2,.95) $\dots$;

[xscale=.6, yscale=.85]
[circle, fill=black, inner sep=2pt] (x) at (0,0) ;
[circle, fill=black, inner sep=2pt] (y) at (6,0) ;
[circle, fill=black, inner sep=2pt] (z) at (3,3) ;

[inner sep=0] (xy1) at (1,0) ;
[inner sep=0] (xy2) at (2,0) ;
[inner sep=0] (xy3) at (3,0) ;
[inner sep=0] (xy4) at (4,0) ;
[inner sep=0] (xy5) at (5,0) ;
[inner sep=0] (xz1) at (.5,.5) ;
[inner sep=0] (xz2) at (1,1) ;
[inner sep=0] (xz3) at (1.5,1.5) ;
[inner sep=0] (xz4) at (2,2) ;
[inner sep=0] (xz5) at (2.5,2.5) ;
[inner sep=0] (yz1) at (5.5,.5) ;
[inner sep=0] (yz2) at (5,1) ;
[inner sep=0] (yz3) at (4.5,1.5) ;
[inner sep=0] (yz4) at (4,2) ;
[inner sep=0] (yz5) at (3.5,2.5) ;

[very thick] (x) – (y) – (z) – (x);
[thick] 	(1.5,0) – (xz2)
(2.5,0) – (xz4)
(3.5,0) – (yz4)
(4.5,0) – (yz2);
at (3.3,-.66) Type $I_3$;
[rotate=30] at (1.8,.8) $\dots$;
[rotate=-30] at (4.3,.8) $\dots$;

[xscale=.6, yscale=.85]
[circle, fill=black, inner sep=2pt] (x) at (0,0) ;
[circle, fill=black, inner sep=2pt] (y) at (6,0) ;
[circle, fill=black, inner sep=2pt] (z) at (3,3) ;

[inner sep=0] (xy1) at (1,0) ;
[inner sep=0] (xy2) at (2,0) ;
[inner sep=0] (xy3) at (3,0) ;
[inner sep=0] (xy4) at (4,0) ;
[inner sep=0] (xy5) at (5,0) ;
[inner sep=0] (xz1) at (.5,.5) ;
[inner sep=0] (xz2) at (1,1) ;
[inner sep=0] (xz3) at (1.5,1.5) ;
[inner sep=0] (xz4) at (2,2) ;
[inner sep=0] (xz5) at (2.5,2.5) ;
[inner sep=0] (yz1) at (5.5,.5) ;
[inner sep=0] (yz2) at (5,1) ;
[inner sep=0] (yz3) at (4.5,1.5) ;
[inner sep=0] (yz4) at (4,2) ;
[inner sep=0] (yz5) at (3.5,2.5) ;

[very thick] (x) – (y) – (z) – (x);
[thick] 	(xy1) – (xz1)
(2.5,0) – (1.33,1.33)
(xy5) – (yz1)
(3.5,0) – (4.66,1.33)
(1.8,1.8) – (4.2,1.8)
(xz5) – (yz5);
at (3.3,-.66) Type $I\!I$;
[rotate=30] at (1.35,.55) $\dots$;
[rotate=-30] at (4.75,.5) $\dots$;
at (3,2.27) $\vdots$;

[xscale=.6, yscale=.85]
[circle, fill=black, inner sep=2pt] (x) at (0,0) ;
[circle, fill=black, inner sep=2pt] (y) at (6,0) ;
[circle, fill=black, inner sep=2pt] (z) at (3,3) ;

[inner sep=0] (xy1) at (1,0) ;
[inner sep=0] (xy3) at (3,0) ;
[inner sep=0] (xy5) at (5,0) ;
[inner sep=0] (xz5) at (2.5,2.5) ;
[inner sep=0] (yz1) at (5.5,.5) ;
[inner sep=0] (yz5) at (3.5,2.5) ;

[very thick] (x) – (y) – (z) – (x);
[thick] 	(xy1) – (xz1)
(xy3) – (1.33,1.33)
(xy5) – (yz1)
(xy3) – (4.66,1.33)
(1.8,1.8) – (4.2,1.8)
(xz5) – (yz5);
at (3.3,-.66) Type $I\!I\!I_1$;
[rotate=30] at (1.45,.5) $\dots$;
[rotate=-30] at (4.7,.5) $\dots$;
at (3,2.27) $\vdots$;

[xscale=.6, yscale=.85]
[circle, fill=black, inner sep=2pt] (x) at (0,0) ;
[circle, fill=black, inner sep=2pt] (y) at (6,0) ;
[circle, fill=black, inner sep=2pt] (z) at (3,3) ;

[inner sep=0] (xy1) at (1,0) ;
[inner sep=0] (xy5) at (5,0) ;
[inner sep=0] (xz1) at (.5,.5) ;
[inner sep=0] (xz5) at (2.5,2.5) ;
[inner sep=0] (yz1) at (5.5,.5) ;
[inner sep=0] (yz2) at (5,1) ;
[inner sep=0] (yz3) at (4.5,1.5) ;
[inner sep=0] (yz4) at (4,2) ;
[inner sep=0] (yz5) at (3.5,2.5) ;
[inner sep=1pt, circle, fill=black] (m) at (3,.95) ;

[very thick] (x) – (y) – (z) – (x);
[thick] 	(xy1) – (xz1)
(2.5,0) – (1.33,1.33)
(xy5) – (yz1)
(3.5,0) – (4.66,1.33)
(1.8,1.8) – (4.2,1.8)
(xz5) – (yz5)
(m) – (xy3)
(m) – (1.55,1.55)
(m) – (4.45,1.55);
at (3.3,-.66) Type $IV$;
[rotate=30] at (1.35,.55) $\dots$;
[rotate=-30] at (4.75,.5) $\dots$;
at (3,2.27) $\vdots$;

[xscale=.6, yscale=.85]
[circle, fill=black, inner sep=2pt] (x) at (0,0) ;
[circle, fill=black, inner sep=2pt] (y) at (6,0) ;
[circle, fill=black, inner sep=2pt] (z) at (3,3) ;

[inner sep=0] (xy1) at (1,0) ;
[inner sep=0] (xy3) at (3,0) ;
[inner sep=0] (xy5) at (5,0) ;
[inner sep=0] (xz1) at (.5,.5) ;
[inner sep=0] (xz5) at (2.5,2.5) ;
[inner sep=0] (yz1) at (5.5,.5) ;
[inner sep=0] (yz5) at (3.5,2.5) ;
[inner sep=1pt, circle, fill=black] (m) at (3,1.05) ;

[very thick] (x) – (y) – (z) – (x);
[thick] 	(xy1) – (xz1)
(2.5,0) – (1.33,1.33)
(xy5) – (yz1)
(3.5,0) – (4.66,1.33)
(1.8,1.8) – (4.2,1.8)
(xz5) – (yz5)
(m) – (3,1.8)
(m) – (1.916,0.666);
[thick, red] (m) – (4.083,0.666);
at (3.3,-.66) Type $V$;
[rotate=30] at (1.35,.55) $\dots$;
[rotate=-30] at (4.75,.5) $\dots$;
at (3,2.27) $\vdots$;

A recurring observation is that every interior (resp. exterior) consolidated[i.e. concatenation of edges seen as a single segment on the previous diagrams, eg. the red segment] edge of a face labeled by $r\in R$ has length $<\frac16\abs{r}$ (resp. $\le\frac12\abs r$).

§.§ Proof of property (CR)

For each $x,y\in G$, we pick $[x,y]$ a geodesic between $x$ and $y$. (In a $G$-equivariant way: pick the geodesic with ShortLex labelling.)

We define $C(x,y)$ as the union of $[x,y]$ with all loops $\gamma$ labeled by relations such that $\abs{\gamma\cap[x,y]}\ge \frac16\abs{\gamma}$ (meaning the number of common edges). We consider $C(x,y)$ as a subgraph, formed by all vertices and edges of this geodesic and these cycles.

We now check that this construction satisfies Property (CR).

* This is obvious.

* Fix $x,y,z\in G$. Let $p_x$ be the point on $[x,y]\cap [z,x]$ furthest from $x$, and similarly for $p_y,p_z$. It follows that $[p_x,p_y],[p_y,p_z],[p_z,p_x]$ form a simple geodesic triangle.

In each of the $6$ types above, any cycle $\gamma$ around a face has a most $6$ sides, hence one of its exterior edges $\gamma\cap [p_a,p_b]$ has length $\ge\frac16\abs{\gamma}$ (for $a,b\in\{x,y,z\}$). It follows that $\gamma\subseteq C(a,b)$. An easy case-by-case analysis now implies that

\[ C(x,y)\cap C(y,z)\cap C(z,x)\ne\emptyset.\]

* Claim. For every $p\in C(x,y)$, we have $d_S(x,p)\ge d_{C(x,y)}([x,y],p)$.

If $p\in[x,y]$, the statement is obvious. Suppose $p\in \gamma$. We consider $[x,p]$ a geodesic between $x$ and $p$. Let $p'$ be the point on $[x,p]\cap\gamma$ furthest from $p$, and $x'$ be the point on $[x,p]\cap[x,y]$ furthest from $x$ (see Figure <ref>app:fig:wlog). Observe that $d_S(x',p')\ge d_{C(x',y)}([x',y],p')$ implies the desired inequality, hence we may suppose w.l.o.g. $p=p'$ and $x=x'$.

[circle, fill=black, inner sep=1.5pt, label=below:$x$] (x) at (-3.5,0) ;
[circle, fill=black, inner sep=1.5pt, label=[label distance=-3.5pt]below:$x'$] (x') at (-2.5,0) ;
[circle, fill=black, inner sep=1.5pt, label=below:$y$] (y) at (2.5,0) ;
[circle, fill=black, inner sep=1.5pt, label=above:$p'$] (p') at (-.3,1.5) ;
[circle, fill=black, inner sep=1.5pt, label=above:$p$] (p) at (1,1.5) ;

[very thick] (x) – (x') – (y);
[very thick] (x') to [out=25, in=-160, looseness=.9] (p') to [out=20, in=160] (p);
[very thick, dashed, Magenta] (-.7,.8)
to [out=90, in=-160, looseness=.7] (p')
to [out=20, in=160] (p)
to [out=-20, in=100, looseness=.7] (1.5,.8);
[Magenta] at (1.7,1.2) $\gamma$;

figure$p$, $p'$, $x$ and $x'$.

[Turquoise!15] (0,1.5) – (-3,0) – (1,0)
to [out=105, in=-45] (.5,.53)
to [out=135, in=-85] (0,1.5);
[Turquoise!30] (.3,0) – (1,0) to [out=105, in=-45] (.5,.53) – (.3,0);
[thick, black] (.3,0) – (.5,.53);
at (.62,.18) $r$;

[Magenta, very thick] (1,0)
to [out=105, in=-45] (.5,.53)
to [out=135, in=-85] (0,1.5)
to [out=95, in=-120] (.25,2.2);
[Magenta] at (.5,1) $\gamma$;

[circle, fill=black, inner sep=1.5pt, label=below:$x$] (x) at (-3,0) ;
[circle, fill=black, inner sep=1.5pt, label=above:$p$] (p) at (0,1.5) ;
[circle, fill=black, inner sep=1.5pt, label=below:$q$] (q) at (1,0) ;
[very thick] (p) – (x) – (q) – (1.5,0);

figureA relation in the $q$ corner.

We pick $q$ an endpoint of $\gamma\cap[x,y]$ such that $\abs{[p,q]}\le\frac12\abs\gamma$ where $[p,q]$ is the corresponding arc of $\gamma$. If both endpoints satisfy this condition, we pick $q$ closer to $x$. We consider the simple geodesic triangle formed by $[x,q]$, $[x,p]$, $[p,q]$.

Observe that the corner $q$ cannot be filled by a triangle relation (Figure <ref>app:fig:corner). Indeed $\abs{r\cap[x,p]}\le\frac12\abs r$, $\abs{r\cap [p,q]}<\frac16\abs{r}$ and the interior edges (at most two of them in Type $V$) have length $<\frac16\abs r$. The same is true for the corner $p$. It follows that the diagram spanned has to be of type $I_2$ (see Figure <ref>app:fig:I2).

[Turquoise!15] (0,1.5) – (-3,0) – (1,0)
to [out=105, in=-45] (.5,.53)
to [out=135, in=-85] (0,1.5);
[Turquoise!30] (0,1.5) – (-.75,1.133) – (0,0) – (1,0)
to [out=105, in=-45] (.5,.53)
to [out=135, in=-85] (0,1.5);
at (-.05,.65) $r$;
[rotate=15] at (-1,.45) $\dots$;
[Magenta, very thick] (1,0)
to [out=105, in=-45] (.5,.53)
to [out=135, in=-85] (0,1.5)
to [out=95, in=-120] (.15,2);
[Magenta] at (.5,1) $\gamma$;

[circle, fill=black, inner sep=1.5pt, label=below:$x$] (x) at (-3,0) ;
[circle, fill=black, inner sep=1.5pt, label=above:$p$] (p) at (0,1.5) ;
[circle, fill=black, inner sep=1.5pt, label=below:$q$] (q) at (1,0) ;
[very thick] (p) – (x) – (q) – (1.5,0);
[thick] (-2,0) – (-2.25,.366);
[thick] (-1.5,0) – (-1.875,.55);
[thick] (0,0) – (-.75,1.133);

figureThe true configuration.

Note that, if $r=\gamma$, then $\abs{r\cap [x,p]}=0$ and the interior edge has length $<\frac16\abs r$, and the second arc from $p$ to $[x,y]$ has length $\le \frac12\abs\gamma$ and is closer to $x$, which contradicts the definition of $q$. We conclude that $r\ne\gamma$, hence $\abs{r\cap[x,q]}\le\frac12\abs r$, $\abs{[p,q]}=\abs{r\cap[p,q]}<\frac16\abs r$ and the interior edge is $<\frac16\abs r$. This forces

\[ d_S(x,p) \ge \abs{[x,p]\cap r} \ge \frac16\abs r. \]

In particular, we get $d_{C(x,y)}(x,y)\le \abs{[p,q]}<\frac16\abs r\le d_S(x,p)$.

Hence, for every $p\in B_S(e,r)\cap C(x,y)$, there exists a relation $\gamma$ and an endpoint $q$ of $\gamma\cap[x,y]$ such that $d_{C(x,y)}(p,q)\le r$. In particular, $d_S(x,q)\le 2r$. Note that each point $q\in[x,y]$ is the endpoint of at most two segments $\gamma\cap[x,y]$. Indeed we cannot have $\gamma_1\cap[x,y]\subseteq \gamma_2\cap[x,y]$ by the $C'(1/6)$ condition. It follows that

\[ \abs{B_S(e,r)\cap C(x,y)} \le (2r+1)^2 =: Q(r). \]

* Fix $x,y\in G$. Let $p,q\in C(x,y)$. We first suppose that $p\in \gamma_1$ and $q\in \gamma_2$, with $\gamma_1\cap\gamma_2\cap[x,y]\ne\emptyset$. Then

\begin{align*}
& \le \min\{\ell_1+a+\ell_2;\; r_1+c+r_2\} \\
& \le \frac12(\ell_1+r_1+\ell_2+r_2+a+c) \\
& \le \frac12\big(5(a+b)+5(b+c)+a+c\big) \\
& \le 5(a+b+c) \le 5 \, d_S(x,y).
\end{align*}

[thick, Turquoise, fill=Turquoise!20] (-2.2,0)
to [out=60, in=170, looseness=.9] (-.8,1.2)
to [out=-10, in=120, looseness=.9] (.5,0) to (-2.2,0);
[thick, Magenta, fill=Magenta!20] (-1.2,0)
to [out=-60, in=180, looseness=.9] (.5,-1.2)
to [out=0, in=-130, looseness=.9] (2,0) to (-1.2,0);
[Turquoise] at (-.9,.5) $\gamma_1$;
[Magenta] at (.5,-.6) $\gamma_2$;

[circle, fill=black, inner sep=1.5pt, label=below:$x$] (x) at (-3,0) ;
[circle, fill=black, inner sep=1.5pt, label=below:$y$] (y) at (3,0) ;
[very thick] (x) – (y);

[circle, fill=black, inner sep=1pt] (l1) at (-2.2,0) ;
[circle, fill=black, inner sep=1pt] (l2) at (-1.2,0) ;
[circle, fill=black, inner sep=1pt] (r1) at (.5,0) ;
[circle, fill=black, inner sep=1pt] (r2) at (2,0) ;
[circle, fill=black, inner sep=1.2pt, label=above:$p$] (p) at (-.8,1.2) ;
[circle, fill=black, inner sep=1.2pt, label=below:$q$] (q) at (.5,-1.2) ;

at (-1.7,-.25) $a$;
at (-.35,-.22) $b$;
at (1.25,-.25) $c$;
at (-2.1,.7) $\ell_1$;
at (.5,.65) $r_1$;
at (-.95,-.77) $\ell_2$;
at (1.8,-.8) $r_2$;

(b) at (0,2) ;

In the other cases ($p$ or $q$ on $[x,y]$; $\gamma_1,\gamma_2$ disjoints), we have $d_S(p,q)\le 3d_S(x,y)$. In conclusion, we have $\diam_S(C(x,y)) \le 5 \, d_S(x,y)$, so $R(r)=5r$ satisfies.

This finishes the proof of the (CR) property. Combining this with Proposition <ref>, we deduce the Rapid Decay property in a uniform and effective way:

Let $G=\la S\mid R\ra$ be a $C'(1/6)$ presentation (with $R$ possibly infinite), then $(G,S)$ has the Rapid Decay property with $P(r)=(10r+1)^3$.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitleProceedings of the National Academy of Sciences
titleTHE WORD PROBLEM

journaltitleMath. notes of the Academy of Sciences of the USSR
titleSimple examples of groups with unsolvable word problem

journaltitleContemporary Mathematics
titleIntroduction to the Rapid Decay property

Berlin, New York

De Gruyter

booktitleProceedings of a Workshop at the Erwin Schrödinger Institute, Vienna, June 18 - July 13, 2001
titleGrowth rates of small cancellation groups

journaltitleCombinatorics, Probability and Computing
titleA Numerical Lower Bound for the Spectral Radius of Random Walks on Surface Groups

journaltitleJournal of Dynamical and Control Systems
titleOn problems related to growth, entropy, and spectrum in group theory

journaltitleAnnales de l'Institut Fourier
titleInfinitely presented graphical small cancellation groups are acylindrically hyperbolic

journaltitleProceedings of the Royal Society of London. Series A.
titleSubgroups of finitely presented groups

journaltitleJournal of the London Math. Society
titleEmbedding Theorems for Groups

journaltitleMonatshefte für Mathematik
titleThe Poisson Boundary of Amenable Extensions

American Mathematical Society

journaltitleTransactions of the American Mathematical Society
titleThe Subgroups of a Free Product of Two Groups with an Amalgamated Subgroup

notePreprint at <https://arxiv.org/abs/2404.10870>
titleMonotone parameters on Cayley graphs of finitely generated groups

American Mathematical Society

journaltitleTransactions of the American Mathematical Society
titleSymmetric Random Walks on Groups

Springer Berlin Heidelberg

seriesClassics in Mathematics
titleCombinatorial Group Theory

journaltitleJournal of Mathematical Sciences
titleAn estimate from above of spectral radii of random walks on surface groups

journaltitleTrudy Mat. Inst. Steklov.
titleOn the algorithmic unsolvability of the word problem in group theory

journaltitleAnnales de l’institut Fourier
titleCogrowth and spectral gap of generic groups

journaltitleTransactions of the American Mathematical Society
titleAcylindrically hyperbolic groups

notePreprint at <https://arxiv.org/abs/2111.01179>
titleComputable analysis on the space of marked groups

Editions de l'Ecole Polytechnique

booktitleActes des Journées X-UPS 2019 : Périodes et transcendance
titleE-fonctions et G-fonctions de Siegel

journaltitleAnnales scientifiques de l'École Normale Supérieure
titleGrowth tightness of free and amalgamated products

Cambridge University Press

seriesCambridge Tracts in Mathematics
titleRandom Walks on Infinite Graphs and Groups

notePreprint available at <https://arxiv.org/abs/1212.5280>
titleGeometry of infinitely presented small cancellation groups, Rapid Decay and quasi-homomorphisms

journaltitleGeometric & Functional Analysis GAFA
titleSome geometric groups with Rapid Decay

journaltitleJournal of Topology and Analysis
titleThe Rapid Decay property and centroids in groups

Springer Science & Business Media

booktitleSur les groupes hyperboliques d’apres Mikhael Gromov
titleSmall cancellation groups