# Impact of network topology changes on information source localization

Piotr Machura, Robert Paluch

###### Abstract

Well-established methods of locating the source of information in a complex
network are usually derived with the assumption of complete and exact
knowledge of network topology. We study the performance of three such
algorithms (LPTVA, GMLA and Pearson correlation algorithm) in scenarios that
do not fulfill this assumption by modifying the network prior to localization.
This is done by adding superfluous new links, hiding existing ones, or
reattaching links in accordance with the network’s structural Hamiltonian. We
find that GMLA is highly resilient to the addition of superfluous edges, as
its precision falls by more than statistical uncertainty only when the number
of links is approximately doubled. On the other hand, if the edge set is
underestimated or reattachment has taken place, the performance of GMLA drops
significantly. In such a scenario the Pearson algorithm is preferable,
retaining most of its performance when other simulation parameters favor
localization (high density of observers, highly deterministic propagation). It
is also generally more accurate than LPTVA, as well as orders of magnitude
faster. The aforementioned differences between localization algorithms can be
intuitively explained, although a need for further theoretical research is
noted.

##### Keywords:

complex network, information propagation, source localization, exponential
random graphs

##  1 Introduction

The exchange of information is the main purpose of many networks found in our
everyday life. The creation of the Internet enabled its users to communicate
on an unprecedented scale. The rapid rise in the usage of social media [1]
fundamentally changed the way we view and absorb the information presented to
us by acquaintances and news publishers alike. The emergence of clickbait [2]
promotes sensation over honesty, encouraging the usage of exaggeration and
deceit in the name of profitable engagement [3]. Due to the instantaneous
nature of social media misinformation propagates in a flash, reaching a wide
audience of users. As a result we, the recipients, are often unaware of the
true origin of viral gossip we encounter, making it difficult to judge and
interpret properly.

The scientific community has taken it upon itself to solve this dilemma, by
establishing methods to identify and combat the spread of misinformation [4,
5]. In this manner, the topic of source location is of crucial importance.
Knowing where a specific piece of information came from can aid in identifying
its purpose and reliability.

Among various types of localization methods, categorized by Jiang et al. [6],
observer-based localization methods are especially popular due to their
relatively low requirements. They can accurately pinpoint the source of
information using data provided by only a few members of the network, together
with the knowledge of its structure. When deriving localization methods, it is
usually assumed that this structure (network topology) is known completely and
exactly. We propose a set of scenarios, outlined in Section 3, in which this
assumption does not hold. That is, the network in which the information has
spread is not the same as the network used during localization. This may be
due to errors made during network reconstruction, lack of knowledge regarding
the full structure, or natural evolution occurring between the time of
propagation and the moment in which the network is recorded.

Examining the simulation performance of three popular source localization
algorithms, outlined in Section 2.2, we seek to find and describe the
qualitative differences between them. Results of such simulations can
potentially aid in choosing the right algorithm for a real-world situation, in
which the “correctness” of the reconstructed network is uncertain.

##  2 Basics

We assume a simple agent-based model, in which $N$ agents are located in the
vertices of a complex network, i.e. an unweighted, undirected graph
$\mathcal{G}=(V,E)$. Edges of such graphs represent a bi-directional
connection through which information may propagate.

###  2.1 Information spread

To simulate the spread of information, we use the synchronous Susceptible-
Infected (SI) model [7]. In the SI model, each node can be in one of two
states: susceptible/healthy (uninformed) or infected (informed). In the
beginning, all nodes are healthy. At some unknown point in time, $t^{*}$ a
single randomly chosen node becomes spontaneously infected. We will refer to
this node as the source of information, denoted $s^{*}$. In every subsequent
time step, infected nodes will try to infect their susceptible neighbors, with
a probability of success $\beta$, called infection rate. The propagation ends
when there are no more healthy nodes in the network. It is assumed that the
network is connected (i.e. there is a path between each pair of nodes) during
the spread. After the propagation completes and the network topology is
changed (see Section 3) this assumption no longer holds.

Figure 1: Illustration of the simulation methodology.  a) At an unknown time
$t^{*}$ the source $s^{*}$ is spontaneously infected.  b) Information
propagates through the network. Infection times $t_{i}$ of chosen nodes
(observers $o_{i}$) are recorded.  c) Network undergoes topological changes.
Some existing edges are removed (dotted line) and some are added (double
line), producing the modified network. The graph may become disconnected in
the process.  d) The modified network is cropped to the largest component
before the source localization algorithm is run.

###  2.2 Locating the source

We consider observer-based methods of source localization. These algorithms
are popular in the literature [8, 9, 10, 11, 12] due to their realistic
assumptions, making possible real-world implementation and usage. The observer
nodes provide some limited knowledge about the spread after it has concluded.
They may represent e.g. social media moderators capable of providing insight,
or individual users reporting their encounters with concerning content.

In our simulations observers form a randomly chosen subset of graph vertices
$\mathcal{O}\subseteq V$, with the ratio $r=|\mathcal{O}|/|V|$ called observer
density. It is assumed that each observer $o_{i}$ measures the time of its
infection $t_{i}$. This is notably different from assumptions made by Pinto
et. al. [8] and Xu, Teng, Zheou et al. [13], where both the observer infection
time and the node by which the observer was infected are known. We find that
this limited approach can still result in satisfactory algorithm performance,
while significantly reducing the amount of information required to perform
localization.

Source localization algorithm assigns a score to every suspect node $s\in
S\subseteq V$ (including observers), given the vector of observer infection
times $[\mathbf{t}]_{i}=t_{i}$, infection rate $\beta$ and graph topology. It
is therefore equivalent to a score function
$\phi(s;\mathbf{t},\beta,\mathcal{G})$. Intuitively, $\phi(s)$ should be
associated with the posterior probability of $s$ being the true source
$s^{*}$, that is

$\mathbb{P}(s=s^{*}|\mathbf{t},\mathcal{G})\sim
f(\phi(s;\mathbf{t},\beta,\mathcal{G})),$ (1)

where $f$ is any strictly increasing function. This allows for ranking
suspects by their score, with the highest scoring suspect

$\hat{s}=\operatorname*{argmax}_{s}\phi(s;\mathbf{t},\beta,\mathcal{G})$ (2)

being the most probable origin of the information. If it is true that
$\hat{s}=s^{*}$ then the localization is successful. See Section 2.2.4 for
further details on evaluating localization algorithms.

####  2.2.1 Maximum likelihood algorithm

The maximum likelihood algorithm has been proposed by Pinto et al in [8]. We
will refer to it as LPTVA (Limited Pinto-Thiran-Vitelli Algorithm), with
limited signifying the fact that only infection times $t_{i}$ are used. It is
analytically derived for tree graphs and extended to general graphs in the way
outlined below.

The unknown inception time $t^{*}$ is accounted for by choosing a reference
observer $o_{1}$ and constructing a vector of infection delays
$\mathbf{t}^{\prime}$ with respect to $t_{1}$

$[\mathbf{t}^{\prime}]_{i}=t_{i+1}-t_{1}.$ (3)

If we assume that the graph in question is a tree $\mathcal{T}$ and let
$P(v_{i},v_{j})$ denote the path between vertices $v_{i}$, $v_{j}$, the
expected value for the $\mathbf{t}^{\prime}$ vector (given $s$ is the source)
can be written as

$[\boldsymbol{\mu}_{s}]_{i}=\mu\left(|P(s,o_{i+1})|-|P(s,o_{1})|\right),$ (4)

where $\mu$ is the mean time it takes for information to transmit through one
edge. In the case of the SI model it is equal to the mean of a geometric
distribution $\mu=\frac{1}{\beta}$. The covariance matrix $\Lambda$ of
$\mathbf{t}^{\prime}$ is given by

$[\Lambda]_{i,j}=\sigma^{2}|P(o_{i+1},o_{1})\cap P(o_{j+1},o_{1})|,$ (5)

where $\sigma^{2}$ is the variance of the time it takes for information to
transmit through one edge. In the case of SI model it is equal to variance of
a geometric distribution $\sigma^{2}=\frac{1-\beta}{\beta^{2}}$.

Using the central limit theorem, we can postulate that $\mathbf{t}^{\prime}$,
as a sum of i.i.d. single-edge delays, follows a multivariate normal
distribution with mean $\boldsymbol{\mu}_{s}$ and covariance matrix $\Lambda$.
Taking a logarithm of this distribution and stripping away $s$-independent
normalization factors we arrive at the score function

$\phi_{\text{LPTVA}}(s)=-(\mathbf{t}^{\prime}-\boldsymbol{\mu}_{s})^{T}\Lambda^{-1}(\mathbf{t}^{\prime}-\boldsymbol{\mu}_{s})-\ln|\Lambda|,$
(6)

which can be calculated for all nodes in the network.

If the graph in question is not a tree, the algorithm can be adjusted by
calculating the score given by (6) with respect to the breadth-first search
(BFS) tree $\mathcal{T}^{(s)}_{BFS}$ rooted at $s$. Such modification is
equivalent to the assumption that the information propagates along the
shortest paths connecting the source with observers. This holds exactly when
$\beta=1$ and contributes to significantly reduced algorithm performance for
non-tree graphs with $\beta$ significantly lower than 1.

####  2.2.2 Gradient maximum likelihood algorithm

The LPTV algorithm, while well established and highly analytical, suffers from
significant computation speed issues. Matrix inversion in equation (6) must be
performed for each suspect, rendering the method effectively unusable for
networks with a large number of nodes.

