# Towards Precise Pruning Points Detection using Semantic-Instance-Aware Plant
Models for Grapevine Winter Pruning Automation

Miguel Fernandes1,2, Antonello Scaldaferri1, Paolo Guadagna3, Giuseppe
Fiameni4,
Tao Teng1,3, Matteo Gatti3 Stefano Poni3, Claudio Semini5, ,
Darwin Caldwell1, , Fei Chen6 This research is supported by the project
“Grapevine Recognition, Manipulation and Winter Pruning Automation” funded by
IIT-Unicatt Joint Lab. The study was co-funded by Italian Ministry of
University and Research PRIN 20172HHNK5 Project. (Corresponding author: Fei
Chen)1Miguel Fernandes, Antonello Scaldaferri, Tao Teng, Darwin Caldwell are
with Active Perception and Robot Interactive Learning Laboratory, Department
of Advanced Robotics, Istituto Italiano di Tecnologia, Via Morego 30, 16163,
Genova, Italy (e-mail: name.surname@iit.it).2Miguel Fernandes is with
Department of Informatics, Bioengineering, Robotics and System Engineering,
Università di Genoa, Viale Causa 13, 16145 Genova, Italy (e-mail:
miguel.ferreira@iit.it).3Paolo Guadagna, Tao Teng, Matteo Gatti, Stefano Poni
are with Department of Sustainable Crop Production, Università Cattolica del
Sacro Cuore, Via Emilia Parmense 84, 29122 Piacenza, Italy (e-mail:
name.surname@unicatt.it).4Giuseppe Fiameni is with NVIDIA AI Technology Center
(NVAITC), Italy (email: gfiameni@nvidia.com).5Claudio Semini is with Dynamic
Legged Systems (DLS) lab, Istituto Italiano di Tecnologia, Via Morego 30,
16163, Genova, Italy (e-mail: name.surname@iit.it).6Fei Chen is with
Department of Mechanical and Automation Engineering, T-Stone Robotics
Institute, The Chinese University of Hong Kong, Chung Chi Rd, Ma Liu Shui,
Hong Kong (e-mail: f.chen@ieee.org).

###### Abstract

Grapevine winter pruning is a complex task, that requires skilled workers to
execute it correctly. The complexity makes it time consuming. It is an
operation that requires about 80-120 hours per hectare annually, making an
automated robotic system that helps in speeding up the process a crucial tool
in large-size vineyards. We will describe (a) a novel expert annotated dataset
for grapevine segmentation, (b) a state of the art neural network
implementation and (c) generation of pruning points following agronomic rules,
leveraging the simplified structure of the plant. With this approach, we are
able to generate a set of pruning points on the canes, paving the way towards
a correct automation of grapevine winter pruning.

##  I INTRODUCTION

An important task to perform in a vineyard is winter pruning, a complex
operation that needs to be completed during the dormant season [1]. Performing
a balanced winter pruning allows a good compromise between remunerative yield
and desired grape quality hence maximizing grower’s income [2, 3]. This
selective operation requires annually about 80-120 man-hours per hectare. Due
to increased skill shortage and limited labor availability in the agricultural
sector, automating winter pruning is a crucial step to increase efficiency and
reduce production costs.

Figure 1: The top half shows an example of manual grapevine pruning and the
bottom half illustrates our robot performing grapevine pruning along with the
desired plant modeling, with the dark blue representing the main cordon, light
blue the canes, yellow the nodes and red mark the pruning points. Figure 2:
Pipeline of the winter pruning system, from the initial step of navigation up
to the cutting.

As part of the ongoing collaboration between Istituto Italiano di Tecnologia
(IIT) and the Universita’ Cattolica del Sacro Cuore, Piacenza (UCSC), the
project VINUM has been addressing the automation of spur winter pruning of
grapevines for the last few years. Figure 1 shows a few images of hand pruning
and a robot-performed pruning. Our current prototype has successfully
performed several trials in controlled environments both inside the laboratory
as well as in a simulated vineyard at UCSC (simulated means that the plants
are growing in pots instead of the field)[4, 5]. Figure 2 provides an overview
of the pipeline that we developed, showing the sequence of operations that the
pruning robot needs to execute from the approach to the vine to the extraction
of the pruning points and cuttings. With consideration to our previous
work[6], where we presented an initial dataset where grapevine organs were
classified into 3 classes, a representative computer model of the grapevine
specimen and an initial pruning point selection, we built upon those bases to
create the new contributions of this paper:

  * •

A new dataset for grapevine segmentation based on five classes instead of
three.

  * •

A more uniform image capture process, along with its validation.

  * •

A pruning points generation based on agronomic rules instead of proof of
concept selection presented previously.

The neural network has also been retrained with the new dataset. In order to
demonstrate the evolution, the neural network of our previous work is compared
with the current one, along with the pruning points that are generated.

The remainder of this paper is structured as follows: Section II presents the
related work, Section III describes the created dataset, Section IV presents
the description and training procedure for the neural network, Section V shows
how we improved the grapevine plant model and the algorithm that creates the
model. Section VI presents the improvement to the pruning point detection. The
experimental setup and results are discussed in Section VII and finally, the
conclusions and possible future works are presented in Section VIII.

##  II Related Work

In the deep learning field, various object segmentation[7], detection[8], and
tracking algorithms[9] have been presented in the scientific communities in
the past years. Some of these studies have also been applied on the agri-food
field, such as fruit detection [10] for yield estimation purposes [11], weed
removal [12, 13] and plant phenotyping [14]. The authors of [15] developed a
method that generates potential pruning points in long-cane pruned grapevines.
The authors in [12] deal with the issues created by the variety of work
regions in the fields, lighting, weather conditions, which leads to the
difficulties for semantic segmentation of crop fields. The authors in [14]
present a proof of concept for quantifying and detecting plant organs for non-
destructive yield estimation. This approach is based on automated detection,
localization, count and analysis of plant parts used to estimate yield. The
authors in [9] present a new public dataset with grape clusters annotated in
300 images and a new annotation with interactive image segmentation to
generate object masks, identifying background and occluding foreground pixels
using Scribbles. There is also an evaluation of two state-of-the-art methods
for object detection, object segmentation and a fruit counting methodology.
Authors in [15] used a trinocular stereo camera system and correspondence
algorithms to obtain a 3D reconstruction of the plant, which is useful to
compute the pruning points in the wild. It achieves this by using a vehicle
that encloses the grapevines, creating consistent lighting and background
conditions that simplify the vision algorithms.

These representative works demonstrated several important concepts, such as
real-time plant segmentation [13], the more in-depth plant feature extraction
for finding multiple parts of the plant[14], and an annotation tool to
generate a segmentation dataset quickly[9] and a pruning generation system.
However, an approach to prune without the use of complex stereo camera systems
or the use of mobile platform that encloses the grapevine, is still missing in
the literature. Our proposed method uses an off-the-shelf depth camera (Intel
realsense) and does not require a uniform background behind the grapevine.

Figure 3: Schematic representation of a grapevine pruning region area,
illustrating the 5 grapevine organs: Main Cordon, Arm, Spur, Cane, and Node.
The red lines indicate the desired pruning points.

##  III Dataset

A dataset is an important component on the implementation of a machine
learning method. Since no dataset with the plant organ segmentation of spur-
pruned grapevines was found by the authors, it was decided to create a new
dataset with the annotation of five classes: main cordon, arm, spur, cane and
node. This structure can be seen in the Fig. 3, along with the correct pruning
points for the shown example. Each class corresponds to a different visible
organ during the winter pruning. The grapevine has several organs, the Main
Cordon, also referred as the permanent cordon. Connected to the main cordon we
may have at least three-year-old wood, which commonly would be called an Arm.
Two-year-old wood which is the Spur, the one-year-old structure is the Cane.
The Cane has several structures which are the Nodes. An example of these
annotation concepts can be seen in Fig. 4. Since it is one of the main
contributions to the scientific community, the authors shared the created
dataset in open access format at https://zenodo.org/record/5501784.

###  III-A Data Acquisition

The data acquisition was performed in the simulated vineyard at UCSC,
Piacenza, Italy. It is composed of two rows of grapevine specimens, running a
shoot thinning experiment, where a group of seven plants is acting as control
group, and the second group of eight grapevines is subjected to shoot
thinning. Each plant has around five spurs, and the photos are taken from both
sides of the grapevine specimen, meaning that there is one picture where the
plant grows from left to right, and the other side where the plant grows from
right to left. The resolution of the images is 4608x3456 pixels, and we have a
total of 148 images.

TABLE I: Number of annotations per class category in each plant group. | Control | Shoot Thinning
---|---|---
Main Cordon | 79 | 84
Cane | 440 | 341
Node | 110 | 912
Arm | 103 | 154
Spur | 116 | 144
Total | 1838 | 1635

There are other two sets of images that were created, one that contains 100
images, captured from another row present in the simulated vineyard, with the
same resolution as previously mentioned but currently not annotated. The other
is an assorted group of images, containing total of 196 images, from various
angles and various resolutions that is partly annotated, with 153 images
annotated out of 196.

###  III-B Data Annotation

The dataset is being annotated following the COCO segmentation dataset, with
the five mentioned classes, the main cordon, the arm, the spur, the cane, and
the node. We chose the COCO format for the annotation since it is a common
format for segmentation annotation, which contributes to a higher availability
of annotation tools that use this format, as well as some neural network
frameworks provide built-in processing of this format. The annotation tool
being used is COCO annotator, a web-based tool that is designed for
efficiently label images. The 149 captured images were annotated and then
split into 80% for training and 20% for images, corresponding to 119 training
images and 30 evaluation images. We consider that there is no current need for
a testing set since what can be considered the testing set for the neural
network is the on-field testing of the platform. The images are being
annotated in their original size, allowing to downscale the image as required.
These images were annotated by two agronomy experts.

Figure 4: Example of a grapevine organ annotation, where purple represents the
main cordon class, green the node arm class, red the spur class, orange the
cane class, and light blue the node class. This picture is taken inside the
simulated vineyard at UCSC, Piacenza, Italy.

##  IV Neural Network

This section describes the neural network architecture and backbone that was
used for this work. The framework that was used is the same as the previous
work, which is Detectron2[16], Facebook AI Research’s implementation of state-
of-the-art detection algorithms, using Pytorch, using Mask R-CNN, and, instead
of using several backbones, we settled for just one, which is the ResNext
X101-FPN[17]. This ResNext is an improvement on the original ResNet network,
considering a new dimension named cardinality on top for the normal height and
depth of a neural network, which is the size of the set of transformations.

The network is being trained using the default training procedure of
Detectron2. This procedure creates a model, optimizer, scheduler, and
dataloader with the default configurations provided along with the model. It
then loads the pre-trained model weights, initializes logging functions and
starts to follow a standard training workflow with a single-optimizer single-
datasource iterative optimization. The training hyperparameters are the
default ones, with the only changes being the batch size changed to 2, from
original value 16, and the number of training iterations that was changed to
50000, from the original 270000. These changes were made to adjust to the size
of our dataset, that is considered small for the network itself.

##  V Grapevine Plant Model Structure & Modeling Algorithm

