Applied mathematics

Nalini Joshi

# On a class of $q$-orthogonal polynomials and the $q$-Riemann Hilbert Problem

Nalini Joshi1 Tomas Lasic Latimer2 1School of Mathematics and Statistics F07,
University of Sydney, Sydney NSW 2006, Australia
2School of Mathematics and Statistics F07, University of Sydney, Sydney NSW
2006, Australia<EMAIL_ADDRESS>
###### Abstract

We give an explicit solution of a $q$-Riemann Hilbert problem which arises in
the theory of orthogonal polynomials, prove that it is unique, and deduce
several properties. In particular we describe the asymptotic behaviour of
zeroes in the limit as the degree of the polynomial approaches infinity.

###### keywords:

Orthogonal polynomials, Riemann Hilbert Problem, $q$-difference calculus

##  1 Introduction

In this paper, we consider a Riemann-Hilbert problem (RHP) associated with a
general class of $q$-orthogonal polynomials and solve it explicitly. The
result is used to deduce properties of such polynomials, in particular, ladder
operators, a Lax pair, a $q$-difference equation and, most importantly, the
asymptotic behaviour of their zeroes in the limit as the degree of the
polynomials approach infinity.

RHPs encapsulate many classical problems of physics and mathematics. Related
problems (under certain conditions) are also known as Wiener-Hopf problems.
Applications include boundary value problems in hydrodynamics, diffraction
theory and radiative transfer theory [noble1962methods]. More recently, RHPs
have been used to describe solutions of partial differential equations of
Korteweg-de Vries type [AC91, BDT88], exactly solvable quantum field and
statistical mechanics models [KBI93], topological and two-dimensional models
of quantum gravity [GM90], and are particularly noteworthy as a method for
describing asymptotic behaviours in the study of ensembles of random matrices
[D99, D00].

Orthogonal polynomials are objects of longstanding interest in mathematics and
physics. Classical orthogonality conditions involved continuous measures, with
weight functions $w(x)$ defined on continuous domains. The pioneering studies
of Lagrange, Laguerre, Hermite and others focused on smooth weight functions
$w(x)$ such that $w^{\prime}(x)/w(x)$ grows no faster than a linear polynomial
in $x$. This condition was extended in two cases by Shohat [shohat1939].
Applications in theoretical physics have led to many more extensions studied
in modern times [maroni1987prolegomenes, fokas1991discrete, Magnus1999,
AsscheBook]. These cases led to families of functions that are now known as
_semi-classical_ orthogonal polynomials.

In this paper, we consider orthogonality conditions defined through a
$q$-discrete measure, that is, for given $q\in\mathbb{R}$, $0<q<1$,
orthogonality measures defined on the multiplicative lattice,
$\\{q^{n}\\}_{n\in\mathbb{Z}}$. Given an appropriate weight function on such a
lattice, we consider orthogonality conditions with respect to the Jackson
integral. (We give the precise definitions in Section 1.2 below.) Such
polynomials, called the $q$-Hahn class [NIST:DLMF, Section 18.27], satisfy
relations analogous to those satisfied by semi-classical polynomials but with
the derivative operator replaced by the $q$-derivative $D_{q}$ (see Equation
(3)). Known properties include ladder operators and associated pairs of
compatible linear equations, called Lax pairs. We provide a new way to deduce
such relations from the corresponding RHP.

Not all properties of $q$-orthogonal polynomials are known. In this paper, we
provide a new result, Theorem 1.2, leading to the asymptotic approximation of
zeroes of $q$-orthogonal polynomials corresponding to a class of $q$-discrete
measures. This leads to a generalisation of an earlier result found for
polynomials orthogonal with respect to a positive discrete measure
[szeg1939orthogonal, Theorem 6.1].

###  1.1 Background

In 1991, Fokas, Its and Kitaev [fokas1991discrete] showed how to formulate and
solve RHPs for families of semi-classical orthogonal polynomials
$\bigl{\\{}n\in\mathbb{N}\bigm{|}P_{n}(x)\bigr{\\}}$ with exponential weight
functions $\exp(-V(x))$ on the real line, where $V$ is a polynomial of even
degree and the coefficient of the highest-degree term is positive. Based on
the RHP framework for orthogonal polynomials, Deift et al. [Deift1999strong]
developed a rigorous methodology to obtain the asymptotic behaviours of the
corresponding orthogonal polynomials in the limit as the degree $n\to+\infty$.
Their work was based on earlier advancements by Deift and Zhou on the steepest
descent method for oscillatory RHPs [deift1993steepest]. Since then RHPs have
been used to determine the asymptotic behaviour of a wide range of families of
orthogonal polynomials.

Fokas et al. [fokas1991discrete] also showed that the above orthogonal
polynomials are related to discrete Painlevé equations through the
coefficients of their 3-term recurrence relations. For a given measure
$d\mu(x)$, monic orthogonal polynomials $\bigl{\\{}P_{n}(x)\bigr{\\}}$ satisfy
an orthogonality relation

$\int P_{n}(x)P_{m}(x)d\mu(x)=\gamma_{n}\delta_{n,m},$

which defines $\gamma_{n}$. Their 3-term recurrence relation takes the form

$xP_{n}(x)=P_{n+1}(x)+b_{n}P_{n}(x)+a_{n}P_{n-1}(x)\,,$ (1)

where

$\displaystyle a_{n}$ $\displaystyle=$ $\displaystyle\gamma_{n}/\gamma_{n-1},$
$\displaystyle b_{n}$ $\displaystyle=$ $\displaystyle\int
xP_{n}(x)^{2}d\mu(x)/\gamma_{n}.$

For convenience, we take the sequence of polynomials to have initial values
$P_{-1}=0$ and $P_{0}=1$. When $V$ is quartic in $x$, actually
$V(z)=-x^{4}/4$, it had earlier been shown [shohat1939, freud1976coefficients]
that $a_{n}$ satisfies the discrete equation

$a_{n}(a_{n+1}+a_{n}+a_{n-1})=n,$ (2)

Fokas et al. called it a discrete Painlevé equation, dPI, and proved that it
has a continuum limit to the first Painlevé equation. Equation (2) is also
known as the string equation in physics due to its appearance in the Hermitian
random matrix model of quantum gravity [fokas1991discrete].

The connection between Equation (2) and dPI was established by considering the
Lax pair satisfied by polynomials orthogonal with respect to $e^{-x^{4}/4}dx$.
Semi-classical orthogonal polynomials satisfy a Lax pair given by a
differential equation in the independent variable $x$ and an iteration in the
degree $n$. Fokas et al. demonstrated a connection between the Lax pair, the
RHP formulation and dPI for this class of semi-classical orthogonal
polynomials [fokas1992isomonodromy].

It is now known that many families of orthogonal polynomials have recurrence
coefficients determined by additive-type discrete Painlevé equations
[Magnus1999, clarkson2018properties, clarkson2020generalised]. More recently,
it has been shown that the recurrence coefficients of $q$-orthogonal
polynomials satisfy multiplicative-type discrete Painlevé equations [Boelen],
where now the non-autonomous term in the equation is iterated on
multiplicative lattices. (For the terminology distinguishing types of discrete
Painlevé equations, we refer to Sakai [s:01].)

Baik et al. have described an interpolation problem [baik2007discrete,
Interpolation Problem 1.2], which can be considered as a discrete RHP for
polynomials orthogonal with respect to a discrete point-wise measure. They use
this setting to prove a number of asymptotic results, expanding on the
approach of Deift et al. Applications of such an approach include discrete
polynomials that are, for example, orthogonal on the integer lattice. We note
that its extension to the multiplicative or $q$-discrete case does not appear
to lead to the results we find in this paper.

The gap in our knowledge of properties of $q$-orthogonal polynomials raises a
number of questions relevant for physics, including quantum physics. Discrete
$q$-Hermite I polynomials describe the dynamics of discrete quantum harmonic
oscillators [atakishiyev2008discrete], little $q$-Jacobi polynomials describe
the unitary representations of the quantum group $SU_{q}(2)$
[masuda1991representations], and $q$-Racah polynomials are used to describe
quantum knot invariants [chan2018orthogonal]. In quantum communication,
perfect state transfer in linear spin chains is achieved when the spin chain
data is related to the Jacobi matrix of $q$-Krawtchouk polynomials
[jafarov2010quantum]. We note that $q$-orthogonal polynomials also appear in
other fields, for example the birth and death process [sasaki2009exactly].

This paper demonstrates the connection between $q$-orthogonal polynomials,
discrete $q$-Painlevé equations [Boelen] and $q$-RHPs. Birkhoff [Birkhoff1913]
and Carmichael [Carmichael] pioneered the study of $q$-RHPs, however their
work was initially restricted to to fuchsian systems. Later, Adams extended
their work beyond fuchsian systems [Adams]. More recently, the application of
Galois theory has been used to derive an analytic approach to singular regular
linear $q$-difference systems [sauloy2003galois]. Isomonodromy conditions have
led to RHPs corresponding to $q$-difference Painlevé equations
$q$-$P_{\rm{IV}}$ [joshi2021riemann] and $q$-$P_{\rm{VI}}$ [Yousuke2020] .

###  1.2 Notation

For completeness, we recall some well known definitions and notations from the
calculus of $q$-differences. These definitions can be found in [Ernst2012].
Throughout the paper we will assume $q\in\mathbb{R}$ and $0<q<1$.

######  Definition 1.1.

We define the $q$-derivative $D_{q}$, Pochhammer symbol $(a;q)_{\infty}$, and
Jackson integrals as follows.

  1. 1.

The $q$-derivative, $D_{q}$, of $f(x)$ is defined as

$D_{q}f(x)=\frac{f(x)-f(qx)}{x(1-q)}\,.$ (3)

Note that

$D_{q}x^{n}=\frac{1-q^{n}}{1-q}x^{n-1}\,.$

  2. 2.

The Pochhammer symbol $(a;q)_{\infty}$ is defined as

$(a;q)_{\infty}=\prod_{j=0}^{\infty}(1-aq^{j})\,.$

  3. 3.

There are two Jackson integrals in the literature. The Jackson integral of
$f(x)$ from 0 to 1 is defined as

$\int_{0}^{1}f(x)d_{q}x=(1-q)\sum_{k=0}^{\infty}f(q^{k})q^{k}\,.$ (4a)
Similarly, the Jackson integral of $f(x)$ from -1 to 1 is defined as
$\int_{-1}^{1}f(x)d_{q}x=(1-q)\sum_{k=0}^{\infty}(f(q^{k})+f(-q^{k}))q^{k}\,.$
(4b)

Note that the results in this paper are applicable to both types of Jackson
integrals. Typical examples of $q$-orthogonal polynomials with a Jackson
integral from -1 to 1 include: discrete $q$-Hermite I polynomials (with weight
$w(x)=(q^{2}x^{2};q^{2})_{\infty}$) [NIST:DLMF, Section 18.27] and $q$-Freud
polynomials $\left(w(x)=x^{\kappa}(q^{4}x^{4};q^{4})_{\infty}\right)$ [Boelen]
. Examples of $q$-orthogonal polynomials with a Jackson integral from 0 to 1
include: little $q$-Jacobi
$\left(w(x)=x^{\kappa}(qx;q)_{\infty}/(bqx;q)_{\infty}\right)$ and little
$q$-Laguerre polynomials $\left(w(x)=x^{\kappa}(qx;q)_{\infty}\right)$
[van2020zero] .

