# Critical behavior of the fluctuation heat capacity near the glass transition
of metallic glasses

R.A. Konchakov  A.S. Makarov  G.V. Afonin  J.C. Qiao  M.G. Vasin  N.P. Kobelev
V.A. Khonik<EMAIL_ADDRESS>Department of General Physics, State
Pedagogical University, Lenin Street 86, Voronezh 394043, Russia  School of
Mechanics and Civil Architecture, Northwestern Polytechnical University, Xi’an
710072, China  Vereshchagin Institute of High Pressure Physics, Russian
Academy of Sciences, Moscow 108840, Russia  Institute of Solid State Physics,
Russian Academy of Sciences, Chernogolovka, Moscow district 142432, Russia

###### Abstract

The high-frequency shear modulus of five Zr-, Pd-, Cu-based conventional and
two high-entropy bulk metallic glasses was measured in a wide temperature
range up to the beginning of crystallization. Using these data and general
thermodynamic relations, the ”fluctuation” heat capacity $\Delta C_{f}$
determined by local structural fluctuations in the defect regions is
introduced and calculated. It is found that $\Delta C_{f}$ temperature
dependence for all metallic glasses has a large peak located slightly below or
above the glass transition temperature but clearly lower than the
crystallization onset temperature. The form of this peak resembles the
characteristic $\lambda$-peak typical for order-disorder phase transitions. It
is suggested that this $\Delta C_{f}$-peak reflects certain underlying
critical phenomenon. The critical temperature $T_{0}$ (peak temperature) and
corresponding critical index $\alpha$ are determined. Averaged over all seven
metallic glasses under investigation in the initial and relaxed states, the
critical index $\textless\alpha\textgreater=0.26$. The results obtained
indicate that the fluctuations of thermal energy near the glass transition
bear the marks of a continuous phase transition. However, the derived critical
index is between those corresponding to a second-order phase transition
($\alpha\approx 0.1$) and a critical transition characterized by a tricritical
point ($\alpha\approx 0.5$).

###### keywords:

metallic glasses, shear modulus, glass transition, heat capacity,
fluctuations, critical phenomena, critical indexes

##  1 Introduction

It is commonly accepted that supercooled liquids at low enough temperatures
inevitably exhibit structural freezing and formation of a solid glassy state,
which is known as the glass transition [1]. Despite decades of intense
investigations, the nature of the glass transition and structural relaxation
of glasses still remains a major problem of condensed matter physics [2, 3, 4,
5, 6, 7, 8, 9, 10]. Currently, quite a few different approaches to a solution
of the glass transition problem have been proposed. A wide range of approaches
is distributed between the two extreme points of view. On the one hand, it is
assumed that the glass transition is a purely kinetic phenomenon, as
evidenced, for instance, by the heating/cooling rate dependence of the glass
transition temperature $T_{g}$. These approaches are summarized in a recent
review [7]. The second hypothesis is that the glass transition constitutes a
specific phase transition or its consequence [2, 6].

The latter point of view is supported by the fact that, despite the enthalpy
and specific volume change continuously at $T_{g}$, their derivatives, the
heat capacity and thermal expansion coefficient, display characteristic jumps
at this temperature111More precisely, the heat capacity displays either a jump
or a specific $\lambda$-shape change at $T_{g}$, depending on whether cooling
or heating is employed [4], as discussed later., which are distinctive of a
second-order phase transition [11]. Furthermore, various microscopic models
and experiments mark the similarity of the glass transition with continuous
phase transitions (see Ref.[12] and papers cited therein). Perhaps, this is
the reason why The International Union of Pure and Applied Chemistry (UPAC)
defines the glass transition as a second-order phase transition [13]. However,
this definition remains controversial, since glass is not an equilibrium state
of matter and, therefore, the glass transition is not a phase transition in
the strict sense.

The main difficulty encountered in the theoretical description of the glass
transition is the lack of a proper order parameter [14]. Among the approaches
to solve this problem, one can distinguish the use of the quantitative
identification of topological defects in amorphous systems. In this case, the
key condition for the phase transition is the existence of nontrivial
topologically protected structural excitations (disclinations) in the liquid
playing the role of quasiparticles. The glass transition then represents the
condensation in the subsystem of quasiparticles so that the glass transition
constitutes a passage between the two states of a system of topological
defects, i.e. a state in which these defects are mobile, and a state in which
they are frozen [15, 17, 16].

The theoretical description of the glass phase as a frozen system of
topologically stable defects was actively developed at the end of the last
century (see, for example, Refs [2, 18, 19]) and currently again attracts the
attention of researchers [20, 21, 15]. This approach is in line with commonly
accepted notions considering defects as the main elements of glass structure
[22, 23], which can be described by certain disclination networks [24, 25]
characterized by the disclination density tensor [14]. In addition, it well
reproduces the characteristic thermodynamic and kinetic properties of the
glass transition such as the Vogel–Fulcher–Tammann law, specific behavior of
the susceptibility and non-linear susceptibilities as well as the appearance
of the boson peak in the frequency dependence of the dynamic structure factor
near $T_{g}$ [15].

An important features of this topological approach is the ability to describe
the singular behavior of the temperature dependence of the heat capacity in
the glass transition, which relate it with the continuous phase transitions
(see, e.g. Ref.[3]). In the above topological theory, the glass transition is
understood as a phase transition in a tricritical point occurring in the
disclination system [15]. According to the theory, the heat capacity
temperature dependence upon approaching to the tricritical point $T_{0}$ from
low temperatures (i.e. upon heating) is proportional to the power function
[26],

$\Delta C^{heating}_{p}\propto(T_{0}-T)^{-\alpha},$ (1)

where $\alpha$=0.5. This is different from the second order phase transition,
for which $\alpha\approx 0.1$. On the other hand, upon crossing of $T_{0}$
from high temperatures (liquid-to-glass transition), the heat capacity does
not have any pronounced singularity but undergoes a jump down,

$\Delta C^{cooling}_{p}=C_{p}^{liquid}-C_{p}^{glass}=const,$ (2)

that agrees with experimental observations of glass transitions [4, 27, 28].

In this work, we investigate the behavior of the heat capacity of defect
subsystem in the vicinity of the glass transition for several metallic glass-
forming alloys, and determine the critical indexes $\alpha$. For this, we
analyze the experimental data on the shear modulus of a few metallic glasses
(MGs) close to the glass transition in terms of the Interstitialcy theory (IT)
[29, 30], which is extensively applied to the understanding of various
relaxation phenomena in MGs (see Refs [31, 32] and papers cited therein). The
IT assumes that relaxation changes of MGs’ physical properties (e.g. shear
modulus, enthalpy, entropy and Gibbs free energy) are related to the evolution
of glass defect subsystem.

##  2 Determination of the heat capacity of the defect subsystem

###  2.1 Interstitialcy theory

According to the IT, melting of metallic crystals is associated with rapid
generation of interstitial atoms in the dumbbell configuration, which
destabilize the lattice [29, 33] but remain identifiable structural objects in
the liquid state [34] and determine its thermodynamic properties [29, 30].
Melt quenching causes freezing of the defects, which can no longer be detected
in the way used in crystals (two atoms trying to occupy the same potential
well) but can nevertheless be identified according to their specific
properties (strong sensitivity to the applied shear stress, specific strain
fields and low-frequency peculiarities in the vibration spectra, just as in
metallic crystals [31]). We call them interstitial-type defects. Heat effects
occurring upon structural relaxation and crystallization of MGs can be
interpreted as a result of a change of the defect concentration [31]. Since
the defects strongly reduce the non-relaxed (high-frequency) shear modulus
(diaelastic effect), their concentration can be estimated by means of shear
modulus measurements [31]. In the course of heat treatment, not only single
interstitial-type defects but also their clusters of different sizes coexist
in the solid glass [35]. Such clusters, including 5-7 interstitial-type
defects, form structural elements of a non-crystalline matrix with a dominant
icosahedral ordering [35]. It is worthy of notice in this connection that an
interstitial cluster containing seven dumbbell interstitials in crystals
constitutes a perfect icosahedron [36].

The predictive ability of the IT was confirmed by comparing theoretical
calculations of the excess enthalpy and other excess thermodynamic potentials
of MGs (i.e. the potentials related exclusively to the solid glassy state)
with the results of their determination from calorimetric experiments.
Overall, these calculations give all excess thermodynamic potentials equal to
their experimental values to a precision of 10-15%. At that, in the
supercooled liquid state (i.e. above $T_{g}$), the calculated and experimental
values of these excess potentials practically coincide [32]. Therefore, the
IT-based concept assuming interstitial-type defects as major elements of a
non-crystalline metallic medium clearly indicates that the excess
thermodynamic potentials of MGs are determined by the interstitial-type defect
subsystem [32].

###  2.2 Calculation of the heat capacity using experimental data on shear
modulus relaxation

Thus, there are solid arguments that the excess thermodynamic potentials of
MGs are almost exclusively determined by the subsystem of interstitial-type
defects frozen in the solid glass by melt quenching [32]. This defect
subsystem can be characterized by the heat capacity $\Delta C_{def}$.
Relaxation changes of the defect subsystem result in a change of the
macroscopic glass entropy by $\Delta S_{def}$. This entropy change can be
calculated using a general thermodynamic relation [26],

$\Delta S_{def}=-\frac{R_{min}}{T},$ (3)

where $R_{min}$ can be considered as the minimal work, which has to be applied
to transform the defect subsystem into a metastable equilibrium with the glass
matrix and $T$ is the absolute temperature. Eq.(3) shows how much the excess
entropy of a non-equilibrium metallic glass differs from its maximal value at
a given temperature [37].

The minimal work $R_{min}$ necessary to rearrange the defect subsystem is
related to the Gibbs free energy barrier $\Delta\mathcal{G}_{def}$ for
elementary transformation in the defect regions [37], which, in turn, is
quantified by the elastic shear resistance of the surrounding medium and that
is why conditioned by the instantaneous (high-frequency) shear modulus $G$
(simply shear modulus hereafter). Thus, one can accept that
$\Delta\mathcal{G}_{def}=GV_{0}$, where $V_{0}$ is a characteristic volume of
local atomic rearrangements in defect regions [38, 39, 40, 41]. At that,
relaxation changes of the defect concentration determine the above minimal
work and can be related to the relaxation component $G_{rel}$ of the shear
modulus $G$ as [37]

$dR_{min}=\frac{N_{A}V_{0}}{\beta}dG_{rel},$ (4)

where dimensionless $\beta$ (about 20 for different MGs) is the shear
susceptibility, which characterizes the dependence of the shear modulus on the
defect concentration [31] (i.e. defines the diaelastic effect) and $N_{A}$ is
the Avogadro number.

Relaxation rearrangements in the defect subsystem are accompanied by a heat
effect, which, using Eqs (3) and (4), can be accepted as [37]

$\delta Q=TdS_{def}=-dR_{min}=-\frac{N_{A}V_{0}}{\beta}dG_{rel}.$