The gradient maximum likelihood algorithm (GMLA) [9] attempts to rectify this
problem by prioritizing the earliest observers and utilizing a gradient-like
selection of suspects. As a consequence, unlike in the case of LPTVA and
Pearson correlation algorithm, the set of suspects is generally only a small
subset of all nodes in the network. All other nodes
$\widetilde{v}\in(V\setminus S)$ are assigned the same score, effectively
equal $-\infty$. While the score function used to rank suspects in GMLA is the
same as (6), the choice of suspects is much more sophisticated.

Firstly, only $K_{f}$ earliest-infected observers are used in the
calculations. The performance of the algorithm varies depending on the exact
value of $K_{f}$, with the optimum usually estimated for each network model on
a case-by-case basis. In our calculations we have used $K_{f}=\sqrt{N}$ for
all considered networks, which is an acceptable rule of thumb [9].

Secondly, the score function is not calculated for all $N$ vertices. Instead,
it is first calculated for the neighbors $S^{(1)}$ of the earliest observer
$o_{1}$. Next, the score is calculated for the previously unchecked neighbors
of the highest scoring $\hat{s}^{(1)}$ from $S^{(1)}$, creating another set of
suspects $S^{(2)}$, from which the highest scoring $\hat{s}^{(2)}$ is chosen.
This process is repeated until there is no node in $S^{(n)}$ (neighbors of
$\hat{s}^{(n-1)}$ not checked in previous steps) with score higher than
$\hat{s}^{(n-1)}$. In such case, the algorithm stops and returns scores
calculated for all members of

$S=\bigcup\limits_{i=1}^{n}S^{(i)}.$ (7)

Empirical studies suggest that the total number of suspects roughly follows
$|S|\sim\hat{k}\log N$, where $\hat{k}$ is the average degree in the network.
Fig. 2 illustrates this gradient-like selection process.

Figure 2: Node selection in GMLA. Initially, the neighbors of the earliest
informed neighbor $o_{1}$ are checked ($S^{(1)}$, colored orange). Highest
scoring vertex $\hat{s}^{(1)}$ from this set is chosen, and its neighbors
$S^{(2)}$ are checked (colored blue). Note that $o_{1}$ is included in
$S^{(2)}$. Next, neighbors $S^{(3)}$ of $\hat{s}^{(2)}$ (colored purple) are
checked, among which highest scoring vertex $\hat{s}^{(3)}$ can be found.
Since the score of $\hat{s}^{(3)}$ is lower than that of $\hat{s}^{(2)}$, the
algorithm terminates with $\hat{s}=\hat{s}^{(2)}$. The final suspect set
consist of all colored nodes $S=S^{(3)}\cup S^{(2)}\cup S^{(1)}$. White
vertexes remain unchecked and are placed at the bottom of the ranking, at
position $N+1$, where $N$ is the size of the network.

GMLA ensures that nodes near high-scoring suspects are checked, while those
far away are ignored, significantly reducing computation time. Using only
$K_{f}$ first observers also proves to be highly beneficial, bringing the
overall localization capability of GMLA in line with, or even exceeding, that
of LPTVA [10].

####  2.2.3 Pearson correlation algorithm

Proposed by Xu, Teng, Zheou et al. [13], the correlation algorithm stands out
as an extremely straightforward, yet highly performant method. If we assume
that the information propagates along the shortest path connecting the source
to observers (which is also an assumption required for extending LPTVA to
general graphs), then it should be intuitively obvious that the higher the
distance from an observer to the source, the longer it takes for this observer
to become infected.

More precisely, in the case of true source $s^{*}$, the vector of infection
times $\mathbf{t}$ should be correlated with the vector of distances between
the source and the observers

$[\mathbf{d}_{s^{*}}]_{i}=d(s^{*},o_{i}),$ (8)

where distance $d(v_{i},v_{j})$ is defined as the length of shortest path
connecting vertices $v_{i}$ and $v_{j}$. The score, calculated for all
suspects, is therefore given by the Pearson correlation coefficient between
$\mathbf{t}$ and distances to the suspect $\mathbf{d}_{s}$

$\phi_{\text{Pearson}}(s)=\rho_{\text{Pearson}}(\mathbf{t},\mathbf{d}_{s}),$
(9)

which should be the highest for the true source $s=s^{*}$.

####  2.2.4 Evaluation measures

Algorithms outlined in Section 2.2 assign a score to every node from the
suspect set $S$. Sorting suspects by the score in descending order produces a
ranking, with the highest scoring suspect in the first place, satisfying (2).

The main measure of algorithm performance chosen for our purposes is its
precision, defined as

$\text{Precision}=\frac{\text{TP}}{\text{TP}+\text{FP}},$ (10)

where TP is the number of true positives, or correctly located sources (1 if
$\phi(s^{*})=\phi(\hat{s})$, 0 otherwise) and FP is the number of false
positives (all nodes $s\neq s^{*}$ such that $\phi(s)=\phi(\hat{s})$). If
there are no ties, then precision is a binary measure, equal to 1 if the
source is at the top of the ranking and 0 otherwise. If $s^{*}$ is tied with
$n$ other nodes at the top of the ranking, then precision is equal to $1/n$.

The second evaluation measure chosen for the purpose of this article is the
credible set size at confidence level $\alpha$, denoted $\text{CSS}_{\alpha}$.
Intuitively it can be understood as the size of the smallest set of top-
scoring nodes containing the source with probability $\alpha$. It is also
equivalent to the $\alpha$-quantile of the rank assigned to the source by the
localization algorithm.

##  3 Changing network topology

Localization derivations outlined in Section 2.2 assumes that the initial
network $\mathcal{G}=(V,E)$, in which the information propagates, is exactly
the same as the graph used by localization algorithms
$\mathcal{G}^{\prime}=(V^{\prime},E^{\prime})$. Such assumption, while
essential for analytical derivation, is not easily satisfied in practice. We
examine a number of scenarios, for which $V=V^{\prime}$ and $E\neq
E^{\prime}$. That is, the set of edges of the initial network $\mathcal{G}$ is
different than the set of edges of the modified network
$\mathcal{G}^{\prime}$, visible to the localization algorithms.

The difference between edge sets may be due to insufficient or inaccurate
information about the network’s structure. A simple interpretation of such
scenario is described in Section 3.2. Another possible reason could be the
natural changes (topological fluctuations) taking place between the time of
propagation and the moment of localization, resulting from the non-static
nature of a real-world network. In such case graphs $\mathcal{G}$ and
$\mathcal{G}^{\prime}$ should possess the same (or highly similar) macroscopic
properties, but differ on an edge-by-edge basis. We model this with
exponential random graphs [14], using a structural Hamiltonian approach
described in Section 3.3.

The general simulation procedure, illustrated in Fig. 1, can be summarized as
follows:

  1. 1.

Create a connected network of the desired model.

  2. 2.

Designate $r\cdot N$ random nodes as observers.

  3. 3.

Propagate information according to the synchronous SI model, recording
infection times $t_{i}$.

  4. 4.

Modify the network by adding random edges/removing random edges/performing
Metropolis steps.

  5. 5.

Locate the information source using all three location algorithms. If the
network became disconnected, only the largest component is searched.

###  3.1 Graph dissimilarity measure

To compare different types of topology changes an appropriate dissimilarity
measure is required. We use Jaccard distance between $E$ and $E^{\prime}$,
defined as

$d_{J}(E,E^{\prime})=1-J(E,E^{\prime})=1-\frac{|E\cap E^{\prime}|}{|E\cup
E^{\prime}|}$ (11)

as the free variable in most of our simulations Other measures, namely Hamming
distance, Sørensen-Dice coefficient and set overlap were considered. Jaccard
distance has been selected because it is normalized, satisfies the triangle
inequality, and has an intuitive interpretation in all studied scenarios.

###  3.2 Adding/hiding links

In this scenario the number of edges in $\mathcal{G}^{\prime}$ is over- or
underestimated. In the first case a fraction of superfluous edges $s_{e}$ is
randomly added to the network, such that

$|E^{\prime}|=(1+s_{e})|E|,\hskip 5.0ptE\subseteq E^{\prime}.$ (12)

The Jaccard distance is thus

$d_{J}(s_{e})=1-\frac{|E|}{(1+s_{e})|E|}=\frac{s_{e}}{1+s_{e}},$ (13)

with the inverse relationship

$s_{e}(d_{J})=\frac{d_{J}}{1-d_{J}}.$ (14)

Similarly, if instead of adding superfluous links we instead randomly hide
$h_{e}$ of them, we arrive at

$|E^{\prime}|=(1-h_{e})|E|,\hskip 5.0ptE^{\prime}\subseteq E,$ (15)

with Jaccard distance

$d_{J}(h_{e})=1-\frac{(1-h_{e})|E|}{|E|}=h_{e}.$ (16)

It should be noted that removing edges may result in component isolation.
While the initial network is guaranteed to be connected, this is no longer the
case for the modified graph. Networks studied by us (see Section 4) undergo a
reversed process of percolation [15], while initially remaining far from the
percolation threshold due to their relatively high average degree. As a
consequence, removing links means that the largest component still contains an
overwhelming majority of nodes. It is therefore the only candidate for
localization, while other components consist mostly of single vertices or
isolated pairs.

Further investigation of the impact of component isolation is discussed in
appendix A. For the purposes of our simulations we assume that, if the network
splits into several components, we look for the source in the largest one.

###  3.3 Topological fluctuations