###  1.3 Main results

Our main results hold under certain properties defined below.

######  Definition 1.2.

A positively oriented Jordan curve $\Gamma$ in $\mathbb{C}$ with interior
$\mathcal{D}_{-}\subset\mathbb{C}$ and exterior
$\mathcal{D}_{+}\subset\mathbb{C}$ is called appropriate if

$\pm q^{m}\in\begin{cases}&\mathcal{D}_{-}\quad{\rm if}\,m\geq 0,\\\
&\mathcal{D}_{+}\quad{\rm if}\,m<0.\end{cases}$

We call $w$ admissible if it is a function analytic in $\mathcal{D}_{-}$ and
$w(z)\in\mathbb{R}$ for $z\in\mathbb{R}$. Furthermore, we call $w$ strictly
positive admissible if $w(z)>0$ at $z=\pm q^{m}$.

An example of an appropriate curve is drawn in Figure 1.

######  Remark 1.1.

In Definition 1.2 we describe the conditions needed for $q$-orthogonal
polynomials with Jackson integral from -1 to 1. For a Jackson integral from 0
to 1 the same definition applies with $\pm q^{k}\rightarrow q^{k}$.

######  Definition 1.3 ($q$-Riemann-Hilbert problem).

Let $\Gamma$ be an appropriate curve (see Definition 1.2) with interior
$\mathcal{D}_{-}$ and exterior $\mathcal{D}_{+}$. Let $w$ be an admissible
function in $\mathcal{D}_{-}$ and define

$h(s)=\sum_{k=-\infty}^{\infty}\frac{2sq^{k}}{s^{2}-q^{2k}}=\sum_{k=-\infty}^{\infty}\left(\frac{q^{k}}{s-q^{k}}+\frac{q^{k}}{s+q^{k}}\right).$

A $2\times 2$ complex matrix function $Y(z)$, $z\in\mathbb{C}$, is called a
_solution of the $q$-Riemann-Hilbert problem_ if it satisfies the following
conditions:

  1. (i)

$Y(z)$ is analytic on $\mathbb{C}\setminus\Gamma$.

  2. (ii)

$Y(z)$ has continuous boundary values $Y_{-}(s)$ and $Y_{+}(s)$ as $z$
approaches $s\in\Gamma$ from $\mathcal{D}_{-}$ and $\mathcal{D}_{+}$
respectively, where

$\displaystyle Y_{+}(s)=Y_{-}(s)\begin{pmatrix}1&w(s)h(s)\\\
0&1\end{pmatrix},\;s\in\Gamma.$ (5)

  3. (iii)

$Y(z)$ satisfies

$\displaystyle Y(z)\begin{pmatrix}z^{-n}&0\\\
0&z^{n}\end{pmatrix}=I+O\left(\frac{1}{|z|}\right),\text{ as }\
|z|\rightarrow\infty.$ (6)

######  Remark 1.2.

Note that the function

$h(z)=\sum_{k=-\infty}^{\infty}\frac{2zq^{k}}{z^{2}-q^{2k}}=\sum_{k=-\infty}^{\infty}\left(\frac{q^{k}}{z-q^{k}}+\frac{q^{k}}{z+q^{k}}\right),$

is meromorphic and is not continuous at $z=0$ which is an accumulation point
of the poles of $h(z)$. Furthermore, note that $h(qz)=h(z)$. Functions of this
nature play an important role in $q$-Riemann Hilbert theory where the elements
of the transition matrix ($(Y_{-})^{-1}Y_{+}$ in Equation (5)) can be related
to Weierstrass elliptic functions, see [Birkhoff1913, Section 19].

The main results of this paper are given by the following theorems.

######  Theorem 1.1 ($q$-RHP).

Let $P_{n}(z)$ be the monic $n^{th}$-degree orthogonal polynomial with respect
to the admissible measure $w(x)d_{q}x$, i.e.,

$\int^{1}_{-1}P_{n}P_{m}w(x)d_{q}x=\gamma_{n}\delta_{n,m}.$

Then $Y(z)$ defined by

$\displaystyle
Y(z)=\begin{bmatrix}P_{n}(z)&\oint_{\Gamma}\frac{P_{n}(s)w(s)h(s)}{2\pi
i(z-s)}ds\\\
\gamma_{n-1}^{-1}P_{n-1}(z)&\oint_{\Gamma}\frac{P_{n-1}(s)w(s)h(s)}{2\pi
i(z-s)\gamma_{n-1}}ds\end{bmatrix}$ (7)

is a unique solution of the Riemann-Hilbert problem given in Definition (1.3).

######  Theorem 1.2.

Let $P_{n}(x)$ be the monic $n^{\rm th}$-degree $q$-orthogonal polynomial with
respect to the admissible weight $w(x)$ on $[-1,0)\cup(0,1]$, i.e.,

$\int^{1}_{-1}P_{n}P_{m}w(x)d_{q}x=\gamma_{n}\delta_{n,m}.$

Denote the zeroes of $P_{n}(x)$ by $\\{x_{i,n}\\}_{i=1}^{n}$. Suppose that the
recurrence coefficients defined in Equation (1) decay sufficiently fast such
that

$\sum_{n=0}^{\infty}|a_{n}|+|b_{n}|<\infty.$

Then , for any $k\in\mathbb{N}$ there exists $1\leq i\leq n$ such that
$x_{i,n}\rightarrow q^{k}$ as $n\rightarrow\infty$.

######  Remark 1.3.

Theorem 1.2 holds for $q$-orthogonal polynomials which may have non-positive
admissible weights.

######  Remark 1.4.

Lemma 2.3 demonstrates that $q$-orthogonal polynomials with strictly positive
admissible weights satisfy Theorem 1.2. Furthermore, we will show in Lemma 2.1
that there exists an upper bound on the rate of convergence proportional to
$M_{1}z^{-2}+M_{2}z^{-1}$.

We use these results to prove a number of properties satisfied by
$q$-orthogonal polynomials. From Theorem 1.1, we deduce the ladder operators
as well as the Lax pair satisfied by $q$-orthogonal polynomials. In
particular, we show that the solution of the $q$-RHP solves a $q$-difference
equation in the independent variable $z$.

###  1.4 Outline

The paper is structured as follows. In Section 2 we prove Theorems 1.1 and
1.2. We begin by solving the $q$-RHP in Section 2.1. Using the $q$-RHP
formalism, in Sections 2.2 and 2.3 we deduce the Lax pair and ladder operators
respectively. In Section 2.4 we describe the asymptotic location of zeroes
using the $q$-RHP. We then conclude with Section 3 where we discuss future
work and summarise our results.

$\Im(z)$$\Re(z)$$-1$$1$$-q^{-1}$$q^{-1}$$-q$$\,q$$Y_{-}$$Y_{+}$$\Gamma$ Figure
1: Example of an appropriate curve $\Gamma$ defined by Definition 1.2.

##  2 Proofs of main results

In this section, we prove Theorems 1.1 and 1.2 and provide additional results
that lead to ladder operators and a Lax pair. As remarked earlier, we focus on
the case of the Jackson integral from -1 to 1 (see Equation (4)). The results
for the case of a Jackson integral from 0 to 1 follow using similar arguments.

###  2.1 Proof of Theorem 1.1

The proof follows along the same lines as in the case of the RHP for semi-
classical orthogonal polynomials given by Fokas et al. (see [Deift1999strong,
Section 3] for a detailed proof). When moving from the semi-classical case to
$q$-orthogonal polynomials a key step relies on the use of the Cauchy residue
theorem to express a contour integral as a discrete sum.

###### Proof.

We show that the second row of $Y$ must be given by Equation (7). A similar
argument can be carried out for the first row.

It follows from the asymptotic condition, Equation (6), that the $(1,1)$ entry
of $Y$ must have leading order $z^{n}$ as $z\rightarrow\infty$. As $Y_{(1,1)}$
is analytic and its jump condition, Equation (5), is given by the identity we
immediately conclude that $Y_{(1,1)}$ is a monic polynomial of degree $n$.
Similarly, it follows that $Y_{(2,1)}$ is a polynomial of degree at most
$n-1$. We denote $Y_{(2,1)}$ by $Q_{n-1}$.

Consider the bottom right entry of Equation (7). By the jump condition,
Equation (5), we have

$Y_{(2,2)}^{+}=Q_{n-1}(s)w(s)h(s)+Y_{(2,2)}^{-}\,.$ (8)

This scalar equation is solved by the Cauchy transform

$Y_{(2,2)}(z)=\frac{1}{2\pi
i}\oint_{\Gamma}\frac{Q_{n-1}(s)w(s)h(s)}{z-s}ds\,,$ (9)

which is analytic in $\mathbb{C}\setminus\Gamma$ and satisfies Equation (8).

The only step remaining is to prove the asymptotic condition, Equation (6),
for $Y_{(2,2)}$. Substituting our expression for $h(s)$ into Equation (9), we
find

$Y_{(2,2)}(z)=\frac{1}{2\pi
i}\oint_{\Gamma}\sum_{k=-\infty}^{\infty}\left(\frac{q^{k}}{s-q^{k}}\frac{Q_{n-1}(s)w(s)}{z-s}+\frac{q^{k}}{s+q^{k}}\frac{Q_{n-1}(s)w(s)}{z-s}\right)ds\,.$

which by Cauchy’s integral formula, for $z\in\text{ext}(\Gamma)$, becomes

$\displaystyle Y_{(2,2)}(z)$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{\infty}\left(q^{k}\frac{Q_{n-1}(q^{k})w(q^{k})}{z-q^{k}}+q^{k}\frac{Q_{n-1}(-q^{k})w(-q^{k})}{z+q^{k}}\right)\,,$
$\displaystyle=$
$\displaystyle\int^{1}_{-1}\frac{Q_{n-1}(x)w(x)}{z-x}d_{q}x\,,$

where the sum to infinity is well defined on $\Gamma$, as $h(s)$ converges as
$k\rightarrow\infty$, and the Jackson integral of an analytic function is well
defined. Note that only the points inside the jump curve $\Gamma$ contribute
to the integral.

Using the geometric series with remainder

$\frac{1}{z-x}=\sum^{l}_{k=0}\left(\frac{x^{k}}{z^{k+1}}\right)+\frac{x^{l+1}}{z^{l+1}(z-x)}\,,\quad\text{for}\,x\neq
z\,,$ (10)

we find

$\displaystyle Y_{(2,2)}(z)$ $\displaystyle=$
$\displaystyle\int^{1}_{-1}\frac{Q_{n-1}(x)w(x)x^{n}}{z^{n}(z-x)}d_{q}x$
$\displaystyle+\sum^{n-1}_{k=0}\frac{1}{z^{k+1}}\int^{1}_{-1}Q_{n-1}(x)w(x)x^{k}d_{q}x\,.$

