# How Social Rewiring Preferences Bridge Polarized Communities

Henrique M. Borges<EMAIL_ADDRESS>Departamento de Física, Instituto Superior Técnico, Universidade de Lisboa,
Lisbon, Portugal  Vítor V. Vasconcelos<EMAIL_ADDRESS>Computational
Science Lab, Informatics Institute, University of Amsterdam, Amsterdam, The
Netherlands  POLDER, Institute for Advanced Study, University of Amsterdam,
Amsterdam, The Netherlands  Center for Urban Mental Health, University of
Amsterdam, Amsterdam, The Netherlands  Flávio L. Pinheiro
<EMAIL_ADDRESS>NOVA Information Management School (NOVA IMS),
Universidade Nova de Lisboa, Lisbon, Portugal

###### Abstract

Recently, social debates have been marked by increased polarization of social
groups. Such polarization not only implies that groups cannot reach a
consensus on fundamental questions but also materializes in more modular
social spaces/networks that further amplify the risks of polarization in less
polarizing topics. How can network adaptation bridge different communities
when individuals reveal homophilic or heterophilic social rewiring
preferences? Here, we consider information diffusion processes that capture a
continuum from simple to complex contagion processes. We use a computational
model to understand how fast and to what extent individual rewiring
preferences bridge initially weakly connected communities and how likely it is
for them to reach a consensus. We show that homophilic and heterophilic
rewiring have different impacts depending on the type of opinion spread.
First, in the case of complex opinion diffusion, we show that even polarized
social networks can reach a population-wide consensus without reshaping their
underlying network. When polarized social structures amplify opinion
polarization, heterophilic rewiring preferences play a key role in creating
bridges between communities and facilitating a population-wide consensus.
Secondly, in the case of simple opinion diffusion, homophilic rewiring
preferences are more capable of fostering consensus and avoiding a co-
existence (dynamical polarization) of opinions. Hence, across a broad profile
of simple and complex opinion diffusion processes, only a mix of heterophilic
and homophilic rewiring preferences avoids polarization and promotes
consensus.

Social Contagion; Adaptive Social Networks; Opinion Dynamics; Polarization

††preprint: XXXX

##  I Introduction

In the past decades, social media platforms have been at the center stage of
social debate and occupy a major role in our social dynamics. These platforms
have also amplified our tendency to form polarized groups whose segregation
and clustering of views prevents them from reaching consensus even on the most
fundamental societal questions [1]. As such, it is not surprising that much
research has been conducted to understand the phenomena of social polarization
better [2, 3, 4, 5, 6, 7]. While past works focused on identifying underlying
mechanisms that can lead to social polarization, both in opinion composition
[8, 9, 10, 11] and in respect to the structural organization of communities
[12, 13, 14, 15, 16, 17], few works have looked into how dynamical processes
on already structurally polarized populations can amplify or mitigate the
degree of structural polarization of a community. Here, we study how the co-
evolution of an information diffusion process—that interpolates between simple
and complex contagion processes—and the network structure of an initially
polarized social network can lead to the reshaping of social structures and
build environments that are more suitable for the formation of consensus.

Empirical evidence suggests that distinct types of information spread
differently [18, 19, 20, 21, 22, 23, 24], but that there is a positive and
direct relationship between the probability that an individual adopts new
information and the number of friends that already hold it [25, 26, 27, 28,
29, 21, 22]. In that context, information diffusion models can be divided into
simple contagion (social learning) or complex contagion (social influence)
processes. Formally, in simple contagion processes, the probability that
information is transmitted is directly proportional to the fraction of
neighbors with such information [18, 30, 19, 20, 31]. In contrast, under
complex contagion, adoption is typically modeled using a threshold function,
where the probability of transmission is one if the fraction of neighbors with
that information exceeds a given threshold and zero otherwise [32, 33, 22,
34]. However, empirical evidence supports the view that a heterogeneous
distribution of thresholds better describes populations [35, 25], leading to
the proposal of more general models [36, 37].

Figure 1: Opinion dynamics in static social networks. Panel a shows the
fixation times, measured for fully connected communities (well-mixed, black
dashed lines) and structured populations (different topologies in orange,
purple, and green lines). These results averaged over $1.0\times 10^{4}$
independent simulations starting from a configuration with equal abundances of
opinions. Vertical lines separate the different dynamical regions described in
the main text, and gray areas indicate the mismatch between well-mixed and
structured populations. This figure corresponds to $p=0$, matches Figure 3a
from Ref. [36], and sets up a baseline scenario in the absence of rewiring.
Panels b and c illustrate the possible outcomes of structural and dynamical
polarization. The former is characterized by a scenario in which polarization
occurs due to structural lock-ins. In the latter, polarization results from
agents’ inability to reach a consensus due to co-existence-like dynamics.

While, from an information diffusion perspective, polarization can be
characterized by a population that cannot reach a consensus (i.e., the
majority of the population cannot align towards the same opinion),
structurally speaking, a polarized population can be described by a modular
network structure with dense within- and sparse between-community connections.
Modular structures emphasize the amplification of group differences in terms
of complex information (i.e., complex contagion or social influence) but do
not affect the dissemination of simple information (i.e., simple contagion or
social learning) [38, 39]. To break such structural lock-ins, populations must
reshape their connections. In that sense, two adaptive network mechanisms
stemming from individual choices are homophily—the degree to which individuals
desire similarity between social contacts—and heterophily—desiring difference.
Coupling the agents’ dynamic states and connections leads to a feedback loop
where the network structure and individuals’ opinions affect each other. Past
works proposed models that combine opinion dynamics with homophilic and
heterophilic network dynamics [40, 41, 42], but they have not addressed the
interplay between the type of information diffusion and the rewiring mechanism
taking place.

Here, we study the feedback between the dynamics of individual opinions and
network structure in contemporary (polarized) social networks and ask to what
extent heterophilic and homophilic individual rewiring preferences can lead to
the bridging of initially polarized communities. We focus on potential future
debates, which will exhibit a range of diffusion properties, and test how
different rewiring preferences influence the potential for consensus formation
in competitive opinion dynamics. Furthermore, we show how the resulting
network structures put populations at risk of polarization in future social
debates. Across a broad profile of simple and complex opinion diffusion
processes, only a mix of heterophilic and homophilic rewiring preferences
avoids polarization and promotes consensus.

##  II Materials and Methods

Let’s consider a finite but large population of $Z>>1$ individuals where each
agent is characterized by one of two contrasting opinions, $A$ or $B$. At any
given moment, the population contains a fraction $x=n^{A}/Z$ of _A_ s and
$1-x=n^{B}/Z$ of _B_ s. Moreover, individuals are embedded in a complex
network of social relationships, where each node corresponds to an individual,
and links capture who influences whom.

We study the case of a co-evolving population in which individuals can update
their opinions and adapt their ties. We consider a stochastic one-step process
in which, at each time step, one of two events takes place. With probability
$p$, individuals attempt to rewire a social tie, and, with probability $1-p$,
their opinion. In both cases, the decision depends on the composition of
individuals’ neighborhoods.

Figure 2: Schematic illustration of the co-evolutionary model used in this
manuscript. The proposed model combines a competitive opinion diffusion
process that co-evolves with a network dynamics process that can follow
homophily (individuals have a preference to be connected with individuals of
the same opinion) or heterophily (individuals have a preference to be
connected with individuals of opposite opinion).

###  II.1 Opinion Dynamics

During an opinion update step, an agent $i$ is selected at random and updates
its opinion $X\in\\{A,B\\}$ to $Y\in\\{A,B\\}$ according to

$p_{i}^{X\to Y}=\bigg{(}\frac{n^{Y}_{i}}{z_{i}}\bigg{)}^{\alpha_{XY}},$ (1)

where $z_{i}$ is the degree of the individual $i$, $n^{Y}_{i}$ is the number
of $i$’s neighbors with opinion $Y$, and $\alpha_{XY}\geq 0$ is the complexity
of opinion $Y$ when learned by an individual with opinion $X$. When
$\alpha_{AB}=\alpha_{BA}=1$, the model resumes to the voter’s model. It is
convenient to reparametrize the complexities into polar coordinates, such that
$\alpha_{AB}=1+r\sin\theta$ and $\alpha_{BA}=1+r\cos\theta$. Hence, with a
single parameter $\theta$, we can explore the four dynamical regions of
interest in fully connected populations:

  * •

A dominance, for $\pi/2\leq\theta<\pi$: This region does not have any internal
fixed point and $x^{*}=0$ is unstable and $x^{*}=1$ is stable. Opinion A will
dominate the population.

  * •

B dominance, for $3\pi/2\leq\theta<2\pi$: This region does not have any
internal fixed point and $x^{*}=0$ is stable and $x^{*}=1$ is unstable.
Opinion B will dominate the population. In Evolutionary Game Theory (EGT),
this and A dominance exhibit dynamics akin to the Prisoner’s Dilemma and
Harmony Game [43, 44, 45].

  * •

Polarization, for $\pi/2\leq\theta<3\pi/2$: this region is characterized by a
single stable internal fixed point that leads to the polarization of opinions,
which is identified by the constant co-existence of both opinions and the
inability of the population to reach a population-wide consensus due to a
dynamical lock. In EGT, this outcome is dynamically similar to a 2-person
Snowdrift Game [46].

  * •

Consensus, for $0\leq\theta<\pi/2$: this region has a single unstable internal
fixed point resulting in coordination dynamics and a population-wide
consensus, which only depends on the initial abundance of opinions. In EGT,
this outcome is dynamically similar to a 2-person Stag-Hunt Game [47].

In the Polarization and Consensus regions, the internal fixed point position
is independent of $r$ and depends only on the ratios of complexities [36]
according to $x^{\ast}=\cot\theta=(\alpha_{BA}-1)/(\alpha_{AB}-1)$. For the
remainder of the manuscript, we shall consider the space spanned by $r=1/2$
and $0\leq\theta\leq 2\pi$. Figure 1 compares the fixation times (time to
consensus) obtained for three different network structures across the four
regions of interest. Except for modular networks, qualitatively, the expected
time to reach consensus in structured populations is consistent with the well-
mixed scenario. In structured populations, the Polarization region is reduced.
Moreover, fixation times peak in the Consensus region in modular population
structures. Such scenarios result from each community reaching a different
local consensus and then being unable to converge to a population-wide
consensus due to imposed structural lock-ins, a well-known result in the
context of complex contagion [38].

###  II.2 Rewiring Preferences

We consider two different families of rewires based on how individuals’
networks are assessed: Homophilic or Heterophilic updates, in which
individuals rewire a connection if their neighborhood is too dissimilar or
similar to them, respectively. As such, during a link update step, a random
individual $i$ breaks a random tie with a probability given by:

$\displaystyle
p_{i_{Hom}}^{X}=\bigg{(}\frac{n_{i}^{Y}}{z_{i}}\bigg{)}^{\beta_{X}}\text{or}$
(2a) $\displaystyle
p_{i_{Het}}^{X}=\bigg{(}1-\frac{n_{i}^{Y}}{z_{i}}\bigg{)}^{\beta_{X}},$ (2b)

where $\beta_{X}$ accounts for the tolerance of an agent with opinion
$X\in\\{A,B\\}$ regarding the composition of its neighborhood for the
homophilic 2a and heterophilic 2b cases. If a link is broken, then $i$ creates
a new tie with a random friend of a neighbor. This ensures that the network
remains connected. This evaluation procedure is similar in spirit to the
Schelling model [48], especially taking into account a heterogeneous-
thresholds interpretation [36].