In our previous work [6], we introduced a 2D plant modeling algorithm, which
considers only three types of organs. This type of model can lead to
inconsistencies in the overall model, resulting in an unreliable information.
Understanding that there where ways to improve the model, using depth
information, we present a new modeling algorithm, that we consider more
reliable and that has stricter relationships between the different detected
organs of the plant, considering the new five-class categorization.

###  V-A Grapevine Plant Model Structure

To create this model we use a tree-based data structure, since its structure
is suitable to represent the relationship of the different detected grapevine
organs. Each node of this data structure is a generic grapevine item, which is
the computational representation of a grapevine organ. Each of them contains
all the information required for the subsequent pruning points estimation
step, such as organ type, instance ID, bounding box, segmentation mask,
origin, endpoint, parent organ, children organs, distance from the parent
organ and other information used for graphical representation. The
relationship information is stored in the parent and children attributes of
each node. In addition, the children items of each node are sorted by the
value of the distance from the parent parameter. Based on the new five-class
categorization, we defined a new set of more specific and stricter
relationships between the different types of organs, to create the new plant
model, listed in Table II.

TABLE II: Relationships between the different types of organs. Parent Organ Type | Children Organs Types
---|---
Main Cordon |  Arm, Spur, Cane
Arm |  Spur, Cane
Spur | Cane
Cane | Node

###  V-B Grapevine Plant Modeling Algorithm

For the modeling algorithm, we use an upgraded version of the previous
algorithm in [6] to compute the connections between two sets of organs of
different types, whose pseudo-code is given in Algorithm 1. It uses the same
concept of overlap between masks as the previous one and uses the same masks
dilation and subdivision heuristics. The main difference is that now we
consider both upwards and downwards growing directions of the organs, i.e.
organs that grow either from the upper side of the parent organ or from the
lower side. To compute all the final connections for the entire model, this
algorithm is executed for each type of parent-children connection, according
to Table II. Each time, it takes as input the two corresponding sets of items,
the first for items of type parent and the second for items of type children.
For the last type of connections, where the nodes are considered, the set of
the children masks is replaced with their corresponding bounding boxes for
simplicity.

parameters : $dilation,max\\_iter,n,include\\_top$

input : $items_{A}\rightarrow{\text{Set of type A items}}$

input : $items_{B}\rightarrow{\text{Set of type B items}}$

output : $connections\rightarrow{\text{Map of connections}}$

$masks_{A}\leftarrow$ set of masks of $items_{A}$

$IDs_{A}\leftarrow$ set of instance IDs of $items_{A}$

foreach  _$i,mask_{A}\in\textbf{enumerate}(masks_{A})$_ do

$masks_{A}[i]\leftarrow mask_{A}*(IDs_{A}[i]+1)$

foreach  _$item\in items_{B}$_ do

$iter\leftarrow 0,connected\leftarrow False$

$mask\leftarrow item$ segmentation mask

while  _$iter\leq max\\_it\textbf{ and not}(connected)$_ do

if  _$iter >0$_ then

Dilate $mask$

$indices\leftarrow mask$ non-zero values indices

Obtain $masks_{A}$ unique values at $indices$

if  _There are non-zero correspondences_ then

$ID_{A},mask_{A}\leftarrow[lowest]$ correspondence

$inter\leftarrow\textbf{intersection}(mask_{A},mask)$

if  _$inter$ is in the $mask$ $[n^{th}]$ slot_ then

$item_{A}\leftarrow items_{A}(ID_{A})$

Add $(item_{A},item)$ to $connections$

$connected\leftarrow True$

$iter++$

if  _$\textbf{not}(connected)\textbf{ and }include\\_top$_ then

Repeat the previous while loop considering the $[highest]$ correspondence and
the $[1^{st}]$ slot

Algorithm 1 Compute connections between two types of organs.

##  VI Pruning Points Detection

After obtaining the grapevine plant model, it is used to compute the pruning
points. One of the main contributions of this work is to provide a set of
pruning points that is as reliable as possible, meaning, the points that are
provided will not damage the plant if cut. There is the possibility that
certain cuts will not be performed. In order to obtain such a set of points,
we defined a set of assessments to simplify the reasoning process of the
pruning points detection phase. The set is comprised of the following
assessments: pruning region location, pruning region canes number, basal cane
growth direction, basal cane vigor, basal cane origin and adjacent pruning
regions distance. In the created model, each pruning region is a grapevine
item and its type can be either arm, spur or cane, according to Table II. The
pruning region location is the side of the main cordon from which the pruning
region grows up. For its assessment, three different angles $\alpha_{V}$,
$\alpha_{I}$ and $\alpha_{D}$ are considered to classify the pruning region as
ventral, intermediate or dorsal, which means that the pruning region grows
from the bottom, middle or top side, respectively. We define $(x_{PR},y_{PR})$
as the pruning region origin image coordinates and $d_{MC}$ as the diameter of
the main cordon, that can be estimated from its segmentation mask, at the
column $x_{PR}$, in pixels. Moreover we define $y$ as the first non-zero row
in the main cordon segmentation mask. With these definitions, the pruning
region location is classified as:

$\begin{cases}dorsal&\mbox{if
}y_{PR}<y+\frac{d_{MC}}{2}*(1-\cos{\frac{\alpha_{D}}{2}})\\\ ventral&\mbox{if
}y_{PR}>y+d-\frac{d_{MC}}{2}*(1-\cos{\frac{\alpha_{V}}{2}})\\\
intermediate&\mbox{otherwise}\end{cases}$ (1)

For the pruning region canes number assessment, a Depth-first search algorithm
is used, counting the items of type cane in the sub-tree represented by the
pruning region. The basal cane, in a pruning region, is the cane closest to
the main cordon. For its growth direction assessment, other two different
angles $\alpha_{L}$ and $\alpha_{C}$ are considered to establish whether it is
vertical or not, in both the lateral and cross sections respectively. We
define $(x_{o},y_{o},z_{o})$ and $(x_{e},y_{e},z_{e})$ as the basal cane
origin and endpoint in the 3D space, that can be computed thanks to the depth
image and camera intrinsic parameters. With these definitions, the growth
direction can be classified as:

$\begin{cases}vertical&\mbox{if
}\frac{|x_{o}-x_{e}|}{|y_{o}-y_{e}|}\leq\alpha_{L}\And\frac{|z_{o}-z_{e}|}{|y_{o}-y_{e}|}\leq\alpha_{C}\\\
not\ vertical&\mbox{otherwise}\end{cases}$ (2)

The vigor of the basal cane is its thickness and it can be estimated from its
segmentation mask and the depth image. It is used to establish which canes to
keep and which to remove, if too thick or too thin, based on two threshold
values. We define $rows$ and $cols$ as the row and column indices of the basal
cane segmentation mask. We suppose that the basal cane is vertical or
horizontal based on its bounding box aspect ratio, for simplicity. The
subsequent considerations are valid for vertical basal canes. In the case of
horizontal basal canes just swap the rows with the columns. Since the depth at
the basal cane segmentation mask boundaries may not be accurate, for each
$row$ in $rows$, we consider an estimation of the $row$ depth, considering the
midpoint between the columns of the mask in that specific $row$. This $row$
depth estimation is then used to obtain the 3D points at the $row$ boundaries,
to compute the $row$ thickness as:

$\begin{gathered}thicknesses\leftarrow\mbox{empty list}\\\ \forall row\in
rows\\\ cols_{row}\leftarrow\mbox{get $cols$ values where $rows$ is $row$}\\\
col_{mean}\leftarrow mean(cols_{row})\\\ depth\leftarrow
estimate\\_real\\_depth(\langle col_{mean},row\rangle)\\\
col_{m},col_{M}\leftarrow\min(cols_{row}),\max(cols_{row})\\\
\vec{p}_{row_{1}}\leftarrow to\\_3D(\langle col_{m},row\rangle,depth)\\\
\vec{p}_{row_{2}}\leftarrow to\\_3D(\langle col_{M},row\rangle,depth)\\\
thickness_{row}\leftarrow|\vec{p}_{row_{1}}-\vec{p}_{row_{2}}|\\\ \mbox{add
$thickness_{row}$ to $thicknesses$}\end{gathered}$ (3)

The vigor final estimation is computed considering the mean value of all the
$thicknesses$ among all the $rows$.

Another important point is the basal canes origin assessment, that is
necessary for two evaluations. The first is to classify the pruning region as
new or not, verifying whether the parent organ type is main cordon or not,
respectively. The second is to verify if the pruning region concerns a
replacement cut or not, verifying whether the parent organ type is arm or not,
respectively. The last considered assessment is the adjacent pruning regions
distance assessment. This is necessary in the cases where there are multiple
new pruning regions that are close together. In this cases, based on a
threshold value, it is verified whether these pruning regions are too close or
not, in order to remove or keep them, respectively. We define $PRs$ as the set
of all the grapevine plant pruning regions. For each pruning region $PR$ in
$PRs$, its distance $d_{PR}$ to adjacent pruning regions is computed as:

$\begin{gathered}PR_{-1}\leftarrow\mbox{get the previous pruning region from
}PRs\\\ PR_{+1}\leftarrow\mbox{get the next pruning region from }PRs\\\
\vec{p}_{PR}\leftarrow\mbox{get the 3D origin of }PR\\\
\vec{p}_{PR_{-1}}\leftarrow\mbox{get the 3D origin of }PR_{-1}\\\
\vec{p}_{PR_{+1}}\leftarrow\mbox{get the 3D origin of }PR_{+1}\\\
d_{PR}\leftarrow\max(|\vec{p}_{PR}-\vec{p}_{PR_{-1}}|,|\vec{p}_{PR}-\vec{p}_{PR_{+1}}|)\end{gathered}$

Furthermore, in order to perform the final pruning in a correct manner, we
defined different types of cuts for the grapevine organs, the details of which
are given in Table III.

TABLE III: Types of pruning cuts. Cut type |  Description
---|---
Clean cut |  The corresponding organ is completely removed.
Base-bud cut |  The base-buds are kept only, while the remaining (upper) part is removed.
Spur cut |  The first N nodes of the basal cane are left, while the rest of it is removed. If it is not a new pruning region, the spur parent organ is cut above the basal cane.
Replacement cut |  The first N nodes of the basal cane are left, while the rest of it is removed. The arm parent organ is cut above the basal cane.

According to the assessments, evaluations, rules, heuristics, equations and
types of cuts described above, the final set of pruning points is derived. In
particular, each pruning point $\vec{pp}$ is computed as a point between two
other points $\vec{p}_{1}$ and $\vec{p}_{2}$. These points $\vec{p}_{1}$ and
$\vec{p}_{2}$ can be nodes locations, canes / spurs / arms origins or
endpoints. It may happen that the estimated pruning points are too far from
their corresponding organ origin. This can happen when nodes are not detected.
In these cases, it is helpful to compute the pruning point using a distance
parameter $d$, that can be set by the user, based on the vineyard grapevine
type. With these definitions, a pruning point $\vec{pp}$ can be computed as:

$\begin{gathered}D\leftarrow|\vec{p}_{1}-\vec{p}_{2}|\\\
w_{1}\leftarrow\frac{|D-d|}{D}\\\ w_{2}\leftarrow 1-w_{1}\\\
\vec{pp}\leftarrow w_{1}*\vec{p_{1}}+w_{2}*\vec{p_{2}}\\\ \end{gathered}$

And its corresponding orientation angle $\alpha$ as:

$\begin{gathered}\delta_{x}\leftarrow{p_{1}}_{x}-{p_{2}}_{x}\\\
\delta_{y}\leftarrow{p_{1}}_{y}-{p_{2}}_{y}\\\
\alpha\leftarrow\begin{cases}0,&\mbox{if }\delta_{x}=0\\\
\frac{\pi}{2},&\mbox{if }\delta_{y}=0\\\
\arctan{\frac{\delta_{y}}{\delta_{x}}}-\mathop{\mathrm{sign}}{\frac{\delta_{y}}{\delta_{x}}}*\frac{\pi}{2},&\mbox{otherwise}\end{cases}\end{gathered}$

Note that if $d$ is $0$, the pruning point is placed in $\vec{p}_{1}$ and if
$d$ is $\frac{1}{2}$, the pruning point is the midpoint between $\vec{p}_{1}$
and $\vec{p}_{2}$.

Since the pruning point is computed as a point between two other points, along
a straight line, it may occur that it is not on the corresponding grapevine
organ, that means it is not contained in the corresponding grapevine item
segmentation mask. As such, we need to move the estimated points on their
corresponding organs. This correction is applied to each pruning point, moving
the point horizontally or vertically until it reaches either its corresponding
segmentation mask or a meaningful area of the depth image.

(a) Ground-Truth Segmentation.

(b) Inferred Segmentation in the lab.

(c) Inferred Segmentation in the wild.

Figure 5: Modeling Algorithm Results: in this figure, the models are drawn on
the color image, to show that it contains all the information needed to
compute the pruning points, using a simplified structure and discarding the
complications of the raw images. Fig.5(a) uses the ground-truth, while Fig.
5(b) uses the output of the neural network, with both cases being in the lab
environment. Fig. 5(c) shows the segmentation neural network operating on the
simulated vineyard.

(a) Ground-Truth Segmentation.

(b) Inferred Segmentation in the lab.

(c) Inferred Segmentation in the wild.

Figure 6: Pruning Points Estimation Results: in this figure, the corresponding
pruning points are estimated using the plant models in Fig. 5. In these images
we can see how the pruning points locations accuracy becomes lower as we move
from perfectly known cases, as in Fig. 6(a), to unknown and challenging cases,
as in Fig. 6(c).

##  VII Experimental Setup & Results

###  VII-A Experimental Setup

For the performance evaluation of the modeling and the pruning points
detection algorithms, we considered two different setups. The first setup, in
a controlled environment, using either ground-truth or inferred segmentations
by the grapevine segmentation neural network, of grapevine plants pictures
acquired inside the lab. The second setup, is based on the simulated vineyard,
using the segmentation masks and the detected grapevine items inferred by the
grapevine segmentation neural network.

###  VII-B Experimental Results

Concerning the neural network, the evaluation metrics used are the
intersection over union, as seen in Table IV. We can see that there is a
significant improvement over our previous results, but we still consider that
there is room for improvement. With these results we also consider that the
dataset can and is useful for grapevine organ segmentation, although for
neural network training the dataset would improve by having more and varied
samples.

TABLE IV: Average Precision and Average Recall after training comparing the previous work X101 backbone and the current X101 backbone. Both metrics are calculated with intersection over union IoU=0.50:0.90, considering all area sizes and a maximum detections value of 100. The dataset for this evaluation is composed of 60 images obtained from the current dataset and the previous work dataset, updated to have the current five classes.  | Previous Work | Current Work
---|---|---
Average Precision | 27.5% | 46.2%
Average Recall | 30.8% | 54.7%

The performance of both the modeling algorithm and the pruning points
detection algorithm cannot be evaluated in a numerical manner, using
conventional performance indices, because no ground-truths were created for
either plant models or pruning points. For this reason, this evaluation is
based only on the qualitative aspects of the obtained results.

####  VII-B1 Modeling Algorithm

Figure 5 shows some output examples of the modeling algorithm. We can notice
how its performance strictly depends on the detection, recognition and
segmentation inference of the grapevine segmentation neural network. In Fig.
5(a), where the segmentation masks are hand-labeled, we can see how the
modeling algorithm is perfectly capable to reconstruct the plant model. As the
segmentation masks deteriorate, the plant modeling accuracy also decreases and
this can be well noted in Fig. 5(c), where we have a scene in-the-wild. The
modeling algorithm is not always perfect even with hand-labeled segmentations,
because, if some organs are occluded, while they are well visible from the
other side of the plant, it is not possible to establish the geometries of
such pruning regions from a single point of view. This shows that the plant
modeling performance is highly dependent on the pruning regions points of
view.

####  VII-B2 Pruning Points Estimation

Figure 6 shows the pruning points estimated from the extracted models in Fig.
5. The pruning points detection performance depends on both the segmentation
inference and the plant modeling algorithm. This algorithm relies on a set of
assessments, for which it uses heuristics reasoning, therefore its performance
is affected by how these assessments are implemented. Furthermore, being
strongly dependent on the depth information, its performance heavily depends
on the type of the depth sensor, as we tackle small-scale fine-grained
objects, i.e. grapevine organs, which can be thin and rough, causing problems
in the distance estimation. However, thanks to the use of redundant reasoning,
as discussed above, it is able to compute pruning points even if items, such
as nodes, are not detected.

##  VIII Conclusions

In this work, we presented a new expert annotated dataset for grapevine
segmentation, a state of the art neural network training and testing and
generation of pruning points that follow agronomic rules. The dataset is
publicly available in open access format at https://zenodo.org/record/5501784.
We also have shown how the new five-class categorization, the use of more
constraining types of relationships and the use of the defined set of
assessments allowed us to develop a system that is capable to estimate a set
of significant pruning points. A potential way to improve the segmentation
network performance is to use depth information for background removal.
Regarding the grapevine modeling algorithm, its limitations are mainly related
to the occlusions that can not be examined from a single point of view.

## References

  * [1] S. Poni, S. Tombesi, A. Palliotti, V. Ughini, and M. Gatti, “Mechanical winter pruning of grapevine: Physiological bases and applications,” _Scientia Horticulturae_ , vol. 204, pp. 88 – 98, 2016. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0304423816301650
  * [2] C. Intrieri and S. Poni, “Integrated evolution of trellis training systems and machines to improve grape quality and vintage quality of mechanized italian vineyards,” _American Journal of Enology and Viticulture_ , vol. 46, no. 1, pp. 116–127, 1995. [Online]. Available: https://www.ajevonline.org/content/46/1/116
  * [3] S. Poni, M. Gatti, A. Palliotti, Z. Dai, E. Duchêne, T.-T. Truong, G. Ferrara, A. M. S. Matarrese, A. Gallotta, A. Bellincontro, F. Mencarelli, and S. Tombesi, “Grapevine quality: A multiple choice issue,” _Scientia Horticulturae_ , vol. 234, pp. 445 – 462, 2018. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0304423817307586
  * [4] T. Teng, M. Fernandes, M. Gatti, S. Poni, C. Semini, D. Caldwell, and F. Chen, “Whole-body control on non-holonomic mobile manipulation for grapevine winter pruning automation,” in _IEEE International Conference on Advanced Robotics and Mechatronics (ICARM)_ , 2021.
  * [5] P. Guadagna, T. Frioni, F. Chen, A. Delmonte Incerti, T. Teng, M. Fernandes, A. Scaldaferri, C. Semini, S. Poni, and M. Gatti, “Fine-tuning and testing of a pre-trained dnn for detecting pruning regions of spur-pruned grapevines,” in _European Conference on Precision Agriculture (ECPA)_ , 2021\.
  * [6] M. Fernandes, A. Scaldaferri, G. Fiameni, T. Teng, M. Gatti, S. Poni, C. Semini, D. Caldwell, and F. Chen, “Grapevine winter pruning automation: On potential pruning points detection through 2d plant modeling using grapevine segmentation,” in _11th IEEE International Conference on CYBER Technology in Automation, Control, and Intelligent Systems (IEEE-CYBER 2021)_ , 2021.
  * [7] F. C. Nogues, A. Huie, and S. Dasgupta, “Object Detection using Domain Randomization and Generative Adversarial Refinement of Synthetic Images,” may 2018. [Online]. Available: http://arxiv.org/abs/1805.11778
  * [8] Y. Zhang, K. Jia, and Z. Wang, “Part-Aware Fine-grained Object Categorization using Weakly Supervised Part Detection Network,” _IEEE Transactions on Multimedia_ , pp. 1–1, jun 2019. [Online]. Available: http://arxiv.org/abs/1806.06198http://dx.doi.org/10.1109/TMM.2019.2939747
  * [9] T. T. Santos, L. L. de Souza, A. A. dos Santos, and S. Avila, “Grape detection, segmentation, and tracking using deep neural networks and three-dimensional association,” _Computers and Electronics in Agriculture_ , vol. 170, jul 2020. [Online]. Available: http://arxiv.org/abs/1907.11819http://dx.doi.org/10.1016/J.COMPAG.2020.105247
  * [10] P. Borianne, F. Borne, J. Sarron, and E. Faye, “Deep Mangoes: from fruit detection to cultivar identification in colour images of mango trees,” sep 2019\. [Online]. Available: http://arxiv.org/abs/1909.10939
  * [11] S. Bargoti and J. P. Underwood, “Image segmentation for fruit detection and yield estimation in apple orchards,” _Journal of Field Robotics_ , vol. 34, no. 6, pp. 1039–1060, 2017. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/rob.21699
  * [12] M. Di Cicco, C. Potena, G. Grisetti, and A. Pretto, “Automatic model based dataset generation for fast and accurate crop and weeds detection,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2017, pp. 5188–5195.
  * [13] A. Milioto, P. Lottes, and C. Stachniss, “Real-time semantic segmentation of crop and weed for precision agriculture robots leveraging background knowledge in cnns,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 2229–2235.
  * [14] J. Grimm, K. Herzog, F. Rist, A. Kicherer, R. Töpfer, and V. Steinhage, “An Adaptive Approach for Automated Grapevine Phenotyping using VGG-based Convolutional Neural Networks,” nov 2018. [Online]. Available: http://arxiv.org/abs/1811.09561
  * [15] T. Botterill, S. Paulin, R. Green, S. Williams, J. Lin, V. Saxton, S. Mills, X. Chen, and S. Corbett-Davies, “A robot system for pruning grape vines,” _Journal of Field Robotics_ , vol. 34, no. 6, pp. 1100–1122, 2017. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/rob.21680
  * [16] Y. Wu, A. Kirillov, F. Massa, W.-Y. Lo, and R. Girshick, “Detectron2,” https://github.com/facebookresearch/detectron2, 2019.
  * [17] S. Xie, R. B. Girshick, P. Dollár, Z. Tu, and K. He, “Aggregated residual transformations for deep neural networks,” _CoRR_ , vol. abs/1611.05431, 2016. [Online]. Available: http://arxiv.org/abs/1611.05431