In Section 3.2 we have described an extremely simplistic approach to
topological changes, in which a number of random edges are added or removed.
We wish to study a combination of these processes, both adding and removing
links. Instead of doing it randomly (which would, in the limiting case,
produce an Erdős–Rényi random graph) we consider a scheme in which some
macroscopic properties of the network are preserved. We achieve this goal
using the framework of exponential random graphs. The specific approach
outlined below draws from works published by Newman et al. [16] and Hołyst et
al. [17].

####  3.3.1 Structural Hamiltonian

Let $H(\mathcal{G};\\{\theta_{i}\\})$, called structural Hamiltonian, be a
scalar function of the graphs structure and a set of parameters $\theta_{i}$,
defined as a linear combination

$H(\mathcal{G})=\sum\limits_{i}\theta_{i}m_{i}(\mathcal{G}),$ (17)

where $m_{i}(\mathcal{G})$ represent any chosen properties of the graph. If
coefficients $\theta_{i}$ are chosen such that the probability of encountering
any given graph satisfies

$\mathbb{P}(\mathcal{G})\sim\exp\left(H(\mathcal{G})\right),$ (18)

then the set of all possible graphs $\Omega_{\mathcal{G}}$, together with
probability distribution (18), constitutes a canonical ensemble.

We consider the case of configuration model, for which the properties $m_{i}$
are individual vertex degrees $k_{i}$. Equation (17) becomes

$H(\mathcal{G})=\sum_{i=1}^{N}\theta_{i}k_{i},$ (19)

where $\theta_{i}$ must be chosen such that (18) is satisfied. It can be shown
[16] that these coefficients are given by a system of $N$ non-linear equations

$\langle
k_{i}\rangle=\sum\limits_{j=1}^{N}p_{ij}=\sum\limits_{j=1}^{N}\frac{1}{1+\exp(\theta_{i}+\theta_{j})},$
(20)

where $p_{ij}$ is the probability of $v_{i}$ and $v_{j}$ being linked,
$\langle k_{i}\rangle$ is the expected degree of $i$-th vertex averaging over
the ensemble. The canonical ensemble is thus defined by the expected sequence
of degrees found in the network.

In the case of Erdős-Rényi (ER) model, it is easily seen that

$\theta_{i}=\theta=\frac{1}{2}\ln\left(\frac{1-p}{p}\right),$ (21)

gives $\langle k_{i}\rangle=pN=\langle k\rangle$, where $p$ is the probability
of any two nodes being linked. For Barabási-Albert (BA) network, the degree of
each vertex can be averaged over a sufficiently large number of realizations,
obtaining $\langle k_{i}\rangle$. Similarly, when considering real networks,
the actual degree of each vertex can be designated as $\langle k_{i}\rangle$.
Equations (20) can then be solved numerically for the BA model and real
networks, obtaining a set of $\theta_{i}$ coefficients for each studied
network type.

####  3.3.2 Metropolis algorithm

A common method of generating sequences of elements from a canonical ensemble
is the Metropolis algorithm. In each step, a completely random change in the
current state (network structure) is performed. Change of state is then
accepted based on the resulting change in the Hamiltonian:

  * –

with probability 1 if $\Delta H\geq 0$;

  * –

with probability $e^{\Delta H}$ if $\Delta H<0$.

For our purposes, a change in the state consists of choosing a random pair of
vertices $(v_{i},v_{j})$ and adding an edge $e_{ij}$ if it does not exist, or
removing it if it does. The resulting change in Hamiltonian is

$\Delta H=\begin{cases}+(\theta_{i}+\theta_{j})&\text{when adding new
}e_{ij},\\\ -(\theta_{i}+\theta_{j})&\text{when removing existing
}e_{ij}.\end{cases}$ (22)

The link addition/removal is then accepted in accordance with the scheme
described above.

Performing a number of Metropolis steps is therefore akin to link re-
attachment, with additional constraints ensuring the degree sequence is
conserved when averaged over the ensemble. The modified network produced in
this manner will have edges different than $E$, but both degree sequence and
(by consequence) degree distribution will be preserved. The changes found in
$\mathcal{G}^{\prime}$ are therefore probable within the ensemble based on
$\mathcal{G}$, with exponential probability (18). We interpret this as the
initial network undergoing topological fluctuations, akin to energy
fluctuations of a thermodynamic system remaining in thermal equilibrium with a
heat bath.

Unlike adding superfluous/hiding edges, the relationship between the number of
Metropolis steps and Jaccard distance is non-trivial and network-dependent. In
our simulations, an experimental estimation of the number of steps needed to
achieve $d_{J}=\\{0,0.1,...,0.7\\}$ has been used.

It should be noted that the structural Hamiltonian is just one possible
approach to the problem of producing a modified network with comparable
macroscopic properties, but a differing set of edges. We have chosen the
exponential random graph model because of its straightforward interpretation,
as well as the possibility of conserving properties other than degree sequence
[18].

##  4 Results

The procedure outlined in Section 3 has been performed for the following
synthetic networks:

  * –

Erdős–Rényi (ER) network with size $N=1000$ and average degree $\langle
k\rangle=8$;

  * –

Barabási-Albert (BA) network with size $N=1000$ and parameters $m_{0}=m=4$.

Additionally, the following real networks have been studied:

  * –

Copenhagen Network Study social media friendship (,,Facebook”) network [19].
Vertices represent a participant of the network study, with edges indicating
friendship on the Facebook social network.

  * –

University Rovira i Virgilii e-mail communication (,,Email”) network [20].
Vertices represent members of e-mail communication at the Rovira i Virgili
University in Spain. Existence of an edge $e_{ij}$ indicates at least one
e-mail message sent either from $i$ to $j$, or from $j$ to $i$.

  * –

University of California, Irvine (,,California”) online community network
[21], transformed into undirected graph similar to Spinelli et al [22].
Vertices represent users of an online community, with edge $e_{ij}$ indicating
at least two messages were sent: one from $i$ to $j$ and one from $j$ to $i$.
The network has been trimmed such that the minimum degree is 2.

The basic properties of real networks described above are summarized in Table
1.

Network | $N$ | $\langle k\rangle$ | $k_{max}$ | $\langle d\rangle$ | $d_{max}$ | $c$
---|---|---|---|---|---|---
Facebook | 800 | 16.1 | 101 | 3.0 | 7 | 0.24
Email | 1133 | 9.6 | 71 | 3.5 | 5 | 0.17
California | 1020 | 12.2 | 110 | 3.0 | 8 | 0.05
Table 1: Basic properties of real networks used in simulations. $\langle
d\rangle$ denotes the average length of the shortest path between two nodes,
$d_{max}$ is the network’s diameter, $c$ is the global clustering coefficient.

Quantitative results for parameters $\beta=0.95$, $r=3$ are displayed in Fig.
3 (precision) and Fig. 4 ($\text{CSS}_{0.75}$).

Figure 3: Precision of given localization algorithm (row) and network (column)
as function of Jaccard distance $d_{J}$. Observer density $r=0.3$, infection
rate $\beta=0.95$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an average of
over $10^{3}$ iterations. Error bars indicate three standard deviations of the
mean.  Figure 4: CSS0.75 of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.3$,
infection rate $\beta=0.95$, GMLA uses $K_{f}=\sqrt{N}$. Each point is a
result of $10^{3}$ iterations.

Upon examining Fig. 3 we immediately notice an obvious difference in the
performance of GMLA, compared to other algorithms. It is much more resistant
to the addition of superfluous edges than LPTVA, with which it shares the
score function. We observe a drop in precision exceeding statistical
uncertainty only when the number of edges is approximately doubled
($d_{j}=0.5$). The same can be observed in Fig. 4, where CSS0.75 remains fixed
at 1 for $d_{J}<0.75$ for the artificial networks. On the contrary, when
hiding links, the precision of GMLA falls drastically, in some cases reaching
near 0 for $d_{J}\geq 0.3$ (ER network). While increasing the average vertex
degree translates to a larger number of suspects being checked during the
gradient-like selection process, decreasing the average vertex degree means
fewer nodes are checked, reducing the probability of encountering $\hat{s}$.
This could be a sufficient explanation for the difference observed between
superfluous and hidden links but does not explain the fact that topological
fluctuations produce a similarly drastic, albeit consistently lesser, decrease
in performance.

Notice that GMLA implicitly assumes that highly-scoring nodes should neighbor
each other. This remains true when new edges are added, but is no longer the
case when hiding links or re-attaching links using the Metropolis algorithm –
the gradient is “broken”. Breaking the gradient should therefore be
responsible for the large performance drop observed for the latter two cases,
with a reduction in average vertex degree resulting in an additional
difference between them. Additionally, when considering only $K_{f}$ earliest
observers, the paths found within the breadth-first search tree are unlikely
to change when adding edges, since their length is already short (on the order
of single edges).

Moreover, GMLA utilizes significantly fewer observers, which is used to filter
noisy information. In our simulations only $\sqrt{N}\approx 32$ earliest
observers, out of $r\cdot N\approx 300$, are used. This furthers the
performance gap between Pearson/LPTVA and GMLA when links are hidden or re-
attached, but notably does not seem to play a significant role when
superfluous links are added.

Turning our attention to the Pearson algorithm, for real networks we notice a
general trend of link addition having a greater impact on precision loss, with
topological fluctuations placed in the middle. For synthetic networks, the
trend is reversed, with link hiding being the worse scenario, although
precision differs significantly only in the case of a high $d_{J}$ ER network.
Difference in performance for both synthetic networks is clearly visible in
the CSS0.75 plot. It shows a significant disparity of approximately an order
of magnitude where $d_{J}\geq 0.6$.