Figure 3: Opinion dynamics with Homophilic and Heterophilic rewiring
preferences in a Consensus regime ($\theta=\pi/4$). Panel a) shows the
fixation times as a function of the rewiring rate, $p$. Panel b) shows the
fraction of times a population ends in an opinion polarization state as a
function of the rewiring rate, $p$. Panel c) shows how the modularity of the
initial structure decays as a function of $p$. Panels d) and e), show the
distribution of the fixation times until reaching consensus for different
rewiring rates, $p$, for a homophilic (d) and heterophilic (e) rewiring
preferences and $\beta=(0.5,0.5)$. In panels a), b), and c) symbols indicate
different values of the strictness of rewiring decisions ($\beta$) and colors
the different rewiring preferences (homophilic in blue and heterophilic
populations in red). Results are the average over $10^{3}$ independent
simulations, each with an upper bound of $2.5\times 10^{6}$ iterations, for an
initial random distribution of equal proportions of _A_ s and _B_ s, on
modular networks with $N=1000$ nodes, and average degree $\langle
z_{i}\rangle=4$.

The tolerance coefficient, $\beta_{X}$, follows a similar definition of
$\alpha_{XY}$. As such, it allows us to interpolate between distinct
scenarios. Lower values of $\beta_{X}$ are associated with harsher
evaluations, which makes it more likely for their neighborhood to change,
compared to an individual with an identical neighborhood but a less stringent
assessment (larger values of $\beta_{X}$). Moreover, individuals of different
opinions can have different tolerance levels, $\beta_{X}$. As such, we define
the pair of tolerance-to-rewiring coefficients as
$\beta=(\beta_{A},\beta_{B})$.

###  II.3 Simulations

We consider the case of a population whose initial structure is modular and
defined by two weakly connected communities. We generated these networks by
randomly linking $q=20$ nodes from two independently generated Barabási-Albert
[49] networks with $N/2$ nodes each. We considered $N=10^{3}$ and an average
degree of $\langle z_{i}\rangle=4$ unless specified otherwise.

Each simulation starts with an equal proportion of _A_ s and _B_ s. It is also
assumed that all individuals have either a homophilic or heterophilic
evaluation of their neighborhood. While consensus is eventually reached in
finite populations, the time taken can be exceedingly long. For that reason,
we set an upper bound of $M_{\text{iter}}=2.5\times 10^{6}$ iterations, which
we take as the maximum time to consensus. We present the average out of
$10^{3}$ independent simulations for each parameter set. To capture different
future polarizing topics, we consider a scenario in which opinions are
randomly distributed in the population and another where opinions are
associated with specific modules of the network.

##  III Consensus Regime

Let us start by considering the properties of the diffusion process that lie
in the structural polarization region for static networks when the modularity
of the networks breaks their ability to reach a population-wide consensus,
i.e., $\theta=\pi/4$. Figure 3a shows the average fixation time as a function
of the rewiring rate $p$, and Figure 3b shows the fraction of simulations in
which populations end polarized in terms of opinions. Besides considering
populations with heterophilic (red) and homophilic (blue) rewiring
preferences, we also look into the strictness of the tolerance-to-rewire
coefficient (symbols), $\beta=(\beta_{A},\beta_{B})$.

Figure 4: Opinion Opinion dynamics with Homophilic and Heterophilic rewiring
preferences in a Consensus regime ($\theta=\pi/4$) with initial opinion
polarized configurations. In this series of results, each network community
starts with a local consensus on a different opinion. Panel a shows the
fixation time as a function of the rewiring rate, $p$. Panel b shows the
fraction of times a population ends in an opinion polarization state as a
function of the rewiring rate, $p$. Panel c shows how the modularity of the
initial structure decays as a function of $p$. Panels d) and e), show the
distribution of the fixation times until reaching consensus for different
rewiring rates, $p$, for a homophilic (d) and heterophilic (e) rewiring
preferences and $\beta=(0.5,0.5)$. In panels a), b), and c) symbols indicate
different values of the strictness of rewiring decisions ($\beta$) and colors
the different rewiring preferences (homophilic in blue and heterophilic
populations in red). Results are the average over $10^{3}$ independent
simulations, each with $M_{\text{iter}}=2.5\times 10^{6}$ iterations, on
modular networks with $N=10^{3}$ nodes, an average degree of $\langle
z_{i}\rangle=4$.

For low rewiring rates ($p<10^{-3}$), we observe a flat fixation time (see
Figure 3a). In that range, the rewiring dynamics are not impactful enough to
generate timely structural changes in the population structure. As such,
population outcomes can be divided into two cases: the fraction of simulations
in which population-wide consensus is reached in a relatively short time
($\approx 10^{5}$ iterations) since both communities reach the same consensus
independently and those simulations in which each community reaches a
different local consensus and for which the simulations stop at the designated
$M_{\text{iter}}$ iterations. Hence, the initial plateau observed is not the
maximum number of iterations but an average of the combination of times from
those two scenarios.

In the consensus regime, for intermediate values of rewiring rates
($10^{-3}<p<10^{-1}$), the nature of the assessment (homophily vs heterophily,
color) has a more significant impact on the results than the strictness of the
assessment (tolerance level, symbols). Homophilic rewiring preferences show
decreased fixation times with lower tolerance-to-rewrite coefficients
($\beta$), whereas heterophilic rewiring leads to shorter fixation times
overall.

The rewiring rate determines if structurally polarized populations can
reshuffle their social structure and bridge communities in due time and, thus,
foster a population-wide consensus (see Figure 3b). As such, the average time
required to reach a consensus decreases monotonically with $p$. However, as
shown in Figures 3d and 3e, the average time will continue to have two
distinct contributions: one that represents the scenario where both modules
reach consensus ($\approx 10^{-5}$) and another corresponding to situations
where consensus is achieved through the rewiring of links and the break of the
initial polarized social structure.

It is possible to track the degree by which rewiring reshapes the original
network by tracking how the network modularity [50, 51, 52] decays with $p$
(see Figure 3c). We compute the modularity assuming the two initial
communities as the network partitions. For low values of rewiring rate ($p$),
the final networks can still keep their initial modular structure intact.
However, when the rewiring probability is large, the network structure begins
to lose its distinctive modular properties, initially slowly and then
abruptly. In fact, it is possible to observe a sharp transition in the
relative modularity of the network at a critical rewiring probability (see
Figure 3c). This critical point marks a transition between a ‘modular-like
network phase,’ below the critical rewiring rate $p_{c}$, and a ‘randomly
rewired network phase,’ for $p>p_{c}$, where the final networks lose the
initial modular character into that of a completely mixed structure with the
number of edges between each pair of nodes (within one of the original
communities) being equivalent to that of a network that has undergone random
rewiring and shares the same degree distribution with this final network.

Overall, the dynamics can be separated into two distinct phases: an initial
fast convergence to population-wide consensus and a second case that lasts
longer and in which the population is first stuck in a polarized opinion state
along the community structure of the network and then, through link rewiring,
is able to build the necessary bridges to reach consensus. For that reason, we
investigate what occurs when the population starts from an initial condition
of an opinion-polarized population with local consensus along the network’s
community structure. Since each community makes up half of the population, we
start with the same abundance of opinions as before. Figures 4a and 4b show
that for $p<p_{c}$, fixation times are longer for this initial set-up in
relation to a random initial set-up, and, for $p\gtrsim 0$, the average
fixation time is $M_{\text{iter}}$ and, thus, all populations end in a
polarized state, effectively removing the scenario where the network achieves
fast population-wide consensus (see, Figures 4d and 4e). Moreover, while
Figures 4a and 4b) display a similar trend for the curves under analysis in
comparison to those from Fig.3a and 3b, we see now that consensus is only
possible after a significant decay in the initial modularity of the network,
see Figure 4c, a task in which heterophilic rewiring preferences are more
efficient than homophilic ones.

These results show that the rewiring process alone does not guarantee that the
network population reaches consensus and, to achieve it, the rewiring process
must occur with a sufficiently high frequency and be of the adequate
type—heterophilic or homophilic— to lead to the desired outcome. Further, the
time to reach it differs even when the outcome is the same for both types.

Figure 5: Opinion dynamics with Homophilic and Heterophilic rewiring
preferences in a Polarization regime ($\theta=11\pi/10$). Panel a shows the
fixation time as a function of the rewiring rate, $p$. Panel b shows the
fraction of times a population ends in an opinion polarization state as a
function of the rewiring rate, $p$. Panel c shows how the modularity of the
initial structure decays as a function of $p$. Panels d) and e), show the
parameter range in which the observed dynamical pattern is aligned with the
dynamical polarization of well-mixed populations. In panels a), b), and c)
symbols indicate different values of the strictness of rewiring decisions
($\beta$) and colors the different rewiring preferences (homophilic in blue
and heterophilic populations in red). Results are the average over $10^{3}$
independent simulations, each with an upper bound of $2.5\times 10^{6}$
iterations, on modular networks with $N=10^{3}$ nodes, an average degree of
$\langle z_{i}\rangle=4$.

##  IV Dynamic Polarization Regime

Let us turn our attention to the regime when individuals easily change to rare
strategies and associated with dynamic polarization in the static and well-
mixed scenario. Non-complete social networks restrict the range of parameters
in which dynamical polarization occurs, facilitating the formation of
consensus. Although, in this case, the initial polarized structure of the
population plays a less relevant role, it is important to understand to which
extent rewiring can affect the chance and time to consensus.

Similarly to structural polarization, Figures 3a-c suggest that the nature of
the assessment (colors) seems to have a much more significant impact on the
results obtained than the strictness (symbols) of the assessment itself.
However, it is also possible to see that homophilic rewiring preferences are
more sensitive to the strictness of the assessment, especially for
intermediate values of $p$.

It is possible to recognize that the larger the rewiring rate, the easier it
becomes for heterophilic populations to remain polarized, as evidenced in the
increasing value of both the fraction of final polarized networks, Fig. 5b,
and the average time to reach consensus, Fig. 5a. Most importantly, however,
the rewiring probability can deeply change the dynamical pattern obtained by
the final networks populated by homophilic individuals.

The time to reach consensus and the fraction of polarized populations, Figures
5a and 5b, tend to increase with $p$. This increase can be attributed to the
lower probability of losing active links (i.e., links that can promote a
change in opinion), resulting in a delay in fixation time. However, in
populations with homophilic rewiring preferences, unlike heterophilic,
fixation times start decreasing for large values of $p$, followed by a
decrease in the fraction of populations that end in polarization. This
unexpected non-linear behavior for homophilic rewiring preferences is fostered
by the fact that if rewiring rates of homophilic individuals pass a critical
point, rewiring will outpace opinion dynamics and, as such, foster the
emergence of compact clusters of like-minded individuals in which the lack of
variability of opinions in a neighborhood limits the changes of opinions
spreading or, in other words, opinion updates. The same is not observed in
heterophilic rewiring preferences, where individuals rewire their links,
constantly looking to surround themselves with others of different opinions.

Moreover, the impact of rewiring dynamics on the initially modular structure
of the social network is also worth analyzing. Like in the first case, the
relative modularity decreases with increased rewiring probability ( Figure
5c), but it exhibits a clearer S-shaped behavior and decays faster with $p$.
This non-linear relationship suggests that the social network, depending on
the rewiring rate ($p$), will be either strongly modular (slow network
adaptation) or lack modularity network (intermediate in heterophilic rewiring
and fast in homophilic rewiring).

Finally, in regards to the results obtained for well-mixed populations, we see
that, when rewiring dynamics is considered, each of the studied rewiring
preferences leads to different dynamical responses: homophilic rewiring
preferences maintain or decrease the range of complexity parameters in which
dynamical polarization is observed (Figure 5d), but heterophilic rewiring
preferences expand the range of parameters and in the limit of very fast
rewiring rates match the well-mixed scenario.

##  V Conclusions

This study delves into the dynamics of consensus formation in polarized social
networks through a coevolutionary model that integrates competing opinions
with adaptive network dynamics. Our research focuses on the interplay between
homophilic and heterophilic rewiring preferences across a range of competing
processes to enhance the understanding of social mechanisms that either
facilitate or impede recovery from social polarization. In scenarios where
information needs significant reinforcement to outcompete alternatives, our
findings reveal two distinct pathways to consensus: a rapid one through
independent community consensus and a slower one driven by rewiring dynamics.
We demonstrate that heterophilic preferences are more effective in bridging
communities for consensus in complex-information-diffusion contexts due to
their ability to diversify opinion spaces. Conversely, in contagions requiring
minimal reinforcement, homophilic rewiring emerges as more adept at fostering
consensus and mitigating polarization risks, displaying a non-linear
relationship with the rewiring rate. This finding suggests that homophilic
preferences may be more resilient to polarization in environments where
information bits are easily interchangeable.