Random walks on the two-dimensional K-comb lattice

Endre Csáki

Alfréd Rényi Institute of Mathematics, Budapest, P.O.B. 127, H-1364, Hungary.
E-mail address<EMAIL_ADDRESS>

Antónia Földes
Department of Mathematics, College of Staten Island, CUNY, 2800 Victory Blvd.,
Staten Island, New York 10314, U.S.A. E-mail address:
<EMAIL_ADDRESS>

Abstract

We study the path behavior of the symmetric walk on some special comb-type
subsets of ${\mathbb{Z}}^{2}$ which are obtained from ${\mathbb{Z}}^{2}$ by
generalizing the comb having finitely many horizontal lines instead of one.

MSC: primary 60F17, 60G50, 60J65; secondary 60F15, 60J10

Keywords: Random walk; 2-dimensional comb; Strong approximation; 2-dimensional
Wiener process; Laws of the iterated logarithm; Iterated Brownian motion

##  1 Introduction

The anisotropic random walk has a huge literature. Some important early work
on this topic is due to Heyde [14], [15]. In our papers [7], [9] we give an
account of some of the relevant literature. An anisotropic walk is defined as
a nearest neighbor random walk on the square lattice $\mathbb{Z}^{2}$ of the
plane with possibly unequal symmetric horizontal and vertical step
probabilities, so that these probabilities depend only on the value of the
vertical coordinate.

A very important special case is the simple random walk on the 2-dimensional
comb lattice which is obtained from ${\mathbb{Z}}^{2}$ by removing all
horizontal lines off the $x$-axis. More formally, consider the random walk
$\\{{\bf C}(N)=\left(C_{1}(N),C_{2}(N)\right);\,N=0,1,2,\ldots\\}$ on
$\mathbb{Z}^{2}$ with the transition probabilities for
$(k,j)\in{\mathbb{Z}^{2}}$, $N=0,1,2,\ldots.$

$\displaystyle{\bf P}({\bf C}(N+1)$ $\displaystyle=$ $\displaystyle(k,j\pm
1)|{\bf C}(N)=(k,j))=\frac{1}{2}\,\,{\rm if}\,\,j\neq 0$ $\displaystyle{\bf
P}({\bf C}(N+1)$ $\displaystyle=$ $\displaystyle(k,\pm 1)|{\bf
C}(N)=(k,0))={\bf P}({\bf C}(N+1)=(k\pm 1,0)|{\bf C}(N)=(k,0))=\frac{1}{4}$
(1.1)

For a recent review of some related literature concerning this simple random
walk we refer to Bertacchi [1] and Csáki et al. [6]. In the latter paper we
established a simultaneous strong approximation for the two coordinates of the
random walk ${\bf C}(N)=(C_{1}(N),C_{2}(N))$ that reads as follows.

Theorem A ([6]) On an appropriate probability space for the simple random walk
$\\{{\bf C}(N)=(C_{1}(N),C_{2}(N));N=0,1,2,\ldots\\}$ on the two-dimensional
comb lattice ${\mathbb{C}}^{2},$ one can construct two independent standard
Wiener processes $\\{W_{1}(t);\,t\geq 0\\}$, $\\{W_{2}(t);\,t\geq 0\\}$ so
that, as $N\to\infty$, we have with any $\varepsilon>0$

$N^{-1/4}|C_{1}(N)-W_{1}(\eta_{2}(0,N))|+N^{-1/2}|C_{2}(N)-W_{2}(N)|=O(N^{-1/8+\varepsilon})\quad
a.s.,$

where $\eta_{2}(0,\cdot)$ is the local time process at zero of $W_{2}(\cdot)$.

In this paper we want to generalize this theorem, by permitting to have
finitely many horizontal lines, instead of one, and also relax the
requirements about the probabilities along these lines as follows. At first we
select a finite set of permitted horizontal lines. We call this set $B$
containing the horizontal lines at $y=m_{j},j=1,2,\ldots,K.$ Then we consider
the random walk on $\mathbb{Z}^{2}$ with the transition probabilities for
$(k,j)\in{\mathbb{Z}^{2}}$, $N=0,1,2,\ldots.$

${\bf P}({\bf C}(N+1)=(k,\ell\pm 1)|{\bf C}(N)=(k,\ell))=\frac{1}{2}\,\,{\rm
if}\,\,\ell\notin B$

and for $m_{j}\in B$

$\displaystyle{\bf P}({\bf C}(N+1)$ $\displaystyle=$ $\displaystyle(k,m_{j}\pm
1)|{\bf C}(N)=(k,m_{j}))=p_{j}$ $\displaystyle{\bf P}({\bf C}(N+1)$
$\displaystyle=$ $\displaystyle(k\pm 1,m_{j})|{\bf
C}(N)=(k,m_{j}))=\frac{1}{2}-p_{j}$ (1.2)

where $0<p_{j}<\frac{1}{2}.$

Unless otherwise stated, we assume also that ${\mathbf{C}}(0)=(0,0)$. We will
call the above random walk as K-comb walk on ${\mathbb{C}}_{K}^{2}.$ Introduce
the notations $\alpha_{j}=2p_{j},\,\,j=1,2\ldots,K$ and

$A_{K}=\sum_{j=1}^{K}\frac{1-\alpha_{j}}{\alpha_{j}}.$ (1.3)

In our paper [10] we considered more general (much bigger) $B$ sets but only
under the condition of $p_{j}=1/4$ for all $j$-s. The main result of this
paper is the following generalization of Theorem A:

###### Theorem 1.1

On an appropriate probability space for the random walk
$\\{{\bf C}(N)=(C_{1}(N),C_{2}(N));N=0,1,2,\ldots\\}$ on the two-dimensional
K-comb lattice ${\mathbb{C}}_{K}^{2},$ one can construct two independent
standard Wiener processes $\\{W_{1}(t);\,t\geq 0\\}$, $\\{W_{2}(t);\,t\geq
0\\}$ so that, as $N\to\infty$, we have with any $\varepsilon>0$

$N^{-1/4}|C_{1}(N)-W_{1}(A_{K}\eta_{2}(0,N))|+N^{-1/2}|C_{2}(N)-W_{2}(N)|=O(N^{-1/8+\varepsilon})\quad
a.s.,$

where $\eta_{2}(0,\cdot)$ is the local time process at zero of $W_{2}(\cdot).$

Remark 1.1  Observe that the above result does not depend on the positions of
the $K$ horizontal lines, only on their numbers and $A_{K}$ defined in (1.3).

Remark 1.2  In case $K=1$ and $p_{1}=1/4$ our Theorem coincides with Theorem
A.

The structure of this paper from now on is as follows. In Section 2 we give
preliminary facts and results. In Section 3, first we redefine the walk on
${\mathbb{C}}_{K}^{2}$ in terms of two independent simple symmetric walks, and
prove our Theorem. In Section 4 some consequences will be discussed.

##  2 Preliminaries

In this section we list some well-known results, and some new ones which will
be used in the rest of the paper. In case of the known ones we won’t give the
most general form of the results, just as much as we intend to use, while the
exact reference will also be provided for the interested reader.

Let $\\{X_{i}\\}_{i\geq 1}$ be a sequence of independent i.i.d. random
variables, with ${\mathbf{P}}(X_{i}=\pm 1)=1/2.$ Then the simple symmetric
random walk on the line is defined as $S(n)=\sum_{i=1}^{n}X_{i},$ and its
local time is $\xi(j,n)=\\#\\{k:0<k\leq n,S(k)=j\\},\,\,n=1,2...,$ for any
integer $j.$

For $\xi(n)=\sup_{x}\xi(x,n)$ we have Kesten’s LIL for local time.

Lemma A (Kesten [17]) For the maximal local time we have

$\limsup_{n\to\infty}\frac{\xi(n)}{(2n\log\log n)^{1/2}}=1\quad a.s.$

Let $(W(t),\,t\geq 0)$ be a standard Wiener process (called also standard
Brownian motion). Its local time $(\eta(x,t),\,x\in\mathbb{R},\,\,t\geq 0)$
(called Wiener local time or Brownian local time) is defined as

$\eta(x,t)=\lim_{\varepsilon\to
0}\frac{1}{2\varepsilon}\int_{0}^{t}I\\{W(s)\in(x-\varepsilon,x+\varepsilon)\\}\,ds,$

where $I\\{\cdot\\}$ denotes the indicator function.

Concerning the increments of the Brownian motion, Brownian local time and
their random walk counterparts we quote the following result from Csörgő and
Révész [13], (see in [20] page 69), Csáki and Földes [8] and Csáki et al. [4].

Lemma B Let $0<a_{T}\leq T$ be a non-decreasing function of $T$. Then, as
$T\to\infty$, we have

$\sup_{0\leq t\leq T-a_{T}}\sup_{0\leq s\leq
a_{T}}|W(t+s)-W(t)|=O(a_{T}(\log(T/a_{T})+\log\log T))^{1/2}\qquad a.s.$
$\sup_{0\leq t\leq
T-a_{T}}|\eta(0,t+a_{T})-\eta(0,t)|=O(a_{T}(\log(T/a_{T})+\log\log
T))^{1/2}\qquad a.s.$ $\sup_{0\leq t\leq
T-a_{T}}|\xi(0,t+a_{T})-\xi(0,t)|=O(a_{T}(\log(T/a_{T})+\log\log
T))^{1/2}\qquad a.s.,$

where in the last line $t$ and $T$ should be integers.

We quote the following simultaneous strong approximation result from Révész
[19].

Lemma C ([19]) On an appropriate probability space for a simple symmetric
random walk

$\\{S(n);\,n=0,1,2,\ldots\\}$ with local time $\\{\xi(x,n);\,x=0,\pm 1,\pm
2,\ldots;\,n=0,1,2,\ldots\\}$ one can construct a standard Wiener process
$\\{W(t);\,t\geq 0\\}$ with local time process
$\\{\eta(x,t);\,x\in\mathbb{R};\,t\geq 0\\}$ such that, as $n\to\infty$, we
have for any $\varepsilon>0$

$|S(n)-W(n)|=O(n^{1/4+\varepsilon})\quad{a.s.}$

and

$\sup_{x\in\mathbb{Z}}|\xi(x,n)-\eta(x,n)|=O(n^{1/4+\varepsilon})\quad{a.s.},$

simultaneously.

The following result about the uniformity of the local time is in Heyde [14],
see also in Csáki and Révész [12].

Lemma D ([12], [14]) For the simple symmetric walk for any $\varepsilon>0$ we
have

$\lim_{n\to\infty}\frac{\sup_{x}|\xi(x+1,n)-\xi(x,n)|}{n^{1/4+\varepsilon}}=0\quad
a.s.$

Remark 2.1 In fact [12] deals with more general random walks, but we only need
it for a simple symmetric random walk.

The following result is the so called exponential Kolmogorov inequality. It is
a direct consequence of Doob’s maximal inequality. Its proof can be found e.g.
on page 139 of Williams [22].