Examining LPTVA performance, the observed difference between modification
scenarios is notably almost indistinguishable in the case of BA and California
networks. This observation remains true for both precision and CSS0.75. Other
networks, where the difference exceeds statistical uncertainty, favor link
hiding. Link addition has the least impact on localization, with fluctuations
situated between them. Notice that, while general curve characteristics are
similar between the two, LPTVA precision is generally on par or lower than
that of Pearson, together with higher CSS0.75. The significantly higher LPTVA
execution time, arising from increased computational complexity (see [10,
Table 1]), must also be taken into account.

Regardless of the localization algorithm used, some general observations
should be noted. For both Pearson and LPTV algorithms, the precision plots are
generally S-shaped, sometimes displaying a degree of resilience to topological
changes. Specifically, in the case of ER network, the precision of the Pearson
algorithm falls by less than the statistical uncertainty for $d_{J}\leq 0.3$,
which translates to removing $30\%$ of existing edges or adding $\approx 43\%$
new ones. The ER topology generally favors localization when compared to other
studied networks. Note that e.g. baseline $d_{J}=0$ gives ER precision
$\approx 1$ and Email precision $\approx 0.8$ for all localization algorithms.

##  5 Conclusion

In this paper, we study the relationship between the performance of three
popular, observer-based algorithms and topological changes introduced in the
network between the moment of propagation and localization. We separately
consider three categories of aforementioned topological modifications: hiding
existing links, introducing superfluous links, and re-attaching links in
accordance with structural Hamiltonian.

Considering the results presented in Section 4, we propose that, when the
modified network edge set is suspected to be overestimated, GMLA should be
used due to its high resilience to superfluous edges. On the contrary, when
the modified network is suspected to be less dense than the initial one or
undergoes topological fluctuations, GMLA should be avoided. In such cases, the
Pearson algorithm provides precision similar or higher compared to LPTVA,
together with an overall lower CSS and orders of magnitude faster execution
time

In some studied network-algorithm-modification combinations a degree of
resilience to topological changes can be observed. Upon examining the
performance for other values of $r$ and $\beta$ (see Appendix B) we note that
it is most noticeable when simulation parameters favor localization (high $r$,
high $\beta$, correctly chosen algorithm) and disappears when imposed
conditions are worsened (low $r$, low $\beta$, incorrectly chosen algorithm).
This observation supports an intuitive idea of a “stock” of localization
performance, which may be depleted by an unfavorable condition and replenished
by a favorable one. In this manner it is possible to “overstock” on precision
by e.g. increasing the observer density or choosing an appropriate algorithm,
thus achieving a level of resilience to topological changes. This idea is
further supported by the fact that resilience is most clearly observed in the
ER network, which by itself favors localization when compared to e.g. the
Email network.

It should be noted that the overall algorithm performance is highly dependent
both on the network and the remaining simulation parameters (see Appendix B).
Results presented by us suggest a need for a theoretical framework, capable of
rigorously explaining observed phenomena.

Furthermore, studied networks undergo percolation, as described in Appendix A,
and as such do not split into multiple large components upon link removal.
Only one component large enough to contain an acceptable number of observers
emerges. If one were to consider scenarios where this is not the case, e.g.
because of the network structure or particular link hiding scheme, then an
argument can be made for a number of different approaches. One may, for
instance, look for the source in the earliest informed component instead of
the largest one, or decide to consider all sufficiently large components and
try to merge their respective results. The possibilities mentioned above
warrant additional research, both theoretical and experimental.

##  Appendix A Impact of component isolation

As mentioned in Section 3.2, hiding random edges may result in component
isolation. Let $C^{*}$ be the largest connected component present in the
network (also called percolation cluster), with $\\{C_{i}\\}$ denoting the set
of components other than the largest one. If the graph became disconnected as
a result of removing random edges, then by necessity $C^{*}\neq V$ and
$\\{C_{i}\\}$ is not empty. Plotting the average size of
$\langle|C_{i}|\rangle$ as a function of Jaccard distance $h_{e}=d_{J}$ (see
Fig. 5) we notice that these components are mostly single vertices.

Figure 5: Average size of network clusters, excluding the largest one. Each
point is an average over $10^{3}$ iterations. Error bars indicate three
standard deviations of the mean.

On the other hand, examining the size of the percolation cluster (see Fig. 6)
it is clear that it still contains more than 75% of the modified network, even
for the highest considered $h_{e}$. This supports the notion that it is the
only suitable candidate for running localization algorithms.

Figure 6: Normalized size of the percolation cluster (largest connected
component). Each point is an average over $10^{3}$ iterations. Error bars
indicate three standard deviations of the mean.

While the percolation cluster encapsulates most of the modified network, it
may be beneficial to examine the impact of cropping the graph. One may
consider a link hiding scheme in which $C^{*}=V$ is guaranteed, i.e. randomly
chosen links are hidden only if their deletion would not split the network
into multiple components. We achieve this by checking whether another path
$P(v_{i},v_{j})$ exists after removing link $e_{ij}$. If such a path exists,
the link is considered “non-essential” – its removal did not split the
network. If such a path does not exists then $e_{ij}$ is reinstated and
another link is hidden instead.

This modification to the hiding scheme turns out to have a negligible impact
on localization performance. A comparison of the two hiding schemes has been
illustrated in Fig. 7. Despite being the most glaring out of all considered
parameter/network/algorithm combinations, the difference does not exceed
statistical uncertainty.

Figure 7: Precision of Pearson algorithm for ER network, modified by hiding
$h_{e}\cdot|E|=d_{J}\cdot|E|$ random edges. Filled markers represent a link
hiding scheme in which the network is artificially held together by removing
only “non-essential” links. Parameters $\beta=0.5$, $r=0.2$. Each point is an
average of over $10^{3}$ iterations. Error bars indicate three standard
deviations of the mean.

##  Appendix B Suplemental material

Results presented in Section 4 constitute parameter combinations most
representative for the purposes of this paper. Nevertheless, the output of
identical simulations performed for a wider range of $r$ and $\beta$ may be of
interest. Variants of Fig. 3 and Fig. 4 are included below as a supplemental
material for this exact purpose.

Figure 8: Precision of given localization algorithm (row) and network (column)
as function of Jaccard distance $d_{J}$. Observer density $r=0.1$, infection
rate $\beta=0.5$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an average of over
$10^{3}$ iterations. Error bars indicate three standard deviations of the
mean. Figure 9: CCSS0.75 of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.1$,
infection rate $\beta=0.5$, GMLA uses $K_{f}=\sqrt{N}$. Each point is a result
of $10^{3}$ iterations.

Figure 10: Precision of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.1$,
infection rate $\beta=0.75$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an
average of over $10^{3}$ iterations. Error bars indicate three standard
deviations of the mean. Figure 11: CCSS0.75 of given localization algorithm
(row) and network (column) as function of Jaccard distance $d_{J}$. Observer
density $r=0.1$, infection rate $\beta=0.75$, GMLA uses $K_{f}=\sqrt{N}$. Each
point is a result of $10^{3}$ iterations.

Figure 12: Precision of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.1$,
infection rate $\beta=0.95$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an
average of over $10^{3}$ iterations. Error bars indicate three standard
deviations of the mean. Figure 13: CCSS0.75 of given localization algorithm
(row) and network (column) as function of Jaccard distance $d_{J}$. Observer
density $r=0.1$, infection rate $\beta=0.95$, GMLA uses $K_{f}=\sqrt{N}$. Each
point is a result of $10^{3}$ iterations.

Figure 14: Precision of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.2$,
infection rate $\beta=0.5$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an
average of over $10^{3}$ iterations. Error bars indicate three standard
deviations of the mean. Figure 15: CCSS0.75 of given localization algorithm
(row) and network (column) as function of Jaccard distance $d_{J}$. Observer
density $r=0.2$, infection rate $\beta=0.5$, GMLA uses $K_{f}=\sqrt{N}$. Each
point is a result of $10^{3}$ iterations.

Figure 16: Precision of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.2$,
infection rate $\beta=0.75$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an
average of over $10^{3}$ iterations. Error bars indicate three standard
deviations of the mean. Figure 17: CCSS0.75 of given localization algorithm
(row) and network (column) as function of Jaccard distance $d_{J}$. Observer
density $r=0.2$, infection rate $\beta=0.75$, GMLA uses $K_{f}=\sqrt{N}$. Each
point is a result of $10^{3}$ iterations.

Figure 18: Precision of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.2$,
infection rate $\beta=0.95$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an
average of over $10^{3}$ iterations. Error bars indicate three standard
deviations of the mean. Figure 19: CCSS0.75 of given localization algorithm
(row) and network (column) as function of Jaccard distance $d_{J}$. Observer
density $r=0.2$, infection rate $\beta=0.95$, GMLA uses $K_{f}=\sqrt{N}$. Each
point is a result of $10^{3}$ iterations.

Figure 20: Precision of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.3$,
infection rate $\beta=0.5$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an
average of over $10^{3}$ iterations. Error bars indicate three standard
deviations of the mean. Figure 21: CCSS0.75 of given localization algorithm
(row) and network (column) as function of Jaccard distance $d_{J}$. Observer
density $r=0.3$, infection rate $\beta=0.5$, GMLA uses $K_{f}=\sqrt{N}$. Each
point is a result of $10^{3}$ iterations.