Our research extends beyond the existing literature by examining how different
rewiring preferences can mitigate or amplify polarization. This approach
contrasts with studies that predominantly emphasize homophilic tendencies in
social networks, suggesting a more nuanced role for heterophilic interactions
in bridging divided communities.

The implications of our findings are significant for policymakers and
designers of social or organizational networks, online and offline. By
promoting a diversity of rewiring preferences, societies can enhance their
resilience to the impacts of social polarization across a spectrum of simple
to complex contagion processes. Identifying the specific complexity of the
contagion of critical issues could further refine strategic approaches.

Expanding the proposed coevolutionary model to include more than two competing
opinions and network communities is a natural next step as the dynamics become
increasingly complex in such scenarios. Investigating different rewiring
mechanisms, formulating optimal strategies for opinion dissemination, and
designing targeted social interventions to control the spread of particular
viewpoints are crucial areas for future exploration. Motivated by specific
datasets, these extensions will allow us to fully capture the complexities of
specific real-world social interactions and individual decision-making
processes. Furthermore, developing new metrics to quantify social polarization
among competing contagion processes, rather than standalone issues, will
enable a deeper understanding of these complex polarization patterns. This
expansion of research will provide a more comprehensive understanding of
social dynamics and guide the development of effective strategies to address
the challenges posed by social polarization.

###  V.1 Acknowledgments

###### Acknowledgements.

FLP acknowledges the financial support provided by FCT Portugal under the
project UIDB/04152/2020 – Centro de Investigação em Gestão de Informação
(MagIC). VVV acknowledges funding from ENLENS under the project ”The Cost of
Large-Scale Transitions: Introducing Effective Targeted Incentives.”

## References

  * [1] Vítor V Vasconcelos, Sara M Constantino, Astrid Dannenberg, Marcel Lumkowsky, Elke Weber, and Simon Levin.  Segregation and clustering of preferences erode socially beneficial coordination.  Proceedings of the National Academy of Sciences, 118(50):e2102153118, 2021.
  * [2] Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis.  Quantifying controversy on social media.  ACM Transactions on Social Computing, 1(1):1–27, 2018.
  * [3] Uthsav Chitra and Christopher Musco.  Analyzing the impact of filter bubbles on social network polarization.  In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 115–123, 2020.
  * [4] Dennis Jacob and Sven Banisch.  Polarization in social media: A virtual worlds-based approach.  Journal of Artificial Societies and Social Simulation, 26(3), 2023\.
  * [5] Emily Kubin and Christian von Sikorski.  The role of (social) media in political polarization: a systematic review.  Annals of the International Communication Association, 45(3):188–206, 2021.
  * [6] Pablo Barberá.  Social media, echo chambers, and political polarization.  Social media and democracy: The state of the field, prospects for reform, 34, 2020.
  * [7] Cass R Sunstein.  Is social media good or bad for democracy.  SUR-Int’l J. on Hum Rts., 15:83, 2018.
  * [8] Balazs Kozma and Alain Barrat.  Consensus formation on adaptive networks.  Physical Review E, 77(1):016102, 2008.
  * [9] Cecilia Nardini, Balázs Kozma, and Alain Barrat.  Who’s talking first? consensus or lack thereof in coevolving opinion formation models.  Physical Review Letters, 100(15):158701, 2008.
  * [10] Tyll Krueger, Janusz Szwabiński, and Tomasz Weron.  Conformity, anticonformity and polarization of opinions: insights from a mathematical model of opinion dynamics.  Entropy, 19(7):371, 2017.
  * [11] Alina Sîrbu, Dino Pedreschi, Fosca Giannotti, and János Kertész.  Algorithmic bias amplifies opinion fragmentation and polarization: A bounded confidence model.  PloS one, 14(3):e0213246, 2019.
  * [12] Richard Durrett, James P Gleeson, Alun L Lloyd, Peter J Mucha, Feng Shi, David Sivakoff, Joshua ES Socolar, and Chris Varghese.  Graph fission in an evolving voter model.  Proceedings of the National Academy of Sciences, 109(10):3682–3687, 2012.
  * [13] Kazutoshi Sasahara, Wen Chen, Hao Peng, Giovanni Luca Ciampaglia, Alessandro Flammini, and Filippo Menczer.  Social influence and unfollowing accelerate the emergence of echo chambers.  Journal of Computational Social Science, 4(1):381–402, 2021.
  * [14] Yi Yu, Gaoxi Xiao, Guoqi Li, Wee Peng Tay, and Hao Fatt Teoh.  Opinion diversity and community formation in adaptive networks.  Chaos: An Interdisciplinary Journal of Nonlinear Science, 27(10), 2017.
  * [15] Antonio F Peralta, Matteo Neri, János Kertész, and Gerardo Iñiguez.  Effect of algorithmic bias and network structure on coexistence, consensus, and polarization of opinions.  Physical Review E, 104(4):044312, 2021.
  * [16] Fernando P Santos, Yphtach Lelkes, and Simon A Levin.  Link recommendation algorithms and dynamics of polarization in online social networks.  Proceedings of the National Academy of Sciences, 118(50):e2102141118, 2021.
  * [17] David JP O’Sullivan, Gary J O’Keeffe, Peter G Fennell, and James P Gleeson.  Mathematical modeling of complex contagion on clustered networks.  Frontiers in Physics, 3:71, 2015.
  * [18] William Goffman and V Newill.  Generalization of epidemic theory.  Nature, 204(4955):225–228, 1964.
  * [19] Daryl J Daley and David G Kendall.  Epidemics and rumours.  Nature, 204(4963):1118–1118, 1964.
  * [20] Damon Centola.  The spread of behavior in an online social network experiment.  Science, 329(5996):1194–1197, 2010.
  * [21] Daniel A Sprague and Thomas House.  Evidence for complex contagion models of social contagion from observational data.  PloS one, 12(7):e0180802, 2017.
  * [22] Bjarke Mønsted, Piotr Sapieżyński, Emilio Ferrara, and Sune Lehmann.  Evidence of complex contagion of information in social media: An experiment using twitter bots.  PloS one, 12(9):e0184148, 2017.
  * [23] Alessandro Vespignani.  Modelling dynamical processes in complex socio-technical systems.  Nature Physics, 8(1):32–39, 2012.
  * [24] Sinan Aral, Lev Muchnik, and Arun Sundararajan.  Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks.  Proceedings of the National Academy of Sciences, 106(51):21544–21549, 2009.
  * [25] Márton Karsai, Gerardo Iniguez, Kimmo Kaski, and János Kertész.  Complex contagion process in spreading of online innovation.  Journal of The Royal Society Interface, 11(101):20140694, 2014.
  * [26] Eytan Bakshy, Itamar Rosenn, Cameron Marlow, and Lada Adamic.  The role of social networks in information diffusion.  In Proceedings of the 21st International Conference on World Wide Web, pages 519–528, 2012.
  * [27] Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan.  Group formation in large social networks: membership, growth, and evolution.  In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 44–54, 2006.
  * [28] Eytan Bakshy, Brian Karrer, and Lada A Adamic.  Social influence and the diffusion of user-created content.  In Proceedings of the 10th ACM Conference on Electronic Commerce, pages 325–334, 2009.
  * [29] Meeyoung Cha, Alan Mislove, and Krishna P Gummadi.  A measurement-driven analysis of information propagation in the flickr social network.  In Proceedings of the 18th International Conference on World Wide Web, pages 721–730, 2009.
  * [30] David Kempe, Jon Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 137–146, 2003.
  * [31] Thomas W Valente.  Social network thresholds in the diffusion of innovations.  Social Networks, 18(1):69–89, 1996.
  * [32] Mark Granovetter.  Threshold models of collective behavior.  American Journal of Sociology, 83(6):1420–1443, 1978.
  * [33] Damon Centola.  How behavior spreads: The science of complex contagions, volume 3.  Princeton University Press Princeton, NJ, 2018.
  * [34] Sune Lehmann and Yong-Yeol Ahn.  Complex spreading phenomena in social systems.  Springer, 10:978–3, 2018.
  * [35] Márton Karsai, Gerardo Iñiguez, Riivo Kikas, Kimmo Kaski, and János Kertész.  Local cascades induced global contagion: How heterogeneous thresholds, exogenous effects, and unconcerned behaviour govern online adoption spreading.  Scientific Reports, 6(1):1–10, 2016.
  * [36] Vítor V Vasconcelos, Simon A Levin, and Flávio L Pinheiro.  Consensus and polarization in competing complex contagion processes.  Journal of the Royal Society Interface, 16(155):20190196, 2019.
  * [37] Nikolaj Horsevad, David Mateo, Robert E Kooij, Alain Barrat, and Roland Bouffanais.  Transition from simple to complex contagion in collective decision-making.  Nature Communications, 13(1):1442, 2022.
  * [38] Damon Centola and Michael Macy.  Complex contagions and the weakness of long ties.  American Journal of Sociology, 113(3):702–734, 2007.
  * [39] Lilian Weng, Filippo Menczer, and Yong-Yeol Ahn.  Virality prediction and community structure in social networks.  Scientific Reports, 3(1):1–6, 2013.
  * [40] Petter Holme and Mark EJ Newman.  Nonequilibrium phase transition in the coevolution of networks and opinions.  Physical Review E, 74(5):056108, 2006.
  * [41] Daichi Kimura and Yoshinori Hayakawa.  Coevolutionary networks with homophily and heterophily.  Physical Review E, 78(1):016103, 2008.
  * [42] Federico Vazquez, Víctor M Eguíluz, and Maxi San Miguel.  Generic absorbing transition in coevolution dynamics.  Physical Review Letters, 100(10):108702, 2008.
  * [43] Anatol Rapoport and Albert M Chammah.  Prisoner’s dilemma: A study in conflict and cooperation, volume 165\.  University of Michigan press, 1965.
  * [44] Amir N Licht.  Games commissions play: 2x2 games of international securities regulation.  Yale J. Int’l L., 24:61, 1999.
  * [45] Ross Cressman.  Evolutionary dynamics and extensive form games, volume 5.  MIT Press, 2003.
  * [46] Michael Doebeli and Christoph Hauert.  Models of cooperation based on the prisoner’s dilemma and the snowdrift game.  Ecology Letters, 8(7):748–766, 2005.
  * [47] Brian Skyrms.  The stag hunt and the evolution of social structure.  Cambridge University Press, 2004.
  * [48] Thomas C Schelling.  Micromotives and macrobehavior.  WW Norton & Company, 1978.
  * [49] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  Science, 286(5439):509–512, 1999.
  * [50] Mark EJ Newman.  Mixing patterns in networks.  Physical Review E, 67(2):026126, 2003.
  * [51] Mark EJ Newman.  Finding and evaluating community structure in networks.  Physical Review E, 69(2):026113, 2004.
  * [52] Mark EJ Newman.  Modularity and community structure in networks.  Proceedings of the National Academy of Sciences, 103(23):8577–8582, 2006.


# A generalization of the probability that the commutator of two group
elements is equal to a given element

Ahmad M.A. Alghamdi  Department of Mathematical Sciences, Faculty of Applied
Sciences
Umm Alqura University, P.O. Box 14035, Makkah, 21955, Saudi Arabia
<EMAIL_ADDRESS>and  Francesco G. Russo  IISSS ”Axel Munthe”
viale Axel Munthe, 80074, Anacapri (Naples), Italy<EMAIL_ADDRESS>
###### Abstract.

The probability that the commutator of two group elements is equal to a given
element has been introduced in literature few years ago. Several authors have
investigated this notion with methods of the representation theory and with
combinatorial techniques. Here we illustrate that a wider context may be
considered and show some structural restrictions on the group.

###### Key words and phrases:

Commutativity degree, relative $n$-th nilpotency degree, probability of
commuting pairs, characters.