Lemma E Let $X_{j},\,j\geq 1$ be i.i.d. random variables with
$\displaystyle{E\left(exp(\theta|X_{j}|)\right)<\infty}$ for some $\theta>0$
and $E(X_{j})=0.$ Then for any $\lambda>0$

${\bf P}\left(\max_{1\leq j\leq
n}\left|\sum_{i=1}^{j}X_{i}\right|>\lambda\right)\leq\exp\left(-\lambda\theta\right)\left(E\left(exp(\theta|X_{j}|)^{n}\right)+E\left(exp(-\theta|X_{j}|)^{n}\right)\right).$

The following result is a generalization of an inequality of Tóth [21].

###### Lemma 2.1

Let $G_{i}$, $i=1,2,\ldots$ be i.i.d. random variables with the common
geometric distribution ${\bf P}(G_{i}=k)=\alpha(1-\alpha)^{k},\quad
k=0,1,2...$ for some $0<\alpha<1.$ Then for $n$ big enough

${\bf P}\left(\max_{1\leq j\leq
n}\left|\sum_{i=1}^{j}\left(G_{i}-\frac{1-\alpha}{\alpha}\right)\right|>\lambda\right)\leq
2\exp\left(-\frac{\lambda^{2}\alpha^{2}}{{4(1-\alpha)n}}\right)$

for $0<\lambda<na$ with some $a>0.$

Proof. The common moment generating function of $G_{i}$-s for $i=1,2,\dots$ is

${\bf E}\left(e^{\theta G_{i}}\right)=\frac{\alpha}{1-e^{\theta}(1-\alpha)}$

and ${\bf E}(G_{i})=\frac{1-\alpha}{\alpha}.$ Then

${\bf
E}\left(e^{\theta(G_{i}-\frac{1-\alpha}{\alpha})}\right)=\frac{\alpha}{(1-e^{\theta}(1-\alpha))e^{\theta(\frac{1-\alpha}{\alpha})}}.$

There exists a constant $\theta_{1}>0,$ such that for $0<\theta<\theta_{1}$ we
have that

$1-e^{\theta}(1-\alpha)=1-(1-\alpha)(1+\theta+\frac{\theta^{2}}{2}+O(\theta^{3})),$

and

$e^{\theta(\frac{1-\alpha}{\alpha})}=1+\frac{1-\alpha}{\alpha}\theta+\left(\frac{1-\alpha}{\alpha}\right)^{2}\frac{\theta^{2}}{2}+O(\theta^{3}),$

where $\theta_{1}$ above might depend on $\alpha.$ Now with elementary
calculation we get, that

$(1-e^{\theta}(1-\alpha))e^{\theta\left(\frac{1-\alpha}{\alpha}\right)}=\alpha-\frac{1-\alpha}{2\alpha}\theta^{2}+O(\theta^{3})=\alpha\left(1-\frac{1-\alpha}{2\alpha^{2}}\theta^{2}\right)+O(\theta^{3}).$

and

${\bf
E}\left(e^{\theta(G_{i}-\frac{1-\alpha}{\alpha})}\right)=1+\theta^{2}\frac{1-\alpha}{2\alpha^{2}}+O(\theta^{3})=e^{\frac{(1-\alpha)\theta^{2}}{2\alpha^{2}}}+O(\theta^{3})\leq
e^{\frac{(1-\alpha)\theta^{2}}{\alpha^{2}}},$

again with $0<\theta\leq\theta_{2}\leq\theta_{1}.$

Considering now the moment generating function $\displaystyle{{\bf
E}\left(e^{-\theta(G_{i}-\frac{1-\alpha}{\alpha})}\right)}$ and almost
identical calculation results that

${\bf E}\left(e^{-\theta(G_{i}-\frac{1-\alpha}{\alpha})}\right)\leq
e^{\frac{(1-\alpha)\theta^{2}}{\alpha^{2}}},$

as well, again with $0<\theta\leq\theta_{3}\leq\theta_{2}.$

Applying now the exponential Kolmogorov Inequality (Lemma E) we get that

$\displaystyle{\bf P}\left(\max_{1\leq j\leq
n}\left|\sum_{i=1}^{j}\left(G_{i}-\frac{1-\alpha}{\alpha}\right)\right|>\lambda\right)$
$\displaystyle<$ $\displaystyle e^{-\lambda\theta}\left({\bf
E}\left(e^{\theta(G_{i}-\frac{1-\alpha}{\alpha})}\right)^{n}+{\bf
E}\left(e^{-\theta(G_{i}-\frac{1-\alpha}{\alpha})}\right)^{n}\right)$ (2.1)
$\displaystyle\leq
2e^{-\lambda\theta}e^{n\frac{(1-\alpha)\theta^{2}}{\alpha^{2}}}\leq
2e^{-\frac{\lambda^{2}\alpha^{2}}{4n(1-\alpha)}}$

where we selected
$\displaystyle{\theta=\frac{\lambda\alpha^{2}}{2n(1-\alpha)}}$, which
obviously can be done for $n$ big enough. $\Box$

##  3 Proof of the Theorem 1.1

First we are to redefine our random walk
$\\{{\mathbf{C}}(N);\,N=0,1,2,\ldots\\}$. It will be seen that the process
described right below is equivalent to that given in the Introduction. For
notational convenience we will say that the set $B$ contains the levels
$\\{m_{j},\quad j=1,2,\ldots K\\}.$ To begin with, on a suitable probability
space consider two independent simple symmetric (one-dimensional) random walks
$S_{1}(\cdot)$, and $S_{2}(\cdot)$. We may assume that on the same probability
space we have $K$ sequences of i.i.d. geometric random variables
$\\{G_{i}(m_{j}),\,i\geq 1,\quad m=1,2,\ldots K\\}$ which are independent from
each other and $S_{1}(\cdot)$, and $S_{2}(\cdot),$ with

$\mathbf{P}(G_{i}(m_{j})=k)=\alpha_{j}(1-\alpha_{j})^{k},\,\,k=0,1,2,\ldots\quad{\rm
with}\quad 0<\alpha_{j}<1,\quad j=1,2,\ldots K\quad$

For simplicity we will say that the sequence of geometric random variables
$\\{G(m_{j})_{i},\,i\geq 1\\}$ belongs to the horizontal level $m_{j}.$ We now
construct our walk $\mathbf{C}(N)$ as follows. We will take all the horizontal
steps consecutively from $S_{1}(\cdot)$ and all the vertical steps
consecutively from $S_{2}(\cdot).$ Consider our walk starting from the origin.
First the walk moves vertically until it arrives at a level which belongs to
$B.$ (It is possible that no vertical step is needed, as the $x$-axis might
belong to B). If this level is level $m_{j}\in B,$ then it takes
$G_{1}(m_{j})$ horizontal steps from $S_{1}(\cdot).$ (Note that
$G_{1}(m_{j})=0$ is possible with probability $\alpha_{j}$). Then we again
take vertical steps from $S_{2}(\cdot),$ as needed to get to a level belonging
to $B,$ then again some horizontal steps from $S_{1}(\cdot)$ as follows. If
this level in $B$ is the same as previously then we take $G_{2}(m_{j})$
horizontal steps. However if it is another level, lets say $m_{\ell}\in B$
then it takes $G_{1}(m_{\ell})$ horizontal steps from $S_{1}(\cdot),$ then the
walk moves vertically taking steps from $S_{2}(\cdot)$ until it hits again a
level in $B$, when again it moves horizontally taking steps from
$S_{1}(\cdot).$ In general, whenever the walk arrives at the level in $B$ then
it takes some horizontal steps, the number of which is given by the next in
line (first unused) geometric random variables belonging to that level.

Let now $H_{N},\,V_{N}$ be the number of horizontal and vertical steps,
respectively, from the first $N$ steps of the just described process.
Consequently, $H_{N}+V_{N}=N$, and

$\left\\{{\bf
C}(N);\,N=0,1,2,\ldots\right\\}=\left\\{(C_{1}(N),C_{2}(N));\,N=0,1,2,\ldots\right\\}$
$\stackrel{{\scriptstyle{d}}}{{=}}\left\\{(S_{1}(H_{N}),S_{2}(V_{N}));\,N=0,1,2,\ldots\right\\},$
(3.1)

where $\stackrel{{\scriptstyle{d}}}{{=}}$ stands for equality in distribution.

Now we introduce a few more notations. Let $\xi_{2}(\cdot,\cdot)$ denote the
local time of $S_{2}(\cdot)$.

$\displaystyle H_{N}$ $\displaystyle=$ $\displaystyle\\#\\{k:\quad 1\leq k\leq
N,\,\,\,C_{1}(k)\neq C_{1}(k-1)\\}$ (3.2) $\displaystyle V_{N}$
$\displaystyle=$ $\displaystyle\\#\\{k:\quad 1\leq k\leq N,\,\,\,C_{2}(k)\neq
C_{2}(k-1)\\}$ (3.3) $\displaystyle D_{2}(V_{N})$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{K}\xi_{2}(m_{j},V_{N})\frac{1-\alpha_{j}}{\alpha_{j}}.$
(3.4)

Clearly $H_{N}$ and $V_{N}$ are the number of horizontal and vertical steps,
respectively, in the first $N$ steps of ${\bf C}(\cdot).$ $D_{2}(V_{N})$ is
the expected occupation time of the levels belonging to $B$ by ${\bf
C}(\cdot)$ in the first $N$ steps.

###### Lemma 3.1

For any $\varepsilon>0$, as $N\to\infty$,

$\max_{1\leq i\leq N}|H_{i}-D_{2}(V_{i})|=O(N^{1/4+\varepsilon})\quad a.s.$

Proof. Recall that $H_{N}$ is the number of horizontal steps in our
construction, and horizontal steps only occur on levels belonging to $B.$ When
the vertical walk arrives to such a level, $m_{j}$, it takes some horizontal
steps, the number of which follows geometric distribution with expected value
$\frac{1-\alpha_{j}}{\alpha_{j}}.$ In $V_{N}$ steps the vertical walk
$S_{2}(\cdot)$ spends $\xi_{2}(m_{j},V_{N})$ steps on the level $m_{j}$, thus
the number of horizontal steps on this level is the sum of
$\xi_{2}(m_{j},V_{N})$ geometric random variables with common expected value
$\frac{1-\alpha_{j}}{\alpha_{j}}.$ The total number of horizontal steps is
$\sum_{j=1}^{K}\sum_{i=1}^{\xi_{2}(m_{j},V_{\ell})}G_{i}(m_{j}).$ However this
statement is slightly incorrect, as if the $N$-th step is a horizontal one,
the corresponding last geometric random variable might remain truncated.
Denote by $H_{N}^{+}$ the number of horizontal steps which includes all the
steps of this last geometric random variable. Then

$H_{N}^{+}-D_{2}(V_{N})=\sum_{j=1}^{K}\sum_{i=1}^{\xi_{2}(m_{j},V_{N})}\left(G_{i}(m_{j})-\frac{1-\alpha_{j}}{\alpha_{j}}\right),$

where $G_{i}(m_{j}),\,i=1,2...$ are the i.i.d. geometric random variables,
belonging to level $m_{j},$ as in Lemma 2.1. According to this lemma and Lemma
A we have