Differentiation of this relation over temperature gives the macroscopic heat
flow, which very well corresponds to the experimental calorimetric data for
different MGs [37].

The isobaric excess heat capacity related to the defect subsystem then becomes

$\Delta C_{def}=T\frac{\partial S_{def}}{\partial
T}=-\frac{N_{A}V_{0}}{\beta}\frac{dG_{rel}}{dT}.$ (5)

As mentioned above, the excess thermodynamic potentials of MGs are conditioned
by the interstitial-type defect subsystem. Then, Eq.(5) shows that the
corresponding excess heat capacity $\Delta C_{def}$ of the whole defect
subsystem is conditioned by the derivative of the relaxation component of the
shear modulus over temperature. Within the IT framework, the heat capacity
$\Delta C_{def}$ constitutes the macroscopic excess heat capacity of metallic
glass with respect to the maternal crystalline state.

On the other hand, one should recall that elementary rearrangements in defect
regions take place as a result of local atomic displacements driven by thermal
fluctuations. To characterize these fluctuation-induced rearrangements, one
can introduce a ”fluctuation” heat capacity $\Delta C_{f}$. According to the
fluctuation thermodynamics, the work $R_{min}$ characterizes the change of the
Gibbs free energy $\Delta\mathcal{G}_{f}$ determined by fluctuation
rearrangements [26]. Then, one can calculate the entropy change due to these
rearrangements using a general thermodynamic relation, $\Delta
S_{f}=-\left.{\partial\Delta\mathcal{G}_{f}}\right/{\partial T}$ [26].
Accepting that $\left.{\partial\Delta\mathcal{G}_{f}}\right/{\partial
T}=\left.{\partial R_{min}}\right/{\partial T}$, where $R_{min}$ is given by
Eq.(4), one arrives at the heat capacity determined by thermal fluctuations,

$\Delta C_{f}=T\frac{d\Delta
S_{f}}{dT}=T\frac{N_{A}V_{0}}{\beta}\frac{d^{2}G_{rel}}{dT^{2}},$ (6)

It is seen that the fluctuation heat capacity $\Delta C_{f}$ is given by the
second derivative of the relaxation component of the shear modulus over
temperature, contrary to the defect-induced heat capacity $\Delta C_{def}$ (5)
determined by the first derivative of the shear modulus relaxation component.
It is also to be mentioned that the defect heat capacity $\Delta C_{def}$ (5)
equals the fluctuation entropy $\Delta S_{f}$. This is in agreement with
general thermodynamic theory of fluctuation, which shows that the mean square
fluctuation of the entropy is proportional to the heat capacity of a body
[26].

To calculate the relaxation component of the shear modulus $G_{rel}$ entering
Eqs (5) and (6), let us represent the shear modulus as a sum of the harmonic,
anharmonic, electronic and relaxation components [37, 42]:

$G(T)=G_{0}\;[1-a_{anh}T-a_{el}T^{2}+a_{rel}(T)].$ (7)

where $G_{0}$ constitutes temperature-independent harmonic contribution to the
shear modulus, the term $-G_{0}a_{anh}T$ gives the anharmonic component, the
summand $-G_{0}a_{el}T^{2}$ describes the component of the shear modulus
occurring due to the free electrons and $G_{0}a_{rel}(T)$ corresponds to the
relaxation component of the shear modulus, which depends on temperature $T$
and thermal prehistory in a complicated way. Expressing the relaxation part of
the shear modulus $G_{rel}$ from Eq.(7) and taking into account that the
electronic component of shear modulus $-G_{0}\alpha_{el}T^{2}$ in Eq.(7) is
much less than any other component [42] and, therefore, can be neglected, one
arrives at

$\frac{dG_{rel}}{dT}\approx\frac{dG}{dT}+G_{0}\alpha_{anh}T,$ (8)
$\frac{d^{2}G_{rel}}{dT^{2}}\approx\frac{d^{2}G}{dT^{2}}.$ (9)

These equations show that the derivatives of the relaxation component of the
shear modulus $G_{rel}$ entering relations (5) and (6) can be calculated from
experimental data on temperature dependencies of the shear modulus $G(T)$.

##  3 Experimental details

The investigation was performed on bulk glassy conventional Cu49Hf42Al9,
Zr46Cu45Al7Ti2, Zr65Cu15Al10Ni10, Pd40Ni40P20, Pd43.2Cu28Ni8.8P20 and high-
entropy Ti16.7Zr16.7Hf16.7Cu16.7Ni16.7Be16.7,
Zr35Hf17.5Ti5.5Al12.5Co7.5Ni12Cu10 (at.%) metallic glasses produced by melt
suction in a copper mold. The non-crystallinity of castings was confirmed by
X-ray diffraction. Differential scanning calorimetry (DSC) was carried out by
a Hitachi DSC 7020 instrument operating in high purity (99.999 %) nitrogen
atmosphere at a heating rate of 3 K/min. The reference cell of the DSC
instrument contains crystallized sample of a glass under investigation so that
the measured heat flow constitutes the difference between the heat flow coming
from glass and its crystalline state.

The electromagnetic acoustic transformation (EMAT) method [43] was used to
measure the transverse resonant frequencies $f$ (500-700 kHz) of samples in a
vacuum of $\approx{0.01}$ Pa. For this purpose, frequency scanning was
automatically performed every 10-15 s upon heating and the resonant frequency
was determined as the frequency corresponding to the maximal signal response
received by a pick-up coil. The shear modulus was then calculated as
$G(T)=G_{rt}f^{2}(T)/f^{2}_{rt}$, where $f_{rt}$ and $G_{rt}$ are the
vibration frequency and shear modulus at room temperature, respectively. The
errors for the absolute $G_{rt}$-values were accepted to be 1-2$\%$. The
errors in the absolute $G(T)$-data are about the same while the error in the
measurements of $G(T)$-changes was estimated to be $\approx 5$ ppm near room
temperature and about 100 ppm near $T_{g}$.

##  4 Experimental results

Figure 1:  Temperature dependences of the shear modulus $G$ of bulk glassy
high-entropy Ti16.7Zr16.7Hf16.7Cu16.7Ni16.7Be16.7 in the initial state and
after relaxation performed by heating into the supercooled liquid state. The
calorimetric glass transition temperature $T_{g}$ and crystallization onset
temperature $T_{cr}$ are indicated by the arrows. The dashed line gives linear
approximation of $G(T)$-dependence at temperatures $T\leq 450$ K where
structural relaxation is absent.

Figure 1 shows temperature dependences of the shear modulus $G$ of high-
entropy Ti16.7 Zr16.7Hf16.7Cu16.7Ni16.7Be16.7 glass in the initial state (1st
run) and after relaxation (2nd run) performed by heating up to $T=688$ K (deep
in the supercooled liquid state) and subsequent cooling to room temperature at
the same rate. In the initial state, one observes a linear $G$-decrease at
temperatures $T\leq 450$ K due to the anharmonicity approximated by a dashed
line, which is followed by an increase of the shear modulus over pure
anharmonic decrease due to exothermal structural relaxation. Reaching the
calorimetric $T_{g}\approx 670$ K leads to a rapid decrease of the shear
modulus so that the slope $dG/dT$ increases from $-3.6\times 10^{-3}$ GPa/K
below $T_{g}$ up to $-2.6\times 10^{-3}$ GPa/K in the supercooled liquid state
above $T_{g}$. Within the IT framework, this shear softening effect and
related strong heat absorption can be understood in terms of a rapid
multiplication of interstitial-type defects above $T_{g}$ [31].

The relaxation by heating up to $T=688$ K and subsequent cooling results in
$\approx 5\%$ increase of the shear modulus at room temperature. Heating of
the relaxed sample does not lead to any exothermal structural relaxation and
$G(T)$-dependence is nearly linear below 600 K. At higher temperatures, the
shear modulus decreases faster than in the case of pure anharmonic behavior,
which is due to the endothermal structural relaxation leading to an increase
of the defect concentration. Above $T_{g}$, temperature dependence $G(T)$ in
the relaxed state coincide with that in the initial state indicating the loss
of the memory of the thermal prehistory in the supercooled liquid region.

Temperature dependences of the shear modulus for other MGs under investigation
are quite similar to that exemplified by Fig.1 and are not shown here.

A typical calorimetric behavior of MGs is illustrated by Fig.2, which shows a
DSC scan of glassy Cu49Hf42Al9. The supercooled liquid state is manifested by
a strong endothermal heat flow, which is followed by sharp crystallization-
induced exothermal reaction. It is important to notice that the initial state
(1st run) is characterized by a notable exothermal reaction, which disappears
after the relaxation (2nd run). Thus, the relaxed sample displays only
endothermal relaxation, which is moderate below $T_{g}$ and quite pronounced
above $T_{g}$.

##  5 Calculation of the heat capacities and estimate of the critical index
$\alpha$

Using the derived $G(T)$-dependences, first, the summands $G_{0}$ and
$G_{0}\alpha_{anh}T$ in Eq.(8) were determined for all MGs. This was done by
linear fitting of these dependences considered in temperature range
corresponding to the absence of structural relaxation as exemplified by the
dashed line in Fig.1 (see also Ref.[42] for more details). This allowed to
derive the relaxation component of the shear modulus as

$G_{rel}(T)=G_{0}\alpha_{rel}(T)=G(T)-G_{0}+G_{0}\alpha_{anh}T.$ (10)