Mathematics Subject Classification 2010: 20P05; 20D60

##  1\. Different formulations of the commutativity degree

Given two elements $x$ and $y$ of a group $G$, several authors studied the
probability that a randomly chosen commutator $[x,y]$ of $G$ satisfies a
prescribed property. P. Erdős and P. Turán [6] began to investigate the case
$[x,y]=1$, noting some structural restrictions on $G$ from bounds of
statistical nature. Their approach involved combinatorial techniques, which
were developed successively in [2, 3, 4, 5, 7, 9, 10, 12, 13, 15, 17] and
extended to the infinite case in [8, 13, 18]. On another hand, P. X. Gallagher
[11] investigated the case $[x,y]=1$, using character theory, and opened
another line of research, illustrated in [3, 4, 12, 16, 19]. The literature
shows that it is possible to variate the condition on $[x,y]$ involving
arbitrary words, which could not be the commutator word $[x,y]$. From now, all
the groups which we consider will be finite.

Given two subgroups $H$ and $K$ of $G$ and two integers $n,m\geq 1$, we define

(1.1)
$\mathrm{p}^{(n,m)}_{g}(H,K)=\small{\frac{|\\{(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\in
H^{n}\times K^{m}\ |\ [x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}]=g\\}|}{|H|^{n}\
|K|^{m}}}$

as the probability that a randomly chosen commutator of weight $n+m$ of
$H\times K$ is equal to a given element of $G$. Denoting

(1.2) $\mathcal{A}=\\{(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\in H^{n}\times
K^{m}\ |\ [x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}]=g\\},$

$|\mathcal{A}|=|H|^{n}\cdot|K|^{m}\cdot\mathrm{p}^{(n,m)}_{g}(H,K)$. The case
$n=m=1$ can be found in [4] and is called generalized commutativity degree of
$G$. For $n=m=1$ and $H=K=G$,

(1.3) $\mathrm{p}^{(1,1)}_{g}(G,G)=\mathrm{p}_{g}(G)=\frac{|\\{(x,y)\in G^{2}\
|\ [x,y]=g\\}|}{|G|^{2}}$

is the probability that the commutator of two group elements of $G$ is equal
to a given element of $G$ in [16].

It is well known (see for instance [1, Excercise 3, p. 183]) that the function
$\psi(g)=|\\{(x,y)\in G\times G\ |\ [x,y]=g\\}|$ is a character of $G$ and we
have $\psi={\underset{\chi\in\mathrm{Irr}(G)}{\sum}}\frac{|G|}{\chi(1)}\chi$,
where $\mathrm{Irr}(G)$ denotes the set of all irreducible complex characters
of $G$. However, the authors exploited this fact in [16, Theorem 2.1], writing
(1.3) as

(1.4)
$\mathrm{p}_{g}(G)=\frac{1}{|G|}{\underset{\chi\in\mathrm{Irr}(G)}{\sum}}\frac{\chi(g)}{\chi(1)},$

For terminology and notations in character theory we refer to [14].

Now for $g=1$,

(1.5)
$\mathrm{p}^{(1,1)}_{1}(G,G)=\mathrm{p}_{1}(G)=\mathrm{d}(G)=\frac{|\\{(x,y)\in
G^{2}\ |\ [x,y]=1\\}|}{|G|^{2}}=\frac{|{\rm Irr}(G)|}{|G|}$

is the $probability$ $of$ $commuting$ $pairs$ $of$ $G$ (or briefly the
$commutativity$ $degree$ of $G$), largely studied in [2, 3, 4, 5, 7, 9, 10,
11, 12, 13, 15, 17, 19]. In particular,

(1.6) $\mathrm{p}^{(n,1)}_{1}(G,G)=\frac{|\\{(x_{1},\ldots,x_{n},x_{n+1})\in
G^{n+1}\ |\
[x_{1},\ldots,x_{n},x_{n+1}]=1\\}|}{|G|^{n+1}}=\mathrm{d}^{(n)}(G),$

is the $n$-th nilpotency degree of $G$ in [2, 7, 9, 17, 18] and that

(1.7) $\mathrm{p}^{(n,1)}_{1}(H,G)=\frac{|\\{(x_{1},\ldots,x_{n},y)\in
H^{n}\times G\ |\ [x_{1},\ldots,x_{n},y]=1\\}|}{|H|^{n}\
|G|}=\mathrm{d}^{(n)}(H,G)$

is the relative $n$-th nilpotency degree of $H$ in $G$, studied in [7, 9, 17,
18]. We may express (1.7) not necessarily with $g=1$; assuming that $H$ is
normal in $G$, [4, Equation (4) and Theorem 4.2] imply

(1.8) $\mathrm{p}^{(1,1)}_{g}(H,G)=\frac{|\\{(x,y)\in H\times G\ |\
[x,y]=g\\}|}{|H|\
|G|}=\frac{1}{|H||G|}{\underset{\chi\in\mathrm{Irr}(G)}{\sum}}\frac{|H|\langle\chi_{H},\chi_{H}\rangle}{\chi(1)}\chi(g),$

where $\chi_{H}$ denotes the restriction of $\chi$ to $H$ and
$\langle,\rangle$ the usual inner product. Our purpose is to study (1.1),
extending the previous contributions in [2, 4, 7, 16, 17]. The main results of
the present paper are in Section 3, in which the general considerations of
Section 2 are applied.

##  2\. Technical properties and some computations

We begin with two elementary observations on (1.1).

######  Remark 2.1.

If $\mathcal{S}=\\{[x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}]\ |\
x_{1},\ldots,x_{n}\in H;y_{1},\ldots,y_{m}\in K\\}$, then
$\mathrm{p}^{(n,m)}_{g}(H,K)=0$ if and only if $g\not\in\mathcal{S}$. On
another hand, $\mathrm{p}^{(n,m)}_{1}(H,K)=1$ if and only if
$[\underbrace{H,\ldots,H}_{n-\mathrm{times}},\underbrace{K,\ldots,K}_{m-\mathrm{times}}]=[_{n}H,_{m}K]=1$.

######  Remark 2.2.

The equation (1.1) assigns by default the map

(2.1) $\mathrm{p}^{(n,m)}_{g}:(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\in
H^{n}\times K^{m}\mapsto\mathrm{p}^{(n,m)}_{g}(H,K)\in[0,1],$

which is a probability measure on $H^{n}\times K^{m}$, satisfying a series of
standard properties such as being multiplicative, symmetric and monotone.

The fact that (2.1) is multiplicative is described by the next result.

######  Proposition 2.3.

Let $E$ and $F$ be two groups such that $e\in E$, $f\in F$, $A,C\leq E$ and
$B,D\leq F$. Then

$\mathrm{p}^{(n,m)}_{(e,f)}(A\times C,B\times
D)=\mathrm{p}^{(n,m)}_{e}(A,B)\cdot\mathrm{p}^{(n,m)}_{f}(C,D).$

###### Proof.

It is enough to note that

$[([a_{1},\ldots,a_{n}],[c_{1},\ldots,c_{n}]),([b_{1},\ldots,b_{m}],[d_{1},\ldots,d_{m}])]=([[a_{1},\ldots,a_{n}],[b_{1},\ldots,b_{m}]],[c_{1},\ldots,c_{n}],[d_{1},\ldots,d_{m}]]).$

∎

Proposition 2.3 is true for finitely many factors instead of only two factors
and this can be checked with easy computations. Therefore the proof is
omitted. The fact that (2.1) is symmetric is described by the next result.

######  Proposition 2.4.

With the notations of (1.1),
$\mathrm{p}^{(n,m)}_{g}(H,K)=\mathrm{p}^{(n,m)}_{g^{-1}}(K,H)$. Moreover, if
$H$, or $K$, is normal in $G$, then
$\mathrm{p}^{(n,m)}_{g}(H,K)=\mathrm{p}^{(n,m)}_{g}(K,H)=\mathrm{p}^{(n,m)}_{g^{-1}}(H,K)$.

###### Proof.

The commutator rule $[x,y]^{-1}=[y,x]$ implies the first part of the result.
Now let $H$ be normal in $G$, $n\leq m$ and
$\mathcal{B}=\\{(y_{1},\ldots,y_{m},x_{1},\ldots,x_{n})\in K^{m}\times H^{n}\
|\ [y_{1},\ldots,y_{m},x_{1},\ldots,x_{n}]=g\\}$. The map
$\varphi:(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\in\mathcal{A}\mapsto(y^{-1}_{1},y^{-1}_{2},\ldots,y^{-1}_{n},y^{-1}_{n+1},\ldots,y^{-1}_{m},y_{1}x_{1}y^{-1}_{1},y_{2}x_{2}y^{-1}_{2},\ldots,y_{n}x_{n}y^{-1}_{n})\in\mathcal{B}$
is bijective and so the remaining equalities follow. A similar argument can be
applied, when the assumption $H$ is normal in $G$ is replaced by $K$ is normal
in $G$. ∎

The fact that (2.1) is monotone is more delicate to prove, since this is a
situation in which we may find upper bounds for (1.1). Details are given later
on. Now we will get another expression for (1.1). With the notations of (1.1),
$\mathrm{Cl}_{K}([x_{1},\ldots,x_{n}])$ denotes the $K$-conjugacy class of
$[x_{1},\ldots,x_{n}]\in H$.

######  Proposition 2.5.

With the notations of (1.1),

(2.2) $\mathrm{p}_{g}^{(n,m)}(H,K)=\frac{1}{|H|^{n}\
|K|^{m}}\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{K}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
H}}{\sum}|C_{K}([x_{1},\ldots,x_{n}])|^{m}.$

###### Proof.

It is straightforward to check that

(2.3)
$C_{K^{m}}([x_{1},\ldots,x_{n}])=\underbrace{C_{K}([x_{1},\ldots,x_{n}])\times\ldots\times
C_{K}([x_{1},\ldots,x_{n}])}_{m-\mathrm{times}}.$

In particular,
$|C_{K^{m}}([x_{1},\ldots,x_{n}])|=|C_{K}([x_{1},\ldots,x_{n}])|^{m}$.

$\mathcal{A}=\underset{[x_{1},\ldots,x_{n}]\in
H}{\bigcup}\\{[x_{1},\ldots,x_{n}]\\}\times T_{[x_{1},\ldots,x_{n}]},$ where
$T_{[x_{1},\ldots,x_{n}]}=\\{(y_{1},\ldots,y_{m})\in K^{m}\ |\
[x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}]=g\\}$. Obviously,
$T_{[x_{1},\ldots,x_{n}]}\not=\emptyset$ if and only if
$g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{K}([x_{1},\ldots,x_{n}])$. Let
$T_{[x_{1},\ldots,x_{n}]}\not=\emptyset$. Then
$|T_{[x_{1},\ldots,x_{n}]}|=|C_{K^{m}}([x_{1},\ldots,x_{n}])|$, because the
map $\psi:[y_{1},\ldots,y_{m}]\mapsto
g\overline{[y_{1},\ldots,y_{m}]}^{{}^{-1}}[y_{1},\ldots,y_{m}]$ is bijective,
where $\overline{[y_{1},\ldots,y_{m}]}$ is a fixed element of
$T_{[x_{1},\ldots,x_{n}]}$. We deduce that

(2.4) $\begin{array}[]{lcl}|\mathcal{A}|=\sum_{[x_{1},\ldots,x_{n}]\in
H}|T_{[x_{1},\ldots,x_{n}]}|=\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{K}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
H}}{\sum}|C_{K^{m}}([x_{1},\ldots,x_{n}])|\vspace{0.3cm}\\\
=\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{K}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
H}}{\sum}|C_{K}([x_{1},\ldots,x_{n}])|^{m}\end{array}$

and the result follows. ∎

Special cases of Proposition 2.5 are listed below.

######  Corollary 2.6.

In Proposition 2.5 , if $m=1$ and $G=K$, then

(2.5) $\mathrm{p}_{g}^{(n,1)}(H,G)=\frac{1}{|H|^{n}\
|G|}\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{G}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
H}}{\sum}|C_{G}([x_{1},\ldots,x_{n}])|.$