Figure 22: Precision of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.3$,
infection rate $\beta=0.75$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an
average of over $10^{3}$ iterations. Error bars indicate three standard
deviations of the mean. Figure 23: CCSS0.75 of given localization algorithm
(row) and network (column) as function of Jaccard distance $d_{J}$. Observer
density $r=0.3$, infection rate $\beta=0.75$, GMLA uses $K_{f}=\sqrt{N}$. Each
point is a result of $10^{3}$ iterations.

Figure 24: Precision of given localization algorithm (row) and network
(column) as function of Jaccard distance $d_{J}$. Observer density $r=0.3$,
infection rate $\beta=0.95$, GMLA uses $K_{f}=\sqrt{N}$. Each point is an
average of over $10^{3}$ iterations. Error bars indicate three standard
deviations of the mean. Figure 25: CCSS0.75 of given localization algorithm
(row) and network (column) as function of Jaccard distance $d_{J}$. Observer
density $r=0.3$, infection rate $\beta=0.95$, GMLA uses $K_{f}=\sqrt{N}$. Each
point is a result of $10^{3}$ iterations.

## Acknowledgments

Research was funded by POB Cybersecurity and data analysis of Warsaw
University of Technology within the Excellence Initiative: Research University
(IDUB) programme.

## References

  * Perrin [2015] A. Perrin,  Social media usage,  Pew research center 125 (2015) 52–68.
  * Bazaco et al. [2019] A. Bazaco, M. Redondo García, P. Sánchez-García,  Clickbait as a strategy of viral journalism: conceptualisation and methods,  Revista Latina de Comunicacion Social 74 (2019) 94–115.
  * Chen et al. [2015] Y. Chen, N. J. Conroy, V. L. Rubin,  Misleading online content: Recognizing clickbait as ”false news”,  WMDD ’15, Association for Computing Machinery, New York, NY, USA, 2015, p. 15–19. doi:10.1145/2823465.2823467.
  * Acemoglu et al. [2010] D. Acemoglu, A. Ozdaglar, A. ParandehGheibi,  Spread of (mis)information in social networks,  Games and Economic Behavior 70 (2010) 194–227.
  * Gradoń et al. [2021] K. T. Gradoń, J. A. Hołyst, W. R. Moy, J. Sienkiewicz, K. Suchecki,  Countering misinformation: A multidisciplinary approach,  Big Data & Society 8 (2021) 20539517211013848.
  * Jiang et al. [2017] J. Jiang, S. Wen, S. Yu, Y. Xiang, W. Zhou,  Identifying propagation sources in networks: State-of-the-art and comparative studies,  IEEE Communications surveys and tutorials 19 (2017) 465–481.
  * Bailey et al. [1975] N. T. Bailey, et al., The mathematical theory of infectious diseases and its applications, Charles Griffin & Company Ltd, 5a Crendon Street, High Wycombe, Bucks HP13 6LE., 1975\.
  * Pinto et al. [2012] P. C. Pinto, P. Thiran, M. Vetterli,  Locating the source of diffusion in large-scale networks,  Phys. Rev. Lett. 109 (2012) 068702.
  * Paluch et al. [2018] R. Paluch, X. Lu, K. Suchecki, B. K. Szymański, J. A. Hołyst,  Fast and accurate detection of spread source in large complex networks,  Scientific Reports 8 (2018) 2508.
  * Gajewski et al. [2022] L. G. Gajewski, R. Paluch, K. Suchecki, A. Sulik, B. K. Szymanski, J. A. Hołyst,  Comparison of observer based methods for source localization in complex networks,  Scientific reports 12 (2022) 5079–5079.
  * Karamchandani and Franceschetti [2013] N. Karamchandani, M. Franceschetti,  Rumor source detection under probabilistic sampling,  in: 2013 IEEE International Symposium on Information Theory, 2013, pp. 2184–2188. doi:10.1109/ISIT.2013.6620613.
  * Agaskar and Lu [2013] A. Agaskar, Y. M. Lu,  A fast Monte Carlo algorithm for source localization on graphs,  in: D. V. D. Ville, V. K. Goyal, M. Papadakis (Eds.), Wavelets and Sparsity XV, volume 8858, International Society for Optics and Photonics, SPIE, 2013, p. 88581N. doi:10.1117/12.2023039.
  * Xu et al. [2019] S. Xu, C. Teng, Y. Zhou, J. Peng, Y. Zhang, Z.-K. Zhang,  Identifying the diffusion source in complex networks with limited observers,  Physica A: Statistical Mechanics and its Applications 527 (2019) 121267\.
  * Holland and Leinhardt [1981] P. W. Holland, S. Leinhardt,  An exponential family of probability distributions for directed graphs,  Journal of the American Statistical Association 76 (1981) 33–50.
  * Li et al. [2021] M. Li, R.-R. Liu, L. Lü, M.-B. Hu, S. Xu, Y.-C. Zhang,  Percolation on complex networks: Theory and application,  Physics Reports 907 (2021) 1–68.
  * Park and Newman [2004] J. Park, M. E. J. Newman,  Statistical mechanics of networks,  Phys. Rev. E 70 (2004) 066117.
  * Fronczak et al. [2006] A. Fronczak, P. Fronczak, J. A. Hołyst,  Fluctuation-dissipation relations in complex networks,  Phys. Rev. E 73 (2006) 016108.
  * Park and Newman [2005] J. Park, M. E. J. Newman,  Solution for the properties of a clustered network,  Phys. Rev. E 72 (2005) 026136.
  * Sapiezynski et al. [2019] P. Sapiezynski, A. Stopczynski, D. D. Lassen, S. Lehmann,  Interaction data from the copenhagen networks study,  Scientific Data 6 (2019) 1–10.
  * Guimerà et al. [2003] R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, A. Arenas,  Self-similar community structure in a network of human interactions,  Phys. Rev. E 68 (2003) 065103.
  * Panzarasa et al. [2009] P. Panzarasa, T. Opsahl, K. M. Carley,  Patterns and dynamics of users’ behavior and interaction: Network analysis of an online community,  Journal of the American Society for Information Science and Technology 60 (2009) 911–932.
  * Spinelli et al. [2016] B. Spinelli, L. E. Celis, P. Thiran,  Observer placement for source localization: The effect of budgets and transmission variance,  in: 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2016, pp. 743–751. doi:10.1109/ALLERTON.2016.7852307.


# On Schur’s irreducibility results and generalised $\phi$-Hermite polynomials

Anuj Jakhar  Department of Mathematics, Indian Institute of Technology (IIT)
Madras<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract.

Let $c$ be a fixed integer such that $c\in\\{0,2\\}.$ Let $n$ be a positive
integer such that either $n\geq 2$ or $2n+1\neq 3^{u}$ for any integer $u\geq
2$ according as $c=0$ or not. Let $\phi(x)$ belonging to ${\mathbf{Z}}[x]$ be
a monic polynomial which is irreducible modulo all primes less than $2n+c$.
Let $a_{i}(x)$ with $0\leq i\leq n-1$ belonging to ${\mathbf{Z}}[x]$ be
polynomials having degree less than $\deg\phi(x)$. Let $a_{n}\in{\mathbf{Z}}$
and the content of $(a_{n}a_{0}(x))$ is not divisible by any prime less than
$2n+c$. For a positive integer $j$, if $u_{j}$ denotes the product of the odd
numbers $\leq j$, then we show that the polynomial
$\frac{a_{n}}{u_{2n+c}}\phi(x)^{2n}+\sum\limits_{j=0}^{n-1}a_{j}(x)\frac{\phi(x)^{2j}}{u_{2j+c}}$
is irreducible over the field ${\mathbf{Q}}$ of rational numbers. This
generalises a well-known result of Schur which states that the polynomial
$\sum\limits_{j=0}^{n}a_{j}\frac{x^{2j}}{u_{2j+c}}$ with
$a_{j}\in{\mathbf{Z}}$ and $|a_{0}|=|a_{n}|=1$ is irreducible over
${\mathbf{Q}}$. We illustrate our result through examples.

###### Key words and phrases:

Irreducibility, Polynomials, Newton Polygons

###### 2010 Mathematics Subject Classification:

11C08, 11R04

##  1\. Introduction and statements of results

For each non-negative integer $j$, we define $u_{j}$ as the product of the odd
numbers $\leq j$. In particular, we have $u_{0}=u_{2}=1$,
$u_{4}=3,~{}u_{6}=15,~{}\cdots.$

In 1929, Schur[9] proved the following two results.

######  Theorem 1.1.

Let $a_{j}$’s for $0\leq j\leq n$, be integers and $|a_{0}|=|a_{n}|=1$. Then
the polynomial $\sum\limits_{j=0}^{n}a_{j}\frac{x^{2j}}{u_{2j}}$ is
irreducible over ${\mathbf{Q}}$.

######  Theorem 1.2.

Let $n$ be a positive integer such that $2n+1\neq 3^{u}$ for any integer
$u\geq 2$. Let $a_{j}$’s for $0\leq j\leq n$, be integers and
$|a_{0}|=|a_{n}|=1$. Then the polynomial
$\sum\limits_{j=0}^{n}a_{j}\frac{x^{2j}}{u_{2j+2}}$ is irreducible over
${\mathbf{Q}}$.

As a consequence of the above theorems, he also proved that the $m^{th}$
classical Hermite polynomial, given by

$H_{m}(x)=\sum\limits_{j=0}^{[m/2]}(-1)^{j}\binom{m}{2j}u_{2j}x^{m-2j},$

is irreducible if $m$ is even and is $x$ times an irreducible polynomial if
$m$ is odd.

In the present paper, we extend Theorems 1.1, 1.2. More precisely, we prove
the following results.