Then, the first and second derivatives of $G_{rel}$ over temperature were
determined (see Eqs ((8) and (9)) and the heat capacities $\Delta C_{def}$
(Eq.(5)) and $\Delta C_{f}$ (Eq.(6)) were next calculated.

Figure 2: DSC trace of glassy Cu49Hf42Al9 in the initial and relaxed states at
a rate of 3 K/min. The inset shows the region below glass transition, the
supercooled liquid region and crystallization onset on an enlarged scale. The
ways of the determination of the glass transition and crystallization onset
temperatures, $T_{g}$ and $T_{cr}$, are shown.  Figure 3: Panel (a):
Temperature dependencies of the defect heat capacity $\Delta C_{def}$ and
fluctuation heat capacity $\Delta C_{f}$ for glassy Cu49Hf42Al9 in the initial
and relaxed state. The glass transition and crystallization onset
temperatures, $T_{g}$ and $T_{cr}$, are indicated. The peaks on $\Delta
C_{f}(T)$-dependences are seen. Panel (b): fluctuation heat capacity $\Delta
C_{f}$ of the same glass as a function of $T_{0}-T$ ($T_{0}$ is the
temperature of the $\Delta C_{f}$-peak) in the logarithmic scale on both axes.
The dashed lines give the least-square fits. The critical indexes $\alpha$ and
critical (peak) temperatures $T_{0}$ are indicated.

Figure 3(a) illustrates the obtained results using the data on Cu49Hf42Al9
glass taken as an example. In the initial state, the defect heat capacity
$\Delta C_{def}$ is first negative then starts to rapidly increase just below
$T_{g}$ up to a level of $\approx 40$ J/(K$\cdot$mol). Further heating results
in a drop of $\Delta C_{def}$ down to zero above the crystallization onset
temperatures $T_{cr}$. The negative $\Delta C_{def}$-values originate from
exothermal structural relaxation (see Fig.2), which is determined by a
decrease of the defect concentration in the initial glass [31]. After the
relaxation, this effect disappears and $\Delta C_{def}$ is always positive
that can be attributed to an increase of the defect concentration and related
heat absorption (which is seen in Fig.2 [31]. Above $T_{g}$, the defect heat
capacity in the initial state is close to that in the relaxed state.

Figure 4: Temperature dependencies of the defect heat capacity $\Delta
C_{def}$ and fluctuation heat capacity $\Delta C_{f}$ for the indicated
conventional and high-entropy MGs in the initial and relaxed states. The peaks
of the fluctuation heat capacity $\Delta C_{f}$ slightly below or above the
glass transition temperature $T_{g}$ are seen. The $\Delta C_{f}(T)$-peaks are
located below the crystallization onset temperatures $T_{cr}$.

The fluctuation heat capacity $\Delta C_{f}$ in both initial and relaxed
states is first close to zero up to temperatures $T\approx T_{g}-20$ K, then
rapidly increases and forms a large peak, which is located by about 50 K below
the crystallization onset temperature $T_{cr}$.

Figure 4 shows temperature dependences of the heat capacities $\Delta C_{def}$
and $\Delta C_{f}$ for all other MGs under investigation. In general, these
dependences are quite similar to that shown in Fig.3(a). The following common
features can be summarized.

First, the defect heat capacities $\Delta C_{def}$ in the initial state are
negative up to temperatures by about 3-15 K below $T_{g}$ but rapidly increase
at higher temperatures. Within the IT framework, these features can be
attributed to exo- (endo-) thermal structural relaxation conditioned by a
decrease (increase) of the defect concentration and related shear hardening
(softening) [31]. It is to be noted that the maximal $\Delta C_{def}$-values
change from $\approx 15$ J/(K$\cdot$mol) to $\approx 40$ J/(K$\cdot$mol) (i.e.
about 0.6 $R$ to 1.6 $R$, where $R$ is the universal gas constant). As a
matter of fact, these maximal $\Delta C_{def}$-values correspond to the
increase of the heat capacity upon heating from the glassy to supercooled
liquid state (i.e. represent the $\Delta C_{glass-liquid}$ heat capacity
increase) and in general agree with literature data. For instance, the maximal
defect heat capacity for glassy Pd43.2Cu28Ni8.8P20 is about $\Delta
C_{def}=20$ J/(K$\cdot$mol) (Fig.4(b)) that practically equals $\Delta
C_{glass-liquid}\approx 21$ J/(K$\cdot$mol) for a similar Pd42.5Cu27Ni9.5P21
glass [44]. At that, Zr-based glasses (Fig.4(b,d,f)) show the maximal values
$\Delta C_{def}\approx 20$ J/(K$\cdot$mol) while about the same values of
$\Delta C_{glass-liquid}$ heat capacity jump are reported for other Zr-based
MGs [45].

The fluctuation heat capacity $\Delta C_{f}$ in all cases demonstrates a peak
at a temperature $T_{0}$. Table 1 gives the characteristic temperatures
$T_{g}$, $T_{cr}$ and the peak temperatures $T_{0}$ in the initial and relaxed
states. It is seen the $\Delta C_{f}$-peak is located by 10 K to 63 K below
the crystallization onset temperature. It can be concluded, therefore, that
this peak is not related to crystallization. It is worthy of notice that the
height of this peak is by more that an order of magnitude bigger that the
height of the defect-induced excess heat capacity peak.

##  6 Discussion

Temperature dependence of the fluctuation heat capacity $\Delta C_{f}(T)$
derived above reflects the changes of the fluctuation energy with increasing
temperature. Figs 3(a) and Fig.4 show that this dependence displays a peak
located quite near the glass transition temperature but below the
crystallization onset temperature. The form of the peak resembles the
characteristic $\lambda$-peak typical for order-disorder phase transitions
[46]. The phenomena occurring in the vicinity of phase transitions due the
fluctuations of the thermodynamic parameters are generally called the critical
phenomena while the transition temperature $T_{0}$ is referred to as the
critical temperature [26, 46]. The approach to a critical point results in
drastic increase of the fluctuations that leads to a (theoretically unlimited)
growth of the second derivatives of the Gibbs free energy including the heat
capacity. The thermodynamic parameters at critical points have certain
peculiarities related to the specificity of fluctuation phenomena [47]. In
particular, the critical points for second-order phase transitions reflect the
abnormal growth of the fluctuations of the order parameter due to the flatness
of the Gibbs free energy near the transition point [26]. Due to the absence of
a discontinuity of the derivative of the Gibbs free energy, second-order phase
transitions are also called ”continuous phase transitions”. The phenomena
associated with continuous phase transitions are also called the critical
phenomena, due to their association with critical points.

A curve of a second-order phase transition separate the phases (on a $(P,T)$
diagram) with different symmetry and cannot terminate in a certain point. This
curve, however, can transform into a curve of a first-order phase transition.
The corresponding transition point is called the tricritical point [26].
Temperature dependence of the change of the isobaric heat capacity near the
critical points is generally described by Eq.(1). The critical index $\alpha$
in this relation reflects the origin of the phase transition. For a second-
order phase transition, $\alpha\approx 0.1$ [48, 49] while for a critical
phenomenon corresponding to a tricritical point $\alpha\approx 0.5$ [15, 26,
47]. In the latter case, fluctuations are less significant but nonetheless
play an important role [47].

Table 1: Glass transition temperatures $T_{g}$, crystallization onset temperatures $T_{cr}$ and peak (critical) temperatures $T_{0}$ in $\Delta C_{f}(T)$-dependences (see Fig.3(a) and Fig.4) together with the critical exponents $\alpha$ for the MGs under investigation in the initial and relaxed states.  N | Glass composition (at.%) | $T_{g}$ | $T_{cr}$ | $T_{0}^{ini}$ | $\alpha^{ini}$ | $T_{0}^{rel}$ | $\alpha^{rel}$
---|---|---|---|---|---|---|---
|  | [K] | [K] | [K] |  | [K] |
1 | $Cu_{49}Hf_{42}Al_{9}$ | 765 | 816 | 790 |  0.30$\pm$0.05 | 783 |  0.54$\pm$0.04
2 | $Zr_{46}Cu_{45}Al_{7}Ti_{2}$ | 671 | 717 | 677 |  0.27$\pm$0.05 | 676 |  0.26$\pm$0.08
3 | $Pd_{40}Ni_{40}P_{20}$ | 580 | 635 | 585 |  0.35$\pm$0.05 | 576 |  0.19$\pm$0.03
4 | $Pd_{43.2}Cu_{28}Ni_{8.8}P_{20}$ | 540 | 606 | 550 |  0.32$\pm$0.10 | 543 |  0.26$\pm$0.08
5 | $Zr_{65}Cu_{15}Al_{10}Ni_{10}$ | 627 | 696 | 643 |  0.18$\pm$0.07 | 640 |  0.26$\pm$0.08
6 | $Ti_{16.7}Zr_{16.7}Hf_{16.7}Cu_{16.7}Ni_{16.7}Be_{16.7}$ | 670 | 695 | 681 |  0.18$\pm$0.04 | 678 |  0.21$\pm$0.05
7 | $Zr_{35}Hf_{17.5}Ti_{5.5}Al_{12.5}Co_{7.5}Ni_{12}Cu_{10}$ | 694 | 724 | 707 |  0.17$\pm$0.04 | 714 |  0.16$\pm$0.04

Thus, the critical index $\alpha$ provides certain information on the nature
of corresponding critical phenomenon. In our investigation, we analyze the
heat capacity $\Delta C_{f}$ conditioned by thermal fluctuations. To obtain
information on related processes, on can plot the function $\Delta C_{f}(T)$
in the logarithmic scale on both axes. Provided that this data representation
is linear, one can determine the critical index $\alpha$. An example for
Cu49Hf42Al9 glass is given in Fig.3(b), which shows $ln\;\Delta C_{f}$ as a
function of $ln\;(T_{0}-T)$ in a small temperature range of $T_{0}-T\leq 10$ K
below $T_{0}$, where $T_{0}$ corresponds to the $\Delta C_{f}(T)$-peak in
Fig.3(a) and accepted to be the critical point. It is seen that this
representation is indeed linear providing a critical index $\alpha\approx
0.30$ in the initial state. Quite surprisingly, the critical index is almost
twice larger for the relaxed state, $\alpha\approx 0.54$. This clearly
indicates that the fine structure of glass in the supercooled liquid state can
be dependent on the thermal prehistory despite the facts that i) $\Delta
C_{f}(T)$-dependences for the initial and relaxed states (Fig.3(a)) look quite
similar (although quite scattered) and ii) the shear modulus behavior in the
supercooled liquid region for the initial and relaxed states is also fairly
similar (Fig.1, just the same was documented earlier for another metallic
glass [42]).

Similar results were obtained for other MGs. In all cases, the dependences
$\Delta C_{f}$ vs $T_{0}-T$ in the log-log scale were found to be linear and
the corresponding critical indexes $\alpha$ were calculated. The results are
summarized in Table 1, which lists $\alpha$-values for the initial and relaxed
states. On the average over all MGs, $\textless\alpha^{ini}\textgreater=0.25$
for the initial state that within the error coincides with
$\textless\alpha^{rel}\textgreater=0.27$ for the relaxed state. Most often,
$\alpha$-values for the initial and relaxed stated are nearly equal while some
exceptions exist (see lines 1 and 3). Ignoring the distinction between
different MGs and their structural states, one can accept that the critical
index $\alpha\approx 0.26$. This is approximately between a second-order
transition ($\alpha\approx 0.1$) and critical behavior near a tricritical
point ($\alpha\approx 0.5$). It is also worthy of notice that the critical
indexes for high-entropy MGs (lines 6 and 7 in Table 1) tend to the values
characteristic of a second-order phase transition that could reflect the high-
entropy nature of these glasses.

The obtained results demonstrate the singular behavior of the fluctuation heat
capacity near the glass-to-liquid transition and confirm the assumption that
the glass transition is a continuous phase transition. In this case, the term
”phase” is used in a broader sense than usually by considering the glassy
state of matter as a phase. At the same time, these result are unexpected. On
the one hand, the derived critical index significantly bigger than that for a
a second order phase transition. On the other hand, it is notably less than
the $\alpha$-value characteristic of a transition with a tricritical point as
predicted in Ref.[15].

To explain the obtained the result, one should note that in the case of the
tricritical behavior the equality $\alpha=0.5$ is true only in the mean field
approximation. In real systems, the accounting for the fluctuation corrections
at the tricritical point can lead to $\alpha<0.5$ [50]. Besides that, it is
known that the calculated critical index is true only in the asymptotic
approximation. In a real situation, however, the critical indexes depend
largely on the details of the model. In addition, one should not forget that
the glassy state is not an equilibrium one and the relaxation dynamics may
lead to additional corrections to the critical indexes. Therefore, the
question about the universality class of the non-crystalline systems under
study remains open for further experimental and theoretical studies.