######  Corollary 2.7 (See [4], Theorem 2.3).

In Proposition 2.5 , if $m=n=1$, then

(2.6) $\mathrm{p}_{g}^{(1,1)}(H,K)=\frac{1}{|H|\
|K|}\underset{\underset{g^{-1}x\in\mathrm{Cl}_{K}(x)}{x\in
H}}{\sum}|C_{K}(x)|.$

In particular, if $G=K$, then $\mathrm{p}_{g}^{(1,1)}(H,G)=\frac{1}{|H|\
|G|}\underset{\underset{g^{-1}x\in\mathrm{Cl}_{G}(x)}{x\in
H}}{\sum}|C_{G}(x)|$.

######  Corollary 2.8 (See [7], Proof of Lemma 4.2).

In Proposition 2.5 , if $m=1$ and $G=K$, then

(2.7) $\mathrm{p}_{1}^{(n,1)}(H,G)=\mathrm{d}^{(n)}(H,G)=\frac{1}{|H|^{n}\
|G|}\underset{x_{1},\ldots,x_{n}\in H}{\sum}|C_{G}([x_{1},\ldots,x_{n}])|.$

######  Corollary 2.9.

In Proposition 2.5 , if $C_{K}([x_{1},\ldots,x_{n}])=1$, then

(2.8)
$\mathrm{p}^{(n,m)}_{1}(H,K)=\frac{1}{|H|^{n}}+\frac{1}{|K|^{m}}-\frac{1}{|H|^{n}\
|K|^{m}}.$

[4, Proposition 3.4] follows from Corollary 2.9, when $m=n=1$.

######  Remark 2.10.

Equation (1.7) makes equivalent the study of $\mathrm{p}^{(n,1)}_{1}(H,G)$ and
that of $\mathrm{d}^{(n)}(H,G)$. This is illustrated in Corollary 2.8 and
noted here for the first time. Therefore there are many information from [2,
7, 9, 17] and [4, 3, 16] which can be connected. It is relevant to point out
that these concepts were treated independently and with different methods in
the last years.

Let $\chi$ be a character of $G$ and $\theta$ be a character of $H\leq G$. The
Frobenius Reciprocity Law [14, Lemma 5.2] gives a link between the restriction
$\chi_{H}$ of $\chi$ to $H$ and the induced character $\theta^{G}$ of
$\theta$. Therefore
$\langle\chi,\theta^{G}\rangle_{G}=\langle\chi_{H},\theta\rangle_{H}.$Write
this number as
$e_{(\chi,\theta)}=\langle\chi,\theta^{G}\rangle_{G}=\langle\chi_{H},\theta\rangle_{H}.$
If $e_{(\chi,\theta)}=0$, then $\theta$ does not appear in $\chi_{H}$ and so
$\chi$ does not appear in $\theta^{G}$. Recall from [14] that, if
$e_{(\chi,\theta)}\neq 0$, then $\chi$ covers $\theta$ (or also $\theta$
belongs to the constituents of $\chi_{H}$). In particular, if
$\theta=\chi_{H}$, then
$e_{(\chi,\chi_{H})}=\langle\chi,(\chi_{H})^{G}\rangle_{G}=\langle\chi_{H},\chi_{H}\rangle_{H}.$
From a classic relation (see [14, Lemma 2.29]),
$e_{(\chi,\chi_{H})}=\langle\chi,(\chi_{H})^{G}\rangle_{G}=\langle\chi_{H},\chi_{H}\rangle_{H}\leq|G:H|\
\langle\chi,\chi\rangle_{G}=|G:H|e_{(\chi,\chi)}$ and the equality holds if
and only if $\chi(x)=0$ for all $x\in G-H$. In particular, if
$\chi\in\mathrm{Irr}(G)$, then $\langle\chi_{H},\chi_{H}\rangle_{H}=|G:H|\
\mathrm{if\ and\ only\ if}\ \chi(x)=0,$ for all $x\in G-H.$ Therefore the
following result is straightforward.

######  Corollary 2.11.

With the notations of (1.1), $\mathrm{p}_{g}^{(1,1)}(H,G)\leq|G:H|\
\mathrm{p}_{1}(G)$ and the equality holds if and only if all the characters
vanish on $G-H$.

At this point, [4, Theorem 4.2] becomes

(2.9) $\zeta(g)=|H|\
\underset{\chi\in\mathrm{Irr}(G)}{\sum}\frac{e_{(\chi_{H},\chi_{H})}}{\chi(1)}\cdotp\chi(g)=|\\{(x,y)\in
H\times G\ |\
[x,y]=g\\}|=\underset{\underset{g^{-1}x\in\mathrm{Cl}_{G}(x)}{x\in
H}}{\sum}|C_{G}(x)|,$

where $\zeta(g)$ is the number of solutions $(x,y)\in H\times G$ of the
equation $[x,y]=g$. Note that (2.9) and [1, Excercise 3, p. 183] give a short
argument to prove that $\zeta(g)$ is a character of $G$ with respect to the
argument in [4, Corollary 4.3]. The equation (1.8) becomes

(2.10) $\mathrm{p}_{g}^{(1,1)}(H,G)=\frac{\zeta(g)}{|H|\ |G|}.$

For the general case that $n>1$, $m>1$ and $G=K$,

(2.11)
$\mathrm{p}_{g}^{(n,m)}(H,G)=\frac{\zeta^{(n,m)}(g)}{|G|^{m}}=\frac{1}{|G|^{m}}\Big{(}\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{G}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
H}}{\sum}|C_{G}([x_{1},\ldots,x_{n}])|^{m}\Big{)},$

where

(2.12)
$\zeta^{(n,m)}(g)=\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{G}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
H}}{\sum}|C_{G}([x_{1},\ldots,x_{n}])|^{m}$

is the number of solutions $(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\in
H^{n}\times G^{m}$ of $[x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}]=g$.

######  Remark 2.12.

There are many evidences from the computations that $\zeta^{(n,m)}(g)$ is a
character of $G$.

Now we may prove upper bounds for (1.1) and find that (2.1) is monotone.

######  Proposition 2.13.

With the notations of (1.1), if $H\leq K$, then
$\mathrm{p}^{(n,m)}_{g}(H,G)\geq\mathrm{p}^{(n,m)}_{g}(K,G).$ The equality
holds if and only if $\mathrm{Cl}_{H}(x)=\mathrm{Cl}_{K}(x)$ for all $x\in G$.

###### Proof.

We note that $\frac{1}{|K|}\leq\frac{1}{|H|}$ and then
$\frac{1}{|K|^{n}}\leq\frac{1}{|H|^{n}}$. By Proposition 2.5,

(2.13)
$\begin{array}[]{lcl}|G|^{m}\cdot\mathrm{p}_{g}^{(n,m)}(K,G)=\frac{1}{|K|^{n}}\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{G}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
K}}{\sum}|C_{G}([x_{1},\ldots,x_{n}])|\vspace{0.3cm}\\\
\leq\frac{1}{|H|^{n}}\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{G}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
K}}{\sum}|C_{G}([x_{1},\ldots,x_{n}])|\end{array}$

in particular the last relation is true for $x_{1},\ldots,x_{n}\in H\leq K$
and continuing

(2.14)
$=\frac{1}{|H|^{n}}\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{G}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
H}}{\sum}|C_{G}([x_{1},\ldots,x_{n}])|=|G|^{m}\cdot p_{g}^{(n,m)}(H,G).$

The rest of the proof is clear. ∎

The next result shows an upper bound, which generalizes [7, Theorem 4.6].

######  Proposition 2.14.

With the notations of (1.1), if $N$ is a normal subgroup of $G$ such that
$H\leq N$, then
$\mathrm{p}^{(n,m)}_{g}(H,G)\leq\mathrm{p}^{(n,m)}_{g}\Big{(}\frac{H}{N},\frac{G}{N}\Big{)}.$
Moreover, if $N\cap[_{n}H,_{m}G]=1$, then the equality holds.

###### Proof.

We have

$\begin{array}[]{lcl}|H|^{n}\ |G|^{m}\
\mathrm{p}^{(n,m)}_{g}(H,G)=|\mathcal{A}|\vspace{0.3cm}\\\
=|\\{(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\in H^{n}\times G^{m}\ |\
[x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}]\cdot g^{-1}=1\\}|\vspace{0.3cm}\\\
=|\\{(x_{1},\ldots,x_{n},y_{1},\ldots,y_{m})\in H^{n}\times G^{m}\ |\
[x_{1},\ldots,x_{n},y_{1},\ldots,y_{m},g^{-1}]=1\\}|\vspace{0.3cm}\\\
=\sum_{x_{1}\in H}\ldots\sum_{x_{n}\in H}\sum_{y_{1}\in G}\ldots\sum_{y_{m}\in
G}|C_{G}([x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}])|\vspace{0.3cm}\\\
=\sum_{x_{1}\in H}\ldots\sum_{x_{n}\in H}\sum_{y_{1}\in G}\ldots\sum_{y_{m}\in
G}\frac{|C_{G}([x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}])N|\cdot|C_{N}([x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}])|}{|N|}\vspace{0.3cm}\\\
\leq\sum_{x_{1}\in H}\ldots\sum_{x_{n}\in H}\sum_{y_{1}\in
G}\ldots\sum_{y_{m}\in
G}|C_{G/N}([x_{1}N,\ldots,x_{n}N,y_{1}N,\ldots,y_{m}N])|\vspace{0.3cm}\\\
\cdot|C_{N}([x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}])|\vspace{0.3cm}\\\
=\sum_{S_{1}\in H/N}\sum_{x_{1}\in S_{1}}\ldots\sum_{S_{n}\in
H/N}\sum_{x_{n}\in S_{n}}\sum_{T_{1}\in G/N}\sum_{y_{1}\in
T_{1}}\ldots\sum_{T_{m}\in G/N}\sum_{y_{m}\in T_{m}}\vspace{0.3cm}\\\
|C_{G/N}([S_{1},\ldots,S_{n},T_{1},\ldots,T_{m}])|\cdot|C_{N}([x_{1},\ldots,y_{m}])|\vspace{0.3cm}\\\
=\Big{(}\sum_{S_{1}\in H/N}\ldots\sum_{S_{n}\in H/N}\sum_{T_{1}\in
G/N}\ldots\sum_{T_{m}\in
G/N}|C_{G/N}([S_{1},\ldots,S_{n},T_{1},\ldots,T_{m}])|\Big{)}\vspace{0.3cm}\\\
\cdot\Big{(}\sum_{x_{1}\in S_{1}}\ldots\sum_{x_{n}\in S_{n}}\sum_{y_{1}\in
T_{1}}\ldots\sum_{y_{m}\in
T_{m}}|C_{N}([x_{1},\ldots,y_{m}])|\Big{)}\vspace{0.3cm}\\\
\leq|N|^{n+m}\sum_{S_{1}\in H/N}\ldots\sum_{S_{n}\in H/N}\sum_{T_{1}\in
G/N}\ldots\sum_{T_{m}\in G/N}\vspace{0.3cm}\\\
|C_{G/N}([S_{1},\ldots,S_{n},T_{1},\ldots,T_{m}])|\vspace{0.3cm}\\\
=\Big{|}\frac{H}{N}\Big{|}^{n}\ \Big{|}\frac{G}{N}\Big{|}^{m}\
p^{(n,m)}_{g}\Big{(}\frac{H}{N},\frac{G}{N}\Big{)}\ |N|^{n+m}=|H|^{n}\
|G|^{m}\
\mathrm{p}^{(n,m)}_{g}\Big{(}\frac{H}{N},\frac{G}{N}\Big{)}.\end{array}$

The condition of equality in the above relations is satisfied exactly when
$N\cap[_{n}H,_{m}G]=1$. The result follows.∎

######  Corollary 2.15.

A special case of Proposition 2.14 is
$\mathrm{p}_{g}(G)\leq\mathrm{p}_{g}(G/N)$.

######  Corollary 2.16 (See [7], Theorem 4.6).