Note that the asymptotic condition, Equation (6), holds when the last term on
the RHS is zero for $k=0,1,2,...,n-2$. This is true iff

$\int^{1}_{-1}Q_{n-1}(x)w(x)x^{k}d_{q}x=0\,,\quad\text{for}\,k\leq n-2\,,$

which is satisfied when $Q_{n-1}$ is an orthogonal polynomial of degree $n-1$
on the $q$-lattice with respect to the weight $w(x)$. We conclude the solution
of $Y_{(2,2)}(z)$ is given by

$Y_{(2,2)}(z)=\left\\{\begin{array}[]{lr}\frac{1}{\gamma_{n-1}}\int^{1}_{-1}\frac{P_{n-1}(x)w(x)}{z-x}d_{q}x-\frac{1}{\gamma_{n-1}}P_{n-1}(z)w(z)h(z),&\text{for
}z\in\text{int}(\Gamma),\\\
\frac{1}{\gamma_{n-1}}\int^{1}_{-1}\frac{P_{n-1}(x)w(x)}{z-x}d_{q}x,&\text{for
}z\in\text{ext}(\Gamma).\end{array}\right.$

After appropriate scaling, and repeating the same arguments for the first row,
it follows that Equation (7) is a solution of the $q$-RHP given by Definition
1.3.

Uniqueness of this solution follows from consideration of the determinant.
Observe that the jump matrix $J=Y_{-}^{-1}Y_{+}$ satisfies $\text{det}(J)=1$.
It immediately follows that $\text{det}(Y^{+})=\text{det}(Y^{-})$ on $\Gamma$.
Thus, $\text{det}(Y)$ is an entire function. By the asymptotic condition,
Equation (6), $\text{det}(Y)\rightarrow 1$, hence by Liouville’s theorem
$\text{det}(Y)=1$. As $\text{det}(Y)=1$ we can deduce $Y^{-1}$ exists and is
analytic in $\mathbb{C}/\Gamma$. Suppose that there exists a second solution
to the $q$-RHP, let us denote this solution by $\widehat{Y}$. If we define
$M=\widehat{Y}Y^{-1}$, it follows that the jump conditions effectively cancel
and $M_{+}=M_{-}$. Thus, $M$ is entire and $M\rightarrow I$ as
$z\rightarrow\infty$. Hence, by Liouville’s theorem $M=I$. We conclude that
$\widehat{Y}=Y$ and there is a single unique solution to the $q$-RHP. ∎

###  2.2 Lax Pair

In this section, we deduce a $q$-difference Lax pair for $q$-orthogonal
polynomials from the $q$-RHP. The Lax pair for a solution $Y_{n}$ to the
$q$-RHP can be written as:

$\displaystyle\Psi_{n+1}(z)$ $\displaystyle=$ $\displaystyle
C_{n}(z)\Psi_{n}(z)\,,$ (11) $\displaystyle\Psi_{n}(qz)$ $\displaystyle=$
$\displaystyle D_{n}(z)\Psi_{n}(z)\,,$ (12)

where,

$\displaystyle\Psi_{n}(z)=Y_{n}(z)\begin{bmatrix}w(z)&0\\\
0&1\end{bmatrix}\,.$

and, $C_{n}$ and $D_{n}$ both have polynomial entries. We first look at an
iteration in $n$. The proof mirrors that of the semi-classical case.

######  Corollary 2.1.

Let $Y_{n}(z)$ be a solution to the $q$-RHP defined in Theorem 1.1. Then
$Y_{n}$ satisfies Equation (11), where

$\displaystyle C_{n}(z)=\begin{bmatrix}z+c_{n,1}&c_{n,2}\\\
c_{n,3}&0\end{bmatrix}\,,$

and $c_{n,1}$, $c_{n,2}$ and $c_{n,3}$ are constants dependent on $n$.

###### Proof.

We observe that the jump condition for the $q$-RHP does not depend on $n$.
Thus $Y_{n+1}Y_{n}^{-1}$ is entire. By considering the asymptotic condition,
Equation (6), and using Liouville’s Theorem we find

$\displaystyle Y_{n+1}Y_{n}^{-1}=\begin{bmatrix}z+c_{n,1}&c_{n,2}\\\
c_{n,3}&0\end{bmatrix}\,,$

where $c_{n,1}$, $c_{n,2}$ and $c_{n,3}$ are constants which can be explicitly
derived using the recurrence relation Equation (1). ∎

We now show that if the weight $w(z)$ satisfies a $q$-difference equation of a
certain form then $Y_{n}$ satisfies Equation (12). The condition on $w(z)$ is
the $q$ analogue of the Pearson relation satisfied by semi-classical weights
[AsscheBook, Section 1.1.1.].

######  Corollary 2.2.

Let $Y_{n}(z)$ be a solution to the $q$-RHP defined in Definition 1.3 with
admissible weight $w(z)$ such that $w(\pm q^{-1})=0$. Furthermore, suppose
that $w(z)$ is admissible for the Jordan curve
$\widetilde{\Gamma}(z)=\Gamma(q^{-1}z)$ (i.e. it is the initial curve scaled
by $q^{-1}$). Define,

$\displaystyle\Psi_{n}(z)=Y_{n}(z)\begin{bmatrix}w(z)&0\\\
0&1\end{bmatrix}\,.$

If $w(qz)/w(z)$ is a polynomial, $\tau(z)$, of degree $m$. Then

$\displaystyle\Psi_{n}(qz)=D_{n}(z)\Psi_{n}(z)\,,$

where $D_{n}(z)$ has polynomial entries with maximum degree $m$.

###### Proof.

Define,

$\displaystyle D_{n}=\Psi_{n}(qz)\Psi_{n}^{-1}(z)\,.$

We note that there may be issues due to zeroes or poles of the weight function
$w$. However we find,

$\displaystyle D_{n}$ $\displaystyle=Y_{n}(qz)\begin{bmatrix}w(qz)/w(z)&0\\\
0&1\end{bmatrix}Y_{n}(z)^{-1}\,,$
$\displaystyle=Y_{n}(qz)\begin{bmatrix}\tau(z)&0\\\
0&1\end{bmatrix}Y_{n}(z)^{-1}\,.$ (13)

Therefore, $D_{n}$ is well defined by taking the limit near poles and zeroes
of $w(z)$. $\Psi(z)$ satisfies the jump condition,

$\displaystyle\lim_{z\rightarrow\widetilde{\Gamma}_{+}}\Psi(z)=\lim_{z\rightarrow\widetilde{\Gamma}_{-}}\Psi(z)\begin{bmatrix}1&h(s)\\\
0&1\end{bmatrix},\;s\in\widetilde{\Gamma}.$

Similarly $\Psi(qz)$ satisfies the jump condition,

$\displaystyle\lim_{z\rightarrow\widetilde{\Gamma}_{+}}\Psi_{n}(qz)=\lim_{z\rightarrow\widetilde{\Gamma}_{-}}\Psi_{n}(qz)\begin{bmatrix}1&h(s)\\\
0&1\end{bmatrix},\;s\in\widetilde{\Gamma},$

as $\Gamma(z)=\widetilde{\Gamma}(qz)$ and $h(qs)=h(s)$. Observing that the
jump conditions are equivalent, we can write the RHP for $D_{n}$ as:

  1. 1.

$D_{n}$ is analytic in $\mathbb{C}\setminus\widetilde{\Gamma}$.

  2. 2.

$D_{n}^{+}(s)=D_{n}^{-}(s)$ for $s\in\widetilde{\Gamma}$.

  3. 3.

$D_{n}$ is of degree $z^{m}$ as $z$ approaches infinity.

Thus $D_{n}$ has polynomial entries of degree at most $m$. By definition of
$D_{n}$ we have

$\displaystyle\Psi_{n}(qz)$ $\displaystyle=D_{n}(z)\Psi_{n}(z),$
$\displaystyle Y_{n}(qz)$
$\displaystyle=D_{n}(z)Y_{n}(z)\begin{bmatrix}\tau(z)^{-1}&0\\\
0&1\end{bmatrix}.$

Corollary 2.2 follows, as well as Equation (12). ∎

######  Remark 2.1.

Repeating the above arguments we find that Corollary 2.2 also applies to
weights where $w(q^{-1}z)/w(z)$ is a polynomial. An example is discrete
$q$-Hermite I polynomials whose weight satisfies $w(q^{-1}z)/w(z)=(1-z^{2})$.
Discrete $q$-Hermite I polynomials satisfy the $q$-difference equation

$\displaystyle\begin{bmatrix}P_{n}(qz)\\\
P_{n-1}(qz)\end{bmatrix}=\begin{bmatrix}1&z(q^{n}-1)\\\
zq^{2-n}&1-z^{2}q^{2-n}\end{bmatrix}\begin{bmatrix}P_{n}(z)\\\
P_{n-1}(z)\end{bmatrix}.$

###  2.3 Ladder operators

In this section we recover ladder operators for $q$-orthogonal polynomials
[chen2008ladder] from the $q$-RHP. The process is similar to that of semi-
classical orthogonal polynomials, the derivation of which can be found here
[AsscheBook, Theorem 4.1]. To avoid onerous calculations, we restrict
ourselves to determining the lowering ladder operator for $q$-orthogonal
polynomials.

######  Corollary 2.3.

Let $\\{P_{n}\\}_{n=0}^{\infty}$ be a sequence of monic $q$-orthogonal
polynomials which satisfy a $q$-RHP with admissible weight $w(z)$ such that
$w(\pm q^{-1})=0$. Then

$D_{q}P_{n}(z)=A_{n}(z)P_{n-1}(z)-B_{n}(z)P_{n}(z)\,,$

where

$\displaystyle A_{n}(z)$ $\displaystyle=$
$\displaystyle\frac{1}{\gamma_{n-1}}\int^{1}_{-1}\frac{u(y)}{qz-y}P_{n}(y)P_{n}(y/q)w(y)d_{q}y\,,$
$\displaystyle B_{n}(z)$ $\displaystyle=$
$\displaystyle\frac{1}{\gamma_{n-1}}\int^{1}_{-1}\frac{u(y)}{qz-y}P_{n}(y)P_{n-1}(y/q)w(y)d_{q}y\,,$

and

$u(z)=\frac{D_{q^{-1}}w(z)}{w(z)}.$

###### Proof.

Define $R=D_{q}(Y)Y^{-1}$. Then it follows that

$\displaystyle-\gamma_{n-1}R_{(1,1)}$
$\displaystyle=D_{q}(P_{n}(z))\int_{-1}^{1}\frac{P_{n-1}(y)w(y)}{y-z}d_{q}y$
(14) $\displaystyle\qquad-
P_{n-1}(z)D_{q}\left(\int_{-1}^{1}\frac{P_{n}(y)w(y)}{y-z}d_{q}y\right)\,.$

Using the orthogonality of $P_{n-1}$ we can apply the geometric series,
Equation (10), to write

$D_{q}(P_{n}(z))\int_{-1}^{1}\frac{P_{n-1}(y)w(y)}{y-z}d_{q}y=\int_{-1}^{1}\frac{D_{q}(P_{n}(y))P_{n-1}(y)w(y)}{y-z}d_{q}y\,.$
(15)

By substituting in the definition of the $q$-derivative into the RHS of
Equation (15) we find

$D_{q}(P_{n}(z))\int_{-1}^{1}\frac{P_{n-1}(y)w(y)}{y-z}d_{q}y=\int_{-1}^{1}\frac{(P_{n}(qy)-P_{n}(y))P_{n-1}(y)w(y)}{y(q-1)(y-z)}d_{q}y\,.$

Similarly, we can substitute in the definition of the $q$-derivative to write
the last term in Equation (14) as,

$P_{n-1}(z)\int_{-1}^{1}P_{n}(y)w(y)\left(\frac{1}{z(q-1)(y-qz)}-\frac{1}{z(q-1)(y-z)}\right)d_{q}y\\\
=P_{n-1}(z)\int_{-1}^{1}P_{n}(y)w(y)\left(\frac{q}{y(q-1)(y-qz)}-\frac{1}{y(q-1)(y-z)}\right)d_{q}y\,,$
(16)

where the equality can be verified by direct calculation. Using the
orthogonality of $P_{n}$ and the geometric series Equation (10) we can write
the RHS of Equation (16) as

$P_{n-1}(z)\int_{-1}^{1}P_{n}(y)w(y)\left(\frac{q}{y(q-1)(y-qz)}-\frac{1}{y(q-1)(y-z)}\right)d_{q}y\\\
=\int_{-1}^{1}P_{n}(y)w(y)\left(\frac{qP_{n-1}(y/q)}{y(q-1)(y-qz)}-\frac{P_{n-1}(y)}{y(q-1)(y-z)}\right)d_{q}y\,.$

Equation (14) can now be written as,

$-\gamma_{n-1}R_{1,1}=\int_{-1}^{1}\frac{P_{n}(qy)P_{n-1}(y)w(y)}{y(q-1)(y-z)}d_{q}y-q\int_{-1}^{1}\frac{P_{n}(y)P_{n-1}(y/q)w(y)}{y(q-1)(y-qz)}d_{q}y\,.$
(17)

From the definition of the Jackson integral (see Equation (4)) we can
immediately determine the identity,

$q\int_{-1}^{1}f(qx)d_{q}x=\int_{-1}^{1}f(x)d_{q}x-(f(1)+f(-1))\,.$

We can apply the above identity to Equation (17) to give us,

$\displaystyle-\gamma_{n-1}R_{1,1}$ $\displaystyle=$ $\displaystyle
q\int_{-1}^{1}\frac{P_{n}(y)P_{n-1}(y/q)w(y/q)}{y(q-1)(y-qz)}d_{q}y-q\int_{-1}^{1}\frac{P_{n}(y)P_{n-1}(y/q)w(y)}{y(q-1)(y-qz)}d_{q}y\,,$
$\displaystyle=$
$\displaystyle\int_{-1}^{1}\frac{P_{n}(y)P_{n-1}(y/q)Dq^{-1}(w(y))}{(qz-y)}d_{q}y.$

By definition, $D_{q}(Y)=RY$. Hence,
$D_{q}Y_{(1,1)}=R_{(1,1)}Y_{(1,1)}+R_{(1,2)}Y_{(1,2)}$. Thus, we have just
proven the form of $B_{n}$. The proof of $A_{n}$ follows a similar argument;
one finds $R_{(1,2)}$ using the same method as $R_{(1,1)}$ which gives the
desired result. ∎

###  2.4 Proof of Theorem 1.2

We know from Corollary 2.1 that the two columns of the solution $Y_{n}$ to the
$q$-RHP both satisfy the same three term recurrence relation, where $a_{n}$
and $b_{n}$ are given by Equation 1. We will now show that they converge to
analytic functions if the recurrence coefficients $a_{n}$ and $b_{n}$ decay
sufficiently fast.

######  Lemma 2.1.

Let $y_{n}(z)$ be determined by the recurrence relation

$y_{n+2}(z)-zy_{n+1}(z)+b_{n+1}y_{n+1}(z)+a_{n+1}y_{n}(z)=0\,,$

where $|z|>0$. If

$\sum_{n=0}^{\infty}|a_{n}|+|b_{n}|<\infty,$ (18)

then

$\lim_{n\to\infty}y_{n}(z)z^{-n}\rightarrow f(z),$ (19)

where convergence is uniform in any compact domain not containing $z=0$ or
poles of $y_{n}$.

###### Proof.

Substituting in $y_{n}=z^{n}u_{n}$ the recurrence relation becomes:

$u_{n+2}-u_{n+1}+\frac{b_{n+1}}{z}u_{n+1}+\frac{a_{n+1}}{z^{2}}u_{n}=0\,.$
(20)

Taking the norm we have

$|u_{n+2}|\leq\left(1+\left|\frac{a_{n+1}}{z^{2}}\right|+\left|\frac{b_{n+1}}{z}\right|\right)\text{max}(|u_{n+1}|,|u_{n}|)\,.$

Using the above relation we can write

$\text{max}(|u_{n+2}|,|u_{n+1}|)\leq\left(1+\left|\frac{a_{n+1}}{z^{2}}\right|+\left|\frac{b_{n+1}}{z}\right|\right)\text{max}(|u_{n+1}|,|u_{n}|)\,.$

Thus, it follows

$|u_{n}|\leq|u_{0}|\prod_{k=0}^{n}\left(1+\left|\frac{a_{k+1}}{z^{2}}\right|+\left|\frac{b_{k+1}}{z}\right|\right)\,,$

by applying a telescopic product. If $a_{n}$ and $b_{n}$ satisfy Equation (18)
then the RHS is bounded. Thus, $|u_{n}|$ is bounded in any compact domain not
containing $z=0$. Hence, by Equation (20) $u_{n}$ is a Cauchy sequence which
converges as $n$ goes to infinity. Moreover, $u_{n}$ converges uniformly in
any compact domain not containing $z=0$. ∎

We now prove Theorem 1.2. First, observe that the $q$-RHP jump, Equation (5),
can be written in one-dimension as

$P_{n}hw+\pi_{-}(P_{n})=\pi_{+}(P_{n})\,,$ (21)

where $P_{n}=Y^{\pm}_{(1,1)}$, $\pi_{-}=Y^{-}_{(1,2)}$ and
$\pi_{+}=Y^{+}_{(1,2)}$. Motivated by the form of Equation (19), we multiply
through by a common factor $z^{-n}$ to give

$z^{-n}P_{n}hw+z^{-n}\pi_{-}(P_{n})=z^{-n}\pi_{+}(P_{n})\,.$

Applying the results of Lemma 2.1, in the limit $n$ goes to infinity the above
becomes

$f^{(0)}(z)hw+f^{(1)}(z)=f^{(2)}(z)\,,$

where $f^{(0)}$ and $f^{(1)}$ are analytic everywhere except $z=0$ and
$f^{(2)}$ is analytic everywhere except $z=0$ and $z=\pm q^{k}$ for
$k\in\mathbb{Z}$. The analyticity of $f^{(i)}$ follows from Morera’s theorem
as convergence is uniform in any compact domain D not containing $0$ or the
poles of $Y_{(1,2)}$.

Furthermore, we can deduce that $f^{(2)}(z)$ is the zero function. We know
that $f^{(2)}(z)$ is analytic at infinity. We also know $z^{-n}\pi_{+}(P_{n})$
decays as $z^{-2n}\gamma_{n}^{-1}$ as $z\rightarrow\infty$. Hence,
$z^{m}f^{(2)}(z)$ goes to zero for any $m$. By Liouville’s theorem we conclude
$f^{(2)}(z)$ is the zero function. Thus,

$f^{(0)}(z)hw+f^{(1)}(z)=0\,,$

If $f^{(0)}(z)$ is non-zero at the poles of $h(z)$ then by the above equation
$f^{(1)}(z)$ must have a pole there. But $f^{(1)}(z)$ is analytic for $z\neq
0$ which is a contradiction. Hence, $f^{(0)}(z)$ must have zeroes at the poles
of $h(z)$, which are at $z=\pm q^{k}$ for $k\in\mathbb{Z}$.

By definition

$f^{(0)}(z)=\lim_{n\to\infty}z^{-n}P_{n}(z)=\lim_{n\to\infty}\prod_{i=1}^{n}\left(1-\frac{z_{i,n}}{z}\right)\,,$

where $z_{i,n}$ are the ordered zeroes of $P_{n}$. Thus, the zeroes of
$f^{(0)}(z)$ are the zeroes of $\lim_{n\to\infty}P_{n}(z)$. Which we have
shown to have zeros at $z=\pm q^{k}$ for $k\in\mathbb{Z}$.

We now show that Theorem 1.2 extends to $q$-orthogonal polynomials with
strictly positive admissible weights by showing that $a_{n}$ and $b_{n}$ decay
sufficiently fast for such polynomials. We start with a well known result on
the zeroes of discrete orthogonal polynomials [freud2014orthogonal, Chapter 1,
Theorem 2.4].

######  Lemma 2.2.

The zeroes of $q$-orthogonal polynomials, with strictly positive weight
$w(x)d_{q}x$, are bounded by the maximum and minimum of the $q$-lattice (i.e.
between 0 and 1, or, -1 and 1 depending on the Jackson integral chosen) and do
not appear more than once between lattice points.

###### Proof.

The proof follows by contradiction. Let $\\{x_{i,n}\\}_{i=1}^{n}$ denote the
ordered zeroes of an orthogonal polynomial, $P_{n}$, of degree $n$ (such that
$x_{n,n}<x_{n-1,n}<...<x_{1,n}$). Assume that for some $i_{ext}$,
$x_{i_{ext},n}$ lies outside the maximum and minimum of the $q$-lattice. It
follows that

$\int\left(\prod_{j=1,j\neq
i_{ext}}^{n}(x-x_{j,n})\right)\left(\prod_{i=1}^{n}(x-x_{i,n})\right)w(x)d_{q}x>0\,,$

where the polynomial on the left is degree $n-1$, while the polynomial on the
right is degree $n$. This contradicts the orthogonality condition. Thus, the
zeroes lie between the maximum and minimum of the $q$-lattice.

Now consider the second part of the lemma. Assume that there exists two
zeroes, $x_{i_{1},n}$ and $x_{i_{2},n}$ which lie between two consecutive
points (i.e. $q^{k},q^{k-1}$) of the Jackson integral. It follows that

$\int\left(\prod_{j=1,j\neq
i_{1},i_{2}}^{n}(x-x_{j,n})\right)\left(\prod_{i=1}^{n}(x-x_{i,n})\right)w(x)d_{q}x>0\,.$

This is again a contradiction to orthogonality. ∎

######  Remark 2.2.

Note that the roots of $q$-orthogonal polynomials are real. This well known
observation follows from the fact that $P_{n}$ must have real coefficients
(from the recurrence relation Equation (1)), combined with Lemma 2.2. (To see
this we use the same arguments as in the proof of Lemma 2.2, omitting any
complex conjugate roots if required.) It also follows that the roots must be
simple (again by using the same arguments in the proof of Lemma 2.2 with the
omission of any multiple roots if required).

We now use Lemma 2.2 to prove that the sum of the recurrence coefficients in
Equation (1) is bounded.

######  Lemma 2.3.

Given a sequence of $q$-orthogonal polynomials on $(0,1]$, with a strictly
positive admissible weight, the recurrence coefficients $a_{n}$ and $b_{n}$
defined in Equation (1) satisfy

$\displaystyle\sum_{n=0}^{\infty}b_{n}$ $\displaystyle\leq$
$\displaystyle\frac{1}{1-q}<\infty,$ (22)
$\displaystyle\sum_{n=0}^{\infty}a_{n}$ $\displaystyle\leq$
$\displaystyle\frac{2}{(1-q)^{2}}<\infty.$ (23)

###### Proof.

Let

$P_{n}(z)=z^{n}+\alpha_{n}z^{n-1}+\beta_{n}z^{n-2}+...\,.$

Applying Equation (1) we find that

$\displaystyle\alpha_{n}$ $\displaystyle=$ $\displaystyle\alpha_{n+1}+b_{n},$
(24) $\displaystyle\beta_{n}$ $\displaystyle=$
$\displaystyle\beta_{n+1}+b_{n}\alpha_{n}+a_{n}.$ (25)

By definition $a_{n}$ and $b_{n}$ are both positive (see Equation (1)). We
know that $-\alpha_{n}$ is equal to the sum of the roots of $P_{n}$.
Furthermore, by Lemma 2.2, $|x_{k,n}|$ is smaller then $|q^{k-1}|$. Thus,
$\alpha_{n}$ is bounded by

$0<-\alpha_{n}<\frac{1}{1-q}.$

Hence taking the telescopic sum of Equation (24) gives

$\alpha_{n+1}=-\sum_{i=1}^{n}b_{i},$

which implies Equation (22).

Similar arguments show that Equation (25) implies Equation (23). ∎

######  Remark 2.3.

Lemma 2.3 also applies to $q$-orthogonal polynomials on $[-1,0)\cup(0,1]$,
with a strictly positive, symmetric, admissible weight. It follows that we can
estimate an upper bound on the rate of convergence in Lemma 2.1 for
$q$-orthogonal polynomials with strictly positive admissible weights;
$|u_{n}(z)-f(z)|\propto
q^{-n}\left(2\left((1-q)z\right)^{-2}+\left((1-q)z\right)^{-1}\right)$.

By applying Lemmas 2.2 and 2.3 we can deduce that Theorem 1.2 holds for
$q$-orthogonal polynomials on $(0,1]$ with strictly positive admissible
weights and $q$-orthogonal polynomials on $(-1,0]\cup(0,1]$ with strictly
positive, symmetric, admissible weights.

We prove a resulting corollary which states that although the zeroes of
$P_{n}$ approach $q^{k}$ as $n$ approaches infinity, they can never actually
equal $q^{k}$ for any sufficiently large $n$. Note that this appears to
contradict Theorem 6.1.1. in [szeg1939orthogonal], possibly due to
typographical errors in the published version.

######  Corollary 2.4.

Let $\\{P_{n}\\}_{n=0}^{\infty}$ be a sequence of $q$-orthogonal polynomials
with strictly positive, symmetric, admissible weight on the $q$-lattice
$[-1,0)\cup(0,1]$ which satisfy Theorem 1.2. Consider an arbitrary point on
the $q$ lattice, $q^{k}$, $k\in\mathbb{N}$. Then there exists an $N_{k}$,
which is a function of $k\in\mathbb{N}$, such that the zeroes of $P_{n}$ for
$n>N_{k}$ cannot equal $q^{k}$.

###### Proof.

Let $P_{n}(z)$ be a monic polynomial which satisfies a $q$-RHP on
$[-1,0)\cup(0,1]$ with strictly positive, symmetric, admissible weight. Assume
that for a given $k$, $P_{n}(q^{k})=0$. As $P_{n}$ has a zero at $q^{k}$ it is
also the $n$th degree orthogonal polynomial for the weight
$w(x)d_{q}x\setminus\pm q^{k}$ i.e. the Jackson integral minus the location
$\pm q^{k}$. Applying Remark 2.3 we know that there exists and $N_{k}$ such
that for $n>N_{k}$

$\left|z^{-n}P_{n}-\prod_{j=0,j\neq
k}^{\infty}(1-z^{-2}q^{2j})\right|<\left|\prod_{j=0,j\neq
k}^{\infty}(1-z^{-2}q^{2j})\right|.$

Thus, if $n>N_{k}$ we arrive at a contradiction. ∎

##  3 Conclusion

In this paper, we provided a framework for studying properties of
$q$-orthogonal polynomials as solutions of $q$-RHPs. This framework enabled us
to deduce certain known properties as well as new results for $q$-orthogonal
polynomials. In particular, we deduced previously known ladder operators and
provided a Lax pair. Furthermore, in Theorem 1.2 we described the asymptotic
location of the zeroes of $q$-orthogonal polynomials. Although, this behaviour
has been shown earlier for positive discrete weights [szeg1939orthogonal,
Theorem 6.1], we prove it under more relaxed constraints in the $q$-discrete
setting.

It is interesting to note that one can determine the asymptotic location of
zeroes of $q$-orthogonal polynomials using the discrete nature of the weight
function for $q$-orthogonal polynomials, which manifests itself as a lack of
analyticity in the RHP jump function. A similar result does not hold using the
RHP for semi-classical orthogonal polynomials, particularly if the
orthogonality weight is non-positive. However, the RHP for both semi-classical
and $q$-orthogonal polynomials can be used to prove the form of the ladder
operators and Lax pairs they respectively satisfy.

An interesting avenue for future exploration of the $q$-RHP is to determine a
form of strong asymptotics in the same vein as the previous work of Deift et
al. [Deift1999strong] for semi-classical orthogonal polynomials. We note that
there has been some work done in this area concerning discrete polynomials
[baik2007discrete]. However, these results do not seem very applicable to the
$q$-orthogonal polynomials discussed in this paper. In particular, they do not
accurately describe the exponentially vanishing behaviour of the recurrence
coefficients. It is hoped that the $q$-RHP representation will provide a good
framework to explore the strong asymptotics of $q$-orthogonal polynomials.

There are no ethics issues.

This article has no additional data.

All the authors have contributed equally to all sections. Nalini Joshi’s ORCID
ID is 0000-0001-7504-4444. Tomas Lasic Latimer’s ORCID ID is
0000-0001-6859-7788

There are no competing interests.

Nalini Joshi’s research was supported by an Australian Research Council
Discovery Projects #DP200100210 and #DP210100129. Tomas Lasic Latimer’s
research was supported the Australian Government Research Training Program and
by the University of Sydney Postgraduate Research Supplementary Scholarship in
Integrable Systems.

The ideas presented here represent our own ideas together with our
understanding of those of other researchers.

## References


# Minorities in networks and algorithms

Fariba Karimi1∗, Marcos Oliveira2, Markus Strohmaier4,3,1
1Complexity Science Hub Vienna, Vienna, Austria
2Computer Science, University of Exeter, Exeter, United Kingdom
3Computational Social Science, GESIS–Leibniz Institute for the Social
Sciences, Cologne, Germany
4Business School, University of Mannheim, Mannheim, Germany
∗Corresponding author; E-mail<EMAIL_ADDRESS>
###### Abstract

In this chapter, we provide an overview of recent advances in data-driven and
theory-informed complex models of social networks and their potential in
understanding societal inequalities and marginalization. We focus on
inequalities arising from networks and network-based algorithms and how they
affect minorities. In particular, we examine how homophily and mixing biases
shape large and small social networks, influence perception of minorities, and
affect collaboration patterns. We also discuss dynamical processes on and of
networks and the formation of norms and health inequalities. Additionally, we
argue that network modeling is paramount for unveiling the effect of ranking
and social recommendation algorithms on the visibility of minorities. Finally,
we highlight the key challenges and future opportunities in this emerging
research topic.

## Introduction

Social inequalities—structured and recurrent patterns of unequal distribution
of wealth, opportunities, and rewards for different social positions or
statuses within a group or society—are on the rise, and current solutions to
these problems are insufficient or failing [1]. For example, during the
COVID-19 pandemic, we witness growing inequality in the mortality rate of
minorities and marginalized groups, which is due to existing structural
inequalities [2]. Structural Inequality is one of the complex manifestations
of social inequalities in which institutions, policies, and societies create
privilege systems resulting from a confluence of unequal relations in roles,
functions, decisions, rights, and opportunities [3], which ultimately produces
structural barriers to equality and inclusiveness.

### Minorities, marginalization, and inequalities.

Before discussing this chapter’s central topic, it is essential to define some
of the fundamental sociological concepts we use throughout the text. Here, we
use the notion of minority to refer to a group of people who share a similar
attribute (e.g., gender, race, ethnicity) and whose size is smaller than other
groups’ size. This imbalance in population size often results in inequalities
and marginalization. Marginalization is defined as “to relegate to an
unimportant or powerless position within a society or group”. Social
inequalities refer to structured and recurrent patterns of unequal
distribution of wealth, opportunities, and rewards for different social
positions or statuses within a group or society [1]. In political philosophy
and economics, scholars distinguish two types of equality: equality of
opportunity and equality of outcome [4]. While we don’t aim to discuss these
concepts in depth, it is worth noting that in many cases, the inequalities
that emerge from networks affect directly the former.

### Emergence of inequalities and biases as a complex interacting system.

Social networks are complex, time-dependent, and path-dependent systems
comprising heterogeneous individuals interacting in evolving adaptive multi-
layer networks of friendship, collaboration, communications, and trade, among
other social interactions [5, 6]. Network models, despite being often
stylized, have provided valuable insights into the emergence of macro-level
phenomena such as riots [7], political movements [8], diffusion of innovations
[9], and predicting and preventing disease outbreaks [10, 11]. Social
mechanisms can be inserted in network models (i.e., mechanistic models) in
order to test hypothetical scenarios, evaluate the consistency of descriptive
theories, explore emergent phenomena, and predict outcomes [12, 13].

Much of the developments in computational models of complex networks have
primarily focused on universality, phase transitions, and the emergence of
scaling [6]. Such a focus has often overlooked that social systems comprise
individuals and groups with fundamentally heterogeneous attributes and
historical precedent. These heterogeneities at the individual level and path
dependencies can significantly impact how people interact and organize their
social relationships.

Social distinction and social differentiation can cause stratification in a
complex society, where gender, race, and ethnicity are among the most
pervasive characteristics (or attributes) that people use to make distinctions
in terms of roles and expectations [14, 15]. Additionally, individual-level
intentions and cognitive biases toward group members have been established and
discussed in social psychology literature extensively [16, 17]. However, the
networks’ impact on population-level bias and inequality remains relatively
unexplored in the literature. Despite this research deficit, previous works
have already established the plausibility of network effects on inequality by
examining network influence, homophily, and diffusion processes, providing
insights for computational modelling and empirical data-driven research [18,
19].

### Human biases and their manifestations in networks.

There are various ways human biases manifest and exacerbate in social
networks. Examples of those biases include social bias, population bias, self-
selection bias, and historical bias [20]. Biases in networks can lead to
unfairness in society and algorithms. For example, historical bias can lead to
the formation of an old boys club in scientific collaboration or for search
engines to show predominantly male CEOs [21]. Social bias, also known as
attributional error [16], is also closely related to the network effect where
other people’s actions in our network proximity affect our judgment and
choices. This phenomenon can directly affect whom we decide to create a link
with or which information to share with others. Popularity bias describes the
human tendency to be attracted to popular items or individuals. For example,
in search engines, the top-ranked results attract disproportionately more
clicks/links than others, leading to cumulative advantages [22]. Many of these
biases may have been driven by some biological and evolutionary processes that
are essential for survival [23]. While we encourage the reader to reflect on
those fundamental processes, any further elaboration is beyond the scope of
this chapter.

Figure 1 illustrates the Network Inequality framework. Social mechanisms in
micro-level results in macro-level emergence of topological and structural
conditions that affect dynamical processes and network-based algorithms.

We have organised the rest of this chapter in the following way. First, we
discuss computational models to address societal issues such as visibility of
minorities in large-scale social networks, minorities in small-scale face-to-
face interactions, perception bias towards minorities, and minorities in
collaborative environments. Second, we discuss visibility of minorities in
network-based algorithms, the interplay between recommender systems and the
network evolution, and in network sampling. Last, we discuss dynamics ’on’
networks such as spreading of norms and diseases, and dynamics ’of’ networks
such as changes in social interactions over time and how these dynamics affect
minorities. We close the paper by discussing key challenges and future
directions.

Figure 1: Illustration of Network Inequality concept. Social mechanisms in
micro-level result in macro-level emergence of topological and structural
conditions that affect dynamics on and of networks. The social networks are
fed into algorithms and the inequality may be exacerbated by algorithms. The
social networks are dynamic and change over time.

## Minorities in social networks

Homophily—the idea that similarity breeds connection—is a fundamental
mechanism of social tie formation [24]. Because individuals may identify
themselves with groups based on categories such as gender, race, and ethnicity
[25], homophily can drive the formation of mixing biases among those
categories, resulting in groups of different sizes, which might affect
individuals’ visibility.

Visibility in networks is often defined as the attention given to an
individual or a group compared to what we would expect from their prevalence
or intrinsic value. Though this definition is somewhat limited (e.g., the
assumption of group prevalence or intrinsic values is debatable), we can use
mechanistic models to evaluate and experiment with such contested definitions
systematically as a form of thought experiments (Gedankenexperiment).

Distorting the visibility of minorities via societal processes or algorithms
can have severe consequences for society. This problem, known as invisibility
syndrome [26], refers to situations in which minorities feel ignored and
overlooked by the wider public. For example, social and academic invisibility
prevents minorities from integrating into social networks and cultivating
their potentials. The invisibility syndrome can have consequences for
minorities. It can lead to minorities becoming silent, also known as the
spiral of silence [27], leaving the community (e.g., dropping out from
academia [28, 29]), or in the extreme case, becoming violent towards the
majority group because they do not have to conform to the same norm of the
majority [30].

### Mixing biases in large-scale networks.

Now let us examine the visibility of minorities in large-scale social
networks. We specifically focus on the effect of group imbalance and mixing
biases (homophily) on the network visibility of minorities and majorities. To
do so, we developed a simple preferential attachment network model with
homophily (BA-Homophily model), including an analytical formulation [31]. This
model allows us to gain an in-depth insight into how nodes’ degrees relate to
group size and homophily. We use average group degree as a proxy for
visibility, and find that homophily can penalize minorities by restricting
their ability to connect to the bigger group. We found an unexpected tipping
point, a non-sweet spot for minorities, in the mid-homophily range where they
can be penalized the most. In the intermediate range of homophily, not only
majority nodes prefer to attach to other majorities due to homophily, but also
newly-arrived minority nodes prefer the majority because of their preferential
attachment. As homophily increases, this dynamic changes, and minorities
manage to recover their degree. In addition, by running a simple Susceptible-
Informed diffusion dynamic, we observe that although strong homophilic
tendencies help minorities recover their degree of connectivity, it will
prevent them from accessing information from the majority group and vice
versa. This insight allows us to quantitatively measure the advantages and
disadvantages of mixing biases between the groups. Finally, we validated our
model by analyzing different empirical networks and comparing them to the
synthetic models.

### Mixing biases in small-scale networks.

Beyond large-scale social networks that are useful to model virtual and
cumulative interactions, in reality, we build meaningful and long-lasting
connections via face-to-face interactions [32]. This essential human behavior
is a primary form of social communication, inherited from our ancestors [33],
and it is a fundamental mechanism for the transmission and affirmation of
culture [34].

Face-to-face interaction is particularly unique due to its spatial-temporal
constraint: individuals must be at the same place and at the same time to
interact. This constraint is critical to interaction opportunities, especially
in confined situations, such as conferences and workplaces. For example, we
only have a limited number of opportunities for interaction at conferences
(e.g., coffee breaks). We found that this constraint, together with group
mixing and size imbalance, can produce disparities in the visibility of social
groups [35]. Once again, these disparities translate into members of specific
social groups having fewer social ties than the average. We disentangle this
phenomenon using a mechanistic model that embeds the properties of face-to-
face interactions.

Due to the constraints in face-to-face interactions, when an individual uses
an opportunity to interact with someone, fewer opportunities remain for
interacting with other individuals. Depending on how groups mix, this
limitation in opportunities leads to inequality. When a majority member
interacts with someone from the majority, fewer opportunities remain for this
individual to interact with minorities, decreasing minority connectivity. This
inequality emerges irrespective of individuals’ abilities. Even when minority
members have a high intrinsic fitness (i.e., attractiveness), they can be at a
disadvantage because group mixing affects how individuals identify other
individuals’ particularities.

This systemic inequality is challenging to mitigate without the help of the
largest group. Our model indicates that majority group mixing explains most of
the variance in connectivity inequality. The minority group can only slightly
reduce inequality, and a successful strategy for this reduction depends on
group size. Our model predicts that, depending on the minority group size,
minority members need to avoid connecting with the minority group to increase
their connectivity. We found a tipping point that determines how minorities
should strategize their social interactions. When the minority size is below a
critical point, homophilic minority interaction decreases minority
connectivity. Conversely, when the minority group size is sufficiently large,
homophilic minority interaction helps in increasing minority connectivity.

### Minorities and perception biases.

The way people perceive the prevalence of others can influence their personal
beliefs and behavior and shapes their collective dynamics. Many studies have
documented biases in these social perceptions, including both overestimation
and underestimation of the size of minority groups. We investigate whether
such seemingly contradictory biases, namely false consensus (overestimation of
the frequency of one’s attributes) and false uniqueness (underestimating the
frequency of our view), can be explained merely by the structure of the social
networks [36]. In other words, how does our estimate about minorities relates
to our social networks?

To address this question, first, we turned to examine this effect through a
series of cross-cultural surveys. We asked questions about different societal
attributes for which we knew the actual frequencies in the general population
from existing national surveys in these countries. Participants answered three
groups of questions. First, they answered questions about themselves (e.g.,
whether they smoke). Second, they estimated the frequency of people with each
attribute in their networks (e.g., what fraction of your friends are
smokers?). Third, we asked the participants to estimate the frequency of
people with a specific attribute in the general population of their country.
These questions allow us to estimate the homophily in personal networks and
the perception of minorities.

Next, we turned to our network model with homophily and examined whether we
can explain the empirical observation in synthetic and real-world networks.
Our results showed that when homophily is high, both minority and majority
groups tend to overestimate their own size. In contrast, when homophily is
low, people tend to overestimate the size of the minority group. More
importantly, if we assume that people often aggregate their own perception
with the perception of their neighbors (i.e., DeGroot weighted belief
formalization), in homophilic networks, individuals cannot improve their
perception because their peers do not add sufficient new information that
would increase the accuracy of their estimates. However, in heterophilic
networks, individuals benefit from considering their neighbors’ more diverse
perceptions.

### Minorities and power.

Though we often refer to minorities as under-represented groups who are
disadvantaged due to the network processes, it is worth noting that some
minorities, despite being smaller in size, disproportionately occupy powerful
positions in networks. To understand how such scenarios happen, let us return
to the scale-free homophilic networks that we described earlier in this
chapter [31]. In this model, mixing likelihood ranges from $0$ to $1$. The
values below $0.5$ are heterophilic scenarios in which the probability of in-
group ties is below 50% resulting in minorities attracting the majorities. In
such cases, because the majority group is larger and prefers to connect with
the minority group, the minority members benefit from growing their number of
connections—while the competition for receiving new connections due to the
preferential attachment is limited due to their small size. The combination of
heterophilic tendencies and preferential attachment results in inequality in
the distribution of degree ranking in networks, as individuals in top ranks,
disproportionately enjoy advantages as they stabilize their position in the
rank and give few opportunities to others to catch up [37]. This effect,
minorities in central positions in the network is related to the majority
illusion [38] idea (a small powerful minority is percieved as the majority in
the network). This is an important aspect, in particular, with respect to
online ranking algorithms such as PageRank [39, 40]. While the majority of the
current works are focusing on the disadvantages that the algorithms create, it
is crucial to reflect on the disparate gap that they can create for the
individuals on the top of the ranks.

### Collaboration, success and dropouts of minorities.

One important implication of network inequality is in academia. Science is
largely a social process in which ideas spread between scholars, role models
influence minds, and young scholars find their mentors and scientific
interests through this process. In academia, collaboration patterns have a
crucial impact on a scholar’s opportunities to establish an academic
reputation and success [41]. The diversity of collaboration [42], the duration
of collaboration [43] and the seniority and prominence of the collaborators
[44] are among those patterns that can impact the academic career of young
scholars. Structural and historical inequalities combined with the social
process of imitation and adoption can create a condition in which minorities
either do not enter certain areas of science or tend to have higher dropouts
[45]. Our analysis of the career age and collaboration patterns of more than
one million computer scientists for more than four decades shows that women
have higher dropouts throughout all career ages, and establish more links with
other female researchers [29], and since they are a minority, this phenomenon
can potentially impact their visibility and ability to access novel ideas or
information.

## Minorities and algorithms

Artificial Intelligence and online algorithms have become cornerstones of many
decision-making processes in industry, academia, and the public sector, from
the diagnosis of diseases and the forecast of recidivism risk in criminal
trials to the recommendation of whom to hire and whom to follow on social
media [46]. At the same time, these algorithms have recently come under public
scrutiny because the relatively high levels of accuracy often come at the cost
of biases, such as misclassifying under-represented groups or reinforcing pre-
existing inequalities. For instance, they may contribute to systematic
discrimination against women in the job market, or against Hispanic and Black
people in justice systems [47]. While the computer science community has
tackled these issues by calibrating their models according to certain
definitions of fairness [48, 49], understanding the influence of social
network structure on algorithmic outcomes requires more attention and future
research.

Machine learning and AI systems often process existing input data in order to
train their models for prediction tasks. Mechanistic network models from the
domain of complexity science can enable researchers to consider various
hypothetical scenarios that can occur in societies but are not available in
input training data. This allows to evaluate the robustness of algorithms with
regard to different aspects concerning minorities, for example fairness or
discrimination. In the following, we illustrate a few examples in which
network models are used to evaluate the fairness of algorithms in the presence
of minorities.

### Minorities and sampling.

When collecting and analysing social network data, online or offline, we are
inherently conducting some form of sampling. For example, surveys or selecting
a school to collect information about the students and their contacts are a
form of random node sampling. In contrast collecting data based on phone calls
is a form of random edge sampling. In social sciences, certain minorities are
denoted as hard-to-reach groups (e.g. homeless people or illegal immigrants)
in which snowball sampling seems to be a promising method to access those
populations. Using the network model with adjustable homophily and minority
size described earlier, we evaluated different sampling techniques with
respect to conserving the topological position of nodes (degree centrality)
and the visibility of groups in top ranks [50]. Our results show that
different network sampling techniques are highly sensitive with regard to
capturing the expected centrality of nodes, and that their accuracy depends on
relative group size differences and on the level of homophily that can be
observed in the network. In other words, uninformed sampling from social
networks with attributes can significantly impair the ability of researchers
to draw valid conclusions about the centrality of nodes in social networks. In
a follow-up work, we examined how network sampling strategy and sample size
affect accuracy of relational inference in networks [51]. Relational inference
leverages relationships between entities and links in a network to infer
information about the network from a small sample. We find that in
heterophilic networks, we can obtain good accuracy when only small samples of
the network are initially labeled, regardless of the sampling strategy.
Surprisingly, this is not the case for homophilic networks, and sampling
strategies that work well in heterophilic networks lead to large inference
errors. In summary this means that social network structures that are driven
by homophily can induce biases on sampling and inference procedures.

### Minorities in network-based ranking and recommender systems.

Many ranking and recommender systems in online algorithms are, based on, and
sensitive to, the directionality of the links in the network. For example,
PageRank centrality deployed by Google, or Who-to-Follow (WTF) link
recommendation systems deployed in Twitter are both based on directed
networks. In order to investigate the effect of directionality of the links
and homophily on the ranking of minorities, we proposed a directed network
model with preferential attachment and homophily and explored the influence of
network structure on the rank distributions of these algorithms [40]. Our
findings, align with other similar works [52], suggest that these two
algorithms can reduce, replicate and amplify the representation of minorities
in top ranks when majorities are homophilic, neutral and heterophilic,
respectively. Moreover, when this representation is reduced, minorities may
improve their visibility in the rank by connecting strategically in the
network, by e.g., increasing their out-degree or homophily when majorities are
also homophilic. Investigating such scenarios in directed networks are
promising avenues that can inform how to design algorithms that achieve
fairness.

As a result of recommender algorithms, users may accept new social links, and
hence, social network structures can change over time. Based on a series of
synthetic network experiments, we showed that not only such algorithms tend to
increase the clustering and cohesion within groups, they are also prone to
favor nodes with high in-degree. This bias towards popular nodes may reinforce
pre-existing social biases and contribute to cumulative advantages [53].

## Minorities and dynamics on and of networks

Social interactions are time-dependent, dynamic, and they change as the social
system evolves. These time dependencies can impact communities in networks
[54], diffusion of information or norms, and causality direction [55]. Non-
Markovian properties of temporal networks constitute an essential dimension of
complexity in time-varying complex systems, and they can lead to different
types of diffusion outcomes [56]. For example, organizational burstiness
(coordinated burst in social interactions such as a coffee break at a
conference) may speed up the complex contagion by activating many social
interactions in a short duration of time [57, 58].

When certain disadvantaged groups arrive in a social system with delay or at a
slower rate, due to historical discrimination or societal inequalities (e.g.,
women in universities [59], or African-Americans in the blue-collar workforce
[60]), the diffusion speed and hierarchy climbing for such groups is slower
compared to more established groups. This late-arrival mechanism affects the
age of the ego-network of minorities, the cumulative advantages, and their
network position. By understanding this dynamic, we recently showed that the
gender disparity in citation patterns of female-led papers and male-led papers
is related mainly to the first-mover advantage of men and not a direct act of
discrimination against women [59]. Nevertheless, it is worth noting that such
effects may create implicit biases and discrimination similar to what
sociologists found as racism without racists effects [61] in which structural
racism can exist without anyone being racist.

Apart from the dynamics of networks, one can also consider dynamical processes
that unfold on networks. Here, we discuss two types of dynamical processes:
(1) diffusion of norms, (2) disease spreading, and how these dynamics affect
minorities. Social scientists argue that diffusion of norms and culture falls
under the category of complex contagion while disease spreading processes are
often simple contagion. Complex contagion describes situations in which
multiple social links of an individual must adopt a new norm or behaviour to
convince this individual to adopt it. The rationale behind these processes is
that humans, as social animals, follow conformity and social imitation when
faced with limited access to information. Mark Granovetter first proposed a
model of contagion to explain the emergence of norms and social uprising [62].
The core principle is that individuals have a threshold or stubbornness to
adopt a new behaviour. An individual will adopt a new behaviour when a certain
fraction of people (within this individual’s observation horizon) also adopt
the behaviour. In large societies, it is safe to assume that our observation
horizon is somewhat limited to our direct contacts111Here, we ignore online
social media exposure.. Borrowing this idea, in one of the early works in
contemporary network science, Watts showed that being embedded in a large-
scale social network, even if the network is completely random, leads to
situations where contagion can occur [7]. This finding points to the fact that
even without any intelligent decision-making process or social engineering,
social contagion can occur depending on how we are wired to others [63].
However, given the fact that groups mix differently (i.e., mixing biases), as
we discussed in the earlier section, how would those biases in mixing affect
the formation of norms and culture? In what societies can minorities propagate
their norms, and in what societies do they need to adopt the majority’s norms?

### Minorities and norms.

Following the same network models we described earlier, we examine the
Granovetter threshold model on networks with the presence of the minorities
and majorities and varying degrees of group mixing [64]. We explore whether
minorities can maintain their norms or even impose their norms on the majority
group and in what situation normative conflict increases or decreases. Our
first finding is that when norms align with the group categories (i.e.,
minorities disproportionately follow one norm while the majorities follow the
opposing norm), friction and conflict occur while people need to swing in one
way or another. Second, in societies with a moderate level of homophily, the
majority norm takes over. Finally, as the minority group increases in size, it
is more likely to retain its norm and influence the majority. Our simulation
supports three strategies for maintaining minority cultural practices employed
by minority groups in reality: isolationism, adopting positions of influence,
and increasing the group size of one’s minority. In future work, it would be
valuable to examine the influence of other mechanisms such as resistance,
changes in the social interactions or heterogeneity in the group mixing.

### Minorities and health inequality.

Pandemics expose and deepen existing racial, ethnic, and income inequalities
in society by aggravating resource constraints and rendering living conditions
direr for those who live on the margins. During the recent COVID-19 pandemic,
we witnessed a disproportionate infection rate among marginalized groups,
people of color [2], and low-income groups [65]. Health inequalities are often
due to existing structural inequalities in which societies perpetuate
discrimination through mutually reinforcing systems of housing, education,
employment, and health care [66]. By combining epidemic modelling in networks
with agent-based simulation, our analysis has shown that within the lower-
income population that cannot afford to quarantine themselves, the epidemic
spreads faster and results in more death. In addition, since low-income
individuals often live in segregated neighbourhoods that are densely
populated, the epidemic has more chance of spreading from one person to
another [67]. These findings demonstrate that inequalities in one layer can
diffuse to other layers of social lives, and it requires complexity thinking
to understand and tackle them.

## Key challenges and future directions

In this chapter, we have reviewed recent data-driven, theory-informed research
on inequality and minorities in social networks from the perspective of
complexity science and computational social science. The research we presented
helps us understand inequalities and marginalization in society; it sheds
light on potential ways to alleviate such critical societal problems. More
importantly, these research studies introduce novel challenges and
opportunities.

For example, network modelling and computational, agent-based simulations help
us understand different dimensions of social interactions and structural
inequalities. With this approach, we can disentangle existing inequalities,
elaborate informed policies to improve the status quo, and prevent the
formation of new inequalities (e.g., biased algorithms). However, we advocate
that complex computational models of society should consider socio-demographic
attributes of individuals, heterogeneity in group mixing, and how societies
evolve and mix over time. In parallel to that, social theories of diffusion,
tie formation mechanisms, and group identity should be modelled and validated
with empirical data as much as possible [68].

Furthermore, we note that inequalities are multi-faceted and multi-
dimensional. While a majority of the current research is on understanding the
effect of gender or race on networks, evidence suggests that individuals who
are in the intersection of multiple disadvantaged categories may be
discriminated against and also experience inequalities more disproportionately
compared to others [69]. Future research should pay more attention to this
aspect.

For data-driven research, we believe that mechanistic computational network
models can play an instrumental role in order to validate competing theories,
providing new theories and insights, and in particular, help machine learning
methods when input data is missing or biased [70]. Understanding how biased
data can affect computational methods is an essential future avenue for
research.

Overall, we hope this chapter supplies readers with a broad overview of the
diverse opportunities and challenges for understanding minority groups in
social networks and serves as an inspiration for their own research agenda,
aiming to transform society for the better.

## Acknowledgement

We thank our key collaborators including Claudia Wagner, Eun Lee, Mirta
Galesic, Lisette Espin-Noboa, Mathieu Génois, Mohsen Jadidi, Maria Zens,
Antonio Ferrara, Julian Kohne, Natalie Gallagher, Sina Sajjadi, Samuel Martin-
Gutierrez, Matthias Raddant, Hyunsik Kong, Petter Holme and Kristina Lerman,
who helped in shaping many of these ideas and research papers. We thank Wayt
Gibbs and Aleszu Bajak for their feedback on the manuscript. Fariba Karimi was
supported by the Austrian research agency FFG, project number 873927.

## References

  * [1] Butler, T. & Watt, P.  _Understanding social inequality_ (Sage, 2006).
  * [2] Bambra, C., Riordan, R., Ford, J. & Matthews, F.  The covid-19 pandemic and health inequalities.  _J Epidemiol Community Health_ 74, 964–968 (2020).
  * [3] Stolte, J. & Emerson, R. M.  Structural inequality: Position and power in network structures (1977).
  * [4] Fleurbaey, M.  Equal opportunity or equal social outcome?  _Economics & Philosophy_ 11, 25–55 (1995).
  * [5] Walby, S.  Complexity theory, systems theory, and multiple intersecting social inequalities.  _Philosophy of the social sciences_ 37, 449–470 (2007).
  * [6] Holovatch, Y., Kenna, R. & Thurner, S.  Complex systems: physics beyond physics.  _European Journal of Physics_ 38 (2017).
  * [7] Watts, D. J.  A simple model of global cascades on random networks.  _Proceedings of the National Academy of Sciences_ 99, 5766–5771 (2002).
  * [8] Galam, S.  Minority opinion spreading in random geometry.  _The European Physical Journal B-Condensed Matter and Complex Systems_ 25, 403–406 (2002).
  * [9] Young, H. P.  The dynamics of social innovation.  _Proceedings of the National Academy of Sciences_ 108, 21285–21291 (2011).
  * [10] Della Rossa, F. _et al._ A network model of italy shows that intermittent regional strategies can alleviate the covid-19 epidemic.  _Nature communications_ 11, 1–9 (2020).
  * [11] Haug, N. _et al._ Ranking the effectiveness of worldwide covid-19 government interventions.  _Nature human behaviour_ 4, 1303–1312 (2020).
  * [12] Holme, P. & Liljeros, F.  Mechanistic models in computational social science.  _Frontiers in Physics_ 3, 78 (2015).
  * [13] Hedström, P. & Ylikoski, P.  Causal mechanisms in the social sciences.  _Annual review of sociology_ 36, 49–67 (2010).
  * [14] Grusky, D.  _Social stratification, class, race, and gender in sociological perspective_ (Routledge, 2019).
  * [15] Jost, J. T., Gaucher, D. & Stern, C.  The world isn’t fair: A system justification perspective on social stratification and inequality.  In _Annual Meeting of International Society of Political Psychology, Herzliya, Israel_ , 317–340 (American Psychological Association, 2015).
  * [16] Fletcher, G. J., Reeder, G. D. & Bull, V.  Bias and accuracy in attitude attribution: The role of attributional complexity.  _Journal of Experimental Social Psychology_ 26, 275–288 (1990).
  * [17] Brewer, M. B.  In-group bias in the minimal intergroup situation: A cognitive-motivational analysis.  _Psychological bulletin_ 86, 307 (1979).
  * [18] DiMaggio, P. & Garip, F.  Network effects and social inequality.  _Annual review of sociology_ 38, 93–118 (2012).
  * [19] Garip, F. & Molina, M. D.  Network amplification.  In _Research Handbook on Analytical Sociology_ (Edward Elgar Publishing, 2021).
  * [20] Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K. & Galstyan, A.  A survey on bias and fairness in machine learning.  _ACM Computing Surveys (CSUR)_ 54, 1–35 (2021).
  * [21] Suresh, H. & Guttag, J. V.  A framework for understanding unintended consequences of machine learning.  _arXiv preprint arXiv:1901.10002_ 2 (2019).
  * [22] Baeza-Yates, R.  Bias on the web.  _Communications of the ACM_ 61, 54–61 (2018).
  * [23] McDermott, R., Fowler, J. H. & Smirnov, O.  On the evolutionary origin of prospect theory preferences.  _The Journal of Politics_ 70, 335–350 (2008).
  * [24] McPherson, M., Smith-Lovin, L. & Cook, J. M.  Birds of a feather: Homophily in social networks.  _Annual review of sociology_ 27, 415–444 (2001).
  * [25] Tajfel, H. & Turner, J. C.  The social identity theory of intergroup behavior. (2004).
  * [26] Franklin, A. J.  Invisibility syndrome and racial identity development in psychotherapy and counseling african american men.  _The Counseling Psychologist_ 27, 761–793 (1999).
  * [27] Noelle-Neumann, E.  The spiral of silence a theory of public opinion.  _Journal of communication_ 24, 43–51 (1974).
  * [28] Wickware, P.  Along the leaky pipeline.  _Nature_ 390, 202 (1997).
  * [29] Jadidi, M., Karimi, F., Lietz, H. & Wagner, C.  Gender disparities in science? dropout, productivity, collaborations and success of male and female computer scientists.  _Advances in Complex Systems_ 1750011 (2017).
  * [30] Bartlett, J. & Miller, C.  The edge of violence: Towards telling the difference between violent and non-violent radicalization.  _Terrorism and Political Violence_ 24, 1–21 (2012).
  * [31] Karimi, F., Génois, M., Wagner, C., Singer, P. & Strohmaier, M.  Homophily influences ranking of minorities in social networks.  _Scientific reports_ 8, 11077 (2018).
  * [32] Schaible, J., Oliveira, M., Zens, M. & Génois, M.  Sensing close-range proximity for studying face-to-face interaction.  In _Handbook of Computational Social Science, Volume 1_ (Routledge, 2021).
  * [33] Dunbar, R.  Neocortex size as a constraint on group size in primates.  _Journal of Human Evolution_ 22, 469–493 (1992).
  * [34] Duncan, S. & Fiske, D. W.  _Face-to-face interaction: research, methods, and theory_ (Lawrence Erlbaum Associates, 1977).
  * [35] Oliveira, M. _et al._ Group mixing drives inequality in face-to-face gatherings.  _Communications Physics_ 5, 1–9 (2022).
  * [36] Lee, E. _et al._ Homophily and minority-group size explain perception biases in social networks.  _Nature human behaviour_ 1–10 (2019).
  * [37] Ghoshal, G. & Barabási, A.-L.  Ranking stability and super-stable nodes in complex networks.  _Nature communications_ 2, 1–7 (2011).
  * [38] Lerman, K., Yan, X. & Wu, X.-Z.  The ”Majority Illusion” in Social Networks.  _PLOS ONE_ 11, e0147617 (2016).
  * [39] Mariani, M. S., Medo, M. & Zhang, Y.-C.  Ranking nodes in growing networks: When pagerank fails.  _Scientific reports_ 5, 1–10 (2015).
  * [40] Espín-Noboa, L., Wagner, C., Strohmaier, M. & Karimi, F.  Inequality and inequity in network-based ranking and recommendation algorithms.  _Scientific reports_ 12, 1–14 (2022).
  * [41] Sarigöl, E., Pfitzner, R., Scholtes, I., Garas, A. & und F Schweitzer.  Predicting scientific success based on coauthorship networks.  _EPJ Data Science_ 2014, 9.
  * [42] AlShebli, B. K., Rahwan, T. & Woon, W. L.  The preeminence of ethnic diversity in scientific collaboration.  _Nature communications_ 9, 1–10 (2018).
  * [43] Petersen, u. A. M.  Quantifying the impact of weak, strong, and super ties in scientific careers.  In _Proceedings of the National Academy of Sciences_ , 4671–4680.
  * [44] Petersen, A. M.  Reputation and impact in academic careers.  In _Proceedings of the National Academy of Sciences_ , 15316–15321.
  * [45] Clifton, S. M. _et al._ Mathematical model of gender bias and homophily in professional hierarchies.  _Chaos: An Interdisciplinary Journal of Nonlinear Science_ 29, 023135 (2019).
  * [46] Kuziemski, M. & Misuraca, G.  Ai governance in the public sector: Three tales from the frontiers of automated decision-making in democratic settings.  _Telecommunications policy_ 44, 101976 (2020).
  * [47] Dressel, J. & Farid, H.  The accuracy, fairness, and limits of predicting recidivism.  _Science advances_ 4, eaao5580 (2018).
  * [48] Zafar, M. B., Valera, I., Rogriguez, M. G. & Gummadi, K. P.  Fairness constraints: Mechanisms for fair classification.  In _Artificial Intelligence and Statistics_ , 962–970 (PMLR, 2017).
  * [49] Lepri, B., Oliver, N., Letouzé, E., Pentland, A. & Vinck, P.  Fair, transparent, and accountable algorithmic decision-making processes.  _Philosophy & Technology_ 31, 611–627 (2018).
  * [50] Wagner, C., Singer, P., Karimi, F., Pfeffer, J. & Strohmaier, M.  Sampling from social networks with attributes.  In _Proceedings of the 26th International Conference on World Wide Web_ , 1181–1190 (International World Wide Web Conferences Steering Committee, 2017).
  * [51] Espín-Noboa, L., Wagner, C., Karimi, F. & Lerman, K.  Towards quantifying sampling bias in network inference.  _WWW Conference_ (2018).
  * [52] Fabbri, F., Bonchi, F., Boratto, L. & Castillo, C.  The effect of homophily on disparate visibility of minorities in people recommender systems.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , vol. 14, 165–175 (2020).
  * [53] Ferrara, A., Espín-Noboa, L., Karimi, F. & Wagner, C.  Link recommendations: Their impact on network structure and minorities.  _arXiv preprint arXiv:2205.06048_ (2022).
  * [54] Mucha, P. J., Richardson, T., Macon, K., Porter, M. A. & Onnela, J.-P.  Community structure in time-dependent, multiscale, and multiplex networks.  _science_ 328, 876–878 (2010).
  * [55] Holme, P.  Modern temporal network theory: a colloquium.  _The European Physical Journal B_ 88, 234 (2015).
  * [56] Scholtes, I. _et al._ Causality-driven slow-down and speed-up of diffusion in non-markovian temporal networks.  _Nature communications_ 5, 1–9 (2014).
  * [57] Karimi, F. & Holme, P.  Threshold model of cascades in empirical temporal networks.  _Physica A: Statistical Mechanics and its Applications_ 392, 3476–3483 (2013).
  * [58] Karimi, F. & Holme, P.  A temporal network version of watts cascade model.  In _Temporal Networks_ , 315–329 (Springer Berlin Heidelberg, 2013).
  * [59] Kong, H., Martin-Gutierrez, S. & Karimi, F.  First-mover advantage explains gender disparities in physics citations.  _arXiv preprint arXiv:2110.02815_ (2021).
  * [60] Telles, E. E.  Industrialization and racial inequality in employment: the brazilian example.  _American Sociological Review_ 46–63 (1994).
  * [61] Bonilla-Silva, E.  _Racism without racists: Color-blind racism and the persistence of racial inequality in the United States_ (Rowman & Littlefield Publishers, 2006).
  * [62] Granovetter, M.  Threshold models of collective behavior.  _American journal of sociology_ 83, 1420–1443 (1978).
  * [63] Karimi, F.  _Tightly knit: spreading processes in empirical temporal networks_.  Ph.D. thesis, Umeå University (2015).
  * [64] Kohne, J. _et al._ The role of network structure and initial group norm distributions in norm conflict.  In _Computational Conflict Research_ , 113–140 (Springer, Cham, 2020).
  * [65] Adam, D.  The pandemic’s true death toll: millions more than official counts.  _Nature_ 601, 312–315 (2022).
  * [66] Bailey, Z. D. _et al._ Structural racism and health inequities in the usa: evidence and interventions.  _The lancet_ 389, 1453–1463 (2017).
  * [67] Sajjadi, S. _et al._ Structural inequalities exacerbate infection disparities: A computational approach.  _arXiv preprint arXiv:2205.04361_ (2022).
  * [68] Watts, D. J.  Should social science be more solution-oriented?  _Nature Human Behaviour_ 1, 1–5 (2017).
  * [69] Crenshaw, K.  Demarginalizing the intersection of race and sex: A black feminist critique of antidiscrimination doctrine, feminist theory and antiracist politics.  _u. Chi. Legal f._ 139 (1989).
  * [70] Steinbacher, M. _et al._ Advances in the agent-based modeling of economic and social behavior.  _SN Business & Economics_ (2021).