######  Theorem 1.3.

Let $n\geq 2$ and $a_{n}$ be integers. Let $\phi(x)$ belonging to
${\mathbf{Z}}[x]$ be a monic polynomial which is irreducible modulo all primes
less than $2n$. Suppose that $a_{0}(x),\cdots,a_{n-1}(x)$ belonging to
${\mathbf{Z}}[x]$ satisfy the following conditions.

  * (i)

$\deg a_{i}(x)<\deg\phi(x)$ for $0\leq i\leq n-1$,

  * (ii)

the content of $(a_{n}a_{0}(x))$ is not divisible by any prime less than $2n$.

Then the polynomial

$f_{1}(x)=\frac{a_{n}}{u_{2n}}\phi(x)^{2n}+\sum\limits_{j=0}^{n-1}a_{j}(x)\frac{\phi(x)^{2j}}{u_{2j}}$

is irreducible over ${\mathbf{Q}}$.

We wish to point out here that the analogues of the above theorem does not
hold for $n=1$ because if $\phi(x)\in{\mathbf{Z}}[x]$ is a monic polynomial of
degree $m\geq 3$, then the polynomial
$\phi(x)^{2}-x^{2}=(\phi(x)+x)(\phi(x)-x)$ is reducible over ${\mathbf{Q}}$.

It may be pointed out that in Theorem 1.3 the assumption “the content of
$a_{0}(x)$ is not divisible by any prime less than $2n$” cannot be dispensed
with. For example, consider the polynomial $\phi(x)=x^{2}-x+5$ which is
irreducible modulo $2$ and $3$. Then the polynomial
$f(x)=\frac{\phi(x)^{4}}{3}-3$ = $\frac{1}{3}(\phi(x)^{2}+3)(\phi(x)^{2}-3)$
is reducible over ${\mathbf{Q}}$.

We also give below an example to show that Theorem 1.3 may not hold if $a_{n}$
is replaced by a (monic) polynomial $a_{n}(x)$ with integer coefficient having
degree less than $\deg\phi(x)$. Consider $\phi(x)=x^{2}-x+5$ which is
irreducible modulo $2$ and $3$. Take $a_{2}(x)=x-3,a_{1}(x)=x+26$ and
$a_{0}(x)=5(x-5)$. Then the polynomial

$a_{2}(x)\frac{\phi(x)^{4}}{3}+a_{1}(x)\phi(x)^{2}+a_{0}(x)$

has $0$ as a root.

######  Theorem 1.4.

Let $n$ be a positive integer such that $2n+1\neq 3^{u}$ for any integer
$u\geq 2$. Let $\phi(x)$ belonging to ${\mathbf{Z}}[x]$ be a monic polynomial
which is irreducible modulo all primes less than $2n+2$. Suppose that
$a_{n},a_{0}(x),\cdots,a_{n-1}(x)$ belonging to ${\mathbf{Z}}[x]$ satisfy the
following conditions.

  * (i)

$\deg a_{i}(x)<\deg\phi(x)$ for $0\leq i\leq n-1$,

  * (ii)

the content of $(a_{n}a_{0}(x))$ is not divisible by any prime less than
$2n+2$.

Then the polynomial

$f_{2}(x)=\frac{a_{n}}{u_{2n+2}}\phi(x)^{2n}+\sum\limits_{j=0}^{n-1}a_{j}(x)\frac{\phi(x)^{2j}}{u_{2j+2}}$

is irreducible over ${\mathbf{Q}}$.

It may be pointed out that in Theorem 1.4 the assumption “the content of
$a_{0}(x)$ is not divisible by any prime less than $2n+2$” cannot be dispensed
with. For example, consider the polynomial $\phi(x)=x^{2}-x+11$ which is
irreducible modulo $2,3$ and $5$. Then the polynomial
$f(x)=\frac{\phi(x)^{4}}{15}+6\frac{\phi(x)^{2}}{3}+15$ =
$\frac{1}{15}(\phi(x)^{2}+15)^{2}$ is reducible over ${\mathbf{Q}}$.

We also give below an example to show that Theorem 1.4 may not hold if $a_{n}$
is replaced by a (monic) polynomial $a_{n}(x)$ with integer coefficient having
degree less than $\deg\phi(x)$. Consider $\phi(x)=x^{2}-x+11$ which is
irreducible modulo $2,3$ and $5$. Take $a_{2}(x)=x-15,a_{1}(x)=x+366$ and
$a_{0}(x)=x-121$. Then the polynomial

$a_{2}(x)\frac{\phi(x)^{4}}{15}+a_{1}(x)\frac{\phi(x)^{2}}{3}+a_{0}(x)$

has $0$ as a root.

As an application of Theorems 1.3, 1.4, we shall prove the following theorem.

######  Theorem 1.5.

Let $m\geq 3$ be an integer. Let $\phi(x)$ belonging to ${\mathbf{Z}}[x]$ be a
monic polynomial which is irreducible modulo all primes $\leq m$. Suppose that
$a_{[\frac{m}{2}]},a_{0}(x),\cdots,a_{[\frac{m}{2}]-1}(x)$ belonging to
${\mathbf{Z}}[x]$ satisfy the following conditions.

  * (i)

$\deg a_{i}(x)<\deg\phi(x)$ for $0\leq i\leq[m/2]-1$,

  * (ii)

the content of $(a_{[\frac{m}{2}]}a_{0}(x))$ is not divisible by any prime
$\leq m$.

Then the polynomial

$H^{\phi}_{m}(x)=a_{[\frac{m}{2}]}\phi(x)^{m}+\sum\limits_{j=1}^{[m/2]}\binom{m}{2j}u_{2j}a_{[\frac{m}{2}]-j}(x)\phi(x)^{m-2j}$

is irreducible over ${\mathbf{Q}}$ if $m$ is even and is $\phi(x)$ times an
irreducible polynomial if $m$ is odd with $m\neq 3^{u}$ for any integer $u\geq
2$.

We wish to point out here that in the above theorem, if we take $\phi(x)=x$
and $a_{[\frac{m}{2}]}=(-1)^{[\frac{m}{2}]},~{}a_{i}(x)=(-1)^{i}$ for $0\leq
i\leq[m/2]-1$, then $H^{\phi}_{m}(x)$ becomes $m$-th classical Hermite
polynomial.

The following corollary is an immediate consequence of the above theorem.

######  Corollary 1.6.

Let $m\geq 3$ be an integer. Let $\phi(x)$ belonging to ${\mathbf{Z}}[x]$ be a
monic polynomial which is irreducible modulo all primes less than $m$. Then
the polynomial

$H_{m}(\phi(x))=\sum\limits_{j=0}^{[m/2]}(-1)^{j}\binom{m}{2j}u_{2j}\phi(x)^{m-2j}$

is irreducible over ${\mathbf{Q}}$ if $m$ is even and is $\phi(x)$ times an
irreducible polynomial if $m$ is odd with $m\neq 3^{u}$ for any integer $u\geq
2$.

We now provide some examples of Theorems 1.3, 1.4.

######  Example 1.7.

Consider $\phi(x)=x^{3}-x+37$. It can be easily checked that $\phi(x)$ is
irreducible modulo $2,3,5$ and $7$. Let $j\geq 2$ and $a_{j}$ be integers. Let
$a_{i}(x)\in{\mathbf{Z}}[x]$ be polynomials each having degree less than $3$
for $0\leq i\leq j-1$. Assume that the content of $(a_{j}a_{0}(x))$ is not
divisible by any prime less than $2j$. Then by Theorem 1.3, the polynomial

$f_{j}(x)=\frac{a_{j}}{u_{2j}}\phi(x)^{2j}+\sum\limits_{i=0}^{j-1}a_{i}(x)\frac{\phi(x)^{2i}}{u_{2i}}$

is irreducible over ${\mathbf{Q}}$ for $j\in\\{2,3,4,5\\}$.

######  Example 1.8.

Consider $\phi(x)=x^{2}-x+17$. It can be easily checked that $\phi(x)$ is
irreducible modulo $2,3,5$ and $7$. Let $j\geq 2$ and $a_{j}$ be integers. Let
$a_{i}(x)\in{\mathbf{Z}}[x]$ be polynomials each having degree less than $2$
for $0\leq i\leq j-1$. Assume that the content of $(a_{j}a_{0}(x))$ is not
divisible by any prime less than $2j+2$. Then by Theorem 1.4, the polynomial

$g_{j}(x)=\frac{a_{j}}{u_{2j+2}}\phi(x)^{2j}+\sum\limits_{i=0}^{j-1}a_{i}(x)\frac{\phi(x)^{2i}}{u_{2i+2}}$

is irreducible over ${\mathbf{Q}}$ for $j\in\\{2,3,4\\}$.

It may be pointed out that, in the above examples, the irreducibility of the
polynomials $f_{5}(x)$ and $g_{4}(x)$ do not seem to follow from any known
irreducibility criterion (cf. [1], [2], [3], [4], [5], [6] and [7]).

##  2\. Preliminary results.

We first introduce the notion of Gauss valuation and $\phi$-Newton polygon.
For a prime $p$, $v_{p}$ will denote the $p$-adic valuation of ${\mathbf{Q}}$
defined for any non-zero integer $b$ to be the highest power of $p$ dividing
$b$. We shall denote by $v_{p}^{x}$ the Gaussian valuation extending $v_{p}$
defined on the polynomial ring ${\mathbf{Z}}[x]$ by