In Proposition 2.14 , if $m=1$ and $g=1$, then
$\mathrm{d}^{(n)}(H,G)\leq\mathrm{d}^{(n)}(H/N,G/N)$.

##  3\. Some upper and lower bounds

A relation among (1.1)–(1.8) is described below.

######  Theorem 3.1.

With the notations of (1.1),
$\mathrm{p}^{(n,m)}_{g}(G,G)\leq\mathrm{p}^{(n,m)}_{g}(H,K)\leq\mathrm{p}^{(n,m)}_{1}(H,K)\leq\mathrm{p}^{(n,m)}_{1}(H,G)\leq\mathrm{p}^{(n,m)}_{1}(H,H).$

###### Proof.

From Proposition 2.13,
$\mathrm{p}^{(n,m)}_{g}(G,G)\leq\mathrm{p}^{(n,m)}_{g}(G,H)$. From Proposition
2.5,

(3.1) $\mathrm{p}^{(n,m)}_{g}(H,K)=\frac{1}{|H|^{n}\
|K|^{m}}\underset{\underset{g^{-1}[x_{1},\ldots,x_{n}]\in\mathrm{Cl}_{K}([x_{1},\ldots,x_{n}])}{x_{1},\ldots,x_{n}\in
H}}{\sum}|C_{K}([x_{1},\ldots,x_{n}])|^{m}$

and for $g=1$ we get

(3.2) $\leq\frac{1}{|H|^{n}\ |K|^{m}}\underset{x_{1},\ldots,x_{n}\in
H}{\sum}|C_{K}([x_{1},\ldots,x_{n}])|^{m}=\mathrm{p}^{(n,m)}_{1}(H,K),$

where in the last passage still Proposition 2.5 is used. From
$C_{K}([x_{1},\ldots,x_{n}])\subseteq C_{G}([x_{1},\ldots,x_{n}])$, we deduce

(3.3) $\leq\underset{x_{1},\ldots,x_{n}\in
H}{\sum}|C_{G}([x_{1},\ldots,x_{n}])|^{m}=\mathrm{p}^{(n,m)}_{1}(H,G).$

Applying Proposition 2.4,
$\mathrm{p}^{(n,m)}_{1}(H,G)=\mathrm{p}^{(n,m)}_{1}(G,H)$ and so
$\mathrm{p}^{(n,m)}_{1}(G,H)\leq\mathrm{p}^{(n,m)}_{1}(H,H)$ by Proposition
2.13. ∎

######  Corollary 3.2.

With the notations of (1.1), if $Z(G)=1$, then
$\mathrm{p}^{(n,1)}_{g}(H,K)\leq\frac{2^{n}-1}{2^{n}}.$

###### Proof.

It follows from Theorem 3.1 and [7, Theorem 5.3]. ∎

Another significant restriction is the following.

######  Theorem 3.3.

With the notations of (1.1), let $p$ be the smallest prime divisor of $|G|$.
Then

  * (i)

$\mathrm{p}^{(n,m)}_{g}(H,K)\leq\frac{2p^{n}+p-2}{p^{m+n}}$;

  * (ii)

$\mathrm{p}^{(n,m)}_{g}(H,K)\geq\frac{(1-p)|Y_{H^{n}}|+p|H^{n}|}{|H^{n}|\
|K^{m}|}-\frac{(|K|+p)|C_{H}(K)|^{n}}{|H^{n}|\ |K^{m}|}$;

where $Y_{H^{n}}=\\{[x_{1},\ldots,x_{n}]\in H^{n}\ |\
C_{K}([x_{1},\ldots,x_{n}])=1\\}$.

###### Proof.

If $[_{n}H,_{m}K]=1$, then $C_{H^{n}}(K^{m})=H^{n}$ and $Y_{H^{n}}$ equals
$H^{n}$ or an empty set according as $K^{m}$ is trivial or nontrivial. Assume
that $[_{n}H,_{m}K]\not=1$. Then $Y_{H^{n}}\cap
C_{H^{n}}(K^{m})=Y_{H^{n}}\cap(C_{H}(K^{m})\times\ldots\times
C_{H}(K^{m}))=Y_{H^{n}}\cap(C_{H}(K)\times C_{H}(K)\times\ldots\times
C_{H}(K))=Y_{H^{n}}\cap(C_{H}(K))^{nm}\not=\emptyset$ and

(3.4) $\begin{array}[]{lcl}\underset{x_{1},\ldots,x_{n}\in
H}{\sum}|C_{K^{m}}([x_{1},\ldots,x_{n}])|=\underset{x_{1},\ldots,x_{n}\in
H}{\sum}|C_{K}([x_{1},\ldots,x_{n}])|^{m}\vspace{0.3cm}\\\
=\underset{x_{1},\ldots,x_{n}\in
Y_{H^{n}}}{\sum}|C_{K}([x_{1},\ldots,x_{n}])|^{m}+\underset{x_{1},\ldots,x_{n}\in
C_{H^{n}}(K)}{\sum}|C_{K}([x_{1},\ldots,x_{n}])|^{m}\vspace{0.3cm}\\\
+\underset{x_{1},\ldots,x_{n}\in H^{n}-(Y_{H^{n}}\cup
C_{H^{n}}(K))}{\sum}|C_{K}([x_{1},\ldots,x_{n}])|^{m}\vspace{0.3cm}\\\
=|Y_{H^{n}}|+|K|\ |C_{H}(K)|^{n}+\underset{x_{1},\ldots,x_{n}\in
H^{n}-(Y_{H^{n}}\cup
C_{H^{n}}(K))}{\sum}|C_{K}([x_{1},\ldots,x_{n}])|^{m}.\end{array}$

Since $p^{m}\leq|C_{K}([x_{1},\ldots,x_{n}])|^{m}\leq\frac{|K^{m}|}{p^{m}}$,
$|Y_{H^{n}}|\leq|H^{n}|$ and
$p^{n}\leq|C_{H}(K)|^{n}\leq\frac{|H^{n}|}{p^{n}}$,