$\displaystyle{\bf P}\left(\max_{1\leq\ell\leq
N}|H_{\ell}^{+}-D_{2}(V_{\ell})|>\lambda\right)={\bf
P}\left(\max_{1\leq\ell\leq
N}\left|\sum_{j=1}^{K}\sum_{i=1}^{\xi_{2}(m_{j},V_{\ell})}\left(G_{i}(m_{j})-\frac{1-\alpha_{j}}{\alpha_{j}}\right)\right|>\lambda\right)$
$\displaystyle<\sum_{j=1}^{K}{\bf P}\ \left(\max_{1\leq\ell\leq
N}\left|\sum_{i=1}^{\xi_{2}(m_{j},V_{\ell})}\left(G_{i}(m_{j})-\frac{1-\alpha_{j}}{\alpha_{j}}\right)\right|>\frac{\lambda}{K}\right)$
$\displaystyle\leq\sum_{j=1}^{K}2\exp\left(-\frac{\lambda^{2}\alpha_{j}^{2}}{{4K^{2}(1-\alpha_{j})N^{1/2+\epsilon}}}\right)\leq
2K\exp\left(-\frac{\lambda^{2}(\alpha^{*})^{2}}{{4K^{2}(1-\alpha^{*})N^{1/2+\epsilon}}}\right),\
$ (3.5)

for any $\epsilon>0,$ with $\alpha^{*}=\min_{1\leq j\leq K}\alpha_{j}$ as the
function $\frac{\alpha^{2}}{1-\alpha}$ is increasing for $0<\alpha<1$, where
we used the fact that

$\max_{1\leq\ell\leq N}\xi_{2}(m_{j},V_{\ell})\leq N^{1/2+\varepsilon}\qquad
a.s.$

if $N$ is big enough.

Selecting $\lambda=N^{1/4+\varepsilon}$ we get by the Borel-Cantelli lemma
that for $N$ large enough

$\max_{1\leq\ell\leq
N}|H_{\ell}^{+}-D_{2}(V_{\ell})|=O(N^{1/4+\varepsilon})\quad a.s.$

Now to estimate the difference of $H_{N}$ and $H_{N}^{+}$, we have to observe,
that their difference is not more than one single geometric random variable,
which happens to be the last one used up to $N$. Thus with $\alpha^{*}$
defined above we have

${\bf P}(|H_{N}^{+}-H_{N}|\geq N^{\varepsilon})\leq{\bf P}(\max_{1\leq j\leq
K}\max_{1\leq i\leq N}G_{i}(m_{j})\geq N^{\varepsilon})\leq N\max_{1\leq j\leq
K}{\bf P}(G_{1}(m_{j})\geq N^{\varepsilon})\leq
N(1-\alpha^{*})^{N^{\varepsilon}}$

and hence by the Borel-Cantelli lemma

$H_{N}^{+}-H_{N}\leq N^{\varepsilon}\quad a.s.$

for all large $N,$ proving our lemma. $\Box$

Now observe that based on Lemma D

$D_{2}(V_{N})=\sum_{j=1}^{K}\xi_{2}(m_{j},V_{N})\frac{1-\alpha_{j}}{\alpha_{j}}=\xi_{2}(0,V_{N})\sum_{j=1}^{K}\frac{1-\alpha_{j}}{\alpha_{j}}+O(N^{1/4+\varepsilon})\quad
a.s.$

Recall the notation
$\displaystyle{A_{K}=\sum_{j=1}^{K}\frac{1-\alpha_{j}}{\alpha_{j}}}$ given in
(1.3). Using this, we have

$D_{2}(V_{N})=A_{K}\xi_{2}(0,V_{N})+O(N^{1/4+\varepsilon})\quad a.s.$

implying by Lemma 3.1 that

$H_{N}=A_{K}\xi_{2}(0,V_{N})+O(N^{1/4+\varepsilon})\quad a.s.$ (3.6)

as well. Moreover by (3.6) and Lemma A we have that
$H_{N}=O(N^{1/2+\varepsilon})$ a.s., thus

$|V_{N}-N|=O(N^{1/2+\varepsilon})\quad a.s.,$

implying by the last statement of Lemma B that

$H_{N}=A_{K}\xi_{2}(0,N)+O(N^{1/4+\varepsilon})\quad a.s.$

Then we have from (3.1), and Lemmas B and C that

$\displaystyle C_{1}(N)$ $\displaystyle=$ $\displaystyle
S_{1}(H_{N})=S_{1}(A_{K}\xi_{2}(0,N)+O(N^{1/4+\varepsilon}))$ (3.7)
$\displaystyle=$ $\displaystyle
W_{1}(A_{K}\xi_{2}(0,N)+O(N^{1/4+\varepsilon}))+O(N^{1/8+\varepsilon})$
$\displaystyle=$ $\displaystyle
W_{1}(A_{K}\eta_{2}(0,N)+O(N^{1/4+\varepsilon}))+O(N^{1/8+\varepsilon})$
$\displaystyle=$ $\displaystyle
W_{1}(A_{K}\eta_{2}(0,N))+O(N^{1/8+\varepsilon})\quad a.s.$

and

$C_{2}(N)=S_{2}(V_{N})=S_{2}(N+O(N^{1/2+\varepsilon}))=W_{2}(N)+O(N^{1/4+\varepsilon})\quad
a.s.$

proving our theorem. $\Box$

##  4 Consequences

Define the continuous version of our random walk process on
${\mathbb{C}^{2}_{K}}$ by linear interpolation, as follows:

$\\{{\bf C}(xN)=(C_{1}(xN),C_{2}(xN)):0\leq x\leq 1\\}.$

We have almost surely, as $N\to\infty$,

$\sup_{0\leq x\leq
1}\left\|\left(\frac{C_{1}(xN)-W_{1}(A_{K}\eta_{2}(0,xN))}{N^{1/4}(\log\log
N)^{3/4}},\frac{C_{2}(xN)-W_{2}(xN)}{(N\log\log N)^{1/2}}\right)\right\|\to
0.$

We have the following laws of the iterated logarithm (for the first statement
see Theorem 2.2 in Csáki et al. [5]).

$\limsup_{n\to\infty}\frac{C_{1}(N)}{\sqrt{A_{K}}N^{1/4}(\log\log
N)^{3/4}}=\frac{2^{5/4}}{3^{3/4}}\quad a.s.\quad{\rm
and}\quad\limsup_{N\to\infty}\frac{C_{2}(N)}{(2N\log\log N)^{1/2}}=1\quad
a.s.$

As to the liminf behavior of the max functionals of the two components, we
have the same results as for the two dimensional comb lattice [6]. These
results are based on the corresponding ones for Wiener process and the
iterated process $W_{1}(\eta_{2}(0,t))$ and the work of Chung [3], Hirsch
[16], Bertoin [2], and Nane [18] .

Based on [18], we get the following: Let $\rho(n),\,n=1,2,\ldots$, be a non-
increasing sequence of positive numbers such that $n^{1/4}\rho(n)$ is non-
decreasing. Then we have almost surely that

$\liminf_{N\to\infty}\frac{\max_{0\leq k\leq
N}C_{1}(k)}{N^{1/4}\rho(N)}=0\quad or\quad\infty$

and

$\liminf_{n\to\infty}\frac{\max_{0\leq k\leq
N}C_{2}(k)}{N^{1/2}\rho(N)}=0\quad or\quad\infty,$

according as to whether the series $\sum_{1}^{\infty}\rho(n)/n$ diverges or
converges.

$\liminf_{N\to\infty}\left(\frac{8\log\log
N}{\pi^{2}N}\right)^{1/2}\max_{0\leq k\leq N}|C_{2}(k)|=1\qquad a.s.$ (4.1)

On the other hand, for the max functional of $|C_{1}(\cdot)|$ we obtain from
[6] the following result.

Let $\rho(n),\,n=1,2,\ldots$, be a non-increasing sequence of positive numbers
such that $n^{1/4}\rho(n)$ is non-decreasing. Then we have almost surely that

$\liminf_{N\to\infty}\frac{\max_{0\leq k\leq
N}|C_{1}(k)|}{N^{1/4}\rho(N)}=0\quad or\quad\infty,$

as to whether the series $\sum_{n=1}^{\infty}\rho^{2}(n)/n$ diverges or
converges.

## References

  * [1] Bertacchi, D. Asymptotic behaviour of the simple random walk on the 2-dimensional comb. Electron. J. Probab. 11 (2006), 1184–1203.
  * [2] Bertoin, J. (1996). Iterated Brownian motion and stable (1/4) subordinator. Statist. Probab. Lett. 27 (1996), 111–114.
  * [3] Chung, K.L. On the maximum partial sums of sequences of independent random variables. Trans. Amer. Math. Soc. 64 (1948), 205–233.
  * [4] Csáki, E., Csörgő, M., Földes, A. and Révész, P. How big are the increments of the local time of a Wiener process? Ann. Probab. 11,(1983), 593-608.
  * [5] Csáki, E., Csörgő, M., Földes, A. and Révész, P. Global Strassen-type theorems for iterated Brownian motions. Stochastic Process. Appl. 59 (1995), 321-341.
  * [6] Csáki, E., Csörgő, M., Földes, A. and Révész, P. Strong limit theorems for a simple random walk on the 2-dimensional comb. Electron. J. Probab. 14 (2009), 2371–2390.
  * [7] Csáki, E., Csörgő, M., Földes, A. and Révész, P. Strong limit theorems for anisotropic random walks on $Z^{2}$. Periodica Math. Hungar. 67 (2013), 71-94.
  * [8] Csáki, E. and Földes, A. How big are the increments of the local time of a recurrent random walk? Z. Wahrsch. Verw. Gebiete 65 (1983), 307-322.
  * [9] Csáki, E., Földes, A. and Révész, P. Some results and problems for anisotropic random walk on the plane. Asymptotic Laws and Methods in Stochastics. A volume in Honour of Miklós Csörgő Fields Institute Communication 76 (2015), 55-76.
  * [10] Csáki, E. and Földes, A. Random walks on comb-type subsets of $Z^{2}$ Journal of Theoretical Probability 33 (2020), 2233-2257.
  * [11] Csáki, E. and Földes, A. Strong Approximation of the Anisotropic Random Walk Revisited Journal of Theoretical Probability (2021), DOI: 10.1007/s10959-021-01142-0.
  * [12] Csáki, E. and Révész, P. Strong invariance for local time. Z. Wahrsch. verw. Gebiete 50 (1983), 5-25.
  * [13] Csörgő, M. and Révész, P. How big are the increments of a Wiener process? Ann. Probab. 7 (1979), 731-737.
  * [14] Heyde, C.C. On the asymptotic behavior of random walks on an anisotropic lattice. J. Statist. Physics 27 (1982), 721-730.
  * [15] Heyde, C.C. Asymptotics for two-dimensional anisotropic random walks. In: Stochastic Processes. Springer, New York, (1993), 125-130.
  * [16] Hirsch, W.M. A strong law for the maximum cumulative sum of independent random variables. Comm. Pure Appl. Math. 18 (1965), 109-127.
  * [17] Kesten, H. An iterated logarithm law for the local time. Duke Math. J. 32 (1965), 447-456.
  * [18] Nane, E. Laws of the iterated logarithm for a class of iterated processes. Statist. Probab. Lett. 79 (2009), 1744–1751.
  * [19] Révész, P. Local time and invariance. Lecture Notes in Math. 861 (1981), 128-145. Springer, New York.
  * [20] Révész, P. Random Walk in Random and Non-Random Environments, 3rd ed. World Scientific, Singapore, 2013.
  * [21] Tóth, B. No more than three favorite sites for simple random walk. Ann. Probab. 29 (2001), 484–503.
  * [22] Williams, D. Probability with Martingales Cambridge University Press, Great Britain, (1991).