In any case, one can expect that a ”phase” transition might exist provided
that the defect subsystem in a metallic glass can be characterized by certain
ordering, e.g. a correlation between orientations of the defects. This seems
reasonable when taking into account that interstitial-type defects under
consideration have certain orientations and interact through their stress
fields. This ordering weakens upon approaching to the critical temperature
$T_{0}$. One can roughly estimate the correlation radius $R_{c}$ of the
interaction between the defects using the relation [51]

$\frac{\left(2R_{c}\right)^{3}}{V_{0}}=\frac{\Delta C_{f}(T_{0})}{\Delta
C_{def}(T_{0})},$ (11)

where $V_{0}$ is the characteristic volume (already mentioned above)
comprising atomic rearrangements in defect regions. Direct comparison of the
shear viscosity and shear modulus for a metallic glass above $T_{g}$ showed
that $V_{0}$ is about one volume per atom $V_{at}$ 222This estimate was
accepted as the average $V_{0}$-value calculated using shear modulus and
viscosity data in the supercooled liquid state for five MGs given in
Ref.[52].. For the data shown in Fig.4, the ratio $\frac{\Delta
C_{f}(T_{0})}{\Delta C_{def}(T_{0})}$ is about 15 to 30 . Thus, the mutual
coordination (ordering) of defects should take place in the volume of about
$(15\div 30)\;V_{at}$. It is to be noted also that the $\Delta C_{f}$-peak for
$Cu_{49}Hf_{42}Al_{9}$ glass (Fig.3(a)) is several times larger that those for
other MGs (Fig.4) while the ratio $\frac{\Delta C_{f}(T_{0})}{\Delta
C_{def}(T_{0})}\approx 40$ is also notably larger. Thus, this glass is
peculiar in some sense that could reflect larger defect ordering, which, in
turn, requires larger energy for its destruction. It is interesting to
underline in this context that the critical temperature $T_{0}$ for this glass
is about 790 K (Fig.3) that practically equals to the temperature of the heat
flow peak in the DSC diagram given in Fig.2.

##  7 Conclusions

We performed detailed measurements of the high-frequency shear modulus $G$ of
seven bulk metallic glasses, including two high-entropy MGs. On this basis,
using the general approach given by the Interstitialcy theory, we calculated
the heat capacity $\Delta C_{def}$ of interstitial-type defect subsystem of
glass. This heat capacity practically equals to the excess heat capacity of
glass with respect to the maternal crystalline state.

Next, we introduced and calculated the ”fluctuation” heat capacity $\Delta
C_{f}$ determined by local structural fluctuations in defect regions. It is
shown that while the defect heat capacity $\Delta C_{def}$ is proportional to
the first derivative of the relaxation component of the shear modulus
$G_{rel}$ over temperature, the fluctuation heat capacity is determined by the
second derivative of $G_{rel}$.

It is found that the fluctuation heat capacity has a peak near the glass
transition temperature but clearly below the crystallization onset
temperature. The height of $\Delta C_{f}$ is 15-40 times larger that the level
of the defect heat capacity in the supercooled liquid state while its form
resembles the characteristic $\lambda$-peak typical for order-disorder phase
transitions. It is argued that this $\Delta C_{f}$-peak corresponds to certain
underlying critical phenomenon and the peak temperature $T_{0}$ represents a
critical temperature.

For all MGs under investigation in the initial and relaxed states, the
averaged critical index is found to be $\textless\alpha\textgreater=0.26$. The
results obtained indicate that the fluctuations of thermal energy near the
glass transition bear the marks of a continuous phase transition. However, the
critical index is between those corresponding to a second-order phase
transition ($\alpha\approx 0.1$) and a critical transition characterized by a
tricritical point ($\alpha\approx 0.5$). It is suggested that the origin of
the observed critical behavior is related to the ordering of the defect
structure below $T_{0}$ and the disruption of this order upon approaching
$T_{0}$. Any similar studies on MGs are unknown to us.

##  8 Acknowledgments

The work was supported by Russian Science Foundation under the project No.
23-12-00162.

## References

  * [1] C.A. Angell, K. Rao K J.Chem. Configurational excitations in condensed matter, and the ”bond lattice” model for the liquid-glass transition, J. Chem. Phys. 57 (1972) 470-481.
  * [2] D.R. Nelson, Order, frustration, and defects in liquids and glasses, Phys. Rev. B 1983 (28) 5515-5535.
  * [3] S.V. Nemilov, Thermodynamic and kinetic aspects of the vitreous state, CRC Press, Boca Raton, 1995.
  * [4] J.C. Dyre. The glass transition and elastic models of glass-forming liquids. Rev. Mod. Phys. 78 (2006) 953-972.
  * [5] S. Wei, F. Yang, J. Bednarcik, I. Kaban, O. Shuleshova, A. Meyer, R. Busch, Liquid–liquid transition in a strong bulk metallic glass-forming liquid, Nat. Commun. 4 (2013) 2083.
  * [6] S. Albert, T. Bauer, M. Mich, G. Biroli, J.-P. Bouchaud, A. Loid, P. Lunkenheimer, R. Tourbot, C. Wiertel-Gasquet, F. Ladieu, Fifth-order susceptibility unveils growth of thermodynamic amorphous order in glass-formers, Science 352 (2016 ) 1308-1311.
  * [7] D.S. Sanditov, M.I. Ojovan, Relaxation aspects of the liquid–glass transition, Physics-Uspekhi, 62 (2019) 111-130.
  * [8] Q. Du, X. Liu, H. Fan, Q. Zeng, Y. Wu,H. Wang, D. Chatterjee, Y. Ren, Y. Ke, P.M. Voyles, Z. Lu, E. Ma, Reentrant glass transition leading to ultrastable metallic glass, Mater. Today 34 (2020) 66-77.
  * [9] W. Dong, Z. Wu, J. Ge, S. Liu, S. Lan, E.P. Gilbert, Y. Ren, D. Ma, X.-L. Wang, In situ neutron scattering studies of a liquid–liquid phase transition in the supercooled liquid of a Zr–Cu–Al–Ag glass-forming alloy, Appl. Phys. Lett. 118 (2021) 191901.
  * [10] J. Shen, Y.H. Sun, J. Orava, H.Y. Bai, W.H. Wang, Liquid-to-liquid transition around the glass-transition temperature in a glass-forming metallic liquid, Acta Mater. 225 (2022) 117588.
  * [11] J.W.P. Schmelzer, I.S. Gutzow, Glasses and the Glass Transition, WILEY-VCH Verlag GmbH $\&$ Co. KGaA, 2011.
  * [12] R.F. Tournier, Glass phase and other multiple liquid-to-liquid transitions resulting from two-liquid phase competition, Chem. Phys. Lett. 665 (2016) 64–70.
  * [13] IUPAC. Compendium of Chemical Terminology. 66, 583 (Cambridge: Royal Society of Chemistry, 1997).
  * [14] V.M. Manichev, Icosahedral order, disclinations and the order parameter in simple metallic glasses, J. Non-Cryst. Sol. 192$\&$193 (1995) 612-615.
  * [15] M.G. Vasin, Glass transition as a topological phase transition, Phys. Rev. E 106 (2022) 044124.
  * [16] M.G. Vasin, V.M. Vinokur, Bose system critical dynamics near quantum phase transition, Physica A 575 (2021) 126035.
  * [17] M.G. Vasin, Gauge theory of glass transition, J. Stat. Mech.: Theory and Experiment (2011) P05009.
  * [18] G. Toulouse, Theory of the frustration effect in spin glasses, Commun. Phys. 2 (1977) 115-119.
  * [19] N. Rivier, Disclination lines in glasses, Phil. Mag. A 40 (1979) 859-868.
  * [20] M. Baggioli, I. Kriuchevskyi, T.W. Sirk, A. Zaccone, Plasticity in amorphous solids is mediated by topological defects in the displacement field, Phys. Rev. Lett. 127 (2021) 015501.
  * [21] M. Baggioli, M. Landry, A. Zaccone, Deformations, relaxation, and broken symmetries in liquids, solids, and glasses: A unified topological field theory, Phys. Rev. E 105 (2022) 024602.
  * [22] Y.Q. Cheng, E. Ma, Atomic-level structure and structure–property relationship in metallic glasses, Prog. Mater. Sci. 56 (2011) 379-473.
  * [23] A. Hirata, L.J. Kang, T. Fujita, B. Klumov, K. Matsue, M. Kotani, A.R. Yavari, M.W. Chen, Geometric frustration of icosahedron in metallic glasses, Science 341 (2013) 376-379.
  * [24] D.W. Qi, S. Wang, Icosahedral order and defects in metallic liquids and glasses, Phys. Rev. B 44 (1991) 884-887.
  * [25] V. Borodin, A model of defects in metallic glasses, J. Non-Cryst. Sol. 192$\&$193 (1995) 599-602.
  * [26] L.D. Landau, E.M. Lifshitz. Statistical Physics. Vol. 5 (3rd ed.). Butterworth-Heineman, 1980.
  * [27] Philip W. Anderson, Lectures on amorphous systems, 1984, R. Balian et al eds. III-Condensed Matter: Les Houches Session XXXI. World Scientific Publishing Company, 159-262.
  * [28] M.I. Ojovan, Viscosity and glass transition in amorphous oxides, Adv. Cond. Matter Phys. 2008 (2008) 817829.
  * [29] A.V. Granato, Interstitialcy model for condensed matter states of face-centered-cubic metals, Phys. Rev. Lett. 68 (1992) 974-977.
  * [30] A.V. Granato, Interstitialcy theory of simple condensed matter, Eur. J. Phys. B 87 (2014) 18.
  * [31] V.A. Khonik, N. Kobelev. Metallic glasses: a new approach to the understanding of the defect structure and physical properties. Metals 9 (2019) 605.
  * [32] A.S. Makarov, M.A. Kretova, G.V. Afonin, J.C. Qiao, A.M. Glezer, N.P. Kobelev, V.A. Khonik, On the nature of the excess internal energy and entropy of metallic glasses, J. Exp. Theor. Phys. Lett. 115 (2022) 102-107.
  * [33] R.A. Konchakov, A.S. Makarov, A.S. Aronin, N.P. Kobelev, V. A. Khonik, On the mechanism of melting in simple metals, J. Exp. Theor. Phys. Lett. 113 (2021) pp. 345–351.
  * [34] K. Nordlund, Y. Ashkenazy, R.S. Averback, A.V. Granato, Strings and interstitials in liquids, glasses and crystals, Europhys. Lett. 71 (2005) 625-631.
  * [35] R.A. Konchakov, A.S. Makarov, N.P. Kobelev, A.M. Glezer, G. Wilde, V.A. Khonik, Interstitial clustering in metallic systems as a source for the formation of the icosahedral matrix and defects in the glassy state, J. Phys.: Condens. Matter 31 (2019) 385703.
  * [36] W. Ingle, R.C. Perrin, H.R. Schober, Interstitial cluster in FCC metals, J. Phys. F: Met. Phys. 11 (1981) 1161-1173.
  * [37] A.S. Makarov, G.V. Afonin, A.S. Aronin, N.P. Kobelev, V.A. Khonik, Thermodynamic approach for the understanding of the kinetics of heat effects induced by structural relaxation of metallic glasses, J. Phys.: Condens. Matter 34 (2022) 125701.
  * [38] S.V. Nemilov, Kinetics of elementary processes in the condensed state. II. Shear relaxation and the equation of state for solids, Russ. J. Phys. Chem. 42 (1968) 726-729.
  * [39] J.C. Dyre, N.B. Olsen, T. Christensen, Local elastic expansion model for viscous-flow activation energies of glass-forming molecular liquids, Phys. Rev. B 53 (1996) 2171-2174.
  * [40] S.V. Nemilov, Interrelation between shear modulus and the molecular parameters of viscous flow for glass forming liquids. J. Non-Cryst. Sol. 352 (2006) 2715-2725.
  * [41] J.C. Dyre, W.H. Wang, The instantaneous shear modulus in the shoving model, J. Chem. Phys. 136 (2012) 224108.
  * [42] A. Makarov, M. Kretova, G. Afonin, N. Kobelev, V. Khonik. Components of the shear modulus and their dependence on temperature and plastic deformation of a metallic glass, Metals 12 (2022) 1964.
  * [43] A.N. Vasil’ev, Yu.P. Gaidukov, Electromagnetic excitation of sound in metals, Sov. Phys. Usp. 26 (1983) 952-973.
  * [44] N. Neuber, O. Gross, M. Frey, B. Bochtler, A. Kuball, S. Hechler, I. Gallino, R. Busch, On the thermodynamics and its connection to structure in the Pt-Pd-Cu-Ni-P bulk metallic glass forming system, Acta Mater. 220 (2021) 117300.
  * [45] Q.K. Jiang, X.D. Wang, X.P. Nie, G.Q. Zhang, H. Ma, H.-J. Fecht, J. Bendnarcik, H. Franz, Y.G. Liu, Q.P. Cao, J.Z. Jiang, Zr–(Cu,Ag)–Al bulk metallic glasses, Acta Mater. 56 (2008) 1785-1796.
  * [46] J. Frenkel. Kinetic Theory of Liquids. Oxford University Press, New York, NY, USA, 1946.
  * [47] S.M. Stishov, A.E. Petrova, Critical points and phase transitions, J. Exp. Theor. Phys. 131 (2020) 1056-1063.
  * [48] J.C. Le Guillou, J. Zinn-Justin, Critical exponents from field theory, Phys. Rev. B 21 (1980) 3976-3998.
  * [49] G.A. Martynov, Fluctuation theory of liquids, High Temp. 56 (2018) 340–350.
  * [50] A.N. Vasiliev, Quantum-Field Renormalization Group in the Theory of Critical Phenomena and Stochastic Dynamics, CRC Press, Boca Raton, FL, 2004, p. 705.
  * [51] V.S. Yeremin, V.S. Voishchev, V.I. Sidorenko, A.F. Klinskikh, V.P. D’yachkova, Yu.M. Sakharov, Features of molecular mobility in the polyshiff base, Polymer Sci. U.S.S.R. 3 (1991) 1241-1249.
  * [52] A.S. Makarov, J.C. Qiao, N.P. Kobelev, A.S. Aronin, V.A. Khonik, Relation of the fragility and heat capacity jump in the supercooled liquid region with the shear modulus relaxation in metallic glasses, J. Phys. Cond. Matter 33 (2021) 275701.