(3.5) $\leq|Y_{H^{n}}|+|K|\
|C_{H}(K)|^{n}+(|H^{n}|-(|Y_{H^{n}}|+|C_{H}(K)|^{n})\cdot\frac{|K^{m}|}{p^{m}}$

and then

(3.6)
$\begin{array}[]{lcl}\mathrm{p}^{(n,m)}_{g}(H,K)\leq\frac{|Y_{H^{n}}|}{|H^{n}|\
|K^{m}|}+\frac{|K|\ |C_{H}(K)|^{n}}{|H^{n}|\
|K^{m}|}+\frac{1}{p^{m}}-\frac{|Y_{H^{n}}|}{p^{m}\
|H^{n}|}-\frac{|C_{H}(K)|^{n}}{p^{m}\ |H^{n}|}\vspace{0.3cm}\\\
\leq\frac{1}{p^{m}}+\frac{1}{p^{m+n-1}}+\frac{1}{p^{m}}-\frac{1}{p^{m+n}}-\frac{1}{p^{m+n}}=\frac{2p^{n}+p-2}{p^{m+n}}.\end{array}$

Hence (i) follows. On another hand, we may continue in the other direction

(3.7) $\geq|Y_{H^{n}}|+|K|\ |C_{H}(K)|^{n}+p\
(|H^{n}|-(|Y_{H^{n}}|+|C_{H}(K)|^{n})$

and then

(3.8) $\mathrm{p}^{(n,m)}_{g}(H,K)\geq\frac{(1-p)|Y_{H^{n}}|}{|H^{n}|\
|K^{m}|}+\frac{p}{|K^{m}|}-\frac{(|K|+p)|C_{H}(K)|^{n}}{|H^{n}|\ |K^{m}|}.$

Then (ii) follows. ∎

The bound in Theorem 3.3 (i) is a little bit different from the bound in [4,
Corollary 3.9], where it is proved that
$\mathrm{p}^{(1,1)}_{g}(H,K)\leq\frac{2p-1}{p^{2}}$ and in particular
$\mathrm{p}^{(1,1)}_{g}(H,K)\leq\frac{3}{4}$. We conclude the following
structural restriction.

######  Corollary 3.4.

In Theorem 3.3, if $\mathrm{p}^{(n,m)}_{g}(H,K)=\frac{2p^{n}+p-2}{p^{m+n}}$,
then

(3.9)
$|H:C_{H}(K)|\leq\Big{(}\frac{p^{n+1}-p^{3}-\frac{p^{2}}{2}+p}{2p^{2}+p-2}\Big{)}^{\frac{1}{n}}.$

###### Proof.

Looking at (3.6) and the proof of Theorem 3.3 (i), we deduce

(3.10)
$\begin{array}[]{lcl}\frac{2p^{n}+p-2}{p^{m+n}}\leq\frac{|Y_{H^{n}}|}{|H^{n}|\
|K^{m}|}+\frac{|K||C_{H}(K)|^{n}}{|H^{n}|\
|K^{m}|}+\frac{1}{p^{m}}\leq\frac{1}{p^{m}}+\frac{1}{p^{m-1}}\
\Big{|}\frac{C_{H}(K)}{H}\Big{|}^{n}+\frac{1}{p^{m}}\vspace{0.3cm}\\\
=\frac{1}{p^{m-1}}\Big{(}\frac{2}{p}+|\frac{C_{H}(K)}{H}|^{n}\Big{)}\end{array}$

and then
$\frac{2p^{n}+p-2}{p^{n+1}}\leq\frac{2}{p}+\Big{|}\frac{C_{H}(K)}{H}\Big{|}^{n}$.
We conclude that
$\frac{p^{n+1}}{2p^{n}+p-2}\geq\frac{p}{2}+\Big{|}\frac{H}{C_{H}(K)}\Big{|}^{n}$
and so

(3.11)
$\frac{p^{n+1}}{2p^{n}+p-2}-\frac{p}{2}=\frac{p^{n+1}-p^{3}-\frac{p^{2}}{2}+p}{2p^{2}+p-2}\geq\Big{|}\frac{H}{C_{H}(K)}\Big{|}^{n}.$

The result follows, once we extract the $n$-th root. ∎

## Acknowledgement

The second author is grateful to the colleagues of the Ferdowsi University of
Mashhad for some helpful comments in the period in which the present work has
been written.

## References

  * [1] J. Alperin and B. Bell, Groups and Representations, Springer, 1995, New York.
  * [2] K. Chiti, M. R. R. Moghaddam and A. R. Salemkar, $n$–isoclinism classes and $n$–nilpotency degree of finite groups, Algebra Colloq. 12 (2005), 225–261.
  * [3] A. K. Das and R. K. Nath, On solutions of a class of equations in a finite group, Commun. Algebra 37 (2009), 3904–3911.
  * [4] A. K. Das and R. K. Nath, On the generalized relative commutative degree of a finite group, Int. Electr. J. Algebra 7 (2010), 140–151.
  * [5] H. Doostie and M. Maghasedi, Certain classes of groups with commutativity degree $d(G)<1/2$, Ars Combinatoria 89 (2008), 263–270.
  * [6] P. Erdős and P. Turán, On some problems of statistical group theory, Acta Math. Acad. Sci. Hung. 19 (1968), 413–435.
  * [7] A. Erfanian, P. Lescot and R. Rezaei, On the relative commutativity degree of a subgroup of a finite group, Comm. Algebra 35 (2007), 4183–4197.
  * [8] A. Erfanian and R. Rezaei, On the commutativity degree of compact groups, Arch. Math. (Basel) 93 (2009), 345–356.
  * [9] A. Erfanian, R. Rezaei and F. G. Russo, Relative $n$-isoclinism classes and relative $n$-th nilpotency degree of finite groups, e-print, Cornell University, 2010, arXiv:0003310 [math.GR].
  * [10] I.V. Erovenko and B. Sury, Commutativity degree of wreath products of finite abelian groups, Bull. Austral. Math. Soc. 77 (2008), 31–36.
  * [11] P. X. Gallagher, The number of conjugacy classes in a finite group, Math. Z. 118 (1970), 175–179.
  * [12] R. M. Guralnick and G. R. Robinson, On the commuting probability in finite groups, J. Algebra 300 (2006), 509–528.
  * [13] W. H. Gustafson, What is the probability that two groups elements commute? Amer. Math. Monthly 80 (1973), 1031–1304.
  * [14] I. M. Isaacs, Character Theory of Finite Groups, Dover Publ., New York, 1994.
  * [15] P. Lescot, Isoclinism classes and commutativity degrees of finite groups, J. Algebra 177 (1987), 847–869.
  * [16] M. R. Pournaki and R. Sobhani, Probability that the commutator of two group elements is equal to a given element, J. Pure Appl. Algebra 212 (2008), 727–734.
  * [17] R. Rezaei and F. G. Russo, $n$-th relative nilpotency degree and relative $n$-isoclinism classes, e-print, Cornell University, 2010, arXiv:1003.2297v1 [math.GR].
  * [18] R. Rezaei and F. G. Russo, Bounds for the relative $n$-th nilpotency degree in compact groups, e-print, Cornell University, 2009, arXiv:0910.4716v1 [math.GR].
  * [19] D. J. Rusin, What is the probability that two elements of a finite group commute?, Pacific J. Math. 82 (1979), 237–247.


# VTOL Failure Detection and Recovery by Utilizing Redundancy

Mohammadreza Mousaei1, Azarakhsh Keipour2, Junyi Geng3 and Sebastian Scherer4
1,3,4 Robotics Institute, Carnegie Mellon University, Pittsburgh, PA
[mmousaei, junyigen<EMAIL_ADDRESS>Robotics Institute, Carnegie
Mellon University, Pittsburgh, PA<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Offering vertical take-off and landing (VTOL) capabilities and the ability to
travel great distances are crucial for Urban Air Mobility (UAM) vehicles.
These capabilities make hybrid VTOLs the clear front-runners among UAM
platforms.

On the other hand, concerns regarding the safety and reliability of autonomous
aircraft have grown in response to the recent growth in aerial vehicle usage.
As a result, monitoring the aircraft status to report any failures and
recovering to prevent the loss of control when a failure happens are becoming
increasingly important. Hybrid VTOLs can withstand some degree of actuator
failure due to their intrinsic redundancy. Their aerodynamic performance,
design, modeling, and control have all been addressed in the previous studies.
However, research on their potential fault tolerance is still a less
investigated field.

In this workshop, we will present a summary of our work on aircraft fault
detection and the recovery of our hybrid VTOL. First, we will go over our
real-time aircraft-independent system for detecting actuator failures and
abnormal behaviors. Then, in the context of our custom tiltrotor VTOL aircraft
design, we talk about our optimization-based control allocation system, which
utilizes the vehicle’s configuration redundancy to recover from different
actuation failures. Finally, we explore the ideas of how these parts can work
together to provide a fail-safe system. We present our simulation and real-
life experiments.

##  I Introduction

Fixed-rotor unmanned aerial vehicles (UAVs), such as multirotors, have
vertical take-off and landing (VTOL) capabilities [1, 2]. However, they are
inefficient. On the other hand, fixed-wings are far more energy-efficient but
lack VTOL capability [3]. Hybrid VTOL UAVs combine VTOL capabilities with
efficient long-range flight and are the clear front-runners for Urban Air
Mobility (UAM).

To securely incorporate UAVs into the airspace for real-world UAM
applications, the aircraft should have a degree of tolerance to different
hardware failures. While the controller is generally designed to be as robust
to failures as possible [4, 5], failures may still happen. Hence, there is a
need to detect and identify the failures and recover from them.

Figure 1: Our custom VTOL tiltrotor platform [6].

The majority of the fault detection methods are heavily model-dependent [7, 8,
9, 10]. On the other hand, signal processing-based techniques [11, 12, 13] do
not require the aircraft’s model and instead detect the faults by analyzing
the signals from the aircraft.

On the failure recovery side, depending on the configuration of the aircraft,
there are a variety of ways to deal with actuator failures [14, 15, 16]. In
the case of hybrid VTOL UAVs, although there has been a recent increase in
research [17, 18, 19, 20, 21, 22], fault tolerance has received only limited
attention [23]. These aircraft offer configuration redundancy; however, little
investigation has been done into using this redundancy to recover from
actuator failures.

This workshop summarizes our works on aircraft fault detection [24, 25] and
failure recovery of our hybrid VTOL design [6]. First, we describe our real-
time RLS-based method for detecting actuator failures and anomalies in
aircraft behavior. Instead of relying on the complete model of the aircraft,
this approach models the connection between correlated input-output signal
pairs and estimates a model online. The generated model is then used for real-
time fault detection of virtually any aircraft without prior training. Then,
we discuss tolerance to numerous types of actuator failures in the context of
our custom tiltrotor VTOL aircraft design (Figure 1). The aircraft is more
resilient to actuator failures thanks to our designed dynamic control
allocation, which takes advantage of system redundancy. The aircraft can thus
recover from a collection of actuator failures in different flight phases by
solving a constraint optimization problem. We present our simulation and real-
world experiments performed to validate our methods. Finally, we explore the
idea of how the detection and recovery systems can create a complete pipeline
from detection to identification and recovery and discuss the possible future
directions to achieve the safety requirement for UAM applications.

##  II Our Work

In this section, we first briefly describe our fault detection system, which
can be used for almost any aircraft [24]. Then we describe our custom VTOL
system and discuss the fault recovery approach implemented in the context of
this system [6].

Figure 2: The flowchart of the fault detection method [24].

The aircraft dynamics are nonlinear and cannot be described by a linear model.
However, instead of modeling the whole aircraft dynamics, the purpose of the
detection part is to describe the interaction between two signals. Because
many signal pairs are linearly connected to one another, we may use a linear
model to estimate their connection. The aircraft dynamics were modeled using
an Autoregressive Exogenous (ARX) Time-Domain Transfer Function model. Using
our model, having past states and the current input is adequate to estimate
the current output.

Assuming a true unknown ARX model for the relationship of input-output
signals, the estimation algorithm aims to compute a prediction model which
converges to the true model given enough samples. Recursive estimation methods
aim to compute a new model estimate by a simple update to the current model
when a new observation becomes available.

Our approach [24] uses the Recursive Least Squares (RLS) method, which is an
online optimization method that recursively finds the coefficients to minimize
a weighted linear least-squares cost function related to the input signals
[26]. Compared to most other methods, RLS exhibits fast convergence [27].
However, this benefit comes at the cost of higher computational complexity.

Once the ARX Time-Domain Transfer Function is estimated for the input-output
pair, the output is predicted from the input using this model at each step.
The error between the prediction and the measured output is utilized to update
the model and calculate its Z-score. A high Z-score indicates a fault in the
system. The algorithm can be written in the form of Fig. 2.

We published our dataset consisting of tens of flights with various actuator
failures on a real aircraft [25]. It has been used in ours and several other
works, including for failure identification with short identification times
[28].

Based on the methods mentioned above, the failure can be detected and
identified in near real-time. Given a correctly detected and identified
failure, the next step is recovery from the failure.

For our tiltrotor VTOL, we developed an optimization-based dynamic control
allocation method in the PX4 flight control stack that can respond to the
configuration changes of the vehicle, such as an actuator failure [6]. Our
designed control diagram is shown in Fig. 3.

Figure 3: An overview of the VTOL recovery method [6].

This control allocation module aims to allocate the desired control setpoint
to the actuators depending on the current state and aircraft configuration. To
execute this allocation, we define a constrained optimization problem.

We first linearize the vehicle dynamics around the equilibrium points. This
linearization leads to the control allocation matrix that maps our actuation
change from the equilibrium points to the resulting forces and moments. To
assign certain actuation for the desired set of forces and moments, the most
straightforward technique is to use the pseudo-inverse of the control
allocation matrix to obtain the least-norm solution.

An issue with the least-norm solution is that it might be out of actuation
limits, which means that the desired values cannot be allocated to the
actuators after trimming. This issue could cause the vehicle to deviate from
the required forces and moments. Another problem is that consecutive solutions
might be far apart, leading to jittery motor performance. So, even if the
least-norm solution is feasible and within the range of actuation, it is not
usable in practice.

To resolve the issues of the least-norm solution, we utilize the fact that our
system is over-actuated, and there exists a non-zero null space that could be
utilized to adjust the least-norm solution while still producing the desired
set of forces and torques. We achieve this by combining the null space and the
least-norm solutions. The least-norm solution achieves the net wrench, whereas
the null space solution generates zero wrenches but remaps the inputs within
the actuator limits while minimizing actuation change between consecutive
steps. The final optimization problem is expressed as follows:

$\displaystyle\min_{\boldsymbol{\lambda}}$ $\displaystyle
J(\mathbf{u}_{\mathrm{sp}})$ (1) $\displaystyle\mathrm{s.t}~{}~{}$
$\displaystyle\mathbf{u}_{\mathrm{min},i}\leq\mathbf{u}_{\mathrm{sp},i}\leq\mathbf{u}_{\mathrm{max},i}$

where $\mathbf{u}_{\mathrm{sp}}$ is the overall control setpoint, $J(\cdot)$
is the objective function where we try to minimize the actuator change from
the trimmed condition,

$J=(\mathbf{u}_{\mathrm{sp}}-\mathbf{u}_{\mathrm{sp},\mathrm{trim}})^{\top}\mathbf{R}(\mathbf{u}_{\mathrm{sp}}-\mathbf{u}_{\mathrm{sp},\mathrm{trim}})$
(2)

where $\mathbf{R}$ is the weight matrix considering the contribution from
different actuators. The inequality constraints of problem (Eq. 1) ensure that
the output is within actuator limits, where $i$ represents the $i^{\text{th}}$
actuator. Simultaneously, minimizing the cost function ensures that the
actuation change is minimized while the commands are kept near the equilibrium
point.

In the event of an actuation failure, we assume the failure has been detected
and identified. With the knowledge of the actuation failure, we zero out or
delete the corresponding column, which represents the failed actuator in the
control allocation matrix. This provides the control allocation for the
failure scenario. We subtract that from the desired wrench since the failed
actuator still produces some wrench. The control allocation problem then
becomes similar to that in the healthy vehicle. The only difference is that
the problem dimension has been reduced by the number of failed actuators.
Therefore, we formulate a similar constrained optimization problem for the
vehicle with actuation failure.

TABLE I: Actuator failure cases in different flight phases [6]. Flight Phase | Failure Description | Cause
---|---|---
Multirotor | Lock of one tilt in hover | Broken servo
Single motor failure in hover | Motor flaw/propeller loss
Fix-wing | Single motor failure in cruise | Motor flaw/propeller loss
Lock of one elevator in cruise | Broken servo
Lock of one aileron in cruise | Broken servo

##  III Experiments and Results

###  III-A Failure Detection

TABLE II: Failure detection statistics [24]. | Failure
---
Type
| # of
---
tests
| Flight
---
Time(s)
| Avg.
---
Detection
Time(s)
| Max
---
Detection
Time(s)
| Accuracy
---
(%)
Engine | 7 | 665 | 2.28 | 3.37 | 100
Rudder | 3 | 171 | 0.21 | 0.25 | -
Elevator | 2 | 181 | 0.36 | 0.36 | -
No Failure | 5 | 262 | - | - | -
Total | 22 | 1735 | 2.02 | 5.6 | 86.36

Our failure detection system is developed and tested using C++ and ROS in
Ubuntu on Nvidia Jetson TX2 onboard computer and Ardupilot autopilot is used
on Pixhawk flight control. The flight test platform is a modified Carbon Z
T-28, a fixed-wing UAV with a wingspan of 2 meters and a central electric
engine.

The statistics from 22 flight tests with various types of failures are
presented in Table II. Different performance metrics are used to evaluate our
technique. Out of 22 tests, we found two False Positive (FP) and two False
Negative (FN) detections, achieving $86.36$ percent accuracy, $88.23$ percent
precision, and $88.23$ percent recall (sensitivity) within the total number of
19 correct sequences. A more detailed description of the tests and results is
available in [24] and our dataset article [25] explains the assessment
measures utilized for our calculations in further detail.

Fig. 4 shows how the system detects the engine failure from a pair of
commanded/measured signals (roll error in this case). After the initial
stabilization phase, the Z-score of the prediction error tends to be
significantly less than the set threshold for the anomaly. However, when the
failure happens, the prediction does not match the measurement anymore, and
the spike in the Z-score indicates that an anomaly has happened. The figure
also shows how the prediction error variance stabilizes with the stabilization
of the predictor model.

Figure 4: Z-Score vs Roll input for an engine failure flight test showing the
detection of the fault from the sudden increase in Z-score [24].

###  III-B Failure Recovery

We model the tiltrotor VTOL in Gazebo based on our design in [6]. The dynamic
control allocation is developed in PX4 autopilot, which can directly run on
real aircraft. The constrained optimization is solved using Algilib [29],
which is a numerical analysis and data processing library.

####  III-B1 Motor Failure in Hover

When the vehicle takes off and hovers before transition, we completely turn
down one of the motors to test this failure. The allocated actuator command is
shown in Fig. 5. When the front-right motor fails, it is evident that all
other effective actuators adjust and compensate for the thrust reduction. It
is worth noting that the tilt angle associated with the failed motor
immediately drops to zero, which is understandable given that the defective
rotor can no longer create any applicable torques. After about 10 seconds, the
actuator commands converge. After recovery, the aircraft is still controllable
and can follow the planned waypoints.

Figure 5: Actuator commands for a motor failure in hover [6].

We compare our approach to one in which the controller is unaware of the motor
failure. The aircraft attitude and flight path are depicted in Fig. 6 for two
scenarios: with and without being alerted of the system failure. Without the
knowledge of the failure, the system is still attempting to allocate a control
wrench to the failed actuator. The vehicle instantly enters an extreme turn,
eventually loses control, and crashes.

Figure 6: Aircraft attitude and path for a motor failure in hover [6].

####  III-B2 Motor Failure During Cruise Flight

Motor failure during the cruise flight is shown in Fig. 7. The dynamical
control allocation allows the aircraft to quickly adapt to the failure and
resume normal flight. It is worth noting that the optimization solution
maintains the complete tilts of all the rotors (all the rotors are facing
forward). The vehicle can recover from the failure by altering the motor speed
and control surfaces. In fact, in high-speed cruise flight, relying more on
motor speed and control surfaces benefits the aircraft because an abrupt tilt
change could be detrimental to the structure. Compared to the case in which
the system is unaware of the failure, it is evident that the failure knowledge
enables the aircraft to maintain a straight route, whereas being oblivious to
the failure causes significant path deviation.

Figure 7: Actuator commands and flight path for a motor failure during cruise
[6].

####  III-B3 Other Failures

The list of failures tested with successful recovery is shown in Table. I.
Tilt angle failure in the hover phase is simulated by injecting a sudden tilt
servo lock at a fixed position (about 60∘ tilt). Even with a 60∘ tilt angle
change, the system can recover quickly after a big sudden disturbance by
dynamically reallocating the rest of the actuators.

The elevator failure during cruise flight is injected with the control surface
locked at 6∘. In this scenario, the rear two rotors tilt back, and the front
two tilt slightly forward over 90∘ to compensate for the continual pitch up
moment generated by the locked elevator while maintaining the force balanced.

Finally, the aileron failure is injected during the cruise flight. When the
aileron is locked at 15∘, the other healthy control surfaces adjust to
compensate for the lower roll control authority in order to sustain cruise
flight.

Ref. [6] provides a more detailed description of the failure recovery
experiments and the test results.

##  IV Conclusions and Future Work

This workshop provided an overview of our failure detection and recovery
progress. We described our method for real-time fault detection using a
recursive least square algorithm and presented the real-world tests
highlighting its accuracy of over 88 percent. Then, in the context of our
custom tiltrotor VTOL, we explained our optimization-based control allocation
approach for failure recovery. Finally, we showcased the extensive
experimental results that validate our failure recovery capability under
various actuator failures.

We suggest the following potential future work directions to move towards
safer UAM vehicles:

  * •

Extending the detection system by monitoring multiple input vs. multiple
output signals,

  * •

Using a nonlinear model for failure detection to provide more precise
predictions,

  * •

Performing real flight tests to validate the described failure recovery
approach further,

  * •

Developing a failure identification systems to identify the type of the
detected failure,

  * •

Integrating the developed detection and recovery systems with an
identification system to form a complete detection, identification, and
recovery pipeline.

## Acknowledgment

The authors would like to thank Dongwei Bai for his support and help with the
mechanical build of the vehicle.

## References

  * [1] A. Keipour, M. Mousaei, A. T. Ashley, and S. Scherer, “Integration of fully-actuated multirotors into real-world applications,” _arXiv preprint arXiv:2011.06666_ , 2020.
  * [2] A. Keipour, G. A. S. Pereira, R. Bonatti, R. Garg, P. Rastogi, G. Dubey, and S. Scherer, “Visual servoing approach for autonomous UAV landing on a moving vehicle,” _arXiv:2104.01272_ , 2021. [Online]. Available: https://arxiv.org/abs/2104.01272
  * [3] S. Schopferer, J. S. Lorenz, A. Keipour, and S. Scherer, “Path planning for unmanned fixed-wing aircraft in uncertain wind conditions using trochoids,” in _2018 International Conference on Unmanned Aircraft Systems (ICUAS)_ , June 2018, pp. 503–512.
  * [4] N. Hegde, V. George, C. Gurudas Nayak, and K. Kumar, “Transition flight modeling and robust control of a VTOL unmanned quad tilt-rotor aerial vehicle,” _Indonesian Journal of Electrical Engineering and Computer Science_ , vol. 18, no. 3, pp. 1252–1261, Jan. 2020\.
  * [5] J. A. Guerrero, R. Lozano, G. Romero, D. Lara-Alabazares, and K. C. Wong, “Robust control design based on sliding mode control for hover flight of a mini tail-sitter unmanned aerial vehicle,” in _2009 35th Annual Conference of IEEE Industrial Electronics_ , 2009, pp. 2342–2347.
  * [6] M. Mousaei, J. Geng, A. Keipour, D. Bai, and S. Scherer, “Design, modeling and control for a tilt-rotor vtol uav in the presence of actuator failure,” 2022\. [Online]. Available: https://arxiv.org/abs/2205.05533
  * [7] M. Kuric, B. Lacevic, N. Osmic, and A. Tahirovic, “Rls-based fault-tolerant tracking control of multirotor aerial vehicles,” in _2017 IEEE International Conference on Advanced Intelligent Mechatronics (AIM)_ , July 2017, pp. 1148–1153.
  * [8] X. Qi, D. Theilliol, J. Qi, Y. Zhang, and J. Han, “A literature review on fault diagnosis methods for manned and unmanned helicopters,” in _2013 International Conference on Unmanned Aircraft Systems (ICUAS)_ , May 2013, pp. 1114–1118.
  * [9] X. Qi, J. Qi, D. Theilliol, Y. Zhang, J. Han, D. Song, and C. Hua, “A review on fault diagnosis and fault tolerant control methods for single-rotor aerial vehicles,” _Journal of Intelligent & Robotic Systems_, vol. 73, no. 1, pp. 535–555, Jan 2014. [Online]. Available: https://doi.org/10.1007/s10846-013-9954-z
  * [10] A. Ansari and D. S. Bernstein, “Aircraft sensor fault detection using state and input estimation,” in _2016 American Control Conference (ACC)_ , July 2016, pp. 5951–5956.
  * [11] Z. Birnbaum, A. Dolgikh, V. Skormin, E. O’Brien, D. Muller, and C. Stracquodaine, “Unmanned aerial vehicle security using behavioral profiling,” in _2015 International Conference on Unmanned Aircraft Systems (ICUAS)_ , June 2015, pp. 1310–1319.
  * [12] Z. Birnbaum, A. Dolgikh, V. Skormin, E. O’Brien, and D. Muller, “Unmanned aerial vehicle security using recursive parameter estimation,” _Journal of Intelligent & Robotic Systems_, vol. 84, no. 1, pp. 107–120, Dec 2016. [Online]. Available: https://doi.org/10.1007/s10846-015-0284-1
  * [13] W. Han, Z. Wang, and Y. Shen, “Fault estimation for a quadrotor unmanned aerial vehicle by integrating the parity space approach with recursive least squares,” _Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering_ , vol. 232, no. 4, pp. 783–796, 2018. [Online]. Available: https://doi.org/10.1177/0954410017691794
  * [14] M. W. Mueller and R. D’Andrea, “Relaxed hover solutions for multicopters: Application to algorithmic redundancy and novel vehicles,” _The International Journal of Robotics Research_ , vol. 35, no. 8, pp. 873–889, 2016\.
  * [15] E. Baskaya, M. Hamandi, M. Bronz, and A. Franchi, “A novel robust hexarotor capable of static hovering in presence of propeller failure,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 4001–4008, 2021.
  * [16] T. Stastny and R. Siegwart, “Nonlinear model predictive guidance for fixed-wing UAVs using identified control augmented dynamics,” in _2018 International Conference on Unmanned Aircraft Systems (ICUAS)_. IEEE, 2018, pp. 432–442.
  * [17] R. C. Busan, P. C. Murphy, D. B. Hatke, and B. M. Simmons, “Wind tunnel testing techniques for a tandem tilt-wing, distributed electric propulsion VTOL aircraft,” in _AIAA SciTech 2021 Forum_ , 2021, p. 1189.
  * [18] X. Lyu, H. Gu, Y. Wang, Z. Li, S. Shen, and F. Zhang, “Design and implementation of a quadrotor tail-sitter VTOL UAV,” in _2017 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2017, pp. 3924–3930.
  * [19] A. Kamal and A. Ramirez-Serrano, “Conceptual design of a highly-maneuverable transitional VTOL UAV with new maneuver and control capabilities,” in _AIAA Scitech 2020 Forum_ , 2020, p. 1733.
  * [20] G. Ducard and M.-D. Hua, “Modeling of an unmanned hybrid aerial vehicle,” in _2014 IEEE Conference on Control Applications (CCA)_. IEEE, 2014, pp. 1011–1016.
  * [21] J. Zhang, P. Bhardwaj, S. A. Raab, S. Saboo, and F. Holzapfel, “Control allocation framework for a tilt-rotor vertical take-off and landing transition aircraft configuration,” in _2018 Applied Aerodynamics Conference_ , 2018, p. 3480.
  * [22] L. Bauersfeld, L. Spannagl, G. J. Ducard, and C. H. Onder, “Mpc flight control for a tilt-rotor VTOL aircraft,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 57, no. 4, pp. 2395–2409, 2021.
  * [23] S. Fuhrer, S. Verling, T. Stastny, and R. Siegwart, “Fault-tolerant flight control of a VTOL tailsitter UAV,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 4134–4140.
  * [24] A. Keipour, M. Mousaei, and S. Scherer, “Automatic real-time anomaly detection for autonomous aerial vehicles,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 5679–5685. [Online]. Available: https://ieeexplore.ieee.org/document/8794286
  * [25] ——, “ALFA: A dataset for UAV fault and anomaly detection,” _The International Journal of Robotics Research_ , vol. 40, no. 2-3, pp. 515–520, 2021\. [Online]. Available: https://journals.sagepub.com/doi/10.1177/0278364920966642
  * [26] M. H. Hayes, _Statistical digital signal processing and modeling_. John Wiley & Sons, 2009.
  * [27] E. Eweda and O. Macchi, “Convergence of the rls and lms adaptive filters,” _IEEE Transactions on Circuits and Systems_ , vol. 34, no. 7, pp. 799–803, July 1987.
  * [28] M. W. Ahmad, M. U. Akram, R. Ahmad, K. Hameed, and A. Hassan, “Intelligent framework for automated failure prediction, detection, and classification of mission critical autonomous flights,” _ISA Transactions_ , 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0019057822000209
  * [29] S. Bochkano. (1999) Alglib. Accessed: 2022-03-01. [Online]. Available: www.alglib.net