# A subexponential bound on the cardinality of abelian quotients
in finite transitive groups

Andrea Lucchini  Andrea Lucchini, Dipartimento di Matematica Pura e Applicata,
University of Padova, Via Trieste 53, 35121 Padova, Italy
<EMAIL_ADDRESS>,  Luca Sabatini  Luca Sabatini, Dipartimento di
Matematica e Informatica “Ulisse Dini”,
University of Firenze, Viale Morgagni 67/a, 50134 Firenze, Italy
<EMAIL_ADDRESS>and  Pablo Spiga  Pablo Spiga, Dipartimento di
Matematica Pura e Applicata,
University of Milano-Bicocca, Via Cozzi 55, 20126 Milano, Italy
<EMAIL_ADDRESS>
###### Abstract.

We show that, for every transitive permutation group $G$ of degree $n\geq 2$,
the largest abelian quotient of $G$ has cardinality at most
$4^{n/\sqrt{\log_{2}n}}$. This gives a positive answer to a 1989 outstanding
question of László Kovács and Cheryl Praeger.

###### Key words and phrases:

permutation groups; symmetric group; abelian quotients

###### 2010 Mathematics Subject Classification:

primary 20B30, 20B35

##  1\. Introduction

László Kovács and Cheryl Praeger [5] have investigated large abelian quotients
in arbitrary permutation groups of finite degree. Their work was motivated by
recent (at that time) investigations on minimal permutation representations of
a finite group [2]. One of the main results in [5] (which is independently
proved in [1]) shows that, for every permutation group of degree $n$, the
largest abelian quotient has order at most $3^{n/3}$. Clearly, this bound is
attained, whenever $n$ is a multiple of $3$, by an elementary abelian
$3$-group of order $3^{n/3}$ having all of its orbits of cardinality $3$.
Furthermore, the authors conjecture that, for transitive groups of degree $n$,
a subexponential bound in $n(\log_{2}n)^{-1/2}$ holds. More history on this
conjecture and more details can be found in the survey paper [8].

The first substantial evidence towards the conjecture goes back to the work of
Aschbacher and Guralnick [1]; they proved the striking result that the largest
abelian quotient of a primitive group of degree $n$ has order at most $n$. In
the concluding remarks, the authors also independently ask whether one can
obtain a subexponetial bound on the order of abelian quotients of transitive
groups in terms of their degrees. We refer to [1, 8] for an infinite family of
transitive groups $G$ of degree $n$ with $|G/G^{\prime}|$ asymptotic to
$\exp(bn/\sqrt{\log_{2}n})$, for some constant $b$.

The second substantial evidence towards the conjecture is in [4], where many
of the results in Section 7 get very close to the desired upper bound. In
particular, Theorem 7.6 in [4] says that if $G$ is a transitive permutation
group of degree $n\geq 2$ and $N\lhd G$ is a still transitive normal subgroup
of $G,$ then the product of the orders of the abelian composition factors of
$G/N$ is at most $4^{n/\sqrt{\log_{2}n}}$.

In this paper, we settle in the affirmative the conjecture of Kovács and
Praeger.

######  Theorem 1.

For every positive integer $n\geq 2$ and for every transitive permutation
group $G$ of degree $n$, we have

$|G/G^{\prime}|\>\leq\>4^{n/\sqrt{\log_{2}n}}.$

The constant $4$ in Theorem 1 should not be taken too seriously, but it seems
remarkably hard to pin down the exact constant. The choice of the constant $4$
in our work is a compromise: it makes the statement of Theorem 1 explicit and
valid for every $n\geq 2$.

##  2\. Preliminaries

Unless otherwise explicitly stated, all the logarithms are to base $2$. Given
a field $\mathbb{F}$, a group $G$, a subgroup $H$ of $G$ and an
$\mathbb{F}H$-module $W$ (or simply $H$-module), we denote by
$W\uparrow_{H}^{G}$ the induced $G$-module of $W$ from $H$ to $G$, that is,
$W\uparrow_{H}^{G}:=W\otimes_{\mathbb{F}H}\mathbb{F}G$. Moreover, given a
$G$-module $M$, we denote by $d_{G}(M)$ the minimal number of generators of
$M$ as a $G$-module. We are ready to report a fundamental result from [7].

######  Lemma 2.1.

_(See[7, Lemma 4])_ There is a universal constant $b^{\prime}$ such that
whenever $H$ is a subgroup of index $n\geq 2$ in a finite group $G$,
$\mathbb{F}$ is a field, $V$ is an $H$-module of dimension $a$ over
$\mathbb{F}$ and $M$ is a $G$-submodule of the induced module
$V\uparrow_{H}^{G}$, then

$d_{G}(M)\>\leq\>\frac{ab^{\prime}n}{\sqrt{\log n}}.$

######  Remark 2.2.

Gareth Tracey, in his monumental work [10] on minimal sets of generators of
transitive groups, has refined Lemma 2.1 in various directions. For instance,
[10, Section 4.3] gives a more quantitative form of Lemma 2.1. Indeed, using
the notation in Lemma 2.1, from [10, Corollary $4.27$ (iii)], we deduce

$d_{G}(M)\leq aE(n,p)\leq\begin{cases}an\frac{2}{c^{\prime}\log
n}&\textrm{when }2\leq n\leq 1260,\\\ an\frac{2}{\sqrt{\pi\log
n}}&\textrm{when }n>1261,\end{cases}$

where $c^{\prime}:=0.552282$, $p$ is the characteristic of $M$ and $E(n,p)$ is
explicitly defined in [10, Section 4]. In particular, we immediately see that
in Lemma 2.1 we may take $b^{\prime}:=2/\sqrt{\pi}$ whenever $n>1261$. With
the help of a computer, we have implemented the function $E(n,p)$ and we have
checked that $E(n,p)\leq 2n/\sqrt{\pi\log n}$ also when $n\leq 1260$.
Therefore in Lemma 2.1 we may take $b^{\prime}:=2/\sqrt{\pi}$.

Let $R$ be a finite group. For each prime number $p$, let $a_{p}(R)$ be the
number of abelian composition factors of $R$ of order $p$, and let

$a(R)\>:=\>\sum_{p\,\mathrm{prime}}a_{p}(R)\log p.$

We now report a useful result of Pyber.

######  Lemma 2.3.

_(See[9, Theorem $2.10$])_ Let $c_{0}:=\log_{9}(48\cdot 24^{1/3})$. The
product of the orders of the abelian composition factors of a primitive
permutation group of degree $r$ is at most $24^{-1/3}r^{1+c_{0}}$.

From Lemma 2.3, we deduce the following.

######  Lemma 2.4.

Let $R$ be a primitive group of degree $r$, let $c_{0}$ be the constant in
Lemma 2.3. Then

$a(R)\>\leq\>(1+c_{0})\log r-\log(24)/3.$

###### Proof.

By definition, the product of the orders of the abelian composition factors of
$R$ is

$\prod_{p\,\mathrm{prime}}p^{a_{p}(R)}=\prod_{p\,\mathrm{prime}}2^{a_{p}(R)\log
p}=2^{a(R)}.$

From Lemma 2.3, this number is at most $24^{-1/3}r^{1+c_{0}}$. The proof
follows by taking logarithms. ∎

Notice that Lemma 2.3 is often used in order to bound the composition length
of a primitive permutation groups. A more precise bound on this composition
length has been recently proved by Glasby, Praeger, Rosa and Verret [3,
Theorem 1.3]. However this stronger bound is not sufficient for our
application, which requires information not only on the number of the
composition factors but also on their order.

Finally, given a finite group $G$, we denote by $G_{\mathrm{ab}}$ the quotient
group $G/G^{\prime}$.

##  3\. Proof of Theorem 1

Let $R$ be a finite group, let $\Delta$ be a finite set and let
$W:=R\,\mathrm{wr}_{\Delta}\mathop{\mathrm{Sym}}(\Delta)$ be the wreath
product of $R$ via $\mathop{\mathrm{Sym}}(\Delta)$. We denote by

$\pi:W\to\mathop{\mathrm{Sym}}(\Delta)$

the projection of $W$ over the top group $\mathop{\mathrm{Sym}}(\Delta)$. Let
$\prod_{\delta\in\Delta}R_{\delta}$ be the base subgroup of $W$ and, for each
$\delta\in\Delta$, consider $W_{\delta}:={\bf N}_{{W}}({{R_{\delta}}})$. As

$W_{\delta}=R_{\delta}\times
R\,\mathrm{wr}\mathop{\mathrm{Sym}}(\Delta\setminus\\{\delta\\}),$

we may consider the projection $\rho_{\delta}:W_{\delta}\to R_{\delta}$. Using
this notation, we adapt the proof of [6, Lemma 2.5] to prove the following.

######  Lemma 3.1.

Let $R$ be a finite group, let $\Delta$ be a set of cardinality at least $2$
and let $G$ be a subgroup of the wreath product
$R\,\mathrm{wr}_{\Delta}\mathop{\mathrm{Sym}}(\Delta)$ with the properties

  1. (1)

$\pi(G)$ is transitive on $\Delta$,

  2. (2)

$\rho_{\delta}({\bf N}_{{G}}({{R_{\delta}}}))=R_{\delta}$, for every
$\delta\in\Delta.$

Then

$\log|G_{\mathrm{ab}}|\>\leq\>\frac{a(R)b^{\prime}|\Delta|}{\sqrt{\log|\Delta|}}+\log|(\pi(G))_{\mathrm{ab}}|,$

where $b^{\prime}$ is the absolute constant appearing in Lemma 2.1, and $a(R)$
is defined in Section 2.

###### Proof.

We argue by induction on the order of $R$. When $|R|=1$, there is nothing to
prove because $\pi(G)\cong G$ and hence
$\log|G_{\mathrm{ab}}|=\log|(\pi(G))_{\mathrm{ab}}|$. Suppose then $R\neq 1$.
We write

(3.1)
$\displaystyle|G_{\mathrm{ab}}|=|G:G^{\prime}M||G^{\prime}M:G^{\prime}|=|(G/M)_{\mathrm{ab}}||M:M\cap
G^{\prime}|.$

Let $L$ be a minimal normal subgroup of $R$. Fix $\delta_{0}\in\Delta$. We
identify $L$ with a normal subgroup $L_{\delta_{0}}$ of the direct factor
$R_{\delta_{0}}$ of the base group $\prod_{\delta\in\Delta}R_{\delta}$ of $W$.
Let $B_{L}$ be the direct product of the distinct $G$-conjugates of
$L_{\delta_{0}}$ and consider $M:=B_{L}\cap G$. We have $M\unlhd G$ and