$v_{p}^{x}(\sum\limits_{i}b_{i}x^{i})=\min_{i}\\{v_{p}(b_{i})\\},b_{i}\in{\mathbf{Z}}.$

######  Definition 2.1.

Let $p$ be a prime number and $\phi(x)\in{\mathbf{Z}}[x]$ be a monic
polynomial which is irreducible modulo $p$. Let $f(x)$ belonging to
${\mathbf{Z}}[x]$ be a polynomial having $\phi$-expansion111If $\phi(x)$ is a
fixed monic polynomial with coefficients in ${\mathbf{Z}}$, then any
$f(x)\in{\mathbf{Z}}[x]$ can be uniquely written as a finite sum
$\sum\limits_{i}b_{i}(x)\phi(x)^{i}$ with $\deg b_{i}(x)<\deg\phi(x)$ for each
$i$; this expansion will be referred to as the $\phi$-expansion of $f(x)$.
$\sum\limits_{i=0}^{n}b_{i}(x)\phi(x)^{i}$ with $b_{0}(x)b_{n}(x)\neq 0$. Let
$P_{i}$ stand for the point in the plane having coordinates
$(i,v_{p}^{x}(b_{n-i}(x)))$ when $b_{n-i}(x)\neq 0$, $0\leq i\leq n$. Let
$\mu_{ij}$ denote the slope of the line joining the points $P_{i}$ and $P_{j}$
if $b_{n-i}(x)b_{n-j}(x)\neq 0$. Let $i_{1}$ be the largest index $0<i_{1}\leq
n$ such that

$\displaystyle\mu_{0i_{1}}=\min\\{\mu_{0j}\ |\ 0<j\leq n,\ b_{n-j}(x)\neq
0\\}.$

If $i_{1}<n$, let $i_{2}$ be the largest index $i_{1}<i_{2}\leq n$ such that

$\displaystyle\mu_{i_{1}i_{2}}=\min\\{\mu_{i_{1}j}\ |\ i_{1}<j\leq n,\
b_{n-j}(x)\neq 0\\}$

and so on. The $\phi$-Newton polygon of $f(x)$ with respect to $p$ is the
polygonal path having segments
$P_{0}P_{i_{1}},P_{i_{1}}P_{i_{2}},\dots,P_{i_{k-1}}P_{i_{k}}$ with $i_{k}=n$.
These segments are called the edges of the $\phi$-Newton polygon of $f(x)$ and
their slopes from left to right form a strictly increasing sequence. The
$\phi$-Newton polygon minus the horizontal part (if any) is called its
principal part.

We shall use the following lemma[8, Theorem 1.3] in the sequel. We omit its
proof.

######  Lemma 2.2.

Let $n,k$ and $\ell$ be integers with $0\leq\ell<k\leq\frac{n}{2}$ and $p$ be
a prime. Let $\phi(x)\in{\mathbf{Z}}[x]$ be a monic polynomial which is
irreducible modulo $p$. Let $f(x)$ belonging to ${\mathbf{Z}}[x]$ be a monic
polynomial not divisible by $\phi(x)$ having $\phi$-expansion
$\sum\limits_{i=0}^{n}f_{i}(x)\phi(x)^{i}$ with $f_{n}(x)\neq 0$. Assume that
$v_{p}^{x}(f_{i}(x))>0$ for $0\leq i\leq n-\ell-1$ and the right-most edge of
the $\phi$-Newton polygon of $f(x)$ with respect to $p$ has slope less than
$\frac{1}{k}$. Let $a_{0}(x),a_{1}(x),\dots,a_{n}(x)$ be polynomials over
${\mathbf{Z}}$ satisfying the following conditions.

  * (i)

$\deg a_{i}(x)<\deg\phi(x)-\deg f_{i}(x)$ for $0\leq i\leq n$,

  * (ii)

$v_{p}^{x}(a_{0}(x))=0$, i.e., the content of $a_{0}(x)$ is not divisible by
$p$,

  * (iii)

the leading coefficient of $a_{n}(x)$ is not divisible by $p$.

Then the polynomial $\sum\limits_{i=0}^{n}a_{i}(x)f_{i}(x)\phi(x)^{i}$ does
not have a factor in ${\mathbf{Z}}[x]$ with degree lying in the interval
$[(\ell+1)\deg\phi(x),(k+1)\deg\phi(x)).$

We now prove the following elementary result will be used in the proof of
Theorems 1.3, 1.4.

######  Lemma 2.3.

Let $n\geq 1$ be an integer and $p$ be a prime number. Let
$\phi(x)\in{\mathbf{Z}}[x]$ be a monic polynomial which is irreducible modulo
$p$. Suppose that $a_{0}(x),a_{1}(x),\cdots,a_{n-1}(x)$ belonging to
${\mathbf{Z}}[x]$ are polynomials each having degree less than $\deg\phi(x)$.
Let $a_{n}$ be an integer with $p\nmid a_{n}$. Let
$b_{0},b_{1},\cdots,b_{n-1}$ be integers such that $p|b_{j}$ for each $j$,
$0\leq j\leq n-1$. Then the polynomial

$F(x)=a_{n}\phi(x)^{2n}+\sum\limits_{j=0}^{n-1}b_{j}a_{j}(x)\phi(x)^{2j}$

can not have any non-constant factor having degree less than $\deg\phi(x)$.

###### Proof.

Let $c$ denote the content of $F(x)$. As $p\nmid a_{n}$, we have $p\nmid c$.
Now suppose to the contrary that there exists a primitive non-constant
polynomial $h(x)\in{\mathbf{Z}}[x]$ dividing $F(x)$ having degree less than
$\deg\phi(x)$. Then in view of Gauss Lemma, there exists
$g(x)\in{\mathbf{Z}}[x]$ such that $\frac{F(x)}{c}=h(x)g(x)$. The leading
coefficient of $F(x)$ and hence those of $h(x)$ and $g(x)$ are coprime with
$p$. Note that $p$ divides $b_{j}$ for $0\leq j\leq n-1$. Therefore on passing
to ${\mathbf{Z}}/p{\mathbf{Z}}$, we see that the degree of $\bar{h}(x)$ is
same as that of $h(x)$. Hence $\deg\bar{h}(x)$ is positive and less than
$\deg\phi(x)$. This is impossible because $\bar{h}(x)$ is a divisor of
$\frac{\overline{F}(x)}{\bar{c}}=\frac{\bar{a}_{n}}{\bar{c}}\bar{\phi}(x)^{2n}$
and $\bar{\phi}(x)$ is irreducible over ${\mathbf{Z}}/p{\mathbf{Z}}$. This
completes the proof of the lemma. ∎

The following result is due to Schur [9] and plays an important role in the
proof of Theorems 1.3, 1.4.

######  Lemma 2.4.

For integers $k$ and $n$ with $n>k>2$, at least one of the $k$ numbers
$2n+1,2n+3,\cdots,2n+2k-1$ is divisible by a prime $p>2k+1$. For $k=2$, the
same result holds unless $2n+1=25$. For $k=1$, the same result holds unless
$2n+1=3^{u}$ for some integer $u\geq 2.$

######  Remark 2.5.

It can be noted that the first part of the above lemma can be rephrased as
saying that, for $k>2$, the product of any $k$ consecutive odd numbers each
$>2k+1$ is divisible by a prime $p>2k+1$.

##  3\. Proof of Theorem 1.3

###### Proof of Theorem 1.3.

By hypothesis, $n\geq 2$. It suffices to show that $F_{1}(x)=u_{2n}f_{1}(x)$
can not have a factor in ${\mathbf{Z}}[x]$ with degree lying in the interval
$[1,(n+1)\deg\phi(x))$. If we choose a prime $p$ such that $p$ divides $2n-1$,
then we have $p$ divides $\frac{u_{2n}}{u_{2j}}$ for each $0\leq j\leq n-1$.
Hence using Lemma 2.3, we see that $F_{1}(x)$ can not have any non-constant
factor having degree less than $\deg\phi(x)$. Now assume that $F_{1}(x)$ has a
factor in ${\mathbf{Z}}[x]$ with degree lying in the interval
$[\deg\phi(x),(n+1)\deg\phi(x))$. We make use of Lemma 2.2 to obtain a
contradiction. We consider a new polynomial $g_{1}(x)$ with
$a_{n}=1=a_{j}(x)$, $0\leq j\leq n-1$, in $F_{1}(x)$ given by

$g_{1}(x)=\phi(x)^{2n}+(2n-1)\phi(x)^{2n-2}+\cdots+(2n-1)\cdots 5\cdot
3\cdot\phi(x)^{2}+(2n-1)\cdots 3\cdot 1.$

We define integers $c_{i}$ such that $c_{2n}=1$, for an odd integer $r$ we
have $c_{r}=0$ and $c_{2n-(r+1)}=(2n-1)(2n-3)\cdots(2n-r+2)(2n-r)$. Hence we
can write $g_{1}(x)=\sum\limits_{i=0}^{2n}c_{i}\phi(x)^{i}$. Observe that for
every $i\in\\{0,1,\cdots,2n-1\\},$ $c_{i}$ is divisible by the product of the
odd numbers in the interval $(i,2n-1].$ Also, for $0\leq j\leq n$,
$c_{2j}=\frac{u_{2n}}{u_{2j}}$. Let $\ell=k-1$ so that $\ell+1=k$. By Lemma
2.4, there is a prime factor $p\geq k+1$ that divides $c_{2n-\ell-1}$ and
$c_{2n-\ell-2}$, which implies that $p|c_{i}$ for all
$i\in\\{0,1,\cdots,2n-\ell-1\\}$. Clearly $p\nmid c_{2n}$. The slope of the
right-most edge of the $\phi$-Newton polygon of $g_{1}(x)$ with respect to $p$
can be determined by

