# On the entropic property of
the Ellipsoidal Statistical model
with the Prandtl number below 2/3

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Entropic property of the Ellipsoidal Statistical model with the Prandtl number
Pr below 2/3 is discussed. Although 2/3 is the lower bound of Pr for the H
theorem to hold unconditionally, it is shown that the theorem still holds even
for $\mathrm{Pr}<2/3$, provided that anisotropy of stress tensor satisfies a
certain criterion. The practical tolerance of that criterion is assessed
numerically by the strong normal shock wave and the Couette flow problems. A
couple of moving plate tests are also conducted.

###### Key words and phrases:

kinetic theory of gases, H theorem, ellipsoidal statistical model, rarefied
gases, Boltzmann equation.

###### 1991 Mathematics Subject Classification:

Primary: 76P05; Secondary: 82C40.

The present work is supported in part by KAKENHI from JSPS (No. 17K18840)

∗ Corresponding author: Shigeru TAKATA

Shigeru Takata∗ and Masanari Hattori

Department of Aeronautics and Astronautics & Advanced Engineering Research
Center,

Kyoto University, Kyoto 615-8540, Japan

Takumu Miyauchi

Department of Aeronautics and Astronautics, Kyoto University, Kyoto 615-8540,
Japan

(Communicated by *****)

##  1\. Introduction

The Ellipsoidal Statistical (ES) model is a relaxation-type kinetic equation
proposed by Holway [9], which involves the celebrated Bhatnagar–Gross–Krook
(BGK) model [3] as a special case. It has a simple structure as the other
kinetic models but still satisfies the H theorem and reproduces a realistic
value of the Prandtl number. Since the proof of its H theorem in Ref. [1], it
has been attracting many researchers as an alternative to the BGK model, e.g.,
[4, 7, 8, 11, 10].

In the case of monatomic gases, that proof was made for the Prandtl number not
less than 2/3. In some practical applications, however, such a restriction
might affect our choice of the Prandtl number. Indeed, for the hard-sphere gas
(one of the most representative models in the kinetic theory) the Prandtl
number is known to be $0.660694$ [14], which is slightly lower than
$2/3$.111In the case of the dense gas, the deviation from $2/3$ can be
enhanced to be down to about $86\%$ of the value at the dilute gas limit,
according to the Enskog theory; see, e.g., J. O. Hirschfelder, C. F. Curtiss
and R. B. Bird, Molecular Theory of Gases and Liquids, John Wiley & Sons, New
York, 1964, Sec. 9.3. In Refs. [15, 6], we were also in such an embarrassing
situation that the Prandtl number of nitrogen gas is slightly below the
corresponding bound for polyatomic gases and made a compromise (by around 10
%) in setting the value of the Prandtl number in numerical computations.

The above lower bound $2/3$ is, however, the condition that the H theorem
holds unconditionally. There is still a room for that the H theorem holds even
for the Prandtl number below that bound under some restriction. In the present
paper, we are going to study this issue and provide a critical condition for
the H theorem to be valid for the Prandtl number below 2/3. The paper is
organized as follows. First, the ES model is briefly reviewed in Sec. 2. Then,
the derivation of the concerned condition is delivered in Sec. 3, which is
followed by some practical assessment tests in Sec. 4. The paper is concluded
in Sec. 5.

##  2\. ES model and H theorem

Let us denote by $f$ the velocity distribution function (VDF) of gas
molecules, which is a function of time $t$, space position $X_{i}$, and
molecular velocity $\xi_{i}$. Then, the collision term of the ES model
$Q_{\mathrm{ES}}(f)$ for monatomic gases reads [1]

$\displaystyle Q_{\mathrm{ES}}(f)=$ $\displaystyle
A_{c}(T)\rho(\mathcal{G}[f]-f),$ (1a)
$\displaystyle\mathcal{G}[f]=\frac{\rho}{\det(2\pi\mathcal{T})}\exp\Big{(}-\frac{1}{2}(\mathcal{T}^{-1})_{ij}(\xi_{i}-v_{i})(\xi_{j}-v_{j})\Big{)},$
(1b) $\displaystyle\rho=\int fd\bm{\xi},\quad
v_{i}=\frac{1}{\rho}\int\xi_{i}fd\bm{\xi},\quad\mathcal{T}_{ij}=(1-\nu)RT\delta_{ij}+\nu\,\Theta_{ij},$
(1c)
$\displaystyle\Theta_{ij}=\frac{1}{\rho}\int(\xi_{i}-v_{i})(\xi_{j}-v_{j})fd\bm{\xi},\quad
T=\frac{1}{3R}\Theta_{ii},$ (1d)

where $\rho$, $v_{i}$, and $T$ are respectively the density, flow velocity,
and temperature of the gas; $R$ is the specific gas constant (the Boltzmann
constant divided by the mass of a molecule); $\delta_{ij}$ is the Kronecker
delta; $A_{c}(T)(>0)$ is a positive function of $T$ such that $A_{c}(T)\rho$
is the collision frequency of the gas molecules. Note that $\mathcal{T}$ (or
$\mathcal{T}_{ij}$) is a $3\times 3$ matrix, that $\Theta_{ij}$ (or $\Theta$)
is the stress tensor divided by the density, and that the summation convention
applies in the definitions of $\mathcal{G}$ and $T$ and throughout the present
paper. The $\nu$ is an adjustable parameter to make the Prandtl number
$\mathrm{Pr}$ a realistic value, and the H theorem is proved to hold
unconditionally in the range $-1/2\leq\nu<1$ [1]. Because of the relation
$\mathrm{Pr}=1/(1-\nu)$ (or $\nu=1-1/\mathrm{Pr}$), this range is identical to
$2/3\leq\mathrm{Pr}<\infty$.

For our purpose, the relevant steps in the proof in Ref. [1] are to show that
(i) $\mathcal{T}$ is positive definite and that (ii) the inequality
$\det\mathcal{T}\geq\det\Theta$ holds, where the equality holds only when
$\Theta$ is a scalar multiple of the identity matrix (see the Appendix A). If
(i) and (ii) remain valid even for $\nu<-1/2$ (or $\mathrm{Pr}<2/3$) under
some condition, the H theorem remains valid as well under that condition. In
the present paper, we are concerned with the case $-1\leq\nu<-1/2$, which
corresponds to the case $1/2\leq\mathrm{Pr}<2/3$.

##  3\. Derivation of condition

Thanks to its definition, $\Theta$ is a symmetric positive definite matrix and
thus has positive real eigenvalues $\lambda_{1}$, $\lambda_{2}$, and
$\lambda_{3}$, as far as the VDF is non-negative. Hence, without loss of
generality, we may assume that $0<\lambda_{1}\leq\lambda_{2}\leq\lambda_{3}$
and accordingly may put $\lambda_{1}=(1-\epsilon)\lambda$,
$\lambda_{2}=(1-\theta\epsilon)\lambda$, and $\lambda_{3}=\lambda$, where
$0\leq\epsilon<1$, $0\leq\theta\leq 1$, and $\lambda>0$. Since by definition
$3RT$ is nothing else than the trace of $\Theta$, it is related to the
eigenvalues as $3RT=\lambda_{1}+\lambda_{2}+\lambda_{3}$ [or
$3RT=(3-\epsilon(1+\theta))\lambda$]. Note that $\epsilon$ indicates the
degree of deviation of the minimum from the maximum eigenvalue and that
$\theta$ is the ratio of the difference between the largest two eigenvalues to
that between the minimum and the maximum eigenvalue.

###  3.1. On the condition for $\mathcal{T}$ to be positive definite

In the frame of the mutually orthogonal eigenvectors of $\Theta$, the
$\mathcal{T}$ as well as $\Theta$ is diagonalized:

$\displaystyle\mathcal{T}$ $\displaystyle=\nu\Theta+(1-\nu)RT\mathrm{Id}$
$\displaystyle=\lambda\,\Biggl{(}\begin{array}[]{ccc}1-\epsilon\nu-\frac{\epsilon(1-\nu)(1+\theta)}{3}&0&0\\\
0&1-\epsilon\theta\nu-\frac{\epsilon(1-\nu)(1+\theta)}{3}&0\\\
0&0&1-\frac{\epsilon(1-\nu)(1+\theta)}{3}\end{array}\Biggr{)},$

where $\mathrm{Id}$ is the $3\times 3$ identity matrix. Since the three
diagonal components multiplied by $\lambda$ are eigenvalues of $\mathcal{T}$,
the condition for $\mathcal{T}$ to be positive definite is simply reduced to

$1-(\epsilon/3)(1-\nu)(1+\theta)>0,\quad\mathrm{i.e.,}\quad
0\leq\epsilon<\frac{3}{1-\nu}\frac{1}{1+\theta},$ (2)

in the present parameter range $-1\leq\nu<-1/2$. Note that, since
$0\leq\epsilon<1$ by construction, the constraint (2) is effective only when
the right-hand side of the last inequality is less than unity, namely

$\theta>\frac{3}{1-\nu}-1=\frac{2+\nu}{1-\nu}\equiv\theta_{\mathcal{T}}(\nu),$
(3)

is fulfilled. The above $\theta_{\mathcal{T}}$ varies monotonically from $1/2$
to $1$ when $\nu$ varies from $-1$ to $-1/2$.

###  3.2. On the condition for $\det\mathcal{T}\geq\det\Theta$ to hold and the
restriction on the equality

After straightforward manipulations, the difference $D$ of $\det\mathcal{T}$
with $\det\Theta$ is written as

$\displaystyle D\equiv$ $\displaystyle\det\mathcal{T}-\det\Theta$
$\displaystyle=$
$\displaystyle\frac{1}{3}\lambda^{3}\epsilon^{2}(1-\nu)\Big{\\{}(1+\nu)(\theta^{2}-\theta+1)$
$\displaystyle-\frac{1}{9}\epsilon(1+\theta)[2\nu+1+(1-\nu)\theta][(2\nu+1)\theta+1-\nu]\Big{\\}}.$
(4)

Here, we need to care the restriction in (ii) of the last paragraph of Sec. 2
that $D=0$ holds only when $\Theta$ is a scalar multiple of the identity
matrix, which is identical to $\epsilon=0$ in the present notation. Hence the
condition for $D\geq 0$ with this restriction is reduced to that the inside of
the curly brackets is positive, i.e.,

$(1+\nu)(\theta^{2}-\theta+1)>\frac{1}{9}\epsilon(1+\theta)[2\nu+1+(1-\nu)\theta][(2\nu+1)\theta+1-\nu],$
(5)

for $\epsilon\neq 0$ in the range $-1\leq\nu<-1/2$. The left-hand side is non-
negative because $0\leq\theta\leq 1$, while the sign of the right-hand side
depends on that of the factor
$F(\theta;\nu)\equiv[2\nu+1+(1-\nu)\theta][(2\nu+1)\theta+1-\nu]$. Let the
smaller and larger zeros of $F$ with fixed $\nu$ be $\theta_{a}$ and
$\theta_{b}$, i.e., $\theta_{a}=-(2\nu+1)/(1-\nu)$ and
$\theta_{b}=-(1-\nu)/(2\nu+1)$. Then, it is readily seen that
$0<\theta_{a}<1<\theta_{b}$ and that $F\geq 0$ for
$\theta_{a}\leq\theta\leq\theta_{b}$ and $F<0$ elsewhere. Hence, we have the
following condition:

$\Biggl{\\{}\begin{array}[]{ll}\displaystyle 0\leq\epsilon<1,&\mbox{for }\
0\leq\theta\leq\theta_{a},\\\ \displaystyle
0\leq\epsilon<\frac{9(1+\nu)(\theta^{2}-\theta+1)}{(1+\theta)F(\theta;\nu)}\equiv\mathcal{F}(\theta;\nu),&\mbox{for
}\ \theta_{a}<\theta\leq 1.\end{array}\Biggr{.}$ (6)

###  3.3. Combined condition

We shall merge the conditions (2) and (6) by taking account of the original
range of $\epsilon$, i.e., $0\leq\epsilon<1$.

Let us start with the observation that
$\theta_{\mathcal{T}}-\theta_{a}=3(\nu+1)/(1-\nu)\geq 0$, so that
$\theta_{a}\leq\theta_{\mathcal{T}}<1$ for $-1\leq\nu<-1/2$. As described
before, the condition (2) becomes effective only when
$\theta>\theta_{\mathcal{T}}$. Our first concern is the size relation between
$3/[(1-\nu)(1+\theta)]$ in (2) and $\mathcal{F}(\theta;\nu)$ in (6) in the
range $\theta_{\mathcal{T}}<\theta\leq 1$. Then, checking the size relation is
reduced to checking the sign of the following quantity

$\Delta\equiv F(\theta;\nu)-3(1-\nu)(1+\nu)(\theta^{2}-\theta+1),$

because all of $(1+\theta)$, $(1-\nu)$, and $F$ are positive. Here,
$\Delta\gtrless 0$ implies $3/[(1-\nu)(1+\theta)]\gtrless\mathcal{F}$. The
simple substitution of $F$ shows, after some manipulations, that

$\displaystyle\Delta$
$\displaystyle=(1-\nu)(-\nu-2)\theta^{2}+(2\nu^{2}+2\nu+5)\theta+(1-\nu)(-\nu-2)$
$\displaystyle=[(1-\nu)\theta-(\nu+2)][-(\nu+2)\theta+(1-\nu)]$
$\displaystyle=-(1-\nu)(\nu+2)(\theta-\theta_{\mathcal{T}})(\theta-\frac{1}{\theta_{\mathcal{T}}}).$
(7)

Remind that $\theta_{\mathcal{T}}<1$ for $-1\leq\nu<-1/2$. Thus $\Delta>0$,
i.e., $\mathcal{F}<3/[(1-\nu)(1+\theta)]$ for $\theta_{\mathcal{T}}<\theta\leq
1$. Our next concern is the size relation between $\mathcal{F}$ and unity in
the range $\theta_{a}<\theta\leq\theta_{\mathcal{T}}$, because
$3/[(1-\nu)(1+\theta)]$ is over or equal to unity in this range. Then, because
$\Delta\leq 0$ for $\theta_{a}<\theta\leq\theta_{\mathcal{T}}$, we have $1\leq
3/[(1-\nu)(1+\theta)]\leq\mathcal{F}$, so that there is no restriction on
$\epsilon$ in the concerned range of $\theta$.

To summarize, we have arrived at the following statement of criterion.

Let $\lambda_{1}\leq\lambda_{2}\leq\lambda_{3}$ be positive real eigenvalues
of the symmetric positive definite matrix $\Theta$ defined by (1d). Let
$\epsilon=1-\lambda_{1}/\lambda_{3}$ and
$\theta=(1-\lambda_{2}/\lambda_{3})/(1-\lambda_{1}/\lambda_{3})$, where
$0\leq\epsilon<1$ and $0\leq\theta\leq 1$ by construction. Then, for
$-1\leq\nu<-1/2$, which corresponds to $1/2\leq\mathrm{Pr}<2/3$, the following
criterion must be fulfilled in order for the H theorem to remain valid:

$\Biggl{\\{}\begin{array}[]{ll}\displaystyle 0\leq\epsilon<1,&\mbox{for
}\displaystyle\ 0\leq\theta\leq\frac{2+\nu}{1-\nu},\\\ \displaystyle
0\leq\epsilon<\mathcal{F}(\theta;\nu),&\mbox{for }\displaystyle\
\frac{2+\nu}{1-\nu}<\theta\leq 1,\end{array}\Biggr{.}$ (8)

where $\mathcal{F}$ is the one defined by (6).

##  4\. Simple test problems

In order to see how much the derived condition (8) is practically restrictive,
we shall carry out a couple of numerical tests such that the strong
anisotropic behavior of the gas be expected. One is the strong shock wave
problem, the other is the time-dependent Couette flow problem. A couple of
additional tests, which are simple but severe, motivated by the result of the
Couette flow will be conducted as well.

###  4.1. Shock wave test

|
---|---
(a) $M_{-}=2$ | (b) $M_{-}=5$
|
(c) $M_{-}=20$ | (d) $M_{-}=40$
Figure 1. Structure of the shock wave for typical Mach numbers $M_{-}$ in the
case of $\mathrm{Pr}=2/3$. (a) $M_{-}=2$, (b) $M_{-}=5$, (c) $M_{-}=20$, and
(d) $M_{-}=40$. Here, $\ell_{-}$ is the mean free path of molecules in the
equilibrium state at rest with density $\rho_{-}$ and temperature $T_{-}$. In
each panel, solid lines indicate
$\rho_{*}=(\rho-\rho_{-})/(\rho_{+}-\rho_{-})$,
$u_{*}=(v_{1}-u_{+})/(u_{-}-u_{+})$, and $T_{*}=(T-T_{-})/(T_{+}-T_{-})$
respectively, while a dash-dotted line indicates $\epsilon$.

Consider a normal shock wave standing at rest against a uniform flow of a
monatomic gas. Let $X_{1}$ be the spatial coordinate along the flow direction
whose origin is located at the center of the shock.222The center of the shock
is defined by the position where the density $\rho$ takes the average of the
densities at the upstream and downstream infinities. Let $\rho_{-}$, $T_{-}$,
and $(u_{-},0,0)$ be the density, temperature, and flow velocity of the
uniform equilibrium state at upstream infinity, while $\rho_{+}$, $T_{+}$, and
$(u_{+},0,0)$ be those at downstream infinity. Then, under the spatially
uniform and the null flow-velocity assumption in the $X_{2}$\- and
$X_{3}$-directions, the problem is formulated as

$\displaystyle\xi_{1}\frac{\partial f}{\partial
X_{1}}=Q_{\mathrm{ES}}(f),\quad-\infty<X_{1}<\infty,$ (9a) under the upstream
and the downstream condition $\displaystyle
f(X_{1},\bm{\xi})\to\frac{\rho_{\pm}}{(2\pi
RT_{\pm})^{3/2}}\exp\Big{(}-\frac{(\xi_{1}-u_{\pm})^{2}+\xi_{2}^{2}+\xi_{3}^{2}}{2RT_{\pm}}\Big{)},\quad\mbox{as
}\ X_{1}\to\pm\infty,$ (9b)

where the upstream and the downstream quantities are related by the
Rankine–Hugoniot conditions [12]:

$\frac{\rho_{-}}{\rho_{+}}=\frac{u_{+}}{u_{-}}=1-\frac{2}{\gamma+1}\frac{M_{-}^{2}-1}{M_{-}^{2}},\quad\frac{T_{+}}{T_{-}}=1+\frac{2(\gamma-1)}{(\gamma+1)^{2}}\frac{(\gamma
M_{-}^{2}+1)(M_{-}^{2}-1)}{M_{-}^{2}}.$ (10)

Here $\gamma=5/3$ and $M_{-}(\geq 1)$ is the Mach number of the flow at
upstream infinity, i.e., $M_{-}=u_{-}/\sqrt{\gamma RT_{-}}$.

The problem can be reduced to that of the marginal VDFs [5]. After the
reduction, it is solved numerically by the standard iterative finite-
difference method. The numerical accuracy is carefully checked enough to
assure the main conclusions drawn from the present computations. Here we omit
the details of the numerical method itself, grid resolution, etc. and simply
present the obtained results.

It is readily seen that $\Theta$ is diagonal333Thanks to the assumption made
just before (9a), the problem is rotationally invariant around the
$X_{1}$-axis. The off-diagonal components are thus null. in the present
coordinates system, and its diagonal components are nothing else than the
eigenvalues $\lambda_{1}$, $\lambda_{2}$, and $\lambda_{3}$ [or
$(1-\epsilon)\lambda$, $(1-\epsilon\theta)\lambda$, and $\lambda$]. Firstly,
the computations have been performed for $M_{-}=2$, $5$, $10$, 20, $40$, and
$60$ under the setting $\mathrm{Pr}=2/3$. Figure 1 shows the structure of the
shock wave in some typical cases. In all the cases, $\Theta_{11}$ is found to
be the largest among the diagonal components. Because the problem is isotropic
in the directions normal to $X_{1}$-direction, $\Theta_{22}=\Theta_{33}$ and
thus $\theta\equiv 1$. Then, the condition (8) is simplified as

$0\leq\epsilon<\mathcal{F}(1;\nu)=\frac{9}{2}\frac{1+\nu}{(\nu+2)^{2}},$ (11)

or equivalently

$0\leq\epsilon<\frac{(\mathrm{Pr}-1/2)}{(\mathrm{Pr}-1/3)^{2}}\mathrm{Pr}\equiv\mathcal{S}(\mathrm{Pr}),$
(12)

using the relation $\nu=1-1/\mathrm{Pr}$. Note that $\mathcal{S}(\mathrm{Pr})$
monotonically increases from $0$ to $1$ as $\mathrm{Pr}$ increases from $1/2$
to $2/3$. The obtained profiles of $\epsilon$, which is given by
$1-\Theta_{33}/\Theta_{11}$ here, inside the shock are also shown by dash-
dotted lines in Figure 1. With the aid of (12), the lower bound of the
acceptable Prandtl number for each Mach number is suggested from the figure,
the result of which is shown in Table 1.

Table 1. The maximum $\epsilon$ for various Mach numbers $M_{-}$ in the case of $\mathrm{Pr}=2/3$. $\mathrm{Pr}_{*}$ is the lower bound of acceptable Prandtl number suggested by $\max\epsilon=\mathcal{S}(\mathrm{Pr}_{*})$; see (12). $M_{-}$ | 2 | 5 | 10 | 20 | 40 | 60
---|---|---|---|---|---|---
$\max\epsilon$ | 0.2786 | 0.5506 | 0.6137 | 0.6387 | 0.6478 | 0.6499
$\mathrm{Pr}_{*}$ | 0.5184 | 0.5454 | 0.5539 | 0.5576 | 0.5590 | 0.5593
$(3/2)\mathrm{Pr}_{*}$ | 0.7776 | 0.8181 | 0.8309 | 0.8364 | 0.8385 | 0.8390
Figure 2. The maximum value of $\epsilon$ vs. $(3/2)\mathrm{Pr}$ for various
upstream Mach numbers $M_{-}$. Symbols indicates the results of computations.
The results of common $M_{-}$ are connected by solid lines in the acceptable
range of $\mathrm{Pr}$ and by dashed lines in the range where condition (8) is
violated.

With these results in mind, further computations have been carried out for
different Prandtl numbers as well. The maximum values of $\epsilon$ in
individual computations are plotted against $\mathrm{Pr}$ for each Mach number
in Figure 2. It is seen that they depend only weakly on $\mathrm{Pr}$ for
every fixed value of $M_{-}$. The intersections of solid lines and the curve
$\epsilon=\mathcal{S}(\mathrm{Pr})$ are indicated by the symbol $\Box$. Their
abscissas indicate the actual lower bounds of acceptable Prandtl number for
the individual $M_{-}$. They are all slightly smaller than the values of
$\mathrm{Pr}_{*}$ in Table 1 for those $M_{-}$. It is seen that in the present
test the condition (8) [or (12)] is tolerant; even for $M_{-}=60$,
$(3/2)\mathrm{Pr}$ can be down to $\simeq 0.83$, i.e., a reduction of
$\mathrm{Pr}$ by around $17\%$ from $2/3$ is acceptable.

Incidentally, even for $\mathrm{Pr}=1/2$ (or $\nu=-1$), where the condition
(12) is violated, stable numerical computations have been carried out. It
would be partially explained by that the condition (2) for $\mathcal{T}$ to be
positive definite is reduced to $0\leq\epsilon<3/4$ and is never violated in
those computations (see Figure 2).

###  4.2. Couette flow and sliding plate test

Consider a monatomic rarefied gas in the gap between two parallel plates which
are kept at a common uniform temperature $T_{0}$. The confined gas is in the
equilibrium state at rest with the temperature $T_{0}$ and the density
$\rho_{0}$. Set the $X_{1}$-direction to be normal to the plates, with its
origin at the middle of the gap. Let the gap width be $L$. At the instance
$t=0$, the two plates suddenly start sliding with a constant speed $V$ in the
directions opposite to each other: the plate at $X_{1}=L/2$ moves in the
$X_{2}$-direction, while that at $X_{1}=-L/2$ in the $-X_{2}$-direction.
Assuming the diffuse reflection boundary condition on the plates, the problem
is formulated as

$\displaystyle\frac{\partial f}{\partial t}+\xi_{1}\frac{\partial f}{\partial
X_{1}}=Q_{\mathrm{ES}}(f),\quad-L/2<X_{1}<L/2,$ (13a) under the initial and
the boundary condition $\displaystyle
f(0,X_{1},\bm{\xi})=\frac{\rho_{0}}{(2\pi
RT_{0})^{3/2}}\exp\Big{(}-\frac{\xi_{1}^{2}+\xi_{2}^{2}+\xi_{3}^{2}}{2RT_{0}}\Big{)},$
(13b) $\displaystyle f(t,\pm L/2,\bm{\xi})=\frac{\sigma_{\pm}}{(2\pi
RT_{0})^{3/2}}\exp\Big{(}-\frac{\xi_{1}^{2}+(\xi_{2}\mp
V)^{2}+\xi_{3}^{2}}{2RT_{0}}\Big{)},\quad\xi_{1}\lessgtr 0,$ (13c) where
$\displaystyle\sigma_{\pm}=\sqrt{\frac{2\pi}{RT_{0}}}\int_{\xi_{1}\gtrless
0}|\xi_{1}|f(t,\pm L/2,\bm{\xi})d\bm{\xi}.$ (13d)

This is the time-dependent Couette flow problem.

As the previous test case, the problem can be reduced to that of the marginal
VDFs [5]. After the reduction, it is solved numerically by the standard
finite-difference method implicit in time. The numerical accuracy is carefully
checked enough to assure the main conclusions drawn from the present
computations. We again omit all the details of the numerical computations. In
the present test, $\Theta$ is not diagonal in the specified Cartesian
coordinates, and the three eigenvalues are given by $\Theta_{33}$ and
$\lambda_{\pm}\equiv[\Theta_{11}+\Theta_{22}\pm\sqrt{(\Theta_{11}-\Theta_{22})^{2}+4\Theta_{12}^{2}}]/2$.

The computations have been carried out for various values of $V$, the
reference Knudsen number, and the Prandtl number. In the present test,
$\epsilon$ is found to be always $1-\lambda_{-}/\lambda_{+}$ and to take its
maximum value on the plates at the initial stage of the time evolution.
Consequently, that value is found to depend only on the plate speed, neither
on the Knudsen number nor the Prandtl number, because at the initial stage the
collision integral is not effective. These observations imply that the most
severe situation is identical to the initial stage of the Rayleigh problem [2,
13] and is represented by the combination of the initial data for incident
molecules and the boundary condition for reflected molecules on the plates.
That is, the most severe test can be conducted by the following VDF:

$f(\bm{\xi})=\Biggl{\\{}\begin{array}[]{ll}\displaystyle\frac{\rho_{0}}{(2\pi
RT_{0})^{3/2}}\exp\Big{(}-\frac{\xi_{1}^{2}+(\xi_{2}-V)^{2}+\xi_{3}^{2}}{2RT_{0}}\Big{)},&\xi_{1}<0,\\\
\displaystyle\frac{\rho_{0}}{(2\pi
RT_{0})^{3/2}}\exp\Big{(}-\frac{\xi_{1}^{2}+\xi_{2}^{2}+\xi_{3}^{2}}{2RT_{0}}\Big{)},&\xi_{1}>0.\end{array}\Biggr{.}$
(14)

Note that this is identical to the steady free molecular solution of the
Couette flow with one plate sliding with speed $V$ and the other plate at
rest. The above reduction of test, which we call a sliding plate test, allows
us to assess the condition of our interest in detail.

For the above VDF (14), $\epsilon$ and $\theta$ are readily obtained as

$\epsilon=\epsilon_{S}(\hat{V})\displaystyle\equiv\frac{\displaystyle\frac{\hat{V}^{2}}{2}\sqrt{1+\frac{16}{\pi\hat{V}^{2}}}}{1+\displaystyle\frac{\hat{V}^{2}}{4}(\sqrt{1+\displaystyle\frac{16}{\pi\hat{V}^{2}}}+1)},\quad\theta=\theta_{S}(\hat{V})\displaystyle\equiv\frac{1}{2}\Big{(}1+\frac{1}{\sqrt{1+\displaystyle\frac{16}{\pi\hat{V}^{2}}}}\Big{)},$
(15)

where $\hat{V}=V/\sqrt{2RT_{0}}$. Note that (a) $\theta>1/2$ from the above,
while $0<\theta_{a}\leq 1/2$ in the range $-1\leq\nu<-1/2$ or
$1/2\leq\mathrm{Pr}<2/3$. It is also found that
$0\leq\epsilon_{S}(\hat{V})<1$. Hence, plugging (15) into (8) yields the
following criterion for the H theorem to remain valid in the present test:

$0\leq\epsilon_{S}(\hat{V})<\frac{9(2-1/\mathrm{Pr})[\theta_{S}(\hat{V})^{2}-\theta_{S}(\hat{V})+1]}{[1+\theta_{S}(\hat{V})]F(\theta_{S}(\hat{V});1-1/\mathrm{Pr})}\equiv\mathcal{F}_{D}(\hat{V};\mathrm{Pr}),$
(16)

where the relation $\nu=1-1/\mathrm{Pr}$ has been used to convert $\nu$ to
$\mathrm{Pr}$. The function $\mathcal{F}_{D}$ is plotted by solid lines for
various values of $\mathrm{Pr}$ in Figure 3, together with $\epsilon_{S}$ by a
dashed line. It is seen from the figure that, by the 20 % (resp. 16 %)
reduction of Prandtl number from $2/3$, the condition (16) is satisfied for
the sliding speed $\hat{V}\lesssim 1.03$ (resp. 1.59).

Figure 3. The functions $\mathcal{F}_{D}$ and $\epsilon_{S}$ in the criterion
(16). The solid lines indicate $\mathcal{F}_{D}$ for
$(3/2)\mathrm{Pr}=0.76,0.78,0.8,\dots,0.96$, while the dashed line indicates
$\epsilon_{S}$.

Incidentally, in the time-dependent Couette flow test, even when the condition
(8) is violated, numerical computations have been carried out stably and
consistently, as far as the condition (2) is satisfied. This observation
agrees with the shock wave test for $\mathrm{Pr}=1/2$.

|
---|---
(a) | (b)
Figure 4. The function $\epsilon_{P}$ and the dimensionless density
$\hat{\rho}$ in the range $-5<\hat{U}<5$. (a) $\epsilon_{P}$, (b)
$\hat{\rho}$. In (a), the values of $\mathcal{S}(\mathrm{Pr})$ for
$(3/2)\mathrm{Pr}=0.76,0.8,0.84,\dots,0.96$ are also indicated by dash-dotted
lines for reference.

###  4.3. Pushing or pulling plate test

Motivated by the sliding plate test, we consider another severe test by the
following VDF:

$f(\bm{\xi})=\Biggl{\\{}\begin{array}[]{ll}\displaystyle\frac{\rho_{0}\hat{\sigma}}{(2\pi
RT_{0})^{3/2}}\exp\Big{(}-\frac{(\xi_{1}-U)^{2}+\xi_{2}^{2}+\xi_{3}^{2}}{2RT_{0}}\Big{)},&\xi_{1}>U,\\\
\displaystyle\frac{\rho_{0}}{(2\pi
RT_{0})^{3/2}}\exp\Big{(}-\frac{\xi_{1}^{2}+\xi_{2}^{2}+\xi_{3}^{2}}{2RT_{0}}\Big{)},&\xi_{1}<U,\end{array}\Biggr{.}$
(17)

where

$\displaystyle\hat{\sigma}(\hat{U})=\frac{1}{\rho_{0}}\sqrt{\frac{2\pi}{RT_{0}}}\int_{\xi_{1}<U}|\xi_{1}-U|fd\bm{\xi}=\exp(-\hat{U}^{2})+\sqrt{\pi}\hat{U}[1+\mathrm{erf}(\hat{U})],$
$\displaystyle\hat{U}=U/\sqrt{2RT_{0}}.$

The above VDF mimics the gas on the plate at the initial instance of a sudden
plate motion in the normal direction with a constant speed $|U|$, by supposing
that, before starting the plate motion, the gas is in the equilibrium state at
rest with density $\rho_{0}$ and temperature $T_{0}$. Here, $U>0$ implies the
pushing plate while $U<0$ implies the pulling plate.

In this case, $\Theta$ is diagonal with $\Theta_{22}=\Theta_{33}$ (thus
$\theta=1$) as in the shock wave test, and the diagonal components are given
by

$\Theta_{11}/(RT_{0})=1+({\hat{U}}/{\sqrt{\pi}})\hat{\sigma}(\hat{U})/\hat{\rho}(\hat{U}),\quad\Theta_{22}=\Theta_{33}=RT_{0},$
(18)

where $\hat{U}=U/\sqrt{2RT_{0}}$ and
$\hat{\rho}(\hat{U})=(1/2)[\hat{\sigma}(\hat{U})+1+\mathrm{erf}(\hat{U})]$ is
the gas density divided by $\rho_{0}$. Note that $\hat{\sigma}>0$ because of
its definition. Accordingly, $\Theta_{11}\gtrless RT_{0}$ for $\hat{U}\gtrless
0$ and $\epsilon$ is written as

$\epsilon=1-(RT_{0}/\Theta_{11})^{\pm 1},\quad\hat{U}\gtrless 0,$ (19)

in the present test. Since $\theta=1$, the condition (8) takes the same form
as (12). Substitution of (19) into (12) eventually leads to the following
condition:

$0\leq\epsilon_{P}(\hat{U})<\mathcal{S}(\mathrm{Pr}),$ (20)

where

$\epsilon_{P}(\hat{U})=1-\Big{(}1+({\hat{U}}/{\sqrt{\pi}})\hat{\sigma}(\hat{U})/\hat{\rho}(\hat{U})\Big{)}^{\mp
1},\quad\hat{U}\gtrless 0.$ (21)

Figure 4 shows the functions $\epsilon_{P}$ and $\hat{\rho}$ respectively in
(a) and (b), where the values of $\mathcal{S}(\mathrm{Pr})$ are also shown for
reference in (a). The present test assesses the robustness of the desired
entropic property for small Prandtl numbers against the anisotropy caused by
strong compression (or expansion). In this sense, the type of test is similar
to that in the shock wave case. Nevertheless, the observed robustness looks
quite different. One possible explanation is the compression rate measured by
the density. In the shock wave test, the ratio of density $\rho_{+}/\rho_{-}$
between the upstream and the downstream infinity is at most four even in the
limit $M_{-}\to\infty$, see (10). But here, the ratio of the density to its
initial value $\hat{\rho}$ or its inverse is beyond this value already around
$\hat{U}=1.70$ or $-0.73$. The present test is thus much harder than the shock
wave test.

##  5\. Conclusions

In the present paper, we have investigated the criterion for the H theorem to
hold even for the ES model with the Prandtl number below $2/3$. The derived
condition that covers the range $1/2\leq\mathrm{Pr}<2/3$ shows that indeed
there is a room for the H theorem to remain valid. The practical tolerance of
the condition is assessed numerically by a couple of tests, i.e., the strong
shock wave and the time-dependent Couette flow problem, and then further
assessed by the sliding and the pushing/pulling plate problem. The condition
is tolerant in the shock wave test enough to accept about $18\%$ reduction of
$\mathrm{Pr}$ below $2/3$ even for the strong shock wave with $M_{-}=5$, while
it is rather restrictive in the Couette flow, the sliding plate, and the
pushing/pulling plate test in the sense that the acceptable reduction of
$\mathrm{Pr}$ of the same level is achieved only within $1.4$ for both
$|\hat{U}|$ and $\hat{V}$. The latter three tests show that the collisionless
gas state caused by the sudden motion of boundary can be a practical source of
restriction on the entropic property of the ES model for small Prandtl numbers
below $2/3$.

##  Appendix A A brief review of the H theorem in Ref. [1]

Proposition 2.1 (the H theorem) of Ref. [1], together with the outline of its
proof, is shown here in terms of the notation in the present paper.

Let

$S(\rho,\bm{v},\mathcal{T})=\min_{g\in\mathcal{X}}\langle H(g)\rangle,$ (22)

where $H(f)=f\ln f$, $\langle\bullet\rangle=\int\bullet\,d\bm{\xi}$, and
$\mathcal{X}(\rho,\bm{v},\mathcal{T})$ is the set defined by
$\mathcal{X}=\\{g\geq 0,(1+\xi_{i}^{2})g\in L^{1}(\mathbb{R}^{3}),\langle
g\rangle=\rho,\langle\xi_{i}g\rangle=\rho
v_{i},\langle\xi_{i}\xi_{j}g\rangle=\rho v_{i}v_{j}+\rho\mathcal{T}_{ij}\\}$.
Then, the following proposition is proved in Ref. [1].

Proposition: For symmetric positive definite tensor $\Theta$ and
$-1/2\leq\nu<1$ we have

  1. (a)

the tensor $\mathcal{T}$ defined in (1c) is symmetric positive definite and
the set $\mathcal{X}(\rho,\bm{v},\mathcal{T})$ is not empty,

  2. (b)

the unique minimizer in (22) is the Gaussian $\mathcal{G}[f]$ defined in (1b),

  3. (c)

the entropy of the Gaussian $\mathcal{G}[f]$ satisfies $\langle
H(\mathcal{G})\rangle=S(\rho,\bm{v},\mathcal{T})\leq
S(\rho,\bm{v},\Theta)\leq\langle H({f})\rangle$,

  4. (d)

consequently the entropy inequalities

$\displaystyle\int Q_{\mathrm{ES}}(f)\ln fd\bm{\xi}\leq 0,$ (23)
$\displaystyle\frac{\partial}{\partial t}\int
H(f)d\bm{\xi}+\frac{\partial}{\partial X_{i}}\int\xi_{i}H(f)d\bm{\xi}\leq 0,$
(24)

hold.

  5. (e)

the equality $\langle H(\mathcal{G})\rangle=\langle H({f})\rangle$ implies
$f=\displaystyle\frac{\rho}{(2\pi
RT)^{3/2}}\exp(-\frac{(\bm{\xi}-\bm{v})^{2}}{2RT})$.

The outline of proof of (a)–(e) given in Ref. [1] is as follows.

  1. On (a):

The first part is assured by straightforward manipulations in terms of the
eigenvalues of $\Theta$ (i.e., $\lambda_{1}$, $\lambda_{2}$, and
$\lambda_{3}$) for $-1/2\leq\nu\leq 1$. Then second part is valid for such
$\mathcal{T}$, because $\mathcal{G}[f]$ belongs to that set.

  2. On (b):

The proof relies on the definition of $H$ and its convexity.

  3. On (c):

The equality $\langle H(\mathcal{G})\rangle=S(\rho,\bm{v},\mathcal{T})$ is
nothing else than (b). The inequality $S(\rho,\bm{v},\mathcal{T})\leq
S(\rho,\bm{v},\Theta)$ is first reduced to $\det\mathcal{T}\geq\det\Theta$ by
using (b). Then, the reduced inequality is validated by an extension of the
Brunn–Minkowsky inequality in the range $-1/2\leq\nu\leq 1$. The inequality
$S(\rho,\bm{v},\Theta)\leq\langle H(f)\rangle$ is a consequence of the
definition of $S$.

  4. On (d):

This is an immediate consequence of (c) and the convexity of $H$.

  5. On (e):

Because of (d), the equality $\langle H(\mathcal{G})\rangle=\langle
H({f})\rangle$ implies $S(\rho,\bm{v},\Theta)=\langle H(f)\rangle$, which in
turn implies that $f$ is the Gaussian with $\mathcal{T}$ being replaced by
$\Theta$. It also implies $S(\rho,\bm{v},\mathcal{T})=S(\rho,\bm{v},\Theta)$,
which leads to $\det\mathcal{T}=\det\Theta$. Then, direct calculations of this
equality show that $\Theta$ is a scalar multiple of the identity matrix and
thus $f$ is the Maxwellian given in (e).

As is clear from the above outline, the clue steps for the extension of the
validity range of the H theorem are to show that (i) $\mathcal{T}$ is positive
definite and (ii) $\det\mathcal{T}\geq\det\Theta$, including that the equality
in (ii) holds only when $f$ is the Maxwellian. The discussions in Sec. 3 of
the present paper focus on the above (i) and (ii).

## References

  * [1] P. Andries, P. Le Tallec, J.-P. Perlat and B. Perthame,  The Gaussian-BGK model of Boltzmann equation with small Prandtl number,  Eur. J. Mech. B-Fluids, 19 (2000), 813–830.
  * [2] G. K. Batchelor,  An Introduction to Fluid Dynamics,  Cambridge University Press, Cambridge, 1967, Sec. 4.3.
  * [3] P. L. Bhatnagar, E. P. Gross and M. Krook,  A model for collision processes in gases. I. Small amplitude processes in charged and neutral one-component systems,  Phys. Rev., 94 (1954), 511–525.
  * [4] S. Brull and J. Schneider,  A new approach for the ellipsoidal statistical model,  Contin. Mech. Thermodyn., 20 (2008), 63–74.
  * [5] C. K. Chu,  Kinetic-theoretic description of the formation of a shock wave,  Phys. Fluids, 8 (1965), 12–22.
  * [6] H. Funagane, S. Takata, K. Aoki and K. Kugimoto,  Poiseuille flow and thermal transpiration of a rarefied polyatomic gas through a circular tube with applications to microflows,  Bollettino U. M. I. Ser. IX, IV (2011), 19–46.
  * [7] M.A. Gallis and J.R. Torczynski,  Investigation of the ellipsoidal-statistical Bhatnagar–Gross–Krook kinetic model applied to gas-phase transport of heat and tangential momentum between parallel walls,  Phys. Fluids, 23 (2011), 030601.
  * [8] M. Groppi, S. Monica and G. Spiga,  A kinetic ellipsoidal BGK model for a binary gas mixture,  Europhys. Lett., 96 (2011), 64002.
  * [9] L. H. Holway,  New statistical models for kinetic theory: Methods of construction,  Phys. Fluids, 9 (1966), 1658–1673.
  * [10] C. Klingenberg, M. Pirner and G. Puppo,  Kinetic ES-BGK models for a multi-component gas mixture,  in XVI International Conference on Hyperbolic Problems: Theory, Numerics, Applications, Springer, (2016), 195–208.
  * [11] J. Meng, L. Wu, J. M. Reese and Y. Zhang,  Assessment of the ellipsoidal-statistical Bhatnagar–Gross–Krook model for force-driven Poiseuille flows,  J. Comp. Phys., 251 (2013), 383–395.
  * [12] H. W. Liepmann and A. Roshko,  Elements of Gasdynamics,  Dover, New York, 2001, Sec. 2.13.
  * [13] Y. Sone,  Kinetic theory analysis of linearized Rayleigh problem,  J. Phys. Soc. Jpn, 19 (1964), 1463–1473.
  * [14] Y. Sone,  Molecular Gas Dynamics,  Birkhäuser, Boston, 2007, Sec. 3.1.9; Supplementary Notes and Errata is available from Kyoto University Research Information Repository (http://hdl.handle.net/2433/66098).
  * [15] S. Takata, H. Funagane and K. Aoki,  Fluid modeling for the Knudsen compressor: Case of polyatomic gases,  Kinetic and Related Models, 3 (2010), 353–372.


WGMwgm QEqe

[1]

[1]organization=Theoretical Statistics and Mathematics Unit, Indian
Statistical Institute, addressline=8th Mile, Mysore Rd, RVCE Post,
city=Bengaluru, postcode=560059, state=Karnataka, country=India

[2]

url]

[2]organization=Physics and Applied Mathematics Unit, Indian Statistical
Institute, addressline=203 B.T. Road, city=Kolkata, postcode=700108,
state=West Bengal, country=India

[3]

[3]organization=Center for Computational Natural Science and Bioinformatics,
International Institute of Informational Technology, addressline=Gachibowli,
city=Hyderabad, postcode=500032, state=Telengana, country=India

# Coprime networks of the composite numbers:
pseudo-randomness and synchronizability

Md Rahil Miraj<EMAIL_ADDRESS>Dibakar Ghosh<EMAIL_ADDRESS>[
Chittaranjan Hens<EMAIL_ADDRESS>
In this paper, we propose a network whose nodes are labeled by the composite
numbers and two nodes are connected by an undirected link if they are
relatively prime to each other. As the size of the network increases, the
network will be connected whenever the largest possible node index $n\geq 49$.
To investigate how the nodes are connected, we analytically describe that the
link density saturates to $6/\pi^{2}$, whereas the average degree increases
linearly with slope $6/\pi^{2}$ with the size of the network. To investigate
how the neighbors of the nodes are connected to each other, we find the
shortest path length will be at most 3 for $49\leq n\leq 288$ and it is at
most 2 for $n\geq 289$. We also derive an analytic expression for the local
clustering coefficients of the nodes, which quantifies how close the neighbors
of a node to form a triangle. We also provide an expression for the number of
$r$-length labeled cycles, which indicates the existence of a cycle of length
at most $O(\log n)$. Finally, we show that this graph sequence is actually a
sequence of weakly pseudo-random graphs. We numerically verify our observed
analytical results. As a possible application, we have observed less
synchronizability (the ratio of the largest and smallest positive eigenvalue
of the Laplacian matrix is high) as compared to Erdős–Rényi random network and
Barabási-Albert network. This unusual observation is consistent with the
prolonged transient behaviors of ecological and predator-prey networks which
can easily avoid the global synchronization.

Keywords: Prime and Composite Numbers, Network Science, Pseudo-random graph.

##  1 Introduction

The study of graphs with intricate connections between the items is known as a
complex network [1, 2, 3, 4]. The field of network science examines a wider
range of systems found in the real world [5, 6, 7, 8, 9, 10, 11, 12],[13]. For
instance, the study of network science can be used to map out emerging
behavior in social networks [14], the proper functionality of the
technological systems (such as the power grid) [15], the spreading mechanism
of diseases among communities [16, 17], the stability of prey-predator systems
[18], neuronal activities [19], signal propagation[20] and the interaction
mechanism in subcellular systems [21].

The study of different mathematical properties of some sets of numbers is now
frequently done using network science [22, 23]. Nodes from those sets are used
to build the networks, which connect each pair of them by directed or
undirected links whenever they fulfill a particular relation. Many such
interesting networks have been found in the literature. For instance,
divisibility networks of natural numbers following usual increasing sequential
order [22] or by taking nodes from the Pascal matrix and constructing a
divisibility network with those nodes [24] are recently developed. Also in
[25], assuming that Goldbach conjecture is true, the authors have broken the
even numbers by the sum of two primes and constructed a network of those prime
numbers by connecting links between two primes depending on the corresponding
even numbers. Sometimes, it is also possible to find analytic expressions of
the measures like average degree, link density, clustering coefficients etc.
and by constructing networks of different size one may check how fast it
agrees with the theoretical results. In [22] the authors have shown
numerically that the divisibility network of natural numbers follows a scale-
free degree distribution. They have shown analytically that the global
clustering coefficient of this network decays to zero whereas the average
degree increases logarithmically as the size of the network increases.

A random graph of $n$ vertices is a graph, whose edges between two vertices
are drawn randomly. On the other hand, a pseudo random graph is a graph that
behaves like a random graph of same number of vertices and same edge density
with a high probability. In order to give a quantitative measure, Andrew
Thomason first introduced the notion of $(p,\alpha)$-jumbled graph in 1987
[26]. He defined a graph $G=(V,E)$ is said to be $(p,\alpha)$-jumbled graph
for real numbers $p$ and $\alpha$ with $0<p<1\leq\alpha$, if for every induced
subgraph $H$ of $G$, we get

$\left|E(H)-p\binom{|H|}{2}\right|\leq\alpha|H|.$

A $(p,O(\sqrt{np}))$-jumbled graph is one of the best possible pseudo-random
graph, as Erdős–Rényi random graph G(n,p) is almost surely
$(p,O(\sqrt{np}))$-jumbled [27].

Since, the largest eigenvalue of the adjacency matrix of a $d$-regular graph
is $d$, Alon [27, 28, 29] defined by $(n,d,\lambda)$-graph, a $d$-regular
graph of $n$ vertices and eigenvalues
$d=\lambda_{1}>\lambda_{2}\geq...\geq\lambda_{n}$ such that
$|\lambda_{i}|\leq\lambda$ for all $i=2,3,...,n$. It has been shown that
$(n,d,\lambda)$-graph with $\lambda$ much smaller than $d$ have certain
pseudo-random properties [28, 29, 30]. And it has also been found in
literature that a $(n,d,\lambda)$-graph is $(d/n,\lambda)$-jumbled [27]. Apart
from the pseudo-random graphs of the type $(p,\alpha)$-jumbled graphs, in
general, in a pseudo-random graph $G$ with any red/blue-coloring of edges such
that the proportion of red colored edges is $r$, it has been found that there
exists a Hamiltonian cycle having the proportion of red edges is close to $r$
[31]. Pancyclicity, i.e, the existence of cycles of all possible lengths in
pseudo-random graphs has also been explored in literature [32].

By slightly relaxing the conditions of $(p,\alpha)$-jumbled graph, we define a
sequence of graphs $\\{G_{n}\\}$ to be weakly pseudo-random [27] if for all
subsets $U\subseteq V(G_{n})$, we have

$\left|E(U)-p\binom{|U|}{2}\right|=o(pn^{2}),$

where $p=p(n)$ is a parameter, which is typically the edge density of graphs
in the sequence. Chung, Graham and Wilson first defined such a graph with
$p=1/2$ and named quasi-random graphs [33] in 1989 and also provided several
equivalent statements, which are actually same as above.

In this study, we construct a network with composite numbers as nodes and if
two of them are relatively prime to one another, we connect them with an
undirected link. In this case, we are looking for answers to certain pertinent
concerns about the structural characteristics of graphs from the standpoint of
graph theory. For instance, how the nodes are linked together and how many
nearby nodes may a node have? We also look for the diameter of the graph and
try to understand how the average shortest path length or the diameter of the
graph depend on the size of the network. We also want to know how a node’s
neighbors are connected between themselves. This property is measured by the
local clustering coefficient of a node, which is defined as the proportion of
the number of neighbors of a node being connected to each other to
$\binom{d}{2}$, where $d$ is the degree of that node [34](sec-2.10).

On the other hand, we revisit the old question of composite number theory:
what is the probability that two randomly chosen composite numbers to be
coprime to each other, which will be answered in the subsequent sections by
analytically calculating the average degree to be $\frac{6n}{{\pi}^{2}}$ and
link density $\frac{6}{{\pi}^{2}}$. Also the existence of labeled cycles of a
given length is another question that one may ask. Here we not only have shown
the existence of such a labeled cycle of some given length but also calculate
an expression for it, which gives us a glimpse of the existence of a cycle of
length at most $O(\log n)$ for large $n$. Therefore the emergence of such
dense graph motivates us to identify or categorize the structural pattern of
the graph, which type of graph it is. So, to answer this question, we are able
to show that the graph sequence namely coprime networks of composite numbers
are actually weakly pseudo-random with $p=\frac{6}{{\pi}^{2}}$. As an
application we have studied the eigenvalues of the Laplacian matrix of the
constructed network and infer that the synchronizability in the coprime
network of composite numbers is quite less as compared to Erdős–Rényi random
network and Barabási-Albert network [5, 35, 36, 37, 38]. This less
synchronizability is noticed in ecological and predator-prey networks.
Synchronization is a natural phenomenon that is mostly observed in a
population of dynamically interacting elements. Synchronization processes play
a very important role in many different contexts such as biology, ecology,
climatology, sociology, technology [39, 38]. It can be seen when oscillating
elements are constrained to interact in a complex network topology[5]. Note
that, two aspects in particular affect the network synchronizability entirely:
the first is the synchronized region associated with the node dynamics and the
second has to do with the eigenvalues of the network structural matrix. In
[40], the authors demonstrated that explosive synchronization occurs at all
even dimensions when Kuramoto oscillators are used in higher dimensions. In
this paper, we have significantly used the eigenvalues of the Laplacian matrix
of our constructed network to infer about the synchronizability.

Figure 1: Coprime networks of composite numbers: (a) $n=25$, (b) $n=30$. Here,
the size of each node is proportional to its degree and the color of each node
is given according to its clustering coefficient with lighter blue nodes as
nodes with higher value of local clustering. For $n=30$, the network is
disconnected. Later we will show that the constructed network will be
connected if $n\geq 49$.

##  2 Construction of the Network

To construct the proposed network, we chose the composite numbers less than or
equal to $n$ as nodes and connect two of them by an undirected edge if they
are coprime to each other, i.e., for $u,v\in\mathbf{V},\leavevmode\nobreak\
u\sim v$, if and only if $gcd(u,v)=1$, where $\mathbf{V}$ is the set of nodes,
i.e., the set of composite numbers less than or equal to $n$. Since, we have a
natural ordering in the composite numbers, so at each step we include the next
composite number as a new node which is greater than the largest node in the
existing network and connect it to those nodes which are coprime to it. Thus
we construct the network in a growing manner. In the constructed network, we
have an identity of each node as a composite number and we can study different
properties of the network as a function of the node index. This is not
possible with other networks, where there is no specific node index.

##  3 Properties of the Network

Now, we see the schematic representation of the networks for $n=25$ and
$n=30$. In this section, we prove a few important properties of the
constructed network. First we are eager to look analytically what is the least
composite number after which we get a connected network always. In the next
theorem, we will show that the occurrence of isolated node is not random,
rather as we increase $n$, after a certain point we will never have an
isolated node.

###### Theorem 1

There doesn’t exist any isolated node in the network constructed as above with
largest possible node index $n\geq 49$.

Proof. We can see that if there is no composite number up to $n$ that is
coprime to some composite number $k$, then the node $k$ will be isolated in
that graph. If $k={p_{1}}^{a_{1}}{p_{2}}^{a_{2}}\cdots{p_{r}}^{a_{r}}$, where
$p_{i}$’s are distinct primes such that $p_{1}=2$, $p_{2}=3$ and so on and
$a_{i}$’s are non-negative integers, except $a_{r}\neq 0$. Now if some $a_{i}$
is $0$, then $k$ will be connected to ${p_{i}}^{2}$, so it will be enough to
take $a_{i}=1$ for all $i=1,2,\cdots,r$. Then the least node greater than $k$
that will be connected to $k$ is the square of the least prime number $p\neq
p_{i}$ for $i=1,2,\cdots,r$, i.e., for $k=p_{1}p_{2}\cdots p_{r}$, the
smallest node that will be connected to $k$ is $p_{r+1}^{2}$, but if
$p_{r+1}^{2}>n$, then $k$ will be isolated.

So, for some $n$, if $p_{r+1}^{2}<p_{1}p_{2}\cdots p_{r}=k_{n}\leq n$, but
$p_{1}p_{2}\cdots p_{r+1}>n$, then if $p_{1}p_{2}.\cdots p_{r}p_{r+1}>n+1$, we
will get $k_{n+1}=k_{n}=p_{1}p_{2}\cdots p_{r}$, which will be connected to
$p_{r+1}^{2}$ and if $p_{1}p_{2}\cdots p_{r}p_{r+1}=n+1$, then by Lemma 5 in
the appendix with $t=2$ and $s=r$, we get $n+1=k_{n+1}=p_{1}p_{2}\cdots
p_{r}p_{r+1}>p_{r+2}^{2}$. So, $k_{n+1}$ will be connected to $p_{r+2}^{2}$
for the latter case.

But the smallest $r$ satisfying $p_{1}p_{2}\cdots p_{r}>p_{r+1}^{2}$ is $r=4$.
So, by induction, we can conclude that we will always have $p_{1}p_{2}\cdots
p_{r}>p_{r+1}^{2}$ for $r\geq 4$. Thus, for $n\geq p_{4}^{2}=7^{2}=49$, there
will be no isolated point.

$\Box$

Now, we can see that in a particular network with largest possible node index
$n$, the total number of nodes is the total number of composite numbers less
than or equal to $n$.

###### Theorem 2

The number of nodes in the proposed network with largest possible node index
$n$ is $N(n)=(n-\pi(n)-1)$, where $\pi(n)$ is the total number of primes less
than or equal to $n$.

Now, we will calculate the total number of edges of a network with greatest
possible node index $n$.

###### Theorem 3

The number of edges in a particular network with largest possible node index
$n$ is

$E(n)=\frac{3}{{\pi}^{2}}n^{2}+n\log\log
n-n\pi(n)+\frac{\pi(n)(\pi(n)+1)}{2}+O(n\log n).$

Proof. If we add nodes by increasing order starting from 4 and connect them by
edges accordingly at each step, the number of new added edges after adding the
$k^{th}$ node is

$E(k)-E(k-1)=\begin{cases}\phi(k)-\pi(k)+w(k)-1,&\text{if $k$ is
$composite$}\\\ 0,&\text{otherwise},\end{cases}$

where $\phi(k)$ is the total number of positive integers less than $k$ which
are coprime to $k$ [41] and $w(k)$ is the total number of distinct prime
factors of $k$.

Therefore, the telescoping sum gives

$E(n)-E(1)=\sum_{\begin{subarray}{c}k=2\\\ k\leavevmode\nobreak\
\text{composite}\end{subarray}}^{n}\Big{[}\phi(k)-\pi(k)+w(k)-1\Big{]}$

gives,

$E(n)=\sum_{\begin{subarray}{c}k=2\\\
k\neq\text{p}\end{subarray}}^{n}\Big{[}\phi(k)-\pi(k)+w(k)-1\Big{]},$ (1)

as $E(1)=0$, where $p$ is prime number.

We can write it as,

$\displaystyle E(n)$
$\displaystyle=\sum_{k=2}^{n}\Big{[}\phi(k)-\pi(k)+w(k)-1\Big{]}-\sum_{p\leq
n}\Big{[}\phi(p)-\pi(p)+w(p)-1\Big{]}$
$\displaystyle=\sum_{k=2}^{n}\Big{[}\phi(k)-\pi(k)+w(k)-1\Big{]}-\sum_{i=1}^{m}\Big{[}\phi(p_{i})-\pi(p_{i})\Big{]},$

where $m=\pi(n)$ and $w(p_{i})=1$ for all $i=1,2,...,m$, where $p_{i}$ is the
i-th prime.

$\displaystyle=\sum_{k=2}^{n}\Big{[}\phi(k)-\pi(k)+w(k)-1\Big{]}-\sum_{i=1}^{m}\Big{[}(p_{i}-1)-(i-1)\Big{]}$
$\displaystyle=\sum_{k=2}^{n}\Big{[}\phi(k)-\pi(k)+w(k)-1\Big{]}-\sum_{i=1}^{m}(p_{i}-i).$

Therefore,

$E(n)=\sum_{k=2}^{n}\phi(k)-\sum_{k=2}^{n}\pi(k)+\sum_{k=2}^{n}w(k)-(n-1)-\sum_{i=1}^{m}p_{i}+\frac{m(m+1)}{2}.$
(2)

Now, using Lemmas 1, 2, 4 in the appendix and from (2), we get

$E(n)=\Big{[}\frac{3}{{\pi}^{2}}n^{2}+O(n\log
n)\Big{]}-\Big{[}mn-\sum_{i=1}^{m}p_{i}\Big{]}+\Big{[}n\log\log
n+B_{1}n+O(n)\Big{]}-(n-1)-\sum_{i=1}^{m}p_{i}+\frac{m(m+1)}{2}$
$=\frac{3}{{\pi}^{2}}n^{2}+n\log\log n-nm+\frac{m(m+1)}{2}+O(n\log
n).\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ $

$\Box$

As we add all the composite numbers up to the natural number $n$ in the graph
one by one as the nodes and at each step we join any two of them by undirected
links if they are relatively prime, we get the desired network for some given
$n$. Then, a node $k$ will be connected to all the composite numbers less than
or equal to $n$ which are coprime to it and that is the degree of $k$.

###### Theorem 4

In the proposed network with largest possible node index $n$:
i. The degree of a node $k$, $d_{k}=\phi(n,k)-\pi(n)+w(k)-1$, where
$\phi(n,k)$ is the total number of positive integers less than or equal to $n$
which are coprime to $k$.
ii. The average degree of the nodes,
$\overline{d(n)}=\frac{6}{{\pi}^{2}}n+O\left(\frac{n}{(\log n)^{2}}\right),$
i.e., $\overline{d(n)}\sim\frac{6}{{\pi}^{2}}n$.
iii. The maximum degree of a node $k$ is $\Delta\leq n-\sqrt{n}-\frac{n}{\log
n}.$
iv. The codegree, i.e., the number of common neighbors between two nodes $k$
and $l$ is $codeg(k,l)=\phi(n,kl)-\pi(n)+w(kl)-1$.

Proof.

i. We have

$d_{k}=\sum\limits_{\begin{subarray}{c}i=2\\\ i\neq\text{prime}\\\
(i,k)=1\end{subarray}}^{n}\mathbf{1}=\sum\limits_{\begin{subarray}{c}i=2\\\
(i,k)=1\end{subarray}}^{n}\mathbf{1}-\sum\limits_{\begin{subarray}{c}p\leq
n\\\ p\nmid k\end{subarray}}^{n}\mathbf{1}=\phi(n,k)-\pi(n)+w(k)-1.$

ii. Now,

$\displaystyle\overline{d(n)}$
$\displaystyle=\frac{1}{n-\pi(n)-1}\sum_{k\in\mathbf{V}}d_{k}=\frac{2E(n)}{n-\pi(n)-1}$
$\displaystyle=\frac{2\Big{[}\frac{3}{{\pi}^{2}}n^{2}+n\log\log
n-n\pi(n)+\frac{\pi(n)(\pi(n)+1)}{2}+O(n\log n)\Big{]}}{n-\pi(n)-1}$
$\displaystyle\sim\frac{2\Big{[}\frac{3}{{\pi}^{2}}n^{2}+n\log\log
n-\frac{n^{2}}{\log n}+\frac{n}{2\log n}\left(\frac{n}{\log
n}+1\right)+O(n\log n)\Big{]}}{n-\frac{n}{\log n}-1}$
$\displaystyle=\frac{2\Big{[}\frac{3}{{\pi}^{2}}n+\log\log n-\frac{n}{\log
n}+\frac{n}{2(\log n)^{2}}+\frac{1}{2\log n}+O(\log n)\Big{]}}{1-\frac{1}{\log
n}-\frac{1}{n}}$ $\displaystyle=\frac{6}{{\pi}^{2}}n+O\left(\frac{n}{(\log
n)^{2}}\right).$

Therefore, $\overline{d(n)}\sim\frac{6}{{\pi}^{2}}n$.

Figure 2: The average degree $\overline{d(n)}$ is plotted by changing the
highest possible node index $n$. Here the average degree increases
monotonically by adding the nodes. The data has been plotted using log-log
scale. The scaling exponent is 1.

Theoretical result suggests that for large $n$, the mean degree scales with
$n^{\alpha}$, where $\alpha=1$, and the proportionality factor is around
$0.60.79(\frac{6}{{\pi}^{2}})$. The data is plotted in Fig.2 with black dots.
The data is plotted in log-log scale. Note that, for computational limitation,
we have varied network size from 10 to $10^{4}$. However, the theoretical line
fits very well with the numerical data.

Clearly, the network is highly dense, and the prefactor suggests that each
node is connected with almost $60.79\%$ nodes of the graph, which further
signify that for a given $n$, we can say that the probability of a pair of
composite numbers to be coprime is $\sim 0.60.79$.

iii. Now, let $r\geq 1$ be such that we have $p_{r}^{2}\leq n<p_{r+1}^{2}$.
Then we can see that $p_{r}^{2}$ will have the maximum degree. So,

$\Delta=d_{p_{r}^{2}}=\phi(n,p_{r}^{2})-\pi(n)+w(p_{r}^{2})-1=\phi(n,p_{r})-\pi(n)=n-\left\lfloor\frac{n}{p_{r}}\right\rfloor-\pi(n)\leq
n-\lfloor\sqrt{n}\rfloor-\pi(n),$

since, $p_{r}^{2}\leq n$. Therefore,

$\Delta\sim n-\sqrt{n}-\frac{n}{\log n}.$

Figure 3: The ratio of the computed and theoretical max
degree($\Delta/\Delta^{\prime}$) is plotted by changing the highest possible
node index $n$. The ratio getting closer to 1 indicates the accuracy of the
theoretical maximum of the degree.

iv. Again, we have

$codeg(k,l)=\sum_{\begin{subarray}{c}i=2\\\ i\neq\text{prime}\\\ (i,k)=1\\\
(i,l)=1\end{subarray}}^{n}\mathbf{1}=\sum_{\begin{subarray}{c}i=2\\\
i\neq\text{prime}\\\
(i,kl)=1\end{subarray}}^{n}\mathbf{1}=\sum_{\begin{subarray}{c}i=2\\\
(i,kl)=1\end{subarray}}^{n}\mathbf{1}-\sum_{\begin{subarray}{c}p\leq n\\\
p\nmid kl\end{subarray}}^{n}\mathbf{1}=\phi(n,kl)-\pi(n)+w(kl)-1.$

$\Box$

###### Theorem 5

The link density in the proposed network with largest possible node index $n$
is

$l(n)=\frac{6}{{\pi}^{2}}+O\left(\frac{\log n}{n}\right),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{i.e.,}\leavevmode\nobreak\ \leavevmode\nobreak\
l(n)\sim\frac{6}{{\pi}^{2}}.$

Proof.

$\displaystyle l(n)$
$\displaystyle=\frac{E(n)}{\binom{N(n)}{2}}=\frac{2E(n)}{(n-\pi(n)-1)(n-\pi(n)-2)}$
$\displaystyle=\frac{2\Big{[}\frac{3}{{\pi}^{2}}n^{2}+n\log\log
n-n\pi(n)+\frac{\pi(n)(\pi(n)+1)}{2}+O(n\log
n)\Big{]}}{(n-\pi(n)-1)(n-\pi(n)-2)}$
$\displaystyle\sim\frac{2\Big{[}\frac{3}{{\pi}^{2}}n^{2}+n\log\log
n-\frac{n^{2}}{\log n}+\frac{n}{2\log n}\left(\frac{n}{\log
n}+1\right)+O(n\log n)\Big{]}}{\left(n-\frac{n}{\log
n}-1\right)\left(n-\frac{n}{\log n}-2\right)}$
$\displaystyle=\frac{2\Big{[}\frac{3}{{\pi}^{2}}+\frac{\log\log
n}{n}-\frac{1}{\log n}+\frac{1}{2\log n}\left(\frac{1}{\log
n}+\frac{1}{n}\right)+O(\frac{\log n}{n})\Big{]}}{\left(1-\frac{1}{\log
n}-\frac{1}{n}\right)\left(1-\frac{1}{\log n}-\frac{2}{n}\right)}$
$\displaystyle=\frac{6}{{\pi}^{2}}+O\left(\frac{\log n}{n}\right)$

Therefore, $l(n)\sim\frac{6}{{\pi}^{2}}$.

$\Box$

###### Theorem 6

The shortest path length between two nodes in the proposed network with
largest possible node index $n$ will be at most $3$ for $n\geq 49$ and it will
be at most $2$ for $n\geq 289$.

Proof. For $n\geq 49$, the graph will be connected from Theorem 1. Now, take
two nodes $k=p_{1}^{a_{1}}p_{2}^{a_{2}}.....p_{r}^{a_{r}}$ and
$l=p_{1}^{b_{1}}p_{2}^{b_{2}}.....p_{s}^{b_{s}}$, assuming $r\leq s$, with
$p_{1}=2$, $p_{2}=3$ and so on. If $gcd(k,l)=1$, then they will be connected.
If $gcd(k,l)\neq 1$ and $p_{s+1}^{2}\leq n$ then both $k$ and $l$ will be
connected to $p_{s+1}^{2}$, so the shortest path length will be $2$.

If $gcd(k,l)\neq 1$ and $p_{s+1}^{2}>n$, then one of the $b_{j}$’s must be $0$
for $1\leq j\leq s-1$, otherwise it will contradict Theorem 1. If $r=s$, then
one of the $a_{i}$’s will also be $0$ for $1\leq i\leq r-1$ as before, then
$k-p_{i}^{2}-p_{j}^{2}-l$ will be the shortest path from $k$ to $l$ of length
$3$ (or of length $2$ if $i=j$) and if $r<s$, then $k-p_{t}^{2}-p_{j}^{2}-l$
will be the shortest path from $k$ to $l$ of length $3$, where $r+1\leq t\leq
s$ and $t\neq j$ (or, again of length $2$ if $t=j$).

Now, for $n\geq 289$, it is enough to show that if $k_{n}$ and $l_{n}$ be two
nodes as before such that we will always have $p_{s+1}^{2}\leq n$ when
$gcd(k_{n},l_{n})\neq 1$. Now, in order to maximize $s$, we will consider
$k_{n}=p_{1}p_{2}\cdots p_{r}$ and $l_{n}=p_{1}p_{r+1}\cdots p_{s}$, with
$s\geq r+1$, such that $k_{n},l_{n}\leq n$, but $p_{1}p_{2}\cdots
p_{r}p_{r+1}>n$ and $p_{1}p_{r+1}\cdots p_{s}p_{s+1}>n$, since if we take
$l_{n}=p_{1}p_{t}\cdots p_{s}$, for $t\geq r+2$, then $k_{n}$ and $l_{n}$ will
be connected to $p_{r+1}^{2}$. Let for some $r,s\geq 2$, if $n\geq
p_{s+1}^{2}$, then to get an induction argument, if $n+1$ is composite, adding
$(n+1)^{th}$ node to the graph, we get two possibilities:

Case-1: Suppose that, $k_{n+1}=k_{n}=p_{1}p_{2}\cdots p_{r}$, i.e., if
$p_{1}p_{2}\cdots p_{r}p_{r+1}>n+1$, then if $p_{1}p_{r+1}\cdots
p_{s}p_{s+1}>n+1$, we will have $l_{n+1}=l_{n}=p_{1}p_{r+1}\cdots p_{s}$ then
from our assumption, we already have $p_{s+1}^{2}<n+1$, so both $k_{n+1}$ and
$l_{n+1}$ will be connected to $p_{s+1}^{2}$. And if $p_{1}p_{r+1}\cdots
p_{s}p_{s+1}=l_{n+1}\leq n+1$, then since $p_{1}p_{r+1}\cdots p_{s}p_{s+1}>n$
from our assumption, we get $p_{1}p_{r+1}\cdots p_{s}p_{s+1}=n+1$. So, using
Lemma 6 in the appendix, for $s\geq r+2$, we get

$n+1=p_{1}p_{r+1}\cdots p_{s}p_{s+1}\geq
p_{1}p_{s-1}p_{s}p_{s+1}>p_{s+2}^{2}.$

Now, for $s=r+1$,

$n+1>p_{1}p_{2}\cdots p_{r}=p_{1}p_{2}\cdots p_{s-1}>p_{s+2}^{2},$

if $s\geq 6$ from Lemma 7 in the Appendix. So $k_{n+1}$ and $l_{n+1}$ both
will be connected to $p_{s+2}^{2}$.

Case-2: In this case, suppose $k_{n+1}\neq k_{n}$, i.e., if $p_{1}p_{2}\cdots
p_{r}p_{r+1}\leq n+1$, then since $p_{1}p_{2}\cdots p_{r}p_{r+1}>n$ from our
assumption, we get $k_{n+1}=p_{1}p_{2}\cdots p_{r}p_{r+1}=n+1$. Now, if
$l_{n+1}=p_{1}p_{r+2}\cdots p_{s}$, then we already have $p_{s+1}^{2}\leq
n<n+1$ from our assumption, so both $k_{n+1}$ and $l_{n+1}$ will be connected
to $p_{s+1}^{2}$. If $l_{n+1}=p_{1}p_{r+2}\cdots p_{s}p_{s+1}$, then using
Lemma 6 in the appendix, for $s\geq r+3$, we get

$n+1>l_{n+1}=p_{1}p_{r+2}\cdots p_{s}p_{s+1}\geq
p_{1}p_{s-1}p_{s}p_{s+1}>p_{s+2}^{2}.$

If $s=r+1$, then

$n+1=p_{1}p_{2}\cdots p_{r}p_{r+1}=p_{1}p_{2}\cdots
p_{s-1}p_{s}>p_{1}p_{2}\cdots p_{s-1}>p_{s+2}^{2},$

for $s\geq 6$ from Lemma 7 in the appendix (actually $s\geq 5$ is enough for
this case). And if $s=r+2$, then

$n+1=p_{1}p_{2}\cdots p_{r}p_{r+1}=p_{1}p_{2}\cdots p_{s-1}>p_{s+2}^{2},$

for $s\geq 6$ from Lemma 7 in the appendix, so both $k_{n+1}$ and $l_{n+1}$
will be connected to $p_{s+2}^{2}$. And if $l^{\prime}=p_{1}p_{r+2}\cdots
p_{t}$, where $t\geq s+2$, then

$l^{\prime}=p_{1}p_{r+2}\cdots p_{t}\geq p_{1}p_{r+2}\cdots
p_{s+1}p_{s+2}>p_{1}p_{r+1}\cdots p_{s+1}\geq n+1,$

since $p_{1}p_{r+1}.....p_{s+1}>n$ from our assumption. So, $l^{\prime}$ will
not be included to the graph for this case.

So, from both the cases we get $s\geq 6$. Hence, for $n\geq p_{7}^{2}=289$ the
shortest path length will be at most $2$.

$\Box$

###### Theorem 7

The number of $r$-length labeled cycles, for $r\geq 4$, in the proposed
network with largest possible node index $n$ is

$C_{n}(r)\leq\left(\frac{6n}{{\pi}^{2}}\right)^{r}+O(n^{r-1}\log^{r-1}n).$

Proof. We try to count how many $r$-length labeled cycles are there in a
coprime network of composite numbers with largest possible node index $n$. We
can see that

$C_{n}(r)=\sum_{\begin{subarray}{c}2\leq a_{1},a_{2},\cdots,a_{r}\leq n\\\
a_{i}\neq\leavevmode\nobreak\ prime\\\ a_{i}\neq a_{j},\leavevmode\nobreak\
i\neq j\\\ (a_{i},a_{i+1})=1\\\
(a_{1},a_{r})=1\end{subarray}}\mathbf{1}\leq\sum_{\begin{subarray}{c}1\leq
a_{1},a_{2},\cdots,a_{r}\leq n\\\ (a_{i},a_{j})=1,\\\ i\neq
j\end{subarray}}\mathbf{1}$

L. T$\acute{o}$th [42] showed that

$\sum_{\begin{subarray}{c}1\leq a_{1},\cdots,a_{r}\leq n\\\
(a_{i},a_{j})=1,\leavevmode\nobreak\ i\neq j\\\
(a_{i},k)=1\end{subarray}}\mathbf{1}=A_{r}f_{r}(k)n^{r}+O(\theta(k)n^{r-1}\log^{r-1}n),$
(3)

where

$A_{r}=\prod_{p}\left(1-\frac{1}{p}\right)^{r-1}\left(1+\frac{r-1}{p}\right),$
$f_{r}(k)=\prod_{p|k}\left(1-\frac{r}{p+r-1}\right),$

and $\theta(k)$ is the number of square-free divisors of $k$.

If the prime factorization of $k$ is
$k=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{s}^{\alpha_{s}}$, where
$s=w(k)$, then

$\theta(k)=\sum_{i=0}^{s}\binom{s}{i}=2^{s}=2^{w(k)}.$

Therefore, using this result with $k=1$ and from Lemma 8 in the appendix, we
get

$\displaystyle\sum_{\begin{subarray}{c}1\leq a_{1},a_{2},\cdots,a_{r}\leq n\\\
(a_{i},a_{j})=1,\\\ i\neq j\end{subarray}}\mathbf{1}$
$\displaystyle=n^{r}\prod_{p}\left(1-\frac{1}{p}\right)^{r-1}\left(1+\frac{r-1}{p}\right)+O(n^{r-1}\log^{r-1}n)$
$\displaystyle\leq
n^{r}\prod_{p}\left(1-\frac{1}{p^{2}}\right)^{r}+O(n^{r-1}\log^{r-1}n)$
$\displaystyle=n^{r}\left(\frac{1}{\zeta(2)}\right)^{r}+O(n^{r-1}\log^{r-1}n)$
$\displaystyle=\left(\frac{6n}{{\pi}^{2}}\right)^{r}+O(n^{r-1}\log^{r-1}n).$

Therefore, we get
$C_{n}(r)\leq\left(\frac{6n}{{\pi}^{2}}\right)^{r}+O(n^{r-1}\log^{r-1}n).$

$\Box$

###### Theorem 8

The local clustering coefficient of a node $k$ in the proposed network with
largest possible node index $n$ is

$c(k)\sim\frac{6}{{\pi}^{2}}\prod_{p|k}\left(\frac{p^{2}}{p^{2}-1}\right)$

Proof. In order to find the local clustering coefficient of a node $k$, first
we have to calculate the total number of triangles $T_{n}(k)$ which has $k$ as
one of the vertices. So,

$T_{n}(k)=\frac{1}{2}\sum_{\begin{subarray}{c}2\leq i,j\leq n\\\ i,j\neq
prime\\\ (i,k)=1\\\ (j,k)=1\\\ (i,j)=1\end{subarray}}\mathbf{1}.$

Now,

$\sum_{\begin{subarray}{c}2\leq i,j\leq n\\\ i,j\neq prime\\\ (i,k)=1\\\
(j,k)=1\\\ (i,j)=1\end{subarray}}\mathbf{1}=\sum_{\begin{subarray}{c}1\leq
i,j\leq n\\\ (i,k)=1\\\ (j,k)=1\\\
(i,j)=1\end{subarray}}\mathbf{1}-2\sum_{\begin{subarray}{c}i=1\\\
(i,k)=1\end{subarray}}^{n}\sum_{\begin{subarray}{c}p\leq n\\\ p\nmid i\\\
p\nmid k\end{subarray}}\mathbf{1}+\sum_{\begin{subarray}{c}p\leq n\\\ p\nmid
k\end{subarray}}\sum_{\begin{subarray}{c}q\leq n\\\ q\nmid i\\\ q\neq
p\end{subarray}}\mathbf{1}-2\sum_{\begin{subarray}{c}i=1\\\
(i,k)=1\end{subarray}}^{n}\mathbf{1}+2\sum_{\begin{subarray}{c}p\leq n\\\
p\nmid k\end{subarray}}\mathbf{1}+1.$ (4)

We can find the closed expressions for all the sums easily except the first
one, say $S_{1}$. So we get

$\sum_{\begin{subarray}{c}2\leq i,j\leq n\\\ i,j\neq prime\\\ (i,k)=1\\\
(j,k)=1\\\ (i,j)=1\end{subarray}}\mathbf{1}=\sum_{\begin{subarray}{c}1\leq
i,j\leq n\\\ (i,k)=1\\\ (j,k)=1\\\
(i,j)=1\end{subarray}}\mathbf{1}+2\sum_{\begin{subarray}{c}i=1\\\
(i,k)=1\end{subarray}}^{n}w(i)-\left[\pi(n)-w(k)\right]\left[2\phi(n,k)-\pi(n)+w(k)-1\right]-2\phi(n,k)+1.$
(5)

We can see that $S_{1}$ is the $r=2$ case of (3). Since,

$A_{2}=\prod_{p}\left(1-\frac{1}{p}\right)\left(1+\frac{1}{p}\right)=\prod_{p}\left(1-\frac{1}{p^{2}}\right)=\frac{1}{\zeta(2)}=\frac{6}{{\pi}^{2}},$
$f_{2}(k)=\prod_{p|k}\left(1-\frac{2}{p+1}\right)=\prod_{p|k}\left(\frac{p-1}{p+1}\right),$

So, we get

$S_{1}=\frac{6}{{\pi}^{2}}\prod_{p|k}\left(\frac{p-1}{p+1}\right)n^{2}+O(2^{w(k)}n\log{n}).$

Therefore,

$\begin{split}T_{n}(k)=&\frac{1}{2}\Big{[}\frac{6}{{\pi}^{2}}\prod_{p|k}\left(\frac{p-1}{p+1}\right)n^{2}-\left[\pi(n)-w(k)\right]\left[2\phi(n,k)-\pi(n)+w(k)-1\right]\\\
&\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ +2\sum_{\begin{subarray}{c}i=1\\\
(i,k)=1\end{subarray}}^{n}w(i)-2\phi(n,k)+O(2^{w(k)}n\log{n})\Big{]}.\end{split}$
(6)

So, the local clustering coefficient of node $k$,

$c(k)=\frac{T_{n}(k)}{\binom{d_{k}}{2}}.$ (7)

Now,

$T_{n}(k)\sim\frac{1}{2}\Big{[}\frac{6}{{\pi}^{2}}\prod_{p|k}\left(\frac{p-1}{p+1}\right)n^{2}-\left[\frac{n}{\log
n}-w(k)\right]\left[\frac{2n\phi(k)}{k}-\frac{n}{\log
n}+w(k)-1\right]+O(2^{w(k)}n\log{n})\Big{]},$

and

$\displaystyle\binom{d_{k}}{2}$
$\displaystyle=\frac{(\phi(n,k)-\pi(n)+w(k)-1)(\phi(n,k)-\pi(n)+w(k)-2)}{2}$
$\displaystyle\sim\frac{(\frac{n\phi(k)}{k}-\frac{n}{\log
n}+w(k)-1)(\frac{n\phi(k)}{k}-\frac{n}{\log n}+w(k)-2)}{2}.$

Therefore,

$\displaystyle c(k)$
$\displaystyle\sim\frac{\Big{[}\frac{6}{{\pi}^{2}}\prod_{p|k}\left(\frac{p-1}{p+1}\right)n^{2}-\left[\frac{n}{\log
n}-w(k)\right]\left[\frac{2n\phi(k)}{k}-\frac{n}{\log
n}+w(k)-1\right]+O(2^{w(k)}n\log{n})\Big{]}}{(\frac{n\phi(k)}{k}-\frac{n}{\log
n}+w(k)-1)(\frac{n\phi(k)}{k}-\frac{n}{\log n}+w(k)-2)}$
$\displaystyle=\frac{\Big{[}\frac{6}{{\pi}^{2}}\prod_{p|k}\left(\frac{p-1}{p+1}\right)-\left[\frac{1}{\log
n}-\frac{w(k)}{n}\right]\left[\frac{2\phi(k)}{k}-\frac{1}{\log
n}+\frac{w(k)}{n}-\frac{1}{n}\right]+O(2^{w(k)}\frac{\log{n}}{n})\Big{]}}{(\frac{\phi(k)}{k}-\frac{1}{\log
n}+\frac{w(k)}{n}-\frac{1}{n})(\frac{\phi(k)}{k}-\frac{1}{\log
n}+\frac{w(k)}{n}-\frac{2}{n})}$
$\displaystyle\sim\frac{6}{{\pi}^{2}}\prod_{p|k}\left(\frac{p-1}{p+1}\right)\left(\frac{k}{\phi(k)}\right)^{2}.$

Since $\phi(k)=k\prod_{p|k}(1-\frac{1}{p})$, so finally we have the form of
$c(k)$ as

$c(k)\sim\frac{6}{{\pi}^{2}}\prod_{p|k}\left(\frac{p^{2}}{p^{2}-1}\right).$
(8)

$\Box$

Figure 4: The average of the local clustering coefficients of the nodes is
plotted by changing the highest possible node index $n$. It shows the average
of the local clustering coefficients approaches near
$\frac{6}{{\pi}^{2}}(\approx 0.61)$ with the increase in $n$. We have used
log-scale for $x$-axis.

##  4 Weak Pseudo-randomness

In this section, we show that the proposed network is weakly pseudo-random.
Apart from the actual definition of weakly pseudo-random graphs, that is for a
real parameter $p=p(n)\in(0,1)$, a sequence of graphs $(G_{n})$ is weakly
pseudo-random [27] if for all subsets $U\subseteq V(G_{n})$, we have

$\left|E(U)-p\binom{|U|}{2}\right|=o(pn^{2}),$

we can also find some equivalent conditions to this in literature [33]. In
particular, we are interested in the following statement [27]: A graph is
weakly pseudo-random if and only if

$\sum_{x,y\in\mathbf{V}}\left|codeg(x,y)-p^{2}N\right|=o(N^{3}),$

where $N$ is the number of nodes and $codeg(x,y)$ is the number of common
neighbors of nodes $x$ and $y$.

Now, since

$codeg(x,y)=\sum_{i\in\mathbf{V}}\mathbf{1}[x\sim i]\mathbf{1}[y\sim
i]=\sum_{i\in\mathbf{V}}A[x,i]A[y,i]=A^{2}[x,y],$

where $A$ is the adjacency matrix of the graph. So, using Theorem 7, we get

$\sum_{x,y\in\mathbf{V}}codeg(x,y)^{2}=\sum_{x,y\in\mathbf{V}}[A^{2}\left[x,y]\right]^{2}=Tr(A^{4})=C_{n}(4)\leq\left(\frac{6n}{{\pi}^{2}}\right)^{4}+O(n^{3}\log^{3}n)=(pn)^{4}+o(n^{4}),$

where $p=\frac{6}{{\pi}^{2}}$. On the other hand,

$\displaystyle\sum_{x,y\in\mathbf{V}}codeg(x,y)$
$\displaystyle=\sum_{x,y\in\mathbf{V}}\sum_{i\in\mathbf{V}}\mathbf{1}[x\sim
i]\mathbf{1}[y\sim
i]=\sum_{i\in\mathbf{V}}\left[\sum_{x\in\mathbf{V}}\mathbf{1}[x\sim
i]\right]^{2}$
$\displaystyle=\sum_{i\in\mathbf{V}}deg(i)^{2}\geq\frac{\left[\sum_{i\in\mathbf{V}}deg(i)\right]^{2}}{N(n)}=N(n)\overline{d(n)}^{2}$
$\displaystyle=(n-\log n-1)\left[\frac{6}{{\pi}^{2}}n+O\left(\frac{n}{(\log
n)^{2}}\right)\right]^{2}=p^{2}n^{3}+o(n^{3}).$

Now, using Cauchy-Schwarz inequality, we get

$\sum_{x,y\in\mathbf{V}}\left|codeg(x,y)-p^{2}N(n)\right|\leq
N(n)\left[\sum_{x,y\in\mathbf{V}}\left(codeg(x,y)-p^{2}N(n)\right)^{2}\right]^{1/2}$
$=N(n)\left[\sum_{x,y\in\mathbf{V}}codeg(x,y)^{2}-2p^{2}N(n)\sum_{x,y\in\mathbf{V}}codeg(x,y)+p^{4}N(n)^{4}\right]^{1/2}$
$\leq
N(n)\left[(pn)^{4}+o(n^{4})-2p^{2}N(n)(p^{2}n^{3}+o(n^{3}))+p^{4}N(n)^{4}\right]^{1/2}.$

Therefore,

$\sum_{x,y\in\mathbf{V}}\left|codeg(x,y)-p^{2}N(n)\right|=o(N(n)^{3}).$

Therefore, this sequence of graphs is weakly pseudo-random with
$p=\frac{6}{{\pi}^{2}}$.

Now, we can directly use the other equivalent conditions[27] to the weak
pseudo-randomness and infer other properties of this network. For instance,
given a graph $L$ of $l\geq 4$ vertices, let $N_{G}^{*}(L)$ be the number of
labeled induced copies of $L$ in a weakly pseudo-random graph, $G$ with $n$
vertices, then

$N_{G}^{*}(L)=(1+o(1))n^{l}p^{|E(L)|}(1-p)^{\binom{l}{2}-|E(L)|}.$ (9)

Taking $L$ to be $r$-length cycle for $r\geq 4$ in (9), we get

$C_{n}(r)=(1+o(1))(N(n))^{r}p^{r}(1-p)^{\frac{r(r-3)}{2}}.$

So, we get a cycle of length $r$ if $N(n)p(1-p)^{\frac{(r-3)}{2}}\geq 1$. This
indicates the existence of a cycle of length $O(\log n)$ for large $n$ as
$p=\frac{6}{{\pi}^{2}}$ is constant.

Again from [27], we get weak pseudo-randomness implies that the maximum
eigenvalue of the adjacency matrix, $\lambda_{1}=(1+o(1))N(n)p$, which is also
evident from Fig:5.

Figure 5: The ratio of the maximum eigenvalue $\lambda_{1}$ of the adjacency
matrix and N(n)p is plotted by changing the highest possible node index $n$.
The ratio approaching 1 provides evidence to $\lambda_{1}=(1+o(1))N(n)p$.

##  5 Discussion and possible applications

In this paper, we have constructed a network with nodes indexed by the
composite numbers and we defined the adjacency of two nodes when their indices
are coprime to each other. As the size of the network increases by adding
nodes one by one to the network starting from the one with index 4, we have
noticed a number of interesting behaviors in some of the statistics that we
have found. We have seen that the link density saturates to
$\frac{6}{{\pi}^{2}}$ and the average degree of the nodes increase linearly
with the increment in $n$, which is the highest possible node index, with
slope again $\frac{6}{{\pi}^{2}}$. This behavior actually supports a well
known result in Number Theory that the probability that two randomly chosen
natural numbers are relatively prime is $\frac{6}{{\pi}^{2}}$ [41]. It also
refers that for large $n$, $\frac{6}{{\pi}^{2}}$(i.e., $60.79\%$) of the total
number of possible edges will be present in the network. We have also seen
that the network will not have any isolated vertex when $n\geq 49$ that means
after this point the network will be connected and starting from any vertex it
will always be possible to visit all the other vertices in this network. But
starting from a given vertex, what is the minimum number of vertices we need
to visit in order to reach a target vertex? We have proved in this context
that the shortest path length between any two nodes will be at most 3 when
$49\leq n\leq 288$ and it is at most 2 for $n\geq 289$. A very interesting
graph property is the existence of Hamiltonian cycles of a given length, that
is the cycles of a specific length that doesn’t visit any vertex more than
once. We have found that the number of these cycles of $r$-length is
$(1+o(1))(N(n))^{r}p^{r}(1-p)^{\frac{r(r-3)}{2}}$ for large $n$. But for a
fixed $n$, as we increase the length $r$ of the cycles, this asymptotic number
of cycles starts dropping and eventually becomes less than $1$, which suggests
us to investigate what is the maximum possible length of a cycle that may
exist in the proposed network. We found that there exists a cycle of length at
most $O(\log n)$ for large $n$. Also for a given vertex, while investigating
the connectivity between its neighbors, we have found a measure named local
clustering coefficient $c(k)$ of a node $k$, which is the proportion of the
total number of triangle whose one vertex is that node itself to the total
number of possible triangles with that node as a vertex. We have shown that
for large $n$,

$c(k)\sim\frac{6}{{\pi}^{2}}\prod_{p|k}\left(\frac{p^{2}}{p^{2}-1}\right),$

which suggests as the size of the network increases, more than
$\frac{6}{{\pi}^{2}}(i.e.,\leavevmode\nobreak\ 60.79\%$) of the neighbors of
any node will be connected to each other.

Though the construction of this network being completely deterministic, it’s
study will still be as interesting and as important as the other random
networks because of the irregular distribution of primes over natural numbers
which makes the coprimality of two nodes to be irregular too. Following
Krivelevich and Sudakov [27] and using some previously discussed results, we
have shown that the graph sequence namely coprime networks of composite
numbers is weakly pseudo-random, which again supports the property that two
integers being relative prime is random-like and that is actually a very
strong motif in analytic number theory.

Figure 6: The variation of the second eigenvalue $\lambda_{2}$ of the
Laplacian matrix is plotted by changing the highest possible node index $n$.
It is observed that the value of $\lambda_{2}$ is increasing with the
increased value of node indices, which provides evidence of the high
connectivity in the constructed network. Figure 7: The ratio of $N$th and 2nd
eigenvalues of the Laplacian matrix is plotted with respect to the highest
possible node index $n$ for the constructed coprime network of composite
numbers and is compared with Erdős–Rényi random network and Barabási-Albert
scale-free network with the same number of nodes $N(n)$ and edges $E(n)$. This
figure suggests less synchronizability in the proposed network as compared to
the other two.

One of the possible application to use any network configuration is to study
collective behavior, namely synchronization, in dynamical networks. The
synchronizability of a network is depended on the eigenvalues of the zero-row-
sum real Laplacian matrix $L$. If $L$ is a $N\times N$ matrix then its
eigenvalues satisfies $0=\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{N}.$
The smaller values of $\frac{\lambda_{N}}{\lambda_{2}}$ gives the more
synchronizability in the network and vice-versa [43, 44, 35]. We first
calculate the second eigenvalue $\lambda_{2}$ of $L$ of the constructed
coprime network of composite numbers by changing the highest possible node
index $n$, shown in Fig.6. From this figure, it is noticed that the value of
$\lambda_{2}$ increases as we increase the number of nodes and the
corresponding links, which gives an evidence of the high connectivity in the
constructed network. Then we calculate the ratio
$\frac{\lambda_{N}}{\lambda_{2}}$ in order to see the synchronizability in the
network by varying the highest possible node index $n$. Next we compare the
synchronizability of the constructed coprime network of composite numbers with
two other networks, namely Erdős–Rényi random network and Barabási-Albert
network with the same number of nodes $N(n)$ and edges $E(n)$. Comparing with
these two networks, we can notice that the synchronizability in the coprime
networks of composite numbers is less from Fig.7. This less synchronizability
is very much desirable in ecological and predator-prey networks to increase
prolonged transient dynamics [45].

##  6 Conclusion

In this paper, we have studied a network which we have constructed by taking
all the composite numbers in a given range starting from 4 and drawing an
undirected link between two of them if they are coprime to each other.
Therefore, the nodes having same set of prime divisors will have exactly same
neighbors, hence same degree and same value of local clustering coefficients.
Among them, the prime powers have larger number of neighbors. We have shown
that the network will be connected if the largest possible node index $n\geq
49$ and the maximum of the shortest path lengths is 3 if $n$ lies between 49
and 288, whereas it is 2 if $n\geq 289$. We have also derived the analytic
expressions for the maximum degree, the average degrees of the nodes, link
density and local clustering coefficients of the nodes. Also, we have found an
expression for the number of $r$-length labeled cycles. Finally, we show that
the constructed network is weakly pseudo-random. The root cause of this is the
coprimality of two integers is random-like.

Also, we have seen that this network has less synchronizability which is
noticed in ecological and predator-prey networks. Someone can also try to find
the degree distribution, i.e., if we choose a node randomly, then what is the
probability that it would have degree $m$,

$\mathbb{P}(m)=\frac{|\\{k\in V:d_{k}=m\\}|}{n-\pi(n)-1}=\frac{|\\{k\in
V:\phi(n,k)+w(k)=m+\pi(n)+1\\}|}{n-\pi(n)-1}.$

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Data availability

No data was used for the research described in the article.

## Remarks

The codes of the plots can be found in https://github.com/Rahil-Miraj/Coprime-
Networks-of-Composite-Numbers.git.

## Acknowledgments

The authors would like to thank Sudipta Mallik, Parthanil Roy, B. Sury and
Niranjan Balachandran for their suggestions and Subrata Ghosh for helping in
the simulations.

## Appendix

In this appendix, we state some results which we have used in the context of
proving the results throughout the paper.

###### Lemma 1

For $x>1$, we have [41]

$\sum_{k\leq x}\phi(k)=\frac{3}{{\pi}^{2}}x^{2}+O(x\log x).$

###### Lemma 2

For $x\geq 1$, we have [46]

$\sum_{k\leq x}\omega(k)=x\log\log x+B_{1}x+O(x),$

where $B_{1}\approx 0.2614972128$ is the Mertens constant.

###### Lemma 3

For $x\geq 1$, we have [46]

$\sum_{k\leq x}\omega(k)^{2}=x(\log\log x)^{2}+O(x\log\log x).$

###### Lemma 4

For $x>2$, we have

$\sum_{k\leq x}\pi(k)={\lfloor x\rfloor}\pi(x)-\sum_{p\leq x}p.$

Proof. Let $m=\pi(x)$. Then,

$\displaystyle\sum_{k\leq x}\pi(k)$ $\displaystyle=\sum_{k=2}^{{\lfloor
x\rfloor}}\pi(k)=\sum_{i=2}^{m}(p_{i}-p_{i-1})\pi(p_{i})+({\lfloor
x\rfloor}-p_{m})(\pi(p_{m})+1)$
$\displaystyle=\sum_{i=2}^{m}(p_{i}-p_{i-1})(i-1)+({\lfloor
x\rfloor}-p_{m})((m-1)+1)$
$\displaystyle=\sum_{i=2}^{m}ip_{i}-\sum_{i=2}^{m}(i-1)p_{i-1}-\sum_{i=2}^{m}p_{i}+m({\lfloor
x\rfloor}-p_{m})$ $\displaystyle=m{\lfloor x\rfloor}-\sum_{i=1}^{m}p_{i}.$

$\Box$

###### Lemma 5

Let $t\geq 2$ be an integer. Then, for $s\geq 2$, whenever
$p_{1}p_{t}p_{t+1}.....p_{s}>p_{s+1}^{2}$ with $p_{1}=2,p_{2}=3$ and so on, we
will have $p_{1}p_{t}p_{t+1}.....p_{s+1}>p_{s+2}^{2}$.

Proof. Let $p_{1}p_{t}p_{t+1}.....p_{s}>p_{s+1}^{2}$. Then,

$p_{1}p_{t}.....p_{s}p_{s+1}>p_{s+1}^{3}.$ (10)

Now, from Bertrand’s postulate [47], there is a prime between $x$ and $2x$ for
all $x>1$, so

$p_{s+1}<p_{s+2}<2p_{s+1},$ $p_{s+2}^{2}<4p_{s+1}^{2}<p_{s+1}^{3},$

if $p_{s+1}>4$, i.e., $p_{s+1}\geq 5=p_{3}$.

Therefore, (10) gives

$p_{1}p_{t}p_{t+1}.....p_{s+1}>p_{s+2}^{2},$

for $s\geq 2$.

$\Box$

###### Lemma 6

Let $t\geq 3$ be an integer. Then, $p_{1}p_{t-1}p_{t}p_{t+1}>p_{t+2}^{2}$.

Proof. We can easily check that this holds true for $t=3$ and $t=4$. Now,
using Bertrand’s postulate again, we get $p_{1}p_{t+1}=2p_{t+1}>p_{t+2}$. Now,
since $11=p_{5}$ is the $2^{nd}$ Ramanujan prime [47],
$p_{t-1}p_{t}>2p_{t}>p_{t+2}$ for $t\geq 5$. So, combining these two results,
we get $p_{1}p_{t-1}p_{t}p_{t+1}>p_{t+2}^{2}$ for $t\geq 5$.

$\Box$

###### Lemma 7

For an integer $t\geq 6$, $p_{1}p_{2}....p_{t-1}>p_{t+2}^{2}$.

Proof. Let us consider the sequence, $\\{a_{t}\\}_{t=2}^{\infty}$, defined as
$a_{t}=p_{1}p_{2}....p_{t-1}-p_{t+2}^{2}$. Then we will have

$a_{t+1}=p_{1}p_{2}....p_{t}-p_{t+3}^{2}>p_{1}p_{2}....p_{t}-p_{t}p_{t+2}^{2}=p_{t}(p_{1}p_{2}....p_{t-1}-p_{t+2}^{2})=p_{t}a_{t}>a_{t},$

for $t>3$, since, $p_{t}p_{t+2}^{2}>4p_{t+2}^{2}>p_{t+3}^{2}$, again from
Bertrand’s postulate. Therefore, $\\{a_{t}\\}$ is increasing for $t\geq 4$ and
since we get the first positive value of $a_{t}$ at $t=6$, we conclude that
for $t\geq 6$, we will always get $p_{1}p_{2}....p_{t-1}>p_{t+2}^{2}$.

$\Box$

###### Lemma 8

For $x\geq 2$ and $r\geq 4$, we have

$\left(1-\frac{1}{x}\right)^{r-1}\left(1+\frac{r-1}{x}\right)\leq\left(1-\frac{1}{x^{2}}\right)^{r}.$

Proof. It is enough to show that

$\left(1+\frac{r-1}{x}\right)\leq\left(1-\frac{1}{x}\right)\left(1+\frac{1}{x}\right)^{r}$

holds for $x\geq 2$ and $r\geq 4$.

Let
$f(r,x)=\left(1-\frac{1}{x}\right)\left(1+\frac{1}{x}\right)^{r}-\left(1+\frac{r-1}{x}\right)$.
We will show that $f(r,x)$ is increasing in $r$ for $r\geq 4$ and $x\geq 2$
and $\min_{r\geq 4}f(r,x)=f(4,x)\geq 0$ for $x\geq 2$.

We have

$\frac{\partial f}{\partial
r}=\left(1-\frac{1}{x}\right)\left(1+\frac{1}{x}\right)^{r}\log
r-1/x>1-1/x>0,$

for $r\geq 4$ and $x\geq 2$. Hence, $f(r,x)$ is increasing in $r$ for $r\geq
4$ and $x\geq 2$.

Now, suppose for some $x\geq 2$, we will get $f(4,x)<0$. Then since
$f(4,2)=0.0313>0$, $f(4,x)=\frac{1}{x^{5}}(2x^{3}-2x^{2}-3x-1)$ will have a
zero in $x>2$. Then $2x^{3}-2x^{2}-3x-1$ will have a zero in $x>2$. But
$2x^{3}-2x^{2}-3x-1$ is increasing for $x>2$ as
$\frac{d(2x^{3}-2x^{2}-3x-1)}{dx}=6x^{2}-4x-3>0$ and takes value $1$ for
$x=2$, a contradiction.

$\Box$

## References

  * Newman [2010] M. Newman, Networks: an introduction, Oxford University Press, 2010.
  * Albert and Barabási [2002] R. Albert, A.-L. Barabási,  Statistical mechanics of complex networks,  Reviews of Modern Physics 74 (2002) 47.
  * Pastor-Satorras et al. [2003] R. Pastor-Satorras, M. Rubi, A. Diaz-Guilera, Statistical mechanics of complex networks, volume 625, Springer Science & Business Media, 2003.
  * Boccaletti et al. [2006] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang,  Complex networks: Structure and dynamics,  Physics Reports 424 (2006) 175–308.
  * Arenas et al. [2008] A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, C. Zhou,  Synchronization in complex networks,  Physics Reports 469 (2008) 93–153.
  * Barrat et al. [2008] A. Barrat, M. Barthelemy, A. Vespignani, Dynamical processes on complex networks, Cambridge University Press, 2008\.
  * Cohen and Havlin [2010] R. Cohen, S. Havlin, Complex networks: structure, robustness and function, Cambridge University Press, 2010.
  * Battiston et al. [2021] F. Battiston, E. Amico, A. Barrat, G. Bianconi, G. Ferraz de Arruda, B. Franceschiello, I. Iacopini, S. Kéfi, V. Latora, Y. Moreno, et al.,  The physics of higher-order interactions in complex systems,  Nature Physics 17 (2021) 1093–1098.
  * Hens et al. [2019] C. Hens, U. Harush, S. Haber, R. Cohen, B. Barzel,  Spatiotemporal signal propagation in complex networks,  Nature Physics 15 (2019) 403–412.
  * Gao et al. [2016] J. Gao, B. Barzel, A.-L. Barabási,  Universal resilience patterns in complex networks,  Nature 530 (2016) 307–312.
  * Barzel and Barabási [2013] B. Barzel, A.-L. Barabási,  Universality in network dynamics,  Nature Physics 9 (2013) 673–681.
  * Meena et al. [2023] C. Meena, C. Hens, S. Acharyya, S. Haber, S. Boccaletti, B. Barzel,  Emergent stability in complex network dynamics,  Nature Physics 19 (2023) 1033–1042.
  * Artime et al. [2024] O. Artime, M. Grassia, M. De Domenico, J. P. Gleeson, H. A. Makse, G. Mangioni, M. Perc, F. Radicchi,  Robustness and resilience of complex networks,  Nature Reviews Physics (2024) 1–18.
  * Borgatti et al. [2009] S. P. Borgatti, A. Mehra, D. J. Brass, G. Labianca,  Network analysis in the social sciences,  Science 323 (2009) 892–895.
  * Menck et al. [2013] P. J. Menck, J. Heitzig, N. Marwan, J. Kurths,  How basin stability complements the linear-stability paradigm,  Nature Physics 9 (2013) 89–92.
  * Wang et al. [2019] W. Wang, Q.-H. Liu, J. Liang, Y. Hu, T. Zhou,  Coevolution spreading in complex networks,  Physics Reports 820 (2019) 1–51.
  * Pastor-Satorras et al. [2015] R. Pastor-Satorras, C. Castellano, P. Van Mieghem, A. Vespignani,  Epidemic processes in complex networks,  Reviews of Modern Physics 87 (2015) 925.
  * Donohue et al. [2016] I. Donohue, H. Hillebrand, J. M. Montoya, O. L. Petchey, S. L. Pimm, M. S. Fowler, K. Healy, A. L. Jackson, M. Lurgi, D. McClean, et al.,  Navigating the complexity of ecological stability,  Ecology Letters 19 (2016) 1172–1185.
  * Bullmore and Sporns [2012] E. Bullmore, O. Sporns,  The economy of brain network organization,  Nature Reviews Neuroscience 13 (2012) 336–349.
  * Ji et al. [2023] P. Ji, J. Ye, Y. Mu, W. Lin, Y. Tian, C. Hens, M. Perc, Y. Tang, J. Sun, J. Kurths,  Signal propagation in complex networks,  Physics Reports 1017 (2023) 1–96.
  * Barabasi and Oltvai [2004] A.-L. Barabasi, Z. N. Oltvai,  Network biology: understanding the cell’s functional organization,  Nature Reviews Genetics 5 (2004) 101–113.
  * Shekatkar et al. [2015] S. M. Shekatkar, C. Bhagwat, G. Ambika,  Divisibility patterns of natural numbers on a complex network,  Scientific Reports 5 (2015) 1–10.
  * Garcia-Perez et al. [2014] G. Garcia-Perez, M. Á. Serrano, M. Boguná,  Complex architecture of primes and natural numbers,  Physical Review E 90 (2014) 022806.
  * Solares-Hernández et al. [2020] P. A. Solares-Hernández, F. A. Manzano, F. J. Pérez-Benito, J. A. Conejero,  Divisibility patterns within pascal divisibility networks,  Mathematics 8 (2020) 254.
  * Chandra and Dasgupta [2005] A. K. Chandra, S. Dasgupta,  A small world network of prime numbers,  Physica A: Statistical Mechanics and its Applications 357 (2005) 436–446.
  * Thomason [1987] A. Thomason,  Pseudo-random graphs,  in: North-Holland Mathematics Studies, volume 144, Elsevier, 1987, pp. 307–331.
  * Krivelevich and Sudakov [2006] M. Krivelevich, B. Sudakov,  Pseudo-random graphs,  More sets, graphs and numbers: A Salute to Vera Sos and András Hajnal (2006) 199–262.
  * Alon and Milman [1985] N. Alon, V. D. Milman,  $\lambda$1, isoperimetric inequalities for graphs, and superconcentrators,  Journal of Combinatorial Theory, Series B 38 (1985) 73–88.
  * Alon [1986] N. Alon,  Eigenvalues and expanders,  Combinatorica 6 (1986) 83–96.
  * Alon and Spencer [2016] N. Alon, J. H. Spencer, The probabilistic method, John Wiley & Sons, 2016\.
  * Kühn and Osthus [2006] D. Kühn, D. Osthus,  Multicolored hamilton cycles and perfect matchings in pseudorandom graphs,  SIAM Journal on Discrete Mathematics 20 (2006) 273–286.
  * Krivelevich et al. [2010] M. Krivelevich, C. Lee, B. Sudakov,  Resilient pancyclicity of random and pseudorandom graphs,  SIAM Journal on Discrete Mathematics 24 (2010) 1–16.
  * Chung et al. [1989] F. R. K. Chung, R. L. Graham, R. M. Wilson,  Quasi-random graphs,  Combinatorica 9 (1989) 345–362.
  * Barabási [2013] A.-L. Barabási,  Network science,  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 371 (2013) 20120375.
  * Barahona and Pecora [2002] M. Barahona, L. M. Pecora,  Synchronization in small-world systems,  Physical Review Letters 89 (2002) 054101.
  * Pecora and Carroll [1998] L. M. Pecora, T. L. Carroll,  Master stability functions for synchronized coupled systems,  Physical Review Letters 80 (1998) 2109.
  * Nishikawa et al. [2003] T. Nishikawa, A. E. Motter, Y.-C. Lai, F. C. Hoppensteadt,  Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?,  Physical Review Letters 91 (2003) 014101.
  * Osipov et al. [2007] G. V. Osipov, J. Kurths, C. Zhou, Synchronization in oscillatory networks, Springer Science & Business Media, 2007\.
  * Pikovsky et al. [2001] A. Pikovsky, M. Rosenblum, J. Kurths,  Synchronization cambridge university press,  Cambridge, England (2001).
  * Dai et al. [2020] X. Dai, X. Li, H. Guo, D. Jia, M. Perc, P. Manshour, Z. Wang, S. Boccaletti,  Discontinuous transitions and rhythmic states in the d-dimensional kuramoto model induced by a positive feedback with the global order parameter,  Physical Review Letters 125 (2020) 194101.
  * Apostol [1998] T. M. Apostol, Introduction to analytic number theory, Springer Science & Business Media, 1998\.
  * Tóth [2002] L. Tóth,  The probability that k positive integers are pairwise relatively prime,  Fibonacci Quart 40 (2002) 13–18.
  * Jafarizadeh et al. [2020] S. Jafarizadeh, F. Tofigh, J. Lipman, M. Abolhasan,  Optimizing synchronizability in networks of coupled systems,  Automatica 112 (2020) 108711.
  * Tang et al. [2014] Y. Tang, F. Qian, H. Gao, J. Kurths,  Synchronization in complex networks and its application–a survey of recent advances and challenges,  Annual Reviews in Control 38 (2014) 184–198.
  * Holland and Hastings [2008] M. D. Holland, A. Hastings,  Strong effect of dispersal network structure on ecological dynamics,  Nature 456 (2008) 792–794.
  * Hardy et al. [1979] G. H. Hardy, E. M. Wright, et al., An introduction to the theory of numbers, Oxford university press, 1979.
  * Sondow [2009] J. Sondow,  Ramanujan primes and bertrand’s postulate,  The American Mathematical Monthly 116 (2009) 630–635.