$\frac{G}{M}=\frac{G}{B_{L}\cap G}\cong\frac{GB_{L}}{B_{L}}.$

Now, from (1), we deduce that $GB_{L}/B_{L}$ is isomorphic to a subgroup of
the wreath product

$(R/L)\mathrm{wr}_{\Delta}\mathop{\mathrm{Sym}}(\Delta).$

Therefore, by induction,

(3.2)
$\displaystyle\log|(G/M)_{\mathrm{ab}}|\leq\frac{a(R/L)b^{\prime}|\Delta|}{\sqrt{\log|\Delta|}}+\log|(\pi(G))_{\mathrm{ab}}|.$

We now distinguish two cases.

$L$ is non-abelian:

Since $M\unlhd W_{\delta_{0}}\cap G$, we deduce
$\rho_{\delta_{0}}(M)\unlhd\rho_{\delta_{0}}(W_{\delta_{0}}\cap G)$. From (2),
we have $\rho_{\delta_{0}}(W_{\delta_{0}}\cap G)=\rho_{\delta_{0}}({\bf
N}_{{G}}({{R_{\delta_{0}}}}))=R_{\delta_{0}}$ and hence
$\rho_{\delta_{0}}(M)\unlhd R_{\delta_{0}}$. Observe that
$\rho_{\delta_{0}}(M)$ is contained in $L_{\delta_{0}}$. As $L_{\delta_{0}}$
is a minimal normal subgroup of $R_{\delta_{0}}$, we get either
$\rho_{\delta_{0}}(M)=1$ or $\rho_{\delta_{0}}(M)=L_{\delta_{0}}$. From (1),
$\pi(G)$ is transitive on $\Delta$ and hence either $\rho_{\delta}(M)=1$ for
each $\delta\in\Delta$, or $\rho_{\delta}(M)=L_{\delta}$ for each
$\delta\in\Delta$.

Suppose $\rho_{\delta_{0}}(M)=1$. As $\rho_{\delta}(M)=1$ for each
$\delta\in\Delta$, we get $M=1$. Now the proof immediately follows from (3.2)
because $G/M\cong G$.

Suppose $\rho_{\delta_{0}}(M)=L_{\delta_{0}}$. Then $M$ is a subdirect product
of $L^{\Delta}=\prod_{\delta\in\Delta}L_{\delta}$. As $L$ is a non-abelian
minimal normal subgroup of $R$, we deduce that $M$ is a direct product of non-
abelian simple groups. Thus $M$ has no abelian composition factor and hence
(3.1) gives $|G_{\mathrm{ab}}|=|(G/M)_{\mathrm{ab}}|$. Moreover, $a(R/L)=a(R)$
and hence, once again, the proof immediately follows from (3.2).

$L$ is abelian:

As $L$ is a minimal normal subgroup of $R$, it is an elementary abelian
$p_{0}$-group, for some prime number $p_{0}$. Let $a_{p_{0}}$ be the
composition length of $L$. In particular,

$a(R)=a(R/L)+a_{p_{0}}\log{p_{0}}.$

The group $B_{L}$ is abelian and the action of $G$ by conjugation on $B_{L}$
endows $B_{L}$ with a natural structure of $G$-module. From its definition, as
$G$-module, $B_{L}$ is isomorphic to the induced module

$L_{\delta_{0}}\uparrow_{K}^{G},$

where $K:={\bf N}_{{G}}({{L_{\delta_{0}}}})$. From (1), $G$ acts transitively
on $\Delta$ and hence $|\Delta|=|G:{\bf N}_{{G}}({{L_{\delta_{0}}}})|=|G:K|$.
From Lemma 2.1, we deduce

$d_{G}(M/(M\cap G^{\prime}))\leq
d_{G}(M)\leq\frac{a_{p_{0}}b^{\prime}|\Delta|}{\sqrt{\log|\Delta|}}.$

However, as $G$ acts trivially by conjugation on $M/(M\cap G^{\prime})$, we
get that $d_{G}(M/(M\cap G^{\prime}))$ is just the dimension of $M/(M\cap
G^{\prime})$ as a vector space over the prime field
$\mathbb{Z}/p_{0}\mathbb{Z}$. Therefore

(3.3) $\displaystyle|M:M\cap G^{\prime}|\leq
p_{0}^{(a_{p_{0}}b^{\prime}|\Delta|/\sqrt{\log|\Delta|})}.$

From (3.1), (3.2), and (3.3), we get

$\displaystyle\log|G_{\mathrm{ab}}|\leq$
$\displaystyle\log|(G/M)_{\mathrm{ab}}|+\log|M:M\cap G^{\prime}|$
$\displaystyle\leq$
$\displaystyle\frac{a(R/L)b^{\prime}|\Delta|}{\sqrt{\log|\Delta|}}+\log|(\pi(G))_{\mathrm{ab}}|+\log(p_{0})\frac{a_{p_{0}}b^{\prime}|\Delta|}{\sqrt{\log|\Delta|}}$
$\displaystyle=$
$\displaystyle(a(R/L)+a_{p_{0}}\log{p_{0}})\frac{b^{\prime}|\Delta|}{\sqrt{\log|\Delta|}}+\log|(\pi(G))_{\mathrm{ab}}|$
$\displaystyle=$ $\displaystyle
a(R)\frac{b^{\prime}|\Delta|}{\sqrt{\log|\Delta|}}+\log|(\pi(G))_{\mathrm{ab}}|.\qed$

With Lemma 3.1 in hand, we prove Theorem 1 by induction on $n$.

Let $G$ be a transitive permutation group of degree $n\geq 2$. From the main
result of [5], we have $|G_{\mathrm{ab}}|\leq 3^{n/3}$. Now the inequality
$3^{n/3}\leq 4^{n/\sqrt{\log n}}$ is satisfied for each $n\leq 20\,603$. In
particular, for the rest of the proof, we may suppose that $n\geq 20\,604$.

Suppose first that $G$ is primitive. In this case, from [1], we have
$|G_{\mathrm{ab}}|\leq n$ and the inequality $n\leq 4^{n/\sqrt{\log n}}$
follows with an easy computation.

Suppose now that $G$ is imprimitive and let $\Omega$ be the domain of $G$.
Among all non-trivial blocks of imprimitivity of $G$, choose one (say
$\Lambda$) minimal with respect to the inclusion. Let
$G_{\\{\Lambda\\}}:=\\{g\in G\mid\Lambda^{g}=\Lambda\\}$ be the setwise
stabilizer of $\Lambda$ in $G$ and let $R\leq\mathop{\mathrm{Sym}}(\Lambda)$
be the permutation group induced by $G_{\\{\Lambda\\}}$ in its action on
$\Lambda$. The minimality of $\Lambda$ yields that $R$ acts primitively on
$\Lambda$.

Let $\Delta:=\\{\Lambda^{g}\mid g\in G\\}$ be the system of imprimitivity
determined by the block $\Lambda$. Then $G$ is a subgroup of the wreath
product

$R\,\mathrm{wr}_{\Delta}\mathop{\mathrm{Sym}}(\Delta).$

We now use the notation of Lemma 3.1 for wreath products. In particular, let
$\pi:R\,\mathrm{wr}_{\Delta}\mathop{\mathrm{Sym}}(\Delta)\to\mathop{\mathrm{Sym}}(\Delta)$
be the projection onto the top group $\mathop{\mathrm{Sym}}(\Delta)$ and, for
each $\delta\in\Delta$, let $R_{\delta}$ be the direct factor of the base
group $\prod_{\delta\in\Delta}R_{\delta}$ corresponding to $\delta$. From the
fact that $G$ acts transitively on $\Omega$ and from the definition of $R$, we
get that the two hypotheses (1) and (2) are satisfied. Therefore, from Lemma
3.1 itself, we deduce

$\log|G_{\mathrm{ab}}|\leq\frac{a(R)b^{\prime}|\Delta|}{\sqrt{\log|\Delta|}}+\log|(\pi(G))_{\mathrm{ab}}|.$

Set $r:=|\Lambda|$. Thus $|\Delta|=n/r$. From Lemma 2.4 and from induction (as
$n/r<n$), we get

(3.4)
$\log|G_{\mathrm{ab}}|\leq\frac{b^{\prime}(n/r)}{\sqrt{\log(n/r)}}\left((1+c_{0})\log
r-\frac{\log(24)}{3}\right)+2\frac{(n/r)}{\sqrt{\log(n/r)}}.$

From Remark 2.2, we see that we may take $b^{\prime}=2/\sqrt{\pi}$. Now, for
$n\geq 20\,604$, a careful calculation shows that the right hand side of (3.4)
is at most $2n/\sqrt{\log n}$ for every divisor $r$ of $n$ with $4<r<n$.

We now discuss the cases $r\in\\{2,3,4\\}$ separately. When $r=2$, we have
$a(R)=1$ and hence

(3.5)
$\log|G_{\mathrm{ab}}|\leq\frac{b^{\prime}(n/2)}{\sqrt{\log(n/2)}}+2\frac{(n/2)}{\sqrt{\log(n/2)}}.$

Now, the right hand side of (3.5) is less than $2n/\sqrt{\log n}$ for each
$n\geq 20\,604$. The computation when $r\in\\{3,4\\}$ is analogous using
$a(R)\leq 1+\log(3)$ when $r=3$, and $a(R)\leq 3+\log(3)$ when $r=4$.

## References

  * [1] M. Aschbacher, R. M. Guralnick, On abelian quotients of primitive groups, Proc. Amer. Math. Soc. 107 (1989), 89–95.
  * [2] D. Easdown, C. E. Praeger, On minimal faithful permutation representations of finite groups, Bull. Austral. Math. Soc. 38 (1988), 207–220.
  * [3] S. P. Glasby, C. E. Praeger, K. Rosa, G. Verret, Bounding the composition length of primitive permutation groups and completely reducible linear groups, J. Lond. Math. Soc. (2) 98 (2018), no. 3, 557–572.
  * [4] R. M. Guralnick, A. Maróti, L. Pyber, Normalizers of primitive permutation groups, Adv. Math. 310 (2017), 1017–1063.
  * [5] L. G. Kovács, C. E. Praeger, Finite permutation groups with large abelian quotients, Pacific J. Math. 136 (1989), 283–292
  * [6] A. Lucchini, Enumerating transitive finite permutation groups, Bull. London Math. Soc. 30 (1998), 569–577.
  * [7] A. Lucchini, F. Menegazzo, M. Morigi, Asymptotic results for transitive permutation groups, Bull. London Math. Soc. 32 (2000), 191–195.
  * [8] C. E. Praeger, C. Schneider, The contribution of L. G. Kovács to the theory of permutation groups, J. Aust. Math. Soc. 102 (2017), no. 1, 20–33.
  * [9] L. Pyber, Asymptotic results for permutation groups, Groups and computation (New Brunswick, NJ, 1991), 197–219, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 11, Amer. Math. Soc., Providence, RI, 1993.
  * [10] G. M. Tracey, Minimal generation of transitive permutation groups, J. Algebra 509 (2018), 40–100.