# A simple algorithm for checking equivalence
of counting functions on free monoids

Petr Kiyashko  Moscow Institute of Physics and Technology, Institutskii per.
9, 141701 Dolgoprudny, Moscow region, Russia<EMAIL_ADDRESS>and
Alexey Talambutsa  Steklov Mathematical Institute of RAS, 8 Gubkina St.,
119991 Moscow, Russia HSE University, Laboratory of Theoretical Computer
Science, 11 Pokrovsky Blvd., 109028 Moscow, Russia<EMAIL_ADDRESS>
###### Abstract.

In this note we propose a new algorithm for checking whether two counting
functions on a free monoid $M_{r}$ of rank $r$ are equivalent modulo a bounded
function. The previously known algorithm has time complexity $O(n)$ for all
ranks $r>2$, however in case $r=2$ it was estimated only as $O(n^{2})$. Here
we apply a new approach, based on explicit basis expansion and weighted
rectangles summation, which allows us to construct a much simpler algorithm
with time complexity $O(n)$ for any $r\geq 2$.

##  1\. Introduction

Let $S_{r}=\\{a_{1},a_{2},\dots a_{r}\\}$ be the alphabet, $r\geq 2$. The free
monoid $M_{r}$ of rank $r$ is defined as the set of all finite words over
$S_{r}$ including the empty word $\epsilon$. For any fixed word $w$ we denote
its length as $|w|$, and for any natural number $i$ such that $1\leq
i\leq|w|$, we denote by $w_{i}$ the $i$-th letter of $w$. If $w$ is a non-
empty word, we denote its last letter as $w_{fin}$.

An _elementary counting function_ $\rho_{v}(w)$ for a fixed word $v\in M_{r}$
counts the number of (possibly intersecting) occurrences of $v$ in the
argument word $w\in M_{r}$. The function $\rho_{\epsilon}$ is defined as
$\rho_{\epsilon}(w)=|w|$. A general _counting function_ on $M_{r}$ is a linear
combination

(1) $f=\sum_{i=0}^{k}x_{i}\rho_{w_{i}}$

with $x_{i}$ being coefficients from $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$
or $\mathbb{C}$ and $w_{i}\in M_{r}$. The ring of integers is the main target
of our interest, and in this case we present the sum (1) in the input of the
algorithm by enlisting the coefficients $x_{i}$ in binary form and the words
$w_{i}$ in natural way (see the full formalization of integer and rational
cases in [2]).

Two counting functions $f$ and $g$ are considered equivalent if their
difference $f-g$ is a bounded function on $M_{r}$. It is worth noting that two
counting functions are equivalent if and only if they coincide on any cyclic
word (see [1, Corollary A.5]).

From this point on, for brevity we will be using counting functions to denote
their equivalence classes, and we will be using $=$ to denote equivalence. Our
goal is to devise an algorithm for checking whether two general counting
functions having form (1) are equivalent. Here are some key insights into the
structure of the equivalence relation obtained in previous works:

######  Theorem 1.1 (Theorem 1.3 in [1], Theorem 1.4 in [3]).

The class of bounded functions (i. e. ones equivalent to $0$) is spanned by
left and right extension relations for all words $w\in M_{r}$ defined as

$l_{w}=\rho_{w}-\sum_{s\in S_{r}}\rho_{sw},$ $r_{w}=\rho_{w}-\sum_{s\in
S_{r}}\rho_{ws}.$

######  Theorem 1.2 (Theorem 1.5 in [1], Theorem 1.5 in [3]).

The basis of the space of classes of equivalent functions is represented by

$\\{\rho_{w}\ |\ w\in M_{r}\text{, where }w_{1}\neq a_{1}\text{ and
}w_{fin}\neq a_{1}\\}.$

We denote by $\widehat{C}$ the space of classes of equivalent functions, and
by $B$ the basis identified in theorem 1.2.

The following result describes the time complexity of a useful formal
procedure, which sums up the coefficients in a general counting function with
repetitions.

######  Lemma 1.3 (Lemma 4.2 in [2]).

Consider a function $f\in\widehat{C}(M_{r})$ with integer coefficients, there
exists a procedure $N$ that takes $f$ as input and produces a function $g$
obtained from $f$ by reducing the coefficients at terms with identical
elementary counting functions. Furthermore, the time complexity of $N$ is
$O(rn)$, where $n$ is the size of $f$ as input.

Now, we state the main result obtained here:

######  Theorem 1.4.

There exists an algorithm that takes as input two counting functions $f$ and
$g$ represented as arbitrary linear combinations of elementary counting
functions and checks whether they are equivalent. Furthermore, for integer
coefficients this algorithm has time complexity $O(r^{3}(|f|+|g|))$, where
$|f|+|g|$ denotes the input size.

Even though the relations for monoid $M_{2}$ have the shortest and easiest
form, the equivalence problem for $M_{2}$ appeared to be most complicated. For
integer coefficients and any monoid $M_{r}$, where $r\geq 3$ the previously
known algorithm from [2] has time complexity $O(r(|f|+|g|))$, still for $r=2$
its complexity could be estimated only as $O(r(|f|+|g|)^{2})$.

Finding an algorithm working in time $O(|f|+|g|)$ for the case of monoid
$M_{2}$ was the main motivation for this work. The main idea of the new
construction is quite natural: to represent all elementary counting functions
from the input by linear combinations of basis elements using the explicit
formulas from [3], and then collapse the coefficients to see whether the
result is a trivial combination (see formal details in [2, Lemma 4.2]).
However, showing that this strategy can be implemented in linear time is not
straightforward.

##  2\. Algorithm for $M_{2}$

In this section, we describe an algorithm which works for the case $M_{2}$ and
in the next section we will extend it to the general case. Actually, we will
be checking whether a counting function having form (1) is bounded. Indeed, if
we are given two counting functions $f$ and $g$, then we can first form the
difference function $f-g$ and then we need to check whether the result is
bounded. As this step is linear with respect to the input size, and the size
of function $f-g$ does not exceed $|f|+|g|$, it does not affect the overall
complexity of the algorithm.

###  2.1. Basis representation

First we describe an explicit procedure which allows to represent elementary
counting function as a linear combination of basis elements. This
decomposition will be used extensively in our considerations later.

Here and further on we will say that applying the left or right extension
relation to the elementary counting function $\rho_{v}$ with $v=s_{1}ws_{2}$
means a substitution of $\rho_{v}$ by

$\rho_{ws_{2}}-\sum_{s\in S\setminus\\{s_{1}\\}}\rho_{sws_{2}}\ \ \ \text{
(left extension)},$ $\rho_{s_{1}w}-\sum_{s\in
S\setminus\\{s_{2}\\}}\rho_{s_{1}ws}\ \ \ \text{ (right extension),}$

which is valid since the extension relation functions are bounded.

Now, we show how to decompose most of the elementary counting functions.

######  Lemma 2.1.

Let $w=a_{1}^{k}va_{1}^{m}\in M_{2}$ with $v_{1}=v_{fin}=a_{2}$. Then

(2) $\rho_{w}=\rho_{v}-\sum_{i=0\ldots
k-1}\rho_{a_{2}a_{1}^{i}v}-\sum_{j=0\ldots
m-1}\rho_{va_{1}^{j}a_{2}}+\sum_{\begin{subarray}{c}i=0\ldots k-1,\\\
j=0\ldots m-1\end{subarray}}\rho_{a_{2}a_{1}^{i}va_{1}^{j}a_{2}}.$

###### Proof.