$\max\limits_{1\leq j\leq
n}\bigg{\\{}\frac{v_{p}(u_{2n})-v_{p}(u_{2n}/u_{2j})}{2j}\bigg{\\}}.$

Using the fact that $v_{p}((2j-1)!)<(2j-1)/(p-1)$, for $1\leq j\leq n$ we
obtain

$v_{p}(u_{2n})-v_{p}(u_{2n}/u_{2j})=v_{p}(u_{2j})\leq
v_{p}((2j-1)!)<\frac{2j-1}{p-1}<\frac{2j}{p-1}.$

As $p\geq k+1$, we deduce that the slope of the right-most edge of the
$\phi$-Newton polygon of $g_{1}(x)$ with respect to $p$ is $<\frac{1}{k}$.
Hence, using Lemma 2.2, we have a contradiction. This completes the proof of
the theorem. ∎

##  4\. Proof of Theorem 1.4.

###### Proof of Theorem 1.4.

It suffices to show that $F_{2}(x)=u_{2n+2}f_{2}(x)$ can not have a factor in
${\mathbf{Z}}[x]$ with degree lying in the interval $[1,(n+1)\deg\phi(x))$. If
we choose a prime $p$ such that $p$ divides $2n+1$, then we have $p$ divides
$\frac{u_{2n+2}}{u_{2j+2}}$ for each $0\leq j\leq n-1$. Hence using Lemma 2.3,
we see that $F_{2}(x)$ can not have any non-constant factor having degree less
than $\deg\phi(x)$. Now assume that $F_{2}(x)$ has a factor in
${\mathbf{Z}}[x]$ with degree lying in the interval
$[\deg\phi(x),(n+1)\deg\phi(x))$. We make use of Lemma 2.2 to obtain a
contradiction. We consider a new polynomial $g_{2}(x)$ with
$a_{n}=1=a_{j}(x)$, $0\leq j\leq n-1$, in $F_{2}(x)$ given by

$g_{2}(x)=\phi(x)^{2n}+(2n+1)\phi(x)^{2n-2}+\cdots+(2n+1)\cdots 7\cdot
5\cdot\phi(x)^{2}+(2n+1)\cdots 5\cdot 3.$

Now we define integers $c_{i}$ such that $c_{2n}=1$, for an odd integer $r$ we
have $c_{r}=0$ and $c_{2n-(r+1)}=(2n+1)(2n-1)\cdots(2n-r+2)$. Hence we can
write $g_{2}(x)=\sum\limits_{i=0}^{2n}c_{i}\phi(x)^{i}$. Observe that for
every $i\in\\{0,1,\cdots,2n-1\\},$ $c_{i}$ is divisible by the product of the
odd numbers in the interval $(i+2,2n+1].$ Also, for $0\leq j\leq n$,
$c_{2j}=\frac{u_{2n+2}}{u_{2j+2}}$. Let $\ell=k-1$ so that $\ell+1=k$. By
Lemma 2.4, there is a prime factor $p\geq k+2$ that divides $c_{2n-\ell-1}$
and $c_{2n-\ell-2}$ unless either (i) $k=2$ and $2n+1=3^{u}$ with some integer
$u\geq 2$ or (ii) $k=4$ and $n=13$. For the moment, suppose we are not in
either of the situations described by (i) and (ii), and fix $p\geq k+2$
dividing $c_{2n-\ell-1}$ and $c_{2n-\ell-2}$. Then $p\nmid c_{2n}$ and
$p|c_{i}$ for all $i\in\\{0,1,\cdots,2n-\ell-1\\}$. Next, we show that the
slope of the right-most edge of the $\phi$-Newton polygon of $g_{2}(x)$ with
respect to $p$ is $<\frac{1}{k}$, but we note here that our argument will only
depend on $p$ being a prime $\geq k+2$ and not on $p$ dividing $c_{2n-\ell-1}$
and $c_{2n-\ell-2}$. The slope of the right-most edge of the $\phi$-Newton
polygon of $g_{2}(x)$ with respect to $p$ can be determined by

$\max\limits_{1\leq j\leq
n}\bigg{\\{}\frac{v_{p}(u_{2n+2})-v_{p}(u_{2n+2}/u_{2j+2})}{2j}\bigg{\\}}.$

For $1\leq j\leq n$, we obtain

$v_{p}(u_{2n+2})-v_{p}(u_{2n+2}/u_{2j+2})=v_{p}(u_{2j+2})\leq v_{p}((2j+1)!).$

If $p>2j+1$, then $v_{p}((2j+1)!)=0.$ If $p\leq 2j+1,$ then $k+1\geq 2j$ and,
from the fact that $v_{p}((2j+1)!)<(2j+1)/(p-1)$, we deduce that

$v_{p}((2j+1)!)<\frac{2j+1}{p-1}\leq\frac{2j+1}{k+1}<\frac{2j}{k}.$

It follows that the slope of the right-most edge of the $\phi$-Newton polygon
of $g_{2}(x)$ with respect to $p$ is $<\frac{1}{k}$. Hence, using Lemma 2.2,
we have a contradiction. Since by hypothesis, we have $2n+1\neq 3^{u}$ for any
integer $u\geq 2$, this contradiction completes the proof of the Theorem 1.4.
∎

##  5\. Proof of Theorem 1.5.

###### Proof of Theorem 1.5.

For proving the result, it is sufficient to show that $H^{\phi}_{2n}(x)$ is
irreducible for all integers $n\geq 2$ and $H^{\phi}_{2n+1}(x)$ is $\phi(x)$
times an irreducible polynomial for all non-negative integers $n$ except in
the case when $2n+1$ is of the form $3^{u}$ for some integer $u\geq 2.$ Let
$m=2n$ or $2n+1$ according as $m$ is even or odd. Let $b_{i}(x)$ with $0\leq
i\leq n-1$ belonging to ${\mathbf{Z}}[x]$ be polynomials having degree less
than $\deg\phi(x)$. Let the content of $(a_{n}b_{0}(x))$ is not divisible by
any prime less than less than or equal to $m$. Then, we define

$f_{1}(x)=\frac{a_{n}}{u_{2n}}\phi(x)^{2n}+\sum\limits_{j=0}^{n-1}b_{j}(x)\frac{\phi(x)^{2j}}{u_{2j}},~{}~{}\mbox{if
$m=2n$, $n\geq 2$ }$

and

$f_{2}(x)=\frac{a_{n}}{u_{2n+2}}\phi(x)^{2n}+\sum\limits_{j=0}^{n-1}b_{j}(x)\frac{\phi(x)^{2j}}{u_{2j+2}},\mbox{
if }m=2n+1\mbox{ and }m\neq 3^{u}\mbox{ for }u\geq 2.$

Using Theorems 1.3, 1.4, we see that $f_{1}(x)$ and $f_{2}(x)$ are irreducible
polynomial over ${\mathbf{Q}}$.

Observe that

$u_{2j}=1\cdot 3\cdots(2j-1)=\frac{(2j)!}{2\cdot 4\cdots
2j}=\frac{(2j)!}{2^{j}j!}.$

Therefore we see that

$\frac{H^{\phi}_{2n}(x)}{u_{2n}}=a_{n}\frac{\phi(x)^{2n}}{u_{2n}}+\sum\limits_{j=0}^{n-1}\binom{n}{j}a_{j}(x)\frac{\phi(x)^{2j}}{u_{2j}},$

and

$\frac{H^{\phi}_{2n+1}(x)}{u_{2n+2}\phi(x)}=a_{n}\frac{\phi(x)^{2n}}{u_{2n+2}}+\sum\limits_{j=0}^{n-1}\binom{n}{j}a_{j}(x)\frac{\phi(x)^{2j}}{u_{2j+2}}.$

So, by taking $b_{j}(x):=\binom{n}{j}a_{j}(x)$ in $f_{1}(x)$ and $f_{2}(x)$,
we have our result. ∎

## References

  * [1] R. Brown, Roots of generalized Schönemann polynomials in henselian extension fields, Indian J. Pure Appl. Math., 39 (2008) 403-410.
  * [2] A. Jakhar, On the factors of a polynomial, Bull. London. Math. Soc., 52 (2020) 158-160.
  * [3] A. Jakhar, On the irreducible factors of a polynomial, Proc. Am. Math. Soc., 148 (2020) 1429-1437.
  * [4] A. Jakhar, On the irreducible factors of a polynomial II, J. Algebra, 556 (2020) 649–655.
  * [5] A. Jakhar, A simple generalization of the Schönemann-Eisenstein irreducibility criterion, Arch. Math., 117 (2021) 375–378.
  * [6] A. Jakhar, N. Sangwan, On a mild generalization of the Schönemann irreducibility criterion, Comm. Algebra, 45 (2017) 1757-1759.
  * [7] B. Jhorar, S. K. Khanduja, A Generalization of the Eisenstein-Dumas-Schönemann Irreducibility Criterion, Proc. Edinb. Math. Soc., 60 (2017) 937-945.
  * [8] A. Jindal, S. K. Khanduja, An extension of Schur’s irreducibility result, (2023) arXiv:2305.04781.
  * [9] I. Schur, Einige Sätze über Primzahlen mit Anwendungen auf Irreduzi- bilitätsfragen, II, Sitzungsber. Preuss. Akad. Wiss. Berlin Phys.-Math. Kl., 14 (1929) 370-391.