Applying the left extension relation to $\rho_{w}$ for $k$ iterations, we
obtain

(3) $\rho_{w}=\rho_{va_{1}^{m}}-\sum_{i=0\ldots
k-1}\rho_{a_{2}a_{1}^{i}va_{1}^{m}}.$

Applying the right extension relation to $\rho_{va_{1}^{m}}$ for $m$
iterations, we obtain

$\rho_{v}-\sum_{j=0\ldots m-1}\rho_{va_{1}^{j}a_{2}},$

and after doing the same transformation to every term in the sum from (3), one
has

$\sum_{i=0\ldots
k-1}\rho_{a_{2}a_{1}^{i}v}-\sum_{\begin{subarray}{c}i=0,\ldots,k-1\\\
j=0,\ldots,m-1\end{subarray}}\rho_{a_{2}a_{1}^{i}va_{1}^{j}a_{2}},$

which yields the desired representation. ∎

The direct application of the Lemma to any input may produce a list of
weighted elementary functions from the basis, but its size can now be
$O(n^{3})$ for the input of size $n$. The subsequent summing of the
coefficients can be estimated then as $O(n^{3})$ for integers or as $O((n\log
n)^{3})$ for rationals. To make the algorithm linear we will bypass this
elongation in Subsection 2.2, where a convenient compressed encoding for sums
from (2) will be introduced. Then, we will show how to effectively work with
the encoded sums.

Note that the words of $M_{2}$, which were not considered in Lemma 2.1, have
form $a_{1}^{k}$. In order to account for this case, let us introduce a few
more definitions.

######  Definition 2.2.

Let
$B_{U}=\\{\rho_{\epsilon}\\}\cup\\{\rho_{a_{2}}\\}\cup\\{\rho_{a_{2}a_{1}^{k}a_{2}}\
|\ k\geq 0\\}\subset B$, and let $U$ be the subspace spanned by $B_{U}$. Let
$V=U^{\perp}$, and let $B_{V}=B\setminus B_{U}$.

######  Lemma 2.3.

The counting function $\rho_{a_{1}^{k}}$ belongs to $U$ for any $k\geq 0$.

###### Proof.

It is possible to derive the exact basis representation of $\rho_{a_{1}^{k}}$,
but it would not be useful. Instead, let us prove this by induction. For $k=0$
it holds that $\rho_{a_{1}^{k}}=\rho_{\epsilon}\in B_{U}$, and for $k=1$ it
holds that $\rho_{a_{1}^{k}}=\rho_{a_{1}}=\rho_{\epsilon}-\rho_{a_{2}}\in U$.
Now, presume that for some $k>1$ it holds that $\rho_{a_{1}^{k-1}}\in U$. Let
us apply the left extension relation to $\rho_{a_{1}^{k}}$:

$\rho_{a_{1}^{k}}=\rho_{a_{1}^{k-1}}-\rho_{a_{2}a_{1}^{k}}.$

The first term on the right hand side of this equation lies in $U$ by the
induction hypothesis. Now we apply the right extension relation to the second
term for $k$ iterations:

$\rho_{a_{2}a_{1}^{k}}=\rho_{a_{2}}-\sum_{i=0\ldots
k-1}\rho_{a_{2}a_{1}^{i}a_{2}}.$

All terms of the right hand side of this equation lie in $B_{U}$, thus
$\rho_{a_{1}^{k}}$ lies in $U$. ∎

######  Lemma 2.4.

Out of the terms of (2) the first term ($\rho_{v}$) can either lie in $U$ or
in $V$, and all the other terms lie in $V$.

###### Proof.

First, consider the term $\rho_{v}$. It is a basis element due to the fact
that $v_{1}=v_{fin}=a_{2}$, thus it either lies in $U$ (when $v=a_{2}$ or
$v=a_{2}a_{1}^{k}a_{2}$), or lies in $V$.

Now, all the individual elementary counting functions in the other three terms
from (2) are of form $\rho_{a_{2}a_{1}^{i}v}$, $\rho_{va_{1}^{j}a_{2}}$ or
$\rho_{a_{2}a_{1}^{i}va_{1}^{j}a_{2}}$. Again, since $v_{1}=v_{fin}=a_{2}$,
each of the three corresponding words has at least one letter $a_{2}$ in the
middle. Therefore none of these function lie in $B_{U}$, and thus the terms
lie in $V$. ∎

In the algorithm we check whether $(f-g)|_{U}\equiv 0$ and whether
$(f-g)|_{V}\equiv 0$ separately. In order to do that, we choose alternative
bases for $U$ and $V$, and then represent $f-g$ in terms of these bases. The
description of the basis for $U$ is quite simple.

######  Lemma 2.5.

$B_{U}^{\prime}:=\\{\rho_{a_{1}^{k}}\ |\ k\geq 0\\}$ is the basis of $U$.
Furthermore, for a word $w=a_{2}a_{1}^{k}a_{2}\in M_{2}$ with $k\geq 0$ it
holds that

$\rho_{w}=\rho_{a_{1}^{k}}-2\rho_{a_{1}^{k+1}}+\rho_{a_{1}^{k+2}}.$

###### Proof.

First, $B_{U}^{\prime}$ is a linearly independent set, because it is a subset
of a basis of $\widehat{C}$ (obtained by symmetrically substituting $a_{1}$
and $a_{2}$ in $B$).

Next, it holds that $\rho_{a_{2}}=\rho_{\epsilon}-\rho_{a_{1}}$, thus
$\rho_{a_{2}}$ lies in the span of $B_{U}^{\prime}$.

Finally, for $w=a_{2}a_{1}^{k}a_{2}$ we may apply the left extension relation
as follows:

$\rho_{a_{2}a_{1}^{k}a_{2}}=\rho_{a_{1}^{k}a_{2}}-\rho_{a_{1}^{k+1}a_{2}},$

and by two applications of right extension relations

$\rho_{a_{1}^{k}a_{2}}-\rho_{a_{1}^{k+1}a_{2}}=(\rho_{a_{1}^{k}}-\rho_{a_{1}^{k+1}})-(\rho_{a_{1}^{k+1}}-\rho_{a_{1}^{k+2}})=\rho_{a_{1}^{k}}-2\rho_{a_{1}^{k+1}}+\rho_{a_{1}^{k+2}}.$

Therefore, all the elements of $B_{U}$ lie in the span of $B_{U}^{\prime}$,
and thus $B_{U}^{\prime}$ is also a basis. ∎

The description of the basis we choose for $V$ is more complicated. Here we
will not provide the proof of its correctness, but rather prove it implicitly
later.

######  Proposition 2.6.

The set

$B_{V}^{\prime}:=\Bigl{\\{}\sum_{\begin{subarray}{c}i=0\ldots k,\\\ j=0\ldots
m\end{subarray}}\rho_{a_{2}a_{1}^{i}va_{2}^{j}a_{2}}\ |\ k,m\geq 0,v\in M_{r}\
where\ v_{1}=v_{fin}=a_{2}\Bigr{\\}}\text{ is a basis of }V.$

###  2.2. The algorithm

Now, let us describe the algorithm for $M_{2}$. The outline of the algorithm
is as follows. First, we replace all the terms with words of form
$a_{1}^{k}va_{1}^{m}$ with their basis decompositions of the form (2). Then,
we divide all of the terms into two sets, one representing the projection onto
$U$, and the other — onto $V$. Finally, we represent these projections in
terms of the bases $B_{U}^{\prime}$ and $B_{V}^{\prime}$, and verify whether
these representations are trivial via the procedure $N$ from Lemma 1.3. As it
turns out, unlike $B_{U}$ and $B_{V}$, the representations in terms of
$B_{U}^{\prime}$ and $B_{V}^{\prime}$ have the size proportional to the
initial input size multiplied by a constant factor, which allows for an
efficient triviality check.

The main idea for $M_{r}$ with $r\geq 3$ will be the same, but the proof is
clearer for $M_{2}$ since the $S_{r}\setminus\\{a_{1}\\}=\\{a_{2}\\}$, and
thus the proposed compressed encodings are simpler. Furthermore, the
representations in terms of $B_{U}^{\prime}$ and $B_{V}^{\prime}$ in the case
of $r\geq 3$ (which will be defined for the general case later) increase the
input size by a factor of $r^{2}$.

First, assume that we have replaced all the terms of form
$\rho_{a_{1}^{k}va_{1}^{m}}$ with the four terms from (2). Having done that,
let us propose and alternative encoding for the terms that we are left with.

We will define an _encoding function_ $\mathbf{e}$ for a non-empty word $w\in
M_{r}$ such that $w_{1}=w_{fin}=a_{2}$. We will encode such word as a sequence
of non-negative integer numbers, which are the lengths of $a_{1}$-powers in
$w$ delimited by letters $a_{2}$. We note that two consecutive letters $a_{2}$
in the word $w$ actually mean a $0$-length sequence of $a_{1}$-s in between.
For the word $a_{2}$, its encoding is an empty sequence, i.e.
$\mathbf{e}(a_{2})=()$. For any other word starting and ending with $a_{2}$,
one has

$\mathbf{e}(a_{2}a_{1}^{k_{1}}a_{2}a_{1}^{k_{2}}\ldots
a_{2}a_{1}^{k_{m}}a_{2})=(k_{1},k_{2},\ldots,k_{m}).$

When the encoding sequence is considered as a word for algorithm processing,
the integers $k_{1},\ldots,k_{m}$ are written in binary notation, separated by
commas and enclosed in parenthesis. For example
$\mathbf{e}(a_{2}^{2}a_{1}^{3}a_{2}a_{1}a_{2})=\texttt{(0,11,1)}$. We
emphasize the meaning of the encoding sequence as a word by calling it _list_.

To make the decomposition algorithm fast, we also introduce slightly more
general encoding, which is suitable for short writing of sums from (2). This
generalization additionally uses two symbols [ and ]. Having these symbols and
two integers $a\leq b$ we encode the interval set $\\{a,a+1,\ldots,b\\}$ as a
word $[a,b]$, where $a$ and $b$ are written in binary notation (however, we
will be using such intervals only when $a=0$).

Now, an encoding list $(k_{1},k_{2},\ldots,k_{m})$ is generalized in such a
way, that $k_{1}$ and $k_{m}$ can be not just integers, but also the intervals
having form $[a,b]$. Having this in mind, we are ready to encode all terms
from (2). The encoding of a single word $\mathbf{e}(v)$ is already defined,
and let $\mathbf{e}^{\prime}(v)$ be the word $\mathbf{e}(v)$ without the
enclosing parethesis, then

$\mathbf{e}\Bigl{(}\sum_{i=0\ldots
k-1}\rho_{a_{2}a_{1}^{i}v}\Bigr{)}=([0,k-1],\ \mathbf{e}^{\prime}(v)),$
$\mathbf{e}\Bigl{(}\sum_{j=0\ldots
m-1}\rho_{va_{1}^{i}a_{2}}\Bigr{)}=(\mathbf{e}^{\prime}(v),\ [0,m-1]),$
$\mathbf{e}\Bigl{(}\sum_{\begin{subarray}{c}i=0\ldots k-1,\\\ j=0\ldots
m-1\end{subarray}}\rho_{va_{1}^{i}a_{2}}\Bigr{)}=([0,k-1],\
\mathbf{e}^{\prime}(v),\ [0,m-1]).$

Thus, using (2) we can equivalently replace every term $x_{i}\rho_{w_{i}}$ of
the input (where $w_{i}\neq a_{1}^{k}$) as four words in generalized encoding
and keep the same coefficient $x_{i}$ in front of them. This enlarges the
length of the input only by a multiplicative constant.

Now, let us separate the obtained encoded terms into those that lie in $U$ and
in $V$. For an encoding list $e=(k_{1},\ldots,k_{m})$ we define its length
$|e|=m$.

######  Lemma 2.7.

Consider a term $t$ from the function $f-g$ after the substitutions via Lemma
2.1. If $t$ can not be encoded with $\mathbf{e}$, or $|\mathbf{e}(t)|\leq 1$,
then $t\in U$. Otherwise, $t\in V$.

###### Proof.

If $t$ can not be encoded, then $t=x\rho_{a_{1}^{k}}$ for some $k\geq 0$.
Therefore from Lemma 2.5 it follows that $t\in U$.

Now, if $|\mathbf{e}(t)|\leq 1$, then $t=\rho_{a_{2}}$ or
$t=\rho_{a_{2}a_{1}^{k}a_{2}}$ for some $k\geq 0$, therefore $t\in B_{U}$.

Finally, if $t$ has is encoded by a list of length at least $2$, then either
$t=\rho_{v}$ with $v_{1}=v_{fin}=a_{2}$ and $\rho_{a_{2}}(v)>2$, or $t$ is a
summation term from (2). In both cases $t\in V$. ∎

####

Now it is clear which terms we have to process to verify $(f-g)|_{U}\equiv 0$,
and which terms we have to process for the verification of $(f-g)|_{V}\equiv
0$.

###  2.3. Case $|e|\leq 1$ and $\rho_{a_{1}^{k}}$ ($U$)

First, we substitute the terms of $\rho_{a_{2}}$ (encoding of length $0$) and
of $\rho_{a_{2}a_{1}^{k}a_{2}}$ (encodings of length $1$) with their
$B_{U}^{\prime}$ decompositions as per Lemma 2.5. Each term is replaced by no
more than $4$ terms of form $\rho_{a_{1}^{k}}$ with words of similar length
and with same coefficients, thus the input size grows by a constant
multiplicative factor. Having done that, we use the procedure $N$ from Lemma
1.3 to reduce the coefficients and check whether $(f-g)|_{U}$ is trivial. The
running time of $N$ is $O(n)$, since we have increased the input size by a
constant, and $r=2$ is also a constant in the case of $M_{2}$.

###  2.4. Case $|e|\geq 2$ ($V$)

Now, we say that two elementary counting functions (or their encodings) from
$V$ are _interacting_ if they if they have some common elements in their
$B_{V}$ basis representations, i. e. that they do not lie in orthogonal
subspaces of $V$ with respect to $B_{V}$. This means that if we replace the
elementary counting functions with encodings of linear combinations of basis
elements, we will only have to collapse coefficients in classes of mutually
interacting functions.

For an encoding list $e$ with $|e|\geq 2$, we define the _core_ of $e$ as a
sublist $\mathbf{c}(e)=(k_{2},\ldots,k_{m-1})$.

######  Lemma 2.8.

Let $e_{1}$ and $e_{2}$ be two encoding lists with $|e_{1}|,|e_{2}|\geq 2$. If
they interact, then

  1. (1)

$|e_{1}|=|e_{2}|$.

  2. (2)

$\mathbf{c}(e_{1})=\mathbf{c}(e_{2})$.

###### Proof.

Note that in every term from Lemma 2.1 all basis elements have the same core
(if encoded). Thus, if two terms interact, i. e. have elements with equal
words, they both must share a common core. ∎

We see that classes of interacting encoding lists share the same length and
core, thus it is sufficient to efficiently collapse terms having fixed length
and core. Furthermore, classes of interacting functions represent separate
subspaces of $V$ with respect to the basis $B_{V}$, thus we can further
decompose the task of estimating $(f-g)|_{V}\equiv 0$ to similar tasks for
these subspaces.

Let us now consider a single class of interacting functions representing a
subspace $V_{i}$. Further we will refer to both the class and the subspace as
$V_{i}$ for brevity.

Since the only varying part of the encodings in $V_{i}$ are the first and last
elements, we may omit the fixed core and write the encoding singular counting
functions, left-sum terms, right-sum terms and two-sided sum terms as

(4) $\displaystyle(k,m),$ $\displaystyle([0,k],\ m),$ $\displaystyle(k,\
[0,m]),$ $\displaystyle([0,k],\ [0,m]).$

respectively, with coefficients inherited from the initial counting function.
Now, for the fixed core we need to check whether the sum of such terms equates
to $0$.

The four types of integer sets described in (4) can be depicted graphically as
follows. Let us consider a $2$-dimensional weighted multiset of rectangles
parallel to the coordinates, which we call a _histogram_. Here, for a
coefficient $x$ the pair $\langle(k,m),x\rangle$ denotes a square at
coordinates $(k,m)$ with weight $x$, the pair $\langle([0,k],m),x\rangle$
denotes a horizontal bar with its base on the $y$ axis at coordinate $m$ and
length $k$, with its weight being $x$ again, the pair
$\langle(k,[0,m]),x\rangle$ denotes a similar vertical bar, and
$\langle([0,k],[0,m]),x\rangle$ denotes a rectangle starting in $(0,0)$ with
width of $k$ and weight of $m$, again, with a weight of $x$.

$y$$x$$m$$m^{\prime}$$k$$k^{\prime}$$([0,\ k],\ [0,\ m])$$([0,\ k],\
m^{\prime})$$(k^{\prime},\ [0,\ m])$$(k^{\prime},\ m^{\prime})$ Figure 1.
Histogram example, without weights depicted.

Now, the shortened encodings defined above with respective coefficients define
such histogram, and their summation equates to $0$ if and only if this
histogram has total weight of $0$ at every grid square $1\times 1$. It turns
out, that we can further simplify the task with the following observation.

######  Observation 2.9.

Instead of considering singular squares, vertical and horizontal bars and
rectangles from (4), we can consider only rectangles by applying the following
subsitutions:

$([0,k],m)=([0,k],\ [0,m])-([0,k],\ [0,m-1]),$ $(k,[0,m])=([0,k\
],[0,m])-([0,k-1],\ [0,m])$
$(k,m)=([0,k],[0,m])-([0,k-1],[0,m])-([0,k],[0,m-1])+([0,k-1],\ [0,m-1]).$

Note that these $(0,0)$-based rectangles exactly represent the elements of
$B_{V}^{\prime}$.

This approach allows us to reduce the histogram only to rectangles while
increasing the size of the input by a multiplicative constant of no more than
$4$. Note, that after this substitution there may be multiple rectangles with
the same coordinates, but different coefficients. Let us denote by $h(x,y)$
the sum of coefficients in the rectangle with coordinates $(x,y)$, and by
$H(x,y)$ the total weight of the histogram at $(x,y)$

####

Now, a histogram containing only $(0,0)$ based rectangles has some convenient
properties. First of all, the histogram is constant $0$ if and only if the
weight of the histogram at every top-right corner of such rectangle is $0$.
Let us consider the top right corner of a rectangle $(x,y)$. Its weight is
affected only by rectangles with the same coordinates, or rectangles that
include $(x,y)$. This means that

$H(x,y)=\sum_{x^{\prime}\geq x,y^{\prime}\geq y}h(x^{\prime},y^{\prime}).$

######  Lemma 2.10.

$H\equiv 0$ if and only if $h\equiv 0$.

###### Proof.

If $h\equiv 0$, then clearly so is $H$. Now presume that $H\equiv 0$. Then we
prove that $h\equiv 0$ by descending induction over $x$ and then $y$.

####

As the base case we take the maximum value of $x_{0}$ over all rectangles, and
the maximum $y_{00}$ value for $x=x_{0}$. The only rectangles that contain
$(x_{0},y_{00})$ are those which have exactly those coordinates, thus
$h(x_{0},y_{00})=H(x_{0},y_{00})=0$, and the base is proven.

####

Now let us consider some $(x,y)$ and let us presume that by induction
hypothesis for all $(x^{\prime},y^{\prime})$ such that $x^{\prime}>x$ or
$x^{\prime}=x$ and $y^{\prime}>y$ it holds that $h(x^{\prime},y^{\prime})=0$.
Then,

$0=H(x,y)=\sum_{x^{\prime}\geq x,y^{\prime}\geq
y}h(x^{\prime},y^{\prime})=h(x,y)+0=h(x,y),$

thus $h(x,y)=0$ and the induction step is proven. ∎

This means that the projection of $f-g$ onto $V_{i}$ is trivial if and only if
its decomposition via functions represented by $(0,0)$-based rectangles is
trivial. Therefore these functions form a basis of $V_{i}$, and the union such
functions for all cores, which is $B_{V}^{\prime}$ by definition, is a basis
of $V$, which coincidentally proves Proposition 2.6.

It now follows that in order to verify $(f-g)|_{V}\equiv 0$ it suffices to
substitute each singular function, left-sum term-and right sum term with two-
sided sum terms as per Observation 2.9, which are exactly elements of the
basis $B_{V}^{\prime}$, and then apply the procedure $N$ from Lemma 1.3 to the
result. Since this substitution also increases the input size by a
multiplicative constant, the time complexity of the invokation of $N$ is also
linear.

Having performed the check for the projection of $f-g$ onto $U$ and then for
the projection onto $V$, we conclude that $f\equiv g$ if and only if both
checks concluded that the projections are trivial. Otherwise, $f$ and $g$ are
not equivalent. Furthermore, the time complexity of both steps is
$O(|f|+|g|)$, thus this algorithm satisfies Theorem 1.4 for the case of
$M_{2}$.

##  3\. Extension to $M_{r}$, $r\geq 3$

In the general monoid case, we consider words in alphabet $S_{r}$. Again, for
any word $w$ we distinguish the powers of letter $a_{1}$ in it, and consider
any other letter $s\in S_{r}\setminus\\{a_{1}\\}$ as a delimiter. The powers
of $a_{1}$ will be encoded by non-negative integer numbers written in binary
form, and the separators are written as from the set
$\\{a_{1},a_{2},\ldots,a_{r}\\}$. To adapt the previous proof to this
generalized case we do three things.

First, let us update the basis decomposition lemmas to suite the general case.

######  Lemma 3.1.

Let $w=a_{1}^{k}va_{1}^{m}\in M_{r}$ with $|v|>0$ and $v_{1}\neq a_{1}$,
$v_{fin}\neq a_{1}$. Then

$\rho_{w}=\rho_{v}-\sum_{\begin{subarray}{c}s\in S_{r}\setminus\\{a_{1}\\},\\\
i=0\ldots k-1\end{subarray}}\rho_{sa_{1}^{i}v}-\sum_{\begin{subarray}{c}s\in
S_{r}\setminus\\{a_{1}\\},\\\ j=0\ldots
m-1\end{subarray}}\rho_{va_{1}^{j}s}+\sum_{\begin{subarray}{c}s_{1},s_{2}\in
S_{r}\setminus\\{a_{1}\\},\\\ i=0\ldots k-1,\\\ j=0\ldots
m-1\end{subarray}}\rho_{s_{1}a_{1}^{i}va_{1}^{j}s_{2}}.$

###### Proof.

The proof is identical to the proof of Lemma 2.1. ∎

Now, let us update the definitions of $U$ and $V$. $B_{U}$ is defined as

$\bigl{\\{}\rho_{\epsilon}\bigr{\\}}\cup\bigl{\\{}\rho_{s}\ |\ s\in
S_{r}\setminus\\{a_{1}\\}\bigr{\\}}\cup\bigl{\\{}\rho_{s_{1}a_{1}^{k}s_{2}}\
|\ s_{1},s_{2}\in S_{r}\setminus\\{a_{1}\\},k\geq 0\bigr{\\}}.$

The definitions of $U$, $V$ and $B_{V}$ are derived from $B_{U}$ similarly to
the case of $M_{2}$.

######  Remark 3.2.

All definitions for the case of $M_{r}$ are the same as for the case of
$M_{2}$, but wherever there was the letter $a_{2}$ there is now a summation
over all letters $s\in S_{r}\setminus\\{a_{1}\\}$.

######  Lemma 3.3.

The set

$B_{U}^{\prime}:=\bigl{\\{}\rho_{\epsilon}\bigr{\\}}\cup\bigl{\\{}\rho_{s}\ |\
s\in
S_{r}\setminus\\{a_{2}\\}\bigr{\\}}\cup\bigl{\\{}\rho_{s_{1}a_{1}^{k}s_{2}}\
|\ s_{1},s_{2}\in S_{r}\setminus\\{a_{2}\\},k\geq 0\bigr{\\}}$

is another basis of $U$. Furthermore, for $w=a_{2}a_{1}^{k}a_{2}\in M_{n}$
with $k\geq 0$ it holds that

$\rho_{w}=\rho_{a_{1}^{k}}-\sum_{s\in
S\setminus\\{a_{2}\\}}a_{1}^{k}s-\sum_{s\in
S\setminus\\{a_{2}\\}}sa_{1}^{k}-\sum_{s_{1},s_{2}\in
S\setminus\\{a_{2}\\}}s_{1}a_{1}^{k}s_{2}.$

###### Proof.

The proof of the first fact is similar to the proof of Lemma 2.5, and the
proof of the second fact is similar to the proof of Lemma 2.1. ∎

######  Proposition 3.4.

The set

$B_{V}^{\prime}:=\Bigl{\\{}\sum_{\begin{subarray}{c}i=0\ldots k,\\\ j=0\ldots
m\\\ s_{1},s_{2}\in
S_{r}\setminus\\{a_{1}\\}\end{subarray}}\rho_{s_{1}a_{1}^{i}va_{1}^{j}s_{2}}\
|\ k,m\geq 0,v\in M_{r}\ where\ v_{1}\neq a_{1}\ and\ v_{fin}\ \neq
a_{2}\Bigr{\\}}$

is a basis of $V$.

####

Next, in the encoding of a single word
$w=s_{1}a_{1}^{k_{1}}s_{2}a_{1}^{k_{2}}\ldots a_{1}^{k_{m}}s_{m+1}$ we start
to specify, which letters go in between the powers of letter $a_{1}$:

$\mathbf{e}(s_{1}a_{1}^{k_{1}}s_{2}a_{1}^{k_{2}}\ldots
a_{1}^{k_{m}}s_{m+1})=(s_{1},k_{1},s_{2},k_{2},\ldots,k_{m},s_{m+1}).$

####

Second, using Lemma 3.1, we replace each term $\rho_{a_{1}^{k}va_{1}^{m}}$ by
$1+2(r-1)+(r-1)^{2}=r^{2}$ terms, which are respectively

$\displaystyle\mathbf{e}(v),$
$\displaystyle(a_{i},[0,k-1],\mathbf{e}^{\prime}(v))\text{, \ \ \ where }i\neq
1,$ $\displaystyle(\mathbf{e}^{\prime}(v),[0,m-1],a_{i})\text{, \ \ \ where
}i\neq 1,$ $\displaystyle(a_{i},[0,k-1],\mathbf{e}^{\prime}(v),[0,m-1],a_{j})\
\text{, \ \ \ where }\ i,j\neq 1.$

(We remind that $\mathbf{e}^{\prime}(v)$ is again the word $\mathbf{e}(v)$
without the enclosing parethesis.)

With all the definitions inplace, the proof is totally identical. We use Lemma
3.1 to decompose most elements of $f-g$ by replacing terms with their
encodings. Then, we separate terms that lie in $U$ from terms that lie in $V$
based on encodability and encoding length. For the subspace $U$, we use the
representation from Lemma 3.3 to decompose the projection onto $U$ in terms of
$B_{U}^{\prime}$, and then use the procedure $N$ to check the triviality. In
the case of $V$, two encoded terms also interact if they have the same cores,
and in the case of $r\geq 3$ the same list of delimiters. Therefore, here the
histogram method also applies to subspaces of interacting functions, and it is
possible to similarly re-represent the projection of $f-g$ onto $V$ in terms
of $B_{V}^{\prime}$ and then use the procedure $N$ to collapse the
coefficients. A more formal listing of the algorithm may be found in Appendix
A.

Here, in both cases the size of the input is increased by a factor of $r^{2}$,
and the running time of $N$ is $O(rn)$, which yields the time complexity of
$O(r^{3}(|f|+|g|))$, which satisfies Theorem 1.4.

##  4\. Acknowledgements

The work of second author was prepared within the framework of the HSE
University Basic Research Program. Both authors are members of research group
which won Junior Leader competition of BASIS foundation.

##  Appendix A Listings

Algorithm 1 General case algorithm

Two counting functions $f$ and $g$ encoded as lists of word and coefficient
pairs.

Return true if $f\equiv g$ is trivial and false otherwise

$D\leftarrow f-g$

if $D$ is empty then

return true

end if

$L\leftarrow$ number of elements in $D$

for $l:=1$ to $L$ do

$w,x\leftarrow$ word and coefficient of the $l$-th element of $D$

if w is of form $a_{1}^{k}va_{1}^{m}$ with $|v|>0$, $v_{1},v_{fin}\neq a_{1}$
then

Remove $\langle w,x\rangle$ from $D$

Add $\langle\mathbf{e}(v),x\rangle$ to $D$

for $s\in S_{r}\setminus\\{a_{1}\\}$ do

Add $\langle(s,[0,k-1],\mathbf{e}^{\prime}(v)),-x\rangle$ to $D$

Add $\langle(\mathbf{e}^{\prime}(v),[0,m-1],s),-x\rangle$ to $D$

for $s^{\prime}\in S_{r}\setminus\\{a_{1}\\}$ do

Add $\langle(s,[0,k-1],\mathbf{e}^{\prime}(v),[0,m-1],s^{\prime}),x\rangle$ to
$D$

end for

end for

else if $w_{1}\neq a_{1}$ and $w_{fin}\neq a_{1}$ then

Remove $\langle w,x\rangle$ from $D$

Add $\langle\mathbf{e}(w),x\rangle$ to $D$

end if

end for

$U\leftarrow$ empty list

$V\leftarrow$ empty list

$L\leftarrow$ new number of elements in $D$

for $l:=1$ to $L$ do

$P\leftarrow$ pop $l$-th element from $D$

if $P$ contains a word $a_{1}^{k}$ then

Add $P$ to $U$

else if $P$ contains an encoding of length $1$ or less then

$w,x\leftarrow$ word (assembled back from encoding) and coefficient from $P$

if $w_{1}=w_{fin}=a_{2}$ then

$k\leftarrow|w|-2$

Remove $\langle w,x\rangle$

Add $\langle\rho_{a_{1}^{k}},x\rangle$ to $U$

for $s\in S_{r}\setminus\\{a_{2}\\}$ do

Add $\langle\rho_{a_{1}^{k}s},-x\rangle$ to $U$

Add $\langle\rho_{sa_{1}^{k}},-x\rangle$ to $U$

for $s^{\prime}\in S_{r}\setminus\\{a_{1}\\}$ do

Add $\langle\rho_{sa_{1}^{k}s^{\prime}},x\rangle$ to $U$

end for

end for

end if

else

$e,x\leftarrow$ encoding list and coefficient from $P$

Remove $\langle e,x\rangle$ from $D$

if $e=(s_{1},k_{1},\ldots,k_{m},s_{m+1})$ (encodes a singular function) then

Add $\langle(s_{1},[0,k_{1}],\mathbf{c}(e),[0,k_{m}],s_{m+1}),x\rangle$ to $V$

Add $\langle(s_{1},[0,k_{1}],\mathbf{c}(e),[0,k_{m}-1],s_{m+1}),-x\rangle$ to
$V$

Add $\langle(s_{1},[0,k_{1}-1],\mathbf{c}(e),[0,k_{m}],s_{m+1}),-x\rangle$ to
$V$

Add $\langle(s_{1},[0,k_{1}-1],\mathbf{c}(e),[0,k_{m}-1],s_{m+1}),x\rangle$ to
$V$

else if $e=(s_{1},[0,k_{1}],\mathbf{c}(e),k_{m},s_{m+1})$ (encodes a left-sum
function) then

Add $\langle(s_{1},[0,k_{1}],\mathbf{c}(e),[0,k_{m}],s_{m+1}),x\rangle$ to $V$

Add $\langle(s_{1},[0,k_{1}],\mathbf{c}(e),[0,k_{m}-1],s_{m+1}),-x\rangle$ to
$V$

else if $e=(s_{1},k_{1},\mathbf{c}(e),[0,k_{m}],s_{m+1})$ (encodes a right-sum
function) then

Add $\langle(s_{1},[0,k_{1}],\mathbf{c}(e),[0,k_{m}],s_{m+1}),x\rangle$ to $V$

Add $\langle(s_{1},[0,k_{1}-1],\mathbf{c}(e),[0,k_{m}],s_{m+1}),-x\rangle$ to
$V$

else

Add $\langle e,x\rangle$ to $V$

end if

end if

end for

if $N(U)$ and $N(V)$ then

return true

else

return false

end if

## References

  * [1] T. Hartnick and A. Talambutsa (2018) Relations between counting functions on free groups and free monoids, Groups Geom. Dyn. 12, 1485–1521.
  * [2] T. Hartnick and A. Talambutsa, Efficient computations with counting functions on free groups and free monoids, Sbornik: Mathematics, 2023, 214(10), 1458–1499.
  * [3] P. Kiyashko, Bases for counting functions on free monoids and groups, arXiv:2306.15520 [math.GR]