Demystifying Arrow of Time

Zura Kakushadze

Free University of Tbilisi, School of Physics111 Zura Kakushadze, Ph.D. is a
Full Professor at Free University of Tbilisi, and a Cofounder and the CEO at
Quantigic®. Email<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
#240 Davit Aghmashenebeli Highway, Tbilisi 0159, Georgia

(March 21, 2024)

Scientific discussions of the arrow of time often get quite confusing due to
highly complex systems they deal with. Popular literature then often coveys
messages that tend to get lost in translation. The purpose of this note is to
demystify the arrow of time by stripping off the unnecessary complexities and
thereby simplifying the discussion. We do this by providing examples that are
exactly solvable and make it easy to see the root cause of the apparent “time-
irreversibility”. We also discuss “time-reversal” solutions, where the initial
state evolves such that it reaches the state which is the same as the initial
state moving backward in time. These solutions are simple enough to be
comprehensible to a highschooler. We discuss the arrow of time both in the
classical and quantum settings, including in the cosmological context.

##  1 Introduction and Summary

The arrow of time, the apparent flow of time only in one direction, is deemed
an unsolved problem. It’s of interest to both the general public and
physicists, due to its scientific, philosophical, spiritual, etc.,
implications. Popular literature, when discussing scientific works on this
subject, often coveys messages that tend to get lost in translation, so to
speak. This is because the issue is nontrivial and scientific discussions
often get quite confusing due to highly complex systems they deal with.

In the context of classical thermodynamics, the arrow of time can be
attributed to the second law of thermodynamics. The latter deals with a
complex notion of entropy (see, e.g., [Landau and Lifshitz, 1980]) and complex
systems composed of a large number of particles (atoms or molecules).
Typically, such systems aren’t computationally tractable, so one usually
resorts to macroscopic (course-grained) approximations. This complexity and
approximations muddy the waters in the context of how is it that the
underlying fundamental dynamics is perfectly time-reversible, yet the systems
one studies theoretically and observes experimentally appear not to be time-
reversible.

In the context of quantum mechanics the discussion gets even more confusing.
It relies on complex concepts of entanglement and decoherence (see, e.g.,
[Lesovik et al, 2016], [von Neumann, 1929], and references therein). The
probabilistic nature of quantum mechanics doesn’t help either, in fact, it
makes things even more confusing. All this complexity, yet again, muddies the
waters in the context of how is it that the underlying unitary quantum
evolution is perfectly time-reversible, yet an observable system appears not
to be.

The purpose of this note is to demystify the arrow of time by stripping off
the unnecessary complexities and thereby simplifying the discussion. Our goal
here isn’t to say something earthshakingly new. Instead, the goal here is to
(hopefully) say things in ways that are easy to follow (at least, in some
parts). We do this by providing examples that are exactly solvable and make it
easy to see that the apparent “time-irreversibility” is due to very special
initial conditions as opposed to some (mysterious or complex) fundamental
principle(s). This, in fact, is the main message of this note: it’s all about
the initial conditions.

This note is organized as follows. In Section 2 we discuss classical one-
dimensional ideal gases, where the kinematics is exactly solvable. In Section
3 we consider mixing such ideal gases to illustrate that the apparent “time-
irreversibility” is due to special initial conditions. Excepting Subsection
3.3 (which involves entropy), Section 3 should be comprehensible to a
highschooler with a basic understanding of kinematics. In Section 3.4 we
discuss “time-reversal” solutions, where the initial state evolves such that
after some time it reaches the state which is the same as the initial state
moving backward in time. In Section 4 we discuss what happens in the quantum
mechanical context and again argue that the apparent “time-irreversibility” is
due to special initial conditions. In Section 5 we discuss special initial
conditions we observe in the cosmological context. We briefly conclude in
Section 6.

##  2 Ideal Gas in One Dimension

In this section we consider a simple model of an ideal gas in one spatial
dimension. One-dimensional kinematics is especially simple, which simplifies
the discussion of the arrow of time.

Consider a one-dimensional ideal gas consisting of identical “molecules”,
which we will treat as point-like particles, all with the same mass $m$. Let
us assume that this gas is placed in a one-dimensional box of length $L$. Let
us further assume that the collisions between the particles are elastic, i.e.,
the total kinetic energy is conserved. Furthermore, let us assume that the
collisions of the particles with the walls of the box are also elastic, i.e.,
when a particle bounces off a wall, its kinetic energy is conserved while its
momentum is reversed. We will also assume that the speeds of the particles are
non-relativistic.

Consider an elastic collision of particle A moving to the right with velocity
$v$ and particle B moving to the left with velocity $u$. (Velocities are
signed quantities, so conventionally choosing our one-dimensional $x$
coordinate axis to run from left to right, $v>0$ and $u<0$.) After the
collision, let the velocity of particle A be $v^{\prime}$ and the velocity of
particle B be $u^{\prime}$. The momentum and kinetic energy are conserved:

$\displaystyle mv+mu=mv^{\prime}+mu^{\prime}$ (1)
$\displaystyle\frac{1}{2}~{}mv^{2}+\frac{1}{2}~{}mu^{2}=\frac{1}{2}~{}mv^{\prime\,2}+\frac{1}{2}~{}mu^{\prime\,2}$
(2)

Because the masses are the same, the solution to the above system of equations
is given by:

$\displaystyle v^{\prime}=u$ (3) $\displaystyle u^{\prime}=v$ (4)

I.e., the particles simply exchange their velocities: particle A is now moving
to the left with velocity $u$ and particle B is now moving to the right with
velocity $v$.

In one dimension, since the particles are identical, we can treat the above
elastic collision as particle A and particle B simply going through each other
(instead of bouncing off each other). This simplifies things greatly. Indeed,
if we have a large number $N$ of identical particles in a one-dimensional box,
if we treat them as simply going through each other, and if we tag each
particle with a label (e.g., number them from 1 to $N$), then we can follow
each particle through time. Its velocity never changes except when it bounces
off a wall, when its velocity reverses. The system is equivalent to $N$ non-
interacting particles in a one-dimensional box.

Before discussing mixing of gases, let us discuss the temperature $T$ of the
gas. By the equipartition theorem [Waterston, 1846], [Waterston, 1892],
[Boltzmann, 1871], [Boltzmann, 1876], it is given by ($k$ is the Boltzmann
constant):

$\frac{1}{2}~{}kT=\frac{1}{2}~{}m\langle v^{2}\rangle$ (5)

Here $\langle v^{2}\rangle$ is the average velocity squared of the $N$
particles in the gas.

##  3 Mixing Gases

###  3.1 Uniform Velocities

Let us now consider two adjacent one-dimensional boxes, box A and box B, both
of length $L$, separated by a wall (a partition), with box B located to the
right of box A. Each box contains $N$ particles described above ($N\gg 1$).
The $2N$ particles in box A and box B are indistinguishable in the sense that
they are all point-like and have the same mass $m$, and have no other
distinguishing intrinsic properties (albeit their velocities are not all the
same). At the initial time $t=0$, the $N$ particles in each box are randomly
distributed along the length $L$ of their box. For simplicity, let us assume
that $N$ is even. Let us further assume that $N/2$ particles in box A have the
same velocity $v_{A}$ ($v_{A}>0$), the other $N/2$ particles in box A have the
same velocity $-v_{A}$, and the distribution of positive and negative
velocities (i.e., the particles moving to the right and to the left) in box A
is random. Similarly, let us assume that $N/2$ particles in box B have the
same velocity $v_{B}$ ($v_{B}>0$), the other $N/2$ particles in box B have the
same velocity $-v_{B}$, and the distribution of positive and negative
velocities in box B is random. Let us further assume (this is not critical)
that the ratio $v_{A}/v_{B}$ is some irrational number, $v_{A}>v_{B}$, and
$v_{A}/v_{B}-1\mathrel{\hbox to0.0pt{\lower 3.0pt\hbox{\hskip
0.0pt$\sim$}\hss}\raise 1.0pt\hbox{$<$}}1$. As above, all scattering is
elastic (including off the walls). The temperatures in box A and box B are
$T_{A}=mv_{A}^{2}/k$ and $T_{B}=mv_{B}^{2}/k$, so $T_{A}>T_{B}$.

Now let us instantaneously remove the wall between box A and box B. Since we
can think of the particles as simply going through each other, even though all
$2N$ particles are identical, it is convenient to think of them as labeled by
A and B, depending on which box they were in at $t=0$. Each particle labeled
by A then has velocity $v_{A}$ or $-v_{A}$, and each particle labeled by B
then has velocity $v_{B}$ or $-v_{B}$. After some sufficiently long time
$t=t_{1}\gg L/v_{B}$, the gases will be thoroughly mixed, with particles
labeled by A and B randomly distributed along the entire length $2L$ of the
combined box, with the positive and negative velocities also randomly
distributed. Let us refer to the initial state at $t=0$ (when the wall between
box A and box B was removed) as state-0, and the state at $t=t_{1}$ as
state-1. In state-1 the average velocity squared is $\langle
v^{2}\rangle_{1}=(v_{A}^{2}+v_{B}^{2})/2$, and, from the macroscopic point of
view, the temperature of the mixed gas is $T_{1}=(T_{A}+T_{B})/2$.

From the microscopic point of view, the time evolution of the system is
exactly solvable, for each individual particle labeled by $a=1,\dots,2N$.
I.e., if at time $t=0$ we know the position $x_{a}(0)$ and the velocity
$v_{a}(0)$ of any given particle labeled by $a$, then we know the position
$x_{a}(t)$ and the velocity $v_{a}(t)=dx_{a}(t)/dt$ thereof at any later time
$t$: $x_{a}(t)=f(x_{a}(0)+v_{a}(0)t)$, where the periodic “saw” function
$f(x)=2L-|2L-x|$ for $0\leq x\leq 4L$, and $f(x+4L)=f(x)$ for all $x\in{\bf
R}$. On the other hand, from the macroscopic point of view, if we didn’t know
the microscopic state, state-1 looks like a completely random state of a gas
of $2N$ particles with the temperature $T_{1}$ in a box of length $2L$.
However, this state is anything but “random”.

To see this, consider state-2, which is constructed from state-1 by
simultaneously flipping the signs of the velocities of all $2N$ particles in
the combined box. Let us start from state-2 and follow the evolution of the
particles labeled by A and particles labeled by B. This evolution is nothing
but playing the evolution of state-0 into state-1 backwards in time. It then
follows that state-2, precisely after time $t_{1}$, will evolve into state-3,
in which the positions of the particles are identical to those in state-0,
while all velocities have their signs flipped. I.e., starting from a seemingly
“random” state-2, after time $t_{1}$, we end up with all particles with
velocities $\pm v_{A}$ neatly placed in what used to be box A (i.e., to the
left of the wall between the original boxes A and B), and all particles with
velocities $\pm v_{B}$ neatly placed in what used to be box B. This state-3 is
a highly non-random state, just as is state-0.

In fact, state-2 is as non-random as state-0, as is state-1. State-1 and
state-2 only look random from a coarse-grained macroscopic description, where
one is only concerned with quantities such as temperature and average velocity
squared. In the above example, because we chose a one-dimensional gas with
identical particles, we can solve the kinematics exactly, i.e., we know the
position and velocity of each of the $2N$ particles precisely at all times.
So, we can start with a highly non-random state-0 and arrive at an equally
non-random state-1, which we can then make look “random”, even though it is
anything but random.

The above example makes it clear that fundamentally there is no difference
whatsoever between state-0 evolving into state-1, and state-2 evolving into
state-3. Without looking into microscopic details, macroscopic observers
(humans) will (in all likelihood) erroneously identify state-1 as “random”,
all the while not giving much thought to state-0, because to them (humans)
such a state is “natural” (humans separate things into containers all the
time). And therein lies the conundrum. If “natural” is defined as being truly
random, then state-0 isn’t “natural” at all, nor is any state it evolves into,
including state-1. Nor is state-2. Therefore, there is nothing surprising in
state-2 evolving into state-3.

The arrow of time, as thought of by macroscopic observers (humans), in the
above example is nothing but the evolution of state-0 into state-1 perceived
as “natural”, while the evolution of state-2 into state-3 perceived as
“unnatural”. (The latter being analogous to a broken egg evolving back into
its unbroken state.) However, this macroscopic perception of the arrow of time
in terms of what is “natural” and “unnatural” is illusory. What’s perceived as
“natural” and “unnatural” relates to the initial conditions. For humans
state-0 is “natural”, but this doesn’t mean it’s truly random or generic. We
can prepare such a state because the initial conditions in which we exist are
not in any way random or generic to start with. Simply put, the arrow of time
is attributable to the initial conditions – within the assumptions of the
above example, that is (we will come back to this below). However,
conceptually, the above example, by stripping off various complexities that
muddy the waters, allows us to clearly see that there’s no fundamental “arrow
of time”: state-0 evolving into state-1 and state-2 evolving into state-3 are
on the equal footing, and all four states are equally non-random and non-
generic (and equally “natural” or “unnatural”, if one uses the human
perception, which isn’t rooted in any fundamental principles).

###  3.2 Nonuniform Velocities

One may dismiss the above example as too simplistic, because we assumed the
magnitudes of the velocities in each box to be uniform. We can readily relax
this.

Consider box A and box B as above, separated by a wall at $t=0$. Each box
still has $N$ particles (all $2N$ particles are indistinguishable). In box A
the particles have nonuniform velocities corresponding to the Boltzmann
distribution [Boltzmann, 1868], [Landau and Lifshitz, 1980] (this is not
critical – see below) with the temperature $T_{A}$, and in box B the particles
have nonuniform velocities corresponding to the Boltzmann distribution with
the temperature $T_{B}$. We can still follow each particle’s evolution, even
though the velocities are nonuniform, as the particles simply go through each
other. As above, it is convenient to think of the particles as labeled by A
and B, depending on which box they were in at $t=0$. We then remove the wall
between the boxes and let the gases mix. After some sufficiently long time
$t=t_{1}\gg L/\sqrt{k~{}\mbox{min}(T_{A},T_{B})/m}$, the gases will be
thoroughly mixed, with particles labeled by A and B randomly distributed along
the entire length $2L$ of the combined box. As above, let us refer to the
initial state at $t=0$ (when the wall between box A and box B was removed) as
state-0, and the state at $t=t_{1}$ as state-1. Then, as above, state-2 is
constructed from state-1 by simultaneously flipping the signs of the
velocities of all $2N$ particles in the combined box.

From the macroscopic point of view, if we didn’t know the microscopic state,
which we can follow precisely through the time evolution of the system (and we
can do it for each individual particle), state-1 looks like a completely
random state of a gas of $2N$ particles with the temperature
$T_{1}=(T_{A}+T_{B})/2$ in a box of length $2L$. However, this state is
anything but “random”. Indeed, state-2, after time $t_{1}$, will evolve into
state-3, in which the positions of the particles are identical to those in
state-0, while all velocities have their signs flipped. So, it makes no
difference whether the velocities are uniform or not, because each particle’s
velocity and position can be solved exactly, so we know the microscopic state
exactly and there is nothing to hide behind. The macroscopic misconstruing of
state-1 and state-2 being “random” again is related to the illusory (human)
attribution of what’s “natural”, which isn’t rooted in any fundamental
principles. The arrow of time again is attributable to the initial conditions.

###  3.3 Entropy and the Second Law of Thermodynamics

At first, there might appear to be something unsettling about state-2 evolving
into state-3 in the context of the second law of thermodynamics. The entropy
of state-2 is the same as the entropy of state-1, which in turn is (naïvely)
expected to be greater than the entropy of state-0 (which is the same as the
entropy of state-3). Then the evolution of state-2 into state-3 would appear
to decrease entropy and violate the second law of thermodynamics. But not
everything is as it seems.

The Sackur-Tetrode equation [Sackur, 1913], [Tetrode, 1912] for the entropy
$S$ of $N$ indistinguishable particles in a one-dimensional box of length $L$
is given by:

$S/kN=\ln(L/\lambda N)+3/2$ (6)

Here $\lambda=h/\sqrt{2\pi mkT}$ is the thermal wavelength, and $h$ is the
Planck constant. Therefore, the Sackur-Tetrode entropies $S_{A}$ and $S_{B}$
of the gases in box A and box B in the previous subsection at $t=0$ are given
by:

$\displaystyle S_{A}=kN\ln(L/\lambda_{A}N)+3kN/2$ (7) $\displaystyle
S_{B}=kN\ln(L/\lambda_{B}N)+3kN/2$ (8)

Here $\lambda_{A}=h/\sqrt{2\pi mkT_{A}}$ and $\lambda_{B}=h/\sqrt{2\pi
mkT_{B}}$. The total entropy at $t=0$ is given by:

$S_{0}=S_{A}+S_{B}=kN^{\prime}\ln(L^{\prime}/\lambda^{\prime}N^{\prime})+3kN^{\prime}/2$
(9)

Here $N^{\prime}=2N$ is the number of particles in both boxes A and B, and
$L^{\prime}=2L$ is the length of the combined box. Also,
$\lambda^{\prime}=h/\sqrt{2\pi mkT^{\prime}}$, where

$T^{\prime}=\sqrt{T_{A}T_{B}}$ (10)

On the other hand, if we apply the Sackur-Tetrode equation to state-1, where
we have $N^{\prime}=2N$ particles in the combined box of length
$L^{\prime}=2L$ with the macroscopic temperature $T_{1}=(T_{A}+T_{B})/2$, we
get the following entropy for state-1:

$S_{1}=kN^{\prime}\ln(L^{\prime}/\lambda_{1}N^{\prime})+3kN^{\prime}/2$ (11)

Here $\lambda_{1}=h/\sqrt{2\pi mkT_{1}}$. Since $\ln(T_{1})>\ln(T^{\prime})$,
we have $S_{1}>S_{0}$. And since state-2 entropy $S_{2}=S_{1}$ and state-3
entropy $S_{3}=S_{0}$, the evolution of state-2 into state-3 would appear to
violate the second law of thermodynamics. However, this apparent “violation”
is as misconstrued and illusory as the time of arrow in this context.

The issue here is that the Sackur-Tetrode equation (6) doesn’t hold for the
one-dimensional system of $N$ particles we discuss above. There are several
assumptions that go into the derivation of (6), including that the system is
macroscopic (in the zeroth approximation this translates into the number of
particles $N$ being large – see below), that the $N$ particles are
indistinguishable, and that the ergodic hypothesis holds (see below). With
these assumptions, one way to arrive at the Sackur-Tetrode equation is to use
the definition of the entropy $S=\ln(\Omega)$ via the number of microstates
$\Omega$ and compute the latter using the phase space approach. Another,
perhaps somewhat simpler but equivalent, approach is to use the relation
between the entropy and the partition function $Z$:

$S=U/T+k\ln(Z)$ (12)

Here $U$ is the average energy (which in the system above is given by
$U=NkT/2$).

For a single quantum particle in a one-dimensional box of length $L$ the
partition function $Z_{1}$ can be computed by summing the Boltzmann weight
$\exp(-E_{i}/kT)$ over all energy levels $E_{i}$. In the continuum (classical)
limit this reduces to a Gaussian integral ($x$ is the spatial coordinate, and
$p$ is the momentum):

$Z_{1}=\frac{1}{h}\int_{0}^{L}dx\int_{-\infty}^{\infty}dp~{}\exp(-p^{2}/2mkT)=L/\lambda$
(13)

Here $\lambda=h/\sqrt{2\pi mkT}$ is the thermal wavelength. For a single
particle in a $D$-dimensional cube, we have $Z_{1}=L^{D}/\lambda^{D}$, or,
more generally, $Z_{1}=V/\lambda^{D}$, where $V$ is a $D$-dimensional volume.
For $N$ indistinguishable particles in $D$ dimensions (in the macroscopic
limit), we have the following (approximate) expression for the partition
function (the division by $N!$ is due to the $N$ particles being
indistinguishable – however, this is an approximation – see below):

$Z=Z_{1}^{N}/N!=V^{N}/\lambda^{N}N!$ (14)

Taking into account that $U=(D/2)kT$ (by the equipartition theorem – see
above), and using the Stirling approximation $\ln(N!)\approx N\ln(N)-N$ for
large $N$, using (12) we arrive at the Sackur-Tetrode equation in $D$
dimensions:

$S/kN=\ln(V/\lambda^{D}N)+(D/2+1)$ (15)

This reduces to (6) for $D=1$.

However, (6) doesn’t apply to the system at hand for several reasons. When
deriving (6), one integrates over a 2-dimensional phase space (in the case of
a single particle in $D=1$, or a $2ND$-dimensional phase space in the case of
$N$ particles in $D$ dimensions) with the canonical measure (i.e., $dxdp/h$),
which implies equal probability of all accessible microstates in the phase
space in the long run (this is Boltzmann’s ergodic hypothesis [Boltzmann,
1898]). This is irrespective of whether one derives the Sackur-Tetrode
equation by counting the number of microstates or by computing the partition
function (as above). However, the ergodic hypothesis clearly doesn’t apply
here. Indeed, due to kinematic constraints in $D=1$, we have a system of non-
interacting $N$ particles, each of which remains in the same energy state ad
infinitum. Simply put, there is no ergodicity here and integration over the
phase space is inapplicable. Each particle’s partition function
$Z_{1-\mbox{\scriptsize particle}}$ can simply be set to 1. (In particular, it
is independent of the temperature $T$.)

Another assumption that goes into the aforesaid derivation is the
indistinguishability of the $N$ particles. The $N$-particle partition function
is then approximated as $Z_{N-\mbox{\scriptsize
particle}}\approx(Z_{1-\mbox{\scriptsize particle}})^{N}/N!$. Dividing by $N!$
(approximately) accounts for the indistinguishability of the $N$ particles.
This is a justified (and good) approximation when $N$ is large and when the
energy of each of the $N$ particles can take a large number $M$ of values
($M\gg N$). Thus, for the argument’s sake, when the energy spectrum is
discrete, we have

$(Z_{1-\mbox{\scriptsize
particle}})^{N}=\left(\sum_{i}\exp(-E_{i}/kT)\right)^{N}$ (16)

Then, the leading contributions to $(Z_{1-\mbox{\scriptsize particle}})^{N}$
come from the terms with all different values of $i$ in the $N$th-power
expansion, whose multiplicity is $N!$, hence the division by $N!$ to avoid
overcounting of the microstates due to the indistinguishability. However, in
our case each particle is stuck in the same energy state, so there are no such
terms, and there is no division by $N!$. The $N$-particle partition function
$Z_{N-\mbox{\scriptsize particle}}$ can simply be set to 1. Then, using (12),
the entropy is simply $S=kN/2$ (for $N$ particles in a one-dimensional box of
length $L$).222 Cf. [Sobol et al, 2021]. Also, it can be argued that an
arbitrary function of only $N$ can be added to the entropy [Jaynes, 1992], so
$S=kN/2$ is superfluous and equivalent to $S=0$. Therefore, mixing the $2N$
particles from box A and box B doesn’t change the total entropy. So, the
process is reversible, which is why state-2 can evolve into state-3, and there
is no violation of the second law of thermodynamics.

So, any “paradox” or “conundrum” arises only due to an “ignorant” approach by
a macroscopic observer who decides to ignore microscopic realities and
describe the system using inadequate macroscopic variables. In this regard it
is instructive to consider the evolution of the system from state-2 to state-3
in the context of the Gibbs paradox (also, mixing paradox) [Gibbs, 1875] as
discussed in [Jaynes, 1992] (entropy is subjective). If the macroscopic
observer knows nothing about the microstates in state-2, then there is no
reason for said observer to suspect that state-3 is anything special, and said
observer will assume that the entropy of state-3 is the same as that of
state-2. In order to start thinking otherwise, said observer would have to
make measurements and discover that in state-3 the temperatures on the left
and right sides of the combined box are different. In fact, to appreciate how
non-generic state-3 is, said observer somehow would have to figure out that
the $N$ particles on the left side (box A) all have absolute velocities
$v_{A}$, while the $N$ particles on the right side (box B) all have absolute
velocities $v_{B}$, all the while believing that in state-2 the $2N$ particles
are indistinguishable. I.e., said observer somehow would have to know that the
$2N$ particles are not in fact indistinguishable. Again, any “paradox” or
“conundrum” arises only due the “ignorance” of said observer.

In this regard it is worthwhile to note the following. While state-0 is
“natural” from a macroscopic observer’s viewpoint (humans separate things into
containers all the time), preparing state-2 would appear to be highly
“unnatural” from said viewpoint. In fact, for large $N$ it’s not even clear if
it would be technologically feasible. On the flipside, theoretically, if in
state-0 at time $t=0$ we know the position $x_{a}(0)$ and the velocity
$v_{a}(0)$ of each particle labeled by $a=1,\dots,2N$, then we know the
position $x_{a}(t)$ and the velocity $v_{a}(t)$ thereof at any later time $t$
as the system is exactly solvable. However, when $N$ is large, in practice we
wouldn’t know $x_{a}(0)$ and $v_{a}(0)$, instead resorting to a macroscopic
description using a few variables (temperature, volume, pressure), which would
invariably imply that we would know nothing about the reversibility of the
mixing of the gases in box A and box B. Also, let us note that state-3, which
is the same as state-0 with all velocities reversed, after a sufficiently long
time $t_{2}$ would evolve into a thoroughly mixed state-4, and state-5
obtained from state-4 by reversing the velocities of all $2N$ particles after
time $t_{2}$ would evolve into state-0.

It is further worth noting that instead of $N$ particles in box A and $N$
particles in box B, we could have started from a simpler system with $N$
particles in box A and empty box B. Upon removal of the wall between box A and
box B, the analysis is similar to that above with the same conclusions.

###  3.4 “Time-reversal” Solutions

State-2 is obtained from state-1 by reversing all velocities. Similarly,
state-3 is obtained from state-0 by reversing all velocities. We can construct
state-0 which is invariant under the reversal of all velocities, i.e., state-0
and state-3 are the same. This can be achieved as follows. Let $a=1,\dots,N$
label the particles in box A, and let $N$ be even. Let $x_{a}(0)=x_{a+1}(0)$
and $v_{a}(0)=-v_{a+1}(0)$, where $a=1,3,5,\dots,(N-1)$. Let the same be the
case for the particles (if there are any) in box B. Then state-0 is invariant
under the reversal of all velocities. This then implies that we have what can
be viewed as a “time-reversal” solution. If we start with state-2
(notwithstanding any technological difficulties), after time $t_{1}$ it
evolves into state-3, which is the same as state-0, which after time $t_{1}$
evolves into state-1, which is the same as state-2 with all velocities
reversed. I.e., state-2 after time $2t_{1}$ evolves into its “mirror” image,
state-1, with all velocities flipped w.r.t. state-2, which is the same as
state-2 going backward in time (hence the name “time-reversal” solutions). In
the process, after time $t_{1}$, the system goes through state-0, which is a
“mirror” image of itself. The entropy is constant during this process. To an
uninformed macroscopic observer, armed with only naïve macroscopic intuition,
such solutions may appear bewildering. However, as discussed above, there is
nothing “paradoxical” about such solutions, and the aforesaid bewilderment is
of said macroscopic observer’s own making.

##  4 Inelastic Collisions, Particle Emissions, etc.

###  4.1 Inelasticity

In the above examples we assumed elastic collisions. In real life collisions
of molecules in a gas are mostly inelastic, so the kinetic energy isn’t
conserved. In such inelastic collisions the kinetic energy can be, e.g.,
transferred to the internal degrees of freedom, not conserved due to changes
in the colliding molecules (chemical reactions), emission of other particles
(e.g., photons), etc. Inelasticity quickly introduces complexity and obscures
time-reversibility. Here we will not discuss the possible sources of
inelasticity exhaustively as this is unnecessary to drive the main point.
Instead, we will focus on photon emissions below.

Before doing so, however, let us mention that what makes the above examples
computationally tractable (in fact, exactly solvable) is that they are one-
dimensional. Even if we assume perfectly elastic collisions in three
dimensions, it is computationally impossible to track a large number $N$ of
molecules, even though each collision is perfectly time-reversible. One then
models the system using a few macroscopic variables, which brings about the
illusory “time-irreversibility”. However, it is instructive to distinguish
between the aforesaid computational complexity and other, perhaps more
profound, sources of illusory “time-irreversibility” we turn to next.

###  4.2 Photon Emissions

If a system evolves deterministically (classical mechanics), then time-
reversibility depends on whether the underlying dynamics is time-reversible.
This is independent of whether the system is computationally tractable. In
quantum mechanics the underlying wave function evolves deterministically
(unitary evolution), and the underlying dynamics is time-reversible. However,
in terms of the observables, the system evolves probabilistically, which
complicates the matters quite a bit. Thus, consider emission of a photon in a
collision of two gas molecules. The collision is inelastic. The photon quickly
moves away from the collision region and becomes part of the environment
(reservoir), i.e., it doesn’t affect any subsequent collisions of molecules in
the gas (see, e.g., [Lesovik et al, 2016]). Therefore, the gas is no longer a
closed system and time-reversibility is lost.

To achieve time-reversibility we would have to reverse the photon emission
process; i.e., we would have to consider the process where the photon is
absorbed in the inverse collision of the original molecules. If this were a
purely classical and deterministic process, things would be much simpler
(albeit not necessarily computationally tractable when a large number of
collisions is involved). However, in quantum mechanics the photon emission and
absorption processes are probabilistic. So, in the time-reversed evolution of
the system, which involves irradiating the gas with a large number of photons,
when dealing with a large number of collisions and a large number of photons
absorbed, the probability that the final state is the original microscopic
state is infinitesimally small, purely due to the probabilistic nature of the
dynamics. Assuming photon emission is the only source of inelasticity, the
aforesaid irradiation may very well achieve (approximately) the same
macroscopic state (as defined by a small number of macroscopic variables such
as temperature) as the original one (i.e., restore the original temperature of
the gas), but the probability that the resultant microscopic state will be the
same as the original microscopic state is indeed infinitesimally small.

It is important to note that this illusory “time-irreversibility” once again
goes back to the initial conditions. The system at hand (a gas emitting
photons into a reservoir) is not a generic, highly symmetrical system.
Instead, it’s a very special, highly asymmetrical open system, which is not in
equilibrium with the environment. Therefore, there is nothing surprising about
its apparent yet illusory “time-irreversibility”.

The upshot here is that we are dealing with highly non-generic, special
initial conditions in systems such as above. E.g., in [Lesovik et al, 2019] it
was argued that to time-reverse the dissipation of a wave packet using an
external electromagnetic field, it would take prohibitively long time of the
order of the age of the universe or longer. That, in itself, doesn’t imply
time-irreversibility, be it practically or theoretically. It took
approximately 14 billion years for the universe to produce the observers
(humans) who can prepare such highly non-generic, special systems (highly
localized wave packets, gas confined to a volume that can be allowed to expand
into another volume, etc.). It should come as no surprise that reversing time
evolution in highly non-generic systems with special initial conditions can
take the age of the universe or longer. (Any bewilderment in this regard is of
the observer’s own making, due to what can be described as the irrationality
of what the observer deems “natural”, just as with the examples of mixing
gases we discuss above.) Put differently, the fact that it would take 14
billion years or longer to restore a broken egg into its original state is no
more surprising than the fact that it took 14 billion years of evolution of
the universe to create an egg (not to mention a human to observe its breakage)
in the first place.

###  4.3 Quantum Wave Packets

In this regard it’s instructive to consider a quantum mechanical wave packet
inside a one-dimensional box of length $L$ (with impenetrable walls at $x=0$
and $x=L$; i.e., the potential $V(x)=0$ for $x\in(0,L)$, and is infinite at
$x=0$ and $x=L$). Let the wave packet wave function at $t=0$ be $\Psi(x,0)$,
which we will assume to be a real-valued, smooth, twice-differentiable
function for $x\in[0,L]$, and which is nonzero inside the interval
$[x_{1},x_{2}]$, $0<x_{1}<x_{2}<L$, and vanishes outside said interval. The
energy levels $E_{n}$ and eigenfunctions $\psi_{n}(x)$ (which satisfy
$\psi_{n}(0)=\psi_{n}(L)=0$, $n=1,2,\dots$) of the Hamiltonian ${\widehat{H}}$
for a particle in the box are given by:

$\displaystyle{\widehat{H}}\psi_{n}(x)=E_{n}\psi_{n}(x)$ (17) $\displaystyle
E_{n}=\frac{\pi^{2}\hbar^{2}n^{2}}{2mL^{2}}$ (18)
$\displaystyle\psi_{n}(x)=\sqrt{\frac{2}{L}}~{}\sin\left(\frac{\pi
nx}{L}\right)$ (19)
$\displaystyle{\widehat{H}}=-\frac{\hbar^{2}}{2m}~{}\frac{\partial^{2}}{\partial
x^{2}},~{}~{}~{}0<x<L$ (20)

The wave packet at $t=0$ is a superposition of the infinite tower of these
eigenfunctions:

$\displaystyle\Psi(x,0)=\sum_{n=1}^{\infty}c_{n}~{}\psi_{n}(x)$ (21)
$\displaystyle c_{n}=\int_{x_{1}}^{x_{2}}dx~{}\Psi(x,0)~{}\psi_{n}(x)$ (22)

With our assumption that $\Psi(x,0)$ is real (which is not critical here), the
coefficients $c_{n}$ then are also real. However, allowing complex phases
doesn’t change any conclusions below.

The evolution of the wave function is given by the Schrödinger equation:

$\displaystyle i\hbar~{}\frac{\partial\Psi(x,t)}{\partial
t}={\widehat{H}}\Psi(x,t)$ (23)
$\displaystyle\Psi(x,t)=\exp(-i{\widehat{H}}t/\hbar)~{}\Psi(x,0)=\sum_{n=1}^{\infty}c_{n}~{}\psi_{n}(x)~{}\exp(-iE_{n}t/\hbar)$
(24)

After a substantially long enough time $t_{1}$, the wave function
$\Psi(x,t_{1})$ is no longer localized. To a macroscopic observer who is only
interested in its spatial shape, this wave function will not appear any more
special than any random wave function. (This is analogous to our discussion of
mixing gases above.) However, $\Psi(x,t_{1})$, into which $\Psi(x,0)$ evolves,
is just as special and non-generic as $\Psi(x,0)$. The wave function
$\Psi(x,-t_{1})$, which evolves into $\Psi(x,0)$ from $t=-t_{1}$ to $t=0$, is
just as special as $\Psi(x,0)$, even though to the aforesaid macroscopic
observer this wave function will not appear any more special than any random
wave function either. Indeed, $\Psi(x,-t_{1})$ is simply the complex conjugate
of $\Psi(x,t_{1})$: $\Psi(x,-t_{1})=\Psi^{*}(x,t_{1})$. However, $\Psi(x,t)$,
for all times $t$, before and after $t=0$, is special and non-generic as it
corresponds to a localized wave packet at $t=0$. For the system to evolve into
this state, its past state at, say, $t=-t_{1}$, must be highly special and
non-generic. So, we are back to special initial conditions. Any difficulty in
time-reversing the dissipation of the wave packet after $t=0$ is due to these
special initial conditions, not illusory “time-irreversibility”.

##  5 Special Initial Conditions: Why, How, …?

The Trillion Dollar Question then is, how come the initial conditions we
observe are so special that we observe the apparent arrow of time? A simple –
and perfectly valid – answer is the anthropic principle [Dicke, 1957],
[Weinberg, 1987]. If the initial conditions weren’t special, we wouldn’t exist
to ponder the question.

However, one can wonder if such special initial conditions can arise
“naturally”, with the ever-present caveat that what’s deemed “natural” can be
subjective and influenced by the very nature of the observers (humans) posing
said question. The standard lore, in the cosmological context, goes as follows
(see, e.g., [Ashtekar et al, 2020] and references therein). Within the cosmic
inflationary scenario, the starting point is the Bunch-Davies [Bunch and
Davies, 1978] vacuum state for the quantum fields, which is homogeneous and
isotropic. It is then (implicitly) assumed that at the end of inflation the
system can be described using classical evolution with a distribution of
states in the classical phase space (position and momentum). This emergence of
classical behavior in the universe, which is assumed to start in an
intrinsically quantum state, is referred to as “quantum-to-classical
transition” or “classicalization”. However, despite decades of effort (see
references in, e.g., [Ashtekar et al, 2020] and [Berjon et al, 2021]), this
classicalization is still not completely understood (see, e.g., [Berjon et al,
2021]). Perhaps even more importantly (see below), it is unclear how the
initial symmetry of the quantum vacuum state (which is homogeneous and
isotropic) is broken such that primordial inhomogeneities and anisotropies
arise, which are then expected to produce the large-scale structure we observe
in the universe (starts, galaxies, galaxy clusters, etc.). In particular, in
the aforesaid standard lore, there doesn’t appear to exist a satisfactory
derivation as it relates to the evolution of an intrinsically quantum state
(Bunch-Davies vacuum) into a classical state with a distribution in the
classical phase space (which is then tied to the aforesaid primordial
inhomogeneities and anisotropies). Instead, it appears to be an ad hoc
assumption with apparent gaps in logic and math (including in the context of
“squeezed states”; see, e.g., [Martin and Vennin, 2016] and references
therein). Therefore, the appearance of primordial inhomogeneities and
anisotropies required for the formation of the observed large-scale structure
in the universe by no means appears to be settled and is an open question
(see, e.g. [Berjon et al, 2021]).

###  5.1 Macroscopic Objects

The discussion in the cosmological context of classicalization and primordial
asymmetries, however, appears to be unnecessarily confusing by mixing various
issues that can be understood much more simply. The universe we observe is
certainly not “classical” but quantum. It’s just that quantum effects are
minuscule on macroscopic scales, which is why we only observe them at
microscopic scales. What follows as it relates to quantum effects is nothing
new, but perhaps (hopefully) the way it’s stated in the context of how special
conditions can arise in the cosmological context is helpful in demystifying
this topic.

Smallness of quantum effects can be thought of in many ways. A standard way is
to look at Heisenberg’s uncertainty principle:

$\Delta x~{}\Delta p\geq\hbar/2$ (25)

Let $M$ be the mass of the object the uncertainties $\Delta x$ and $\Delta p$
in whose position $x$ and momentum $p$ we wish to understand. Let $\Delta v$
be the uncertainty in the velocity $v=p/M$. Then we have

$\Delta x~{}\Delta v\geq\hbar/2M$ (26)

For macroscopic objects the mass $M$ is large (compared with atomic scales)
and the r.h.s. of (26) is so small that the lower bound it imposes on $\Delta
x~{}\Delta v$ is immaterial in the context of realistic measurement errors
$(\Delta x)_{m}$ and $(\Delta v)_{m}$ by a macroscopic observer, i.e.,
$(\Delta x)_{m}~{}(\Delta v)_{m}\gg\hbar/2M$. So, the “quantumness” of the
system is well beyond the measurement precision capabilities of the observer.

Another, quintessentially quantum, way of thinking about smallness of quantum
effects is to consider quantum tunneling. Let’s consider a gas of $N$
particles in a one-dimensional box. Let one of the walls of the box not be
impenetrable, i.e., let’s have a potential barrier of a finite height at said
wall. Let the probability for a single particle to tunnel through the wall be
$P$. We don’t have to assume that $P$ is exponentially small, it can be, say,
$P\sim 0.1$. Assuming the $N$ particles are non-interacting and their number
is large, the probability of $M$ particles tunneling though the wall is $\sim
P^{M}$. This probability for any macroscopic subset of $M$ particles to tunnel
through the wall (even if $M\ll N$; recall that Avogadro’s constant
$N_{A}\approx 6\times 10^{23}$ per mole) is tiny and doesn’t affect the
macroscopic characteristics of the gas (as measured by a macroscopic observer
with realistic measurement precision capabilities).

I.e., macroscopic objects behave classically not because the world around us
is classical, and not due to some “classicalization” scheme, but because
quantum effects for large objects are small. So, in the cosmological context
what needs to be explained isn’t some “classicalization” scheme, but clumping
of matter in the early universe that leads to the formation of macroscopic
objects.

###  5.2 Clumping of Matter

However, if this clumping itself is homogeneous and isotropic, the resulting
large-scale structure will also be homogeneous and isotropic at all scales,
which is not what we observe in the universe. The aforesaid assumption (in the
context of the aforesaid standard lore) that quantum fluctuations somehow will
break the initial symmetry lacks justification and it is unclear what the
mechanism would be for such symmetry breaking. We can readily understand this
already in the context of non-relativistic quantum mechanics. Here we could
consider a simpler one-dimensional analog of the system we describe below.
However, the three-dimensional example is just as easy to follow and is more
“realistic”.

Thus, consider an infinite three-dimensional cubic lattice. (The choice of the
lattice is not critical here, so long as we have periodicity.) The nodes of
the lattice have the coordinates ${\vec{r}}_{\vec{n}}={\vec{n}}L$, where
${\vec{n}}=(n_{1},n_{2},n_{3})$, $n_{i}\in{\bf Z}$ ($i=1,2,3$) are integers,
and $L$ is the lattice spacing. Let us now consider a system where we have a
particle of mass $m$ (initially – see below) localized around each node (so we
have an infinite number of such particles). Let us label these particles by
$a$, and their coordinates and momenta by ${\vec{r}}_{a}$ and ${\vec{p}}_{a}$.
Let us assume that the particles are non-relativistic. Let us include
Newtonian gravitational interactions between the particles. Then the
Schrödinger equation and quantum Hamiltonian are given by:333 Here we won’t
include the effects of wave function collapse due to gravitational self-
interaction [Diosi, 1984], [Penrose, 1996].

$\displaystyle i\hbar~{}\frac{\partial\Psi({\vec{r}}_{a},t)}{\partial
t}={\widehat{H}}\Psi({\vec{r}}_{a},t)$ (27)
$\displaystyle{\widehat{H}}=-\frac{\hbar^{2}}{2m}\sum_{a}\frac{\partial^{2}}{\partial{\vec{r}}_{a}^{2}}-\sum_{a\neq
b}\frac{G_{N}m^{2}}{{|{\vec{r}}_{a}-{\vec{r}_{b}}|}}$ (28)

Here $G_{N}$ is Newton’s gravitational constant. (Here we assume that the
space is static; we will discuss expanding space in a moment.) So, we have
unitary evolution with a Hamiltonian that is invariant under translations and
rotations. In particular, it preserves all the symmetries of the cubic
lattice.

Now let us assume that at $t=0$ the wave function $\Psi({\vec{r}}_{a},0)$
corresponds to the particles localized around the nodes of the lattice. Let
$f(r)$ be a smooth, twice-differentiable function of $r$ ($r\geq 0$), such
that $f(r)=0$ for $r\geq R$, where $R\ll L$. Let ${\vec{h}}$ be a one-to-one
map between the set $\\{a\\}$ and the set $\\{{\vec{n}}\\}$, i.e., for each
value of $a$, ${\vec{h}}(a)$ is a vector ${\vec{n}}_{a}\in\\{{\vec{n}}\\}$,
and the inverse $g$ of ${\vec{h}}$ gives $g({\vec{n}}_{a})=a$. Let us now take
the initial wave function to be

$\Psi({\vec{r}}_{a},0)=\sum_{a}f(|{\vec{r}}_{a}-{\vec{n}}_{a}L|)$ (29)

I.e., at $t=0$ we have a spherically symmetric wave packet localized at each
of the nodes of the square lattice. (If so desired, we can regularize the
infinite sum by considering the space to be a large 3-torus instead.) Since
the Hamiltonian is invariant under lattice shifts, and so is
$\Psi({\vec{r}}_{a},0)$, then $\Psi({\vec{r}}_{a},t)$ is also invariant under
lattice shifts at all subsequent times $t>0$.

If the wave packets have random nonzero group velocities, then the lattice
symmetry is broken and clumping of wave packets will occur due to the
gravitational attraction. The resultant wave function will no longer have the
symmetry of the lattice. However, this is not due to “quantum fluctuations”
but the initial conditions.

Generally, in the cosmological context, to have inhomogeneities and
anisotropies in the large-scale structure of the universe, there need to be
primordial inhomogeneities and anisotropies in the early universe as part of
the initial conditions. So, if the universe starts in an intrinsically quantum
state, the initial conditions must include inhomogeneities and anisotropies as
unitary quantum evolution will not introduce such asymmetries. Otherwise, the
universe would be homogeneous and isotropic and/or there would be large
quantum probabilities of observing identical macroscopic objects in different
directions and/or parts of space. The latter issue is related to the
“classicalization” problem. However, there is no issue if the initial
conditions intrinsically include inhomogeneities and anisotropies, which then
can result in clumping of matter due to the gravitational interaction, thereby
leading to the formation of the observed large-scale structure with
macroscopic objects in it, which appear to be classical (rather than quantum)
for the reasons discussed above.

Let us note that in the above discussion we assumed that space wasn’t
expanding. Let us consider an expanding spacetime with the metric (in the
units where the speed of light $c=1$)

$ds^{2}=-dt^{2}+a^{2}(t)d{\vec{r}}^{2}$ (30)

Here $a(t)$ is the scale factor, which increases with time $t$. Then the
Hamiltonian (28) is modified by simply replacing ${\vec{r}}_{a}$ and
${\vec{r}}_{b}$ by $a(t){\vec{r}}_{a}$ and $a(t){\vec{r}}_{b}$, which doesn’t
affect the invariance of the Hamiltonian under translations and rotations, so
the conclusions discussed above are unmodified.

###  5.3 How Can Initial Conditions That Include Us Arise?

If we accept that the initial conditions intrinsically include inhomogeneities
and anisotropies, that may appear to imply that the initial conditions would
have to be tailored for humans to exist, for the author to be typing these
words, and for the reader to be reading them. At least for some, that could be
a big ask. However, not all may be as it might appear. If we assume randomness
in primordial inhomogeneities and anisotropies (with any possible non-Gaussian
contributions; see, e.g., [Ezquiaga et al, 2023] and references therein), in
the infinite three-dimensional space this will result in an infinite number of
possible configurations of special initial conditions, which can include those
resulting in the patch of space we live in. These asymmetries can be due to
fluctuations in spatial density of matter and in the momenta. I.e., so long as
we assume randomness (possibly with fat tails), what we observe around us
would appear to have to happen somewhere in the infinite space with
probability 1. Using business lingo, this is a “big idea”.

This by itself doesn’t answer the question of how such random (albeit possibly
fat-tailed) asymmetries arose. If we assume that all interactions and matter
in the universe are quantum and subject to unitary evolution (which itself is
homogeneous and isotropic), then it is difficult to see how such asymmetries
would magically arise starting from a symmetric vacuum configuration. I.e.,
these asymmetries would have to be inherent in the initial quantum state. One
can only speculate why they were present in said state, e.g., one could
consider big-bounce cosmology [Poplawski, 2012], ekpyrotic and cyclic models
[Lehners, 2009], etc.

Logically, there is another avenue, to wit, to forgo some of the assumptions
discussed above. One of these assumptions is unitary evolution of quantum
systems. Another is that all interactions and matter in the universe are
quantum. While experimentally we know that ordinary matter and strong and
electroweak interactions are quantum, we don’t have any experimental evidence
that dark matter is quantum, or that gravity is quantum. There are theoretical
arguments based on thought experiments (see, e.g., [Eppley and Hannah, 1977]
and [Page and Geilker, 1981], whose critiques appear, e.g., in [Mattingly,
2006] and [Hawkins, 1982], respectively) why gravity should be quantum;
however, currently there is no experimental evidence that gravity is in fact
quantum (and, theoretical arguments aside, physics is an experimental
science). The (perhaps technical, as opposed to conceptual) issue with keeping
gravity classical is related to the question of how to couple it to quantum
matter. The issues with semiclassical gravity (where gravity is coupled to the
expectation value of the energy-momentum tensor for quantum fields) discussed
in, e.g., [Page and Geilker, 1981] might be surmountable via a mechanism for
wave function collapse [Großardt, 2022]. Coupling of classical gravity to
quantum matter via stochastic interactions [Oppenheim, 2023] is another avenue
(albeit with its own open questions). One noteworthy aspect of the latter
approach in the context of the initial conditions is that, perhaps the
generation of random primordial density fluctuations can be attributable to
the intrinsic stochastic interactions therein.

##  6 Concluding Remarks

Let us conclude with some clarifying remarks.

First, when discussing processes involving particle emission and absorption
(e.g., photons), we venture outside the realm of non-relativistic quantum
mechanics into relativistic quantum field theory (QFT) (e.g., quantum
electrodynamics (QED)). In QFT we have the $CPT$ theorem (see, e.g., [Blum and
Martínez de Velasco, 2022] and references therein), which states that the
theory is invariant under simultaneous $C$ (charge conjugation, or particle-
antiparticle exchange), $P$ (spatial inversion, or parity transformation) and
$T$ (time reversal) transformations. $CP$ is mostly conserved except in weak
interactions involving kaons (or K-mesons), which contain a strange quark
[Christenson et al, 1964]. $CP$ violation implies violation of time-reversal
in said interactions. However, it is unclear whether this violation is
significant enough to account for the arrow of time on cosmic scales (cf.
[Vaccaro, 2016]). The same comment applies to $CP$ violation in the lepton
sector (even if it explains the observed matter-antimatter asymmetry in the
universe via leptogenesis; see, e.g., [Davidson et al, 2008] and references
therein).

Speaking of QFT, typical theoretical objections to not quantizing gravity
(see, e.g., [Eppley and Hannah, 1977] and [Page and Geilker, 1981])
essentially boil down to the following. The classical Einstein equation reads
(in $c=1$ units):

$R_{\mu\nu}-\frac{1}{2}g_{\mu\nu}R=8\pi G_{N}T_{\mu\nu}$ (31)

Here $g_{\mu\nu}$ is the spacetime metric, $R_{\mu\nu}$ and $R$ are the tensor
and scalar curvatures, and $T_{\mu\nu}$ is the energy-momentum tensor (for all
matter and non-gravitational interactions). The latter becomes an operator
${\widehat{T}}_{\mu\nu}$ when matter and non-gravitational interactions are
quantized. So, then the conundrum is how to make sense of (31) if its l.h.s.
remains a number (rather than an operator). In semiclassical gravity one
replaces $T_{\mu\nu}$ in the r.h.s. of (31) by the expectation value
$\langle{\widehat{T}}_{\mu\nu}\rangle$ (see, e.g., [Großardt, 2022]), and the
decades-old discussion ensues.

However, before jumping the gun, one may wish to consider the following simple
point. The issue is how to consistently couple QFT to classical gravity.
However, does it even make sense to seek such “consistent” coupling of QFT to
classical gravity when QFT itself isn’t self-consistent? Indeed, QED has a
Landau pole [Landau et al, 1954]. In the electroweak theory the weak
hypercharge group $U(1)_{Y}$ also has a Landau pole. An embedding of the
strong and electroweak interactions into a grand unified theory (GUT) would
avoid a Landau pole. However, there is no experimental evidence for GUTs, and
their telltale sign, which is proton decay, hasn’t been observed, albeit this
doesn’t rule out all GUTs, but does rule out some (for a recent discussion,
see, e.g., [Ohlsson, 2023] and references therein). One of the indirect
“hints” for a GUT is the observation that the electroweak and strong couplings
approximately meet in the minimal supersymmetric standard model (MSSM), but
not in its non-supersymmetric counterpart (see, e.g., [Schwichtenberg, 2019]
and references therein). However, there is still no experimental evidence for
supersymmetry. (Non-supersymmetric GUTs can be constructed, but generally
require additional matter fields at intermediate scales below the GUT scale,
or large threshold corrections due to non-degenerate masses of superheavy
fields (Id).) Furthermore, GUTs generally predict magnetic monopoles [’t
Hooft, 1974], [Polyakov, 1974], which would be produced in the early universe
[Guth and Tye, 1980], [Einhorn et al, 1980], and are then explained away by
cosmic inflation [Guth, 1981]. Inflation introduces its own issues (as
discussed above), which then require additional ingredients, etc. And so on,
and so forth, possibly ad infinitum.

The main purpose of the immediately preceding paragraph is to illustrate how
solving one problem can turn into a self-fulfilling prophecy if one allows for
tunnel vision to take over. The original problem was that of consistently
coupling classical gravity to not-self-consistent QED. It’s important to keep
in mind that various computational techniques developed in physics (one of
which is perturbative QED) aren’t complete theories without limitations. They
work well in certain regimes and/or certain computations, but aren’t adequate
in others. For instance, we don’t compute the (zeroth-approximation) hydrogen
atom spectrum using perturbative QED. Instead, we compute it using the non-
relativistic Schrödinger equation. To account for the fine structure of the
hydrogen atom spectrum, we use the relativistic Dirac equation. To compute the
Lamb shift and anomalous magnetic dipole moment of the electron, we use QED
[Bethe, 1947], [Schwinger, 1948]. These computational methods clearly have
limitations. E.g., it’s unclear how to make sense of QED to all orders in
perturbation theory [Dyson, 1952], there’s a Landau pole, etc. The lesson here
is that overambitious, all-encompassing theories (apart from being very hard)
often don’t produce predictive computational tools. So, then the question is,
pragmatically speaking, what’s better, to spend decades on trying to couple
gravity consistently to quantum matter and interactions (this includes both
keeping gravity classical, and quantizing gravity, including via string theory
(see, e.g., [Becker et al, 2007])), or to find a computational method that
would allow to make experimentally verifiable and falsifiable predictions?
(Arguably, it’s a matter of taste.)

Now, back to the arrow of time, it’s all about the special initial conditions.
The Trillion Dollar Question, once again, is how the special initial
conditions in our universe arose. Cosmic inflation tries to answer some of the
questions in this regard, at the expense of introducing others (see, e.g.,
[Penrose, 1989], [Earman and Mosterín, 1999], [Ijjas et al, 2014], and the
discussion above). As discussed above, the question of special initial
conditions is an open question for various reasons, including how the
asymmetries we observe arose (and the inflationary scenario doesn’t appear to
answer this question). Therefore, the mystery of the apparent arrow of time,
which is attributable to the special initial conditions, is a mystery of why,
how, etc., these special initial conditions exist (albeit assuming randomness
appears to suffice – see above). Hopefully, this note, by stripping off
various (arguably, unnecessary) complexities, which typically muddy the waters
in discussions thereof, helps demystify the arrow of time, even if it doesn’t
answer the Trillion Dollar Question definitively.

### Acknowledgments

I am grateful to my mother Mila Kakushadze for encouraging me to write up this
note.

## References

  * [1]
  * Ashtekar et al, 2020 A. Ashtekar, A. Corichi and A. Kesavan (2020) Emergence of classical behavior in the early Universe. Phys. Rev. D102(2): 023512.
  * Becker et al, 2007 K. Becker, M. Becker and J.H. Schwarz (2007) String Theory and M-Theory: A Modern Introduction. New York, NY: Cambridge University Press.
  * Berjon et al, 2021 J. Berjon, E. Okon and D. Sudarsky (2021) Critical review of prevailing explanations for the emergence of classicality in cosmology. Phys. Rev. D103(4): 043521.
  * Bethe, 1947 H.A. Bethe (1947) The Electromagnetic Shift of Energy Levels. Phys. Rev. 72(4): 339-341.
  * Blum and Martínez de Velasco, 2022 A.S. Blum and A. Martínez de Velasco (2022) The genesis of the CPT theorem. Eur. Phys. J. H47: 5.
  * Boltzmann, 1868 L. Boltzmann (1868) Studien über das Gleichgewicht der lebendigen Kraft zwischen bewegten materiellen Punkten. Wiener Berichte 58: 517-560.
  * Boltzmann, 1871 L. Boltzmann (1871) Einige allgemeine Sätze über Wärmegleichgewicht. Wiener Berichte 63: 679-711.
  * Boltzmann, 1876 L. Boltzmann (1876) Über die Natur der Gasmoleküle. Wiener Berichte 74: 553-560.
  * Boltzmann, 1898 L. Boltzmann (1898) Vorlesungen über Gastheorie. Vol. 2. Leipzig, Germany: J.A. Barth.
  * Bunch and Davies, 1978 T.S. Bunch and P.C.W. Davies (1978) Quantum field theory in de Sitter space: renormalization by point-splitting. Proc. R. Soc. Lond. A360(1700): 117-134.
  * Christenson et al, 1964 J.H. Christenson, J.W. Cronin, V.L. Fitch and R. Turlay (1964) Evidence for the $2\pi$ Decay of the ${K_{2}}^{0}$ Meson. Phys. Rev. Lett. 13(4): 138-140.
  * Davidson et al, 2008 S. Davidson, E. Nardi and Y. Nir (2008) Leptogenesis. Physics Reports 466(4-5): 105-177.
  * Dicke, 1957 R.H. Dicke (1957) Gravitation without a principle of equivalence. Reviews of Modern Physics 29(3): 363-376.
  * Diosi, 1984 L. Diósi (1984) Gravitation and quantum-mechanical localization of macro-objects. Phys. Lett. A105(4-5): 199-102.
  * Dyson, 1952 F.J. Dyson (1952) Divergence of Perturbation Theory in Quantum Electrodynamics. Phys. Rev. 85(4): 631-632.
  * Earman and Mosterín, 1999 J. Earman and J. Mosterín (1999) A Critical Look at Inflationary Cosmology. Philosophy of Science 66(1): 1-49.
  * Einhorn et al, 1980 M.B. Einhorn, D.L. Stein and D. Toussaint (1980) Are grand unified theories compatible with standard cosmology? Phys. Rev. D21(12): 3295-3298.
  * Eppley and Hannah, 1977 K. Eppley and E. Hannah (1977) The necessity of quantizing the gravitational field. Foundations of Physics 7(1): 51-68.
  * Ezquiaga et al, 2023 J.M. Ezquiaga, J. García-Bellido and V. Vennin (2023) Massive Galaxy Clusters Like El Gordo Hint at Primordial Quantum Diffusion. Phys. Rev. Lett. 130(12): 121003.
  * Gibbs, 1875 J.W. Gibbs (1875-1878) On the Equilibrium of Heterogeneous Substances. Connecticut Acad. Sci.
  * Großardt, 2022 A. Großardt (2022) Three little paradoxes: Making sense of semiclassical gravity. AVS Quantum Sci. 4(1): 010502.
  * Guth, 1981 A.H. Guth (1981) Inflationary universe: A possible solution to the horizon and flatness problems. Phys. Rev. D23(2): 347-356.
  * Guth and Tye, 1980 A.H. Guth and S-H.H. Tye (1980) Phase transitions and magnetic monopole production in the very early universe. Phys. Rev. Lett. 44(10): 631–635; Err. ibid. 44(14): 963.
  * Hawkins, 1982 B. Hawkins (1982) Indirect Evidence for Quantum Gravity? Phys. Rev. Lett. 48(7): 520.
  * Ijjas et al, 2014 A. Ijjas, P.J. Steinhardt and A. Loeb (2014) Inflationary schism. Phys. Lett. B736: 142-146.
  * Jaynes, 1992 E.T. Jaynes (1992) The Gibbs Paradox. In: Maximum Entropy and Bayesian Methods (eds. C.R. Smith, G.J. Erickson and P.O. Neudorfer). Dordrecht, Holland: Kluwer Academic Publishers, pp. 1-22.
  * Landau et al, 1954 L.D. Landau, A.A. Abrikosov and I.M. Khalatnikov (1954) An asymptotic expression for the photon Green function in quantum electrodynamics. Dokl. Akad. Nauk SSSR 95(6): 1177-1180 (in Russian).
  * Landau and Lifshitz, 1980 L.D. Landau and E.M. Lifshitz (1980) Course of Theoretical Physics. Vol. 5: Statistical Physics. Oxford, UK: Pergamon Press (3rd ed).
  * Lehners, 2009 J.-C. Lehners (2009) Ekpyrotic and cyclic cosmology. Phys. Rep. 465(6): 223-263.
  * Lesovik et al, 2016 G.B. Lesovik, A.V. Lebedev, I.A. Sadovskyy, M.V. Suslov and V.M. Vinokur (2016) H-theorem in quantum physics. Scientific Reports 6: 32815.
  * Lesovik et al, 2019 G.B. Lesovik, I.A. Sadovskyy, M.V. Suslov, A.V. Lebedev and V.M. Vinokur (2019) Arrow of Time and its Reversal on IBM Quantum Computer. Scientific Reports 9: 4396.
  * Martin and Vennin, 2016 J. Martin and V. Vennin (2016) Quantum discord of cosmic inflation: Can we show that CMB anisotropies are of quantum-mechanical origin? Phys. Rev. D93(2): 023505.
  * Mattingly, 2006 J. Mattingly (2006) Why Eppley and Hannah’s thought experiment fails. Phys. Rev. D73(6): 064025.
  * Ohlsson, 2023 T. Ohlsson (2023) Proton decay. Nuclear Physics B993: 116268.
  * Oppenheim, 2023 J. Oppenheim (2023) A Postquantum Theory of Classical Gravity? Phys. Rev. X13(4): 041040.
  * Page and Geilker, 1981 D.N. Page and C.D. Geilker (1981) Indirect Evidence for Quantum Gravity. Phys. Rev. Lett. 47(14): 979-982.
  * Penrose, 1989 R. Penrose (1989) Difficulties with Inflationary Cosmology. Annals of the New York Academy of Sciences 571(1): 249-264.
  * Penrose, 1996 R. Penrose (1996) On gravity’s role in state reduction. Gen. Relativ. Gravit. 28(5): 581-600.
  * Polyakov, 1974 A.M. Polyakov (1974) Particle spectrum in quantum field theory. JETP Letters 20: 194-195. (ZhETF Pis. Red. 20(6): 430-433.)
  * Poplawski, 2012 N. Poplawski (2012) Nonsingular, big-bounce cosmology from spinor-torsion coupling. Phys. Rev. D85(10): 107502.
  * Sackur, 1913 O. Sackur (1913) Die universelle Bedeutung des sog. elementaren Wirkungsquantums. Annalen der Physik 40: 67-86.
  * Schwichtenberg, 2019 J. Schwichtenberg (2019) Gauge coupling unification without supersymmetry. Eur. Phys. J. C79: 351.
  * Schwinger, 1948 J. Schwinger (1948) On Quantum-Electrodynamics and the Magnetic Moment of the Electron. Phys. Rev. 73(4): 416-417.
  * Sobol et al, 2021 A. Sobol, P. Güntert and R. Riek (2021) On the Entropy of a One-Dimensional Gas with and without Mixing Using Sinai Billiard. Entropy 23(9): 1188.
  * Tetrode, 1912 H. Tetrode (1912) Die chemische Konstante der Gase und das elementare Wirkungsquantum. Annalen der Physik 38: 434-442; Err. ibid. 39: 255.
  * ’t Hooft, 1974 G. ’t Hooft (1974) Magnetic monopoles in unified gauge theories. Nuclear Physics B79(2): 276-284.
  * Vaccaro, 2016 J.A. Vaccaro (2016) Quantum asymmetry between time and space. Proc. R. Soc. A472(2185): 20150670.
  * von Neumann, 1929 J. von Neumann (1929) Beweis des Ergodensatzes und des H-Theorems in der neuen Mechanik. Zeitschrift für Physik 57: 30-70.
  * Waterston, 1846 J.J. Waterston (1846) On the physics of media that are composed of free and elastic molecules in a state of motion. Proc. R. Soc. Lond. 5: 604.
  * Waterston, 1892 J.J. Waterston (1892) On the physics of media that are composed of free and perfectly elastic molecules in a state of motion. Philosophical Transactions of the Royal Society of London 183: 1-79.
  * Weinberg, 1987 S. Weinberg (1987) Anthropic bound on the cosmological constant. Phys. Rev. Lett. 59(22): 2607-2610.


# On the group pseudo-algebra of finite groups

Mark L. Lewis  Department of Mathematical Sciences, Kent State University,
Kent, OH 44242, USA  Quanfu Yan  Department of Mathematical Sciences, Kent
State University, Kent, OH 44242, USA

Abstract. Let $G$ be a finite group. The group pseudo-algebra of $G$ is
defined as the multi-set $C(G)=\\{(d,m_{G}(d))\mid d\in{\rm Cod}(G)\\},$ where
$m_{G}(d)$ is the number of irreducible characters of with codegree $d\in{\rm
Cod}(G)$. We show that there exist two finite $p$-groups with distinct orders
that have the same group pseudo-algebra, providing an answer to Question 3.2
in [11]. In addition, we also discuss under what hypothesis two $p$-groups
with the same group pseudo-algebra will be isomorphic.

Keywords: Finite $p$-groups, Characters, Group pseudo-algebra.
MSC: 20C15, 20D15.

##  1 Introduction

All groups considered in this article are finite. As usual, $G$ will always be
a finite group, and $k(G)$ denotes the number of conjugacy classes of $G.$ We
write ${\rm Irr}(G)$ to denote the set of complex irreducible characters of
$G$ and ${\rm cd}(G)=\\{\chi(1)\mid\chi\in{\rm Irr}(G)\\}.$ Let $\chi\in{\rm
Irr}(G)$. The codegree of $\chi$ is defined as

${\rm cod}\chi=\frac{|G:\ker\chi|}{\chi(1)},$

which was introduced by Qian, Wang and Wei in [13]. The concept has been
studied extensively and proved to have interesting connections with some
algebraic structure of finite groups (see, for example, [11, 9, 12, 14, 4]).

In [11], A. Moretó first introduced the concept of the group pseudo-algebra,
which is defined as the multi-set

$C(G)=\\{(d,m_{G}(d))\mid d\in{\rm Cod}(G)\\},$

where ${\rm Cod}(G)=\\{{\rm cod}\chi\mid\chi\in{\rm Irr}(G)\\}$ and $m_{G}(d)$
is the number of irreducible characters having codegree $d$. He showed that if
two finite abelian groups have the same group pseudo-algebra, then they are
isomorphic. Additionally, a natural question arises: must groups have the same
order if they have the same group pseudo-algebra? A particular case of the
question asks whether $G\cong A$ provided that $C(G)=C(A),$ where $G$ is a
finite group and $A$ is an abelian $p$-group for some prime $p.$ He gave an
affirmative answer when either $A$ is cyclic or the exponent of $A$ does not
exceed $p^{2}$ (see [11, Theorem 3.4]). Thus, the next natural case to look is
when the exponent of $A$ is $p^{3}.$ We will prove that if $G$ is a nonabelian
group and $A$ is an abelian $p$-group of exponent $p^{3}$ so that $C(G)=C(A)$,
then $p=2.$ This result guides us in constructing examples, suggesting that
the question does not always yield a positive answer.

######  Theorem 1.1.

Let $p$ be a prime. There exists an abelian $p$-group $A$ and a group $G$ with
$C(G)=C(A)$ so that $G$ is not isomorphic to $A.$ Hence, groups may have
different orders even though they have the same group pseudo-algebra.

From the above theorem, it is clear that the question is not always true when
the abelian $p$-group $A$ has three generators. Thus, it might be a good idea
to focus on the case when $A$ has two generators, in particular, when $A\cong
C_{p^{n}}\times C_{p},$ where $p$ is a prime. We first consider metacyclic
groups $G$ satisfying $C(G)=C(A)$ and it turns out that $G$ must be isomorphic
to $A.$ Applying this result, we can prove that for a group $G$ and $A\cong
C_{p^{n}}\times C_{p},$ if $C(G)=C(A),$ then either $G\cong A$ or
$|G:G^{\prime}|=p^{2}$ and $p>2.$

######  Theorem 1.2.

Let $G$ be a group and $A\cong C_{p^{n}}\times C_{p},$ where $p$ is a prime
and $n\geqslant 3$ is an integer. Suppose that $C(G)=C(A).$ Then $G$ is a
$p$-group and one of the following holds:

$(1)$ $G\cong A.$

$(2)$ $|G:G^{\prime}|=p^{2},$ $p>2$ and $Z(G)$ is noncyclic. In addition,
there is a unique maximal subgroup $X$ of $G^{\prime}$ which is normal in $G$
so that the factor group $G/X$ is nonabelian of order $p^{3}$ and of exponent
$p.$

Applying the above result, we show that $G\cong A$ if $A\cong C_{p^{3}}\times
C_{p}$ and $C(G)=C(A).$ We also demonstrate that under the same hypothesis as
stated in the above theorem, if, in addition, $G$ has either a metacyclic
maximal subgroup or a two-generator derived subgroup $G^{\prime},$ then
$G\cong A.$

######  Theorem 1.3.

Let $G$ be a group and $A\cong C_{p^{n}}\times C_{p},$ where $p$ is a prime.
Suppose that $C(G)=C(A).$ Then $G\cong A$ if one of the following holds:

$(1)$ $G$ has a metacyclic maximal subgroup,

$(2)$ The derived subgroup $G^{\prime}$ is generated by two elements,

$(3)$ The derived subgroup $G^{\prime}$ is abelian.

The work in this paper was completed by the second author (P.h.D student)
under the supervision of the first author at ***. The contents of this paper
may appear as part of the second author’s P.h.D dissertation.

##  2 Main Results

In this section, we start by stating a fact that will be used frequently.
Theorem A in [13] yields that if $G$ is a group such that ${\rm Cod}(G)$ is a
set of powers of a prime $p,$ then $G$ is a $p$-group. Now we prove the
following basic lemmas.

######  Lemma 2.1.

Let $G$ be a nonabelian group and $A$ be an abelian $p$-group of order $p^{a}$
for some prime $p$. Suppose that $C(G)=C(A).$ Then $|{\rm cd}(G)|\geqslant 3.$

[Proof]Since $A$ is abelian, we have that $A\cong{\rm Irr}(A)$ and so ${\rm
Cod}(A)$ coincides with the set of element orders of $A$. Hence ${\rm
Cod}(G)={\rm Cod}(A)$ is a set of powers of $p.$ It follows that $G$ is a
$p$-group. Assume that $|{\rm cd}(G)|<3.$ Then $|{\rm cd}(G)|=2$ as $G$ is
nonabelian. So we may assume ${\rm cd}(G)=\\{1,p^{e}\\}$ for some positive
integer $e.$ Let $|A|=p^{a}$, $|G|=p^{n}$ and $|G:G^{\prime}|=p^{r}.$ By
$C(G)=C(A),$ we have that $k(G)=k(A)=p^{a}.$ Then $p^{r}<p^{a}<p^{n}.$ Notice
that $|G|=|G:G^{\prime}|+(k(G)-|G:G^{\prime}|)p^{2e}.$ Thus
$p^{n-r}-1=(p^{a-r}-1)p^{2e},$ contrary to the fact that $p^{2e}$ does not
divide $p^{n-r}-1.$ Hence $|{\rm cd}(G)|\geqslant 3,$ as wanted.

Now we delve deeper into the degree set of $G.$ In particular, we consider the
case when ${\rm cd}(G)=\\{1,p,p^{2}\\}.$

######  Lemma 2.2.

Let $G$ be a nonabelian group and $A$ be an abelian $p$-group of order $p^{a}$
for some prime $p$. Suppose that $C(G)=C(A)$ and ${\rm
cd}(G)=\\{1,p,p^{2}\\}.$ Then $p=2$ and $|G|=2^{a+2}.$ In particular, if we
write $|G:G^{\prime}|=p^{r}$ and $k_{1}=|\\{\chi\in{\rm
Irr}(G)\mid\chi(1)=p\\}|$ and $k_{2}=|\\{\chi\in{\rm
Irr}(G)\mid\chi(1)=p^{2}\\}|,$ then $k_{1}=p^{a}-p^{r}-p^{r-2}$ and
$k_{2}=p^{r-2}.$

[Proof]Following the same reasoning process as in Lemma 2.1, $G$ is a
$p$-group. Since $C(G)=C(A)$, we have that $k(G)=k(A)=p^{a}$ and so
$|G|>p^{a}$ as $G$ is nonabelian. On the other hand, we have that

$\displaystyle|G|$ $\displaystyle=$
$\displaystyle|G:G^{\prime}|+k_{1}p^{2}+k_{2}p^{4}$ $\displaystyle\leqslant$
$\displaystyle p^{r}+p^{2}+(p^{a}-p^{r}-1)p^{4}$ $\displaystyle=$
$\displaystyle p^{a+4}-p^{r+4}+p^{r}-p^{4}+p^{2}$ $\displaystyle<$
$\displaystyle p^{a+4}.$

Hence, $|G|=p^{a+1},p^{a+2},\ {\rm or}\ p^{a+3}.$ Notice that
$|G:G^{\prime}|=k(G)-k_{1}-k_{2}$ and so
$|G|=k(G)+k_{1}(p^{2}-1)+k_{2}(p^{4}-1).$ Hence $(p^{2}-1)\mid(|G|-k(G))$,
which indicates that $|G|=p^{a+2}.$ By [5, Theorem 3], such groups do not
exist if $p$ is odd. Hence, $p=2.$ Now it is easy to see that
$k_{1}=p^{a}-p^{r}-p^{r-2}$ and $k_{2}=p^{r-2}$.

With the above lemmas, we are prepared to provide an example for Theorem 1.1,
and it is advisable to look at $2$-groups. Let $A\cong C_{2^{3}}\times
C_{2}\times C_{2}$ be an abelian $2$-group. Then
$C(A)=\\{(1,1),(2,7),(2^{2},8),(2^{3},16)\\}.$ Since $\chi(1)<{\rm cod}\chi$
for all non-principal characters $\chi$ of $G,$ it follows that ${\rm cd}(G)$
is a subset of $\\{1,2,2^{2}\\}.$ By Lemma 2.1 and Lemma 2.2, if there is a
group $G$ so that $C(G)=C(A)$, then $|G|=2^{7}$ and ${\rm cd}(G)=\\{1,2,4\\}.$
We notice that such a group does exist. For example, using GAP, $G$ can be one
of SmallGroup$(128,755)$, SmallGroup$(128,756),$ SmallGroup$(128,773)$.

Since there is a counterexample when $A$ has three generators, we move on to
the case when $A=C_{p^{n}}\times C_{p}$, where $p$ is a prime. If $G$ is a
group satisfying that $C(G)=C(A)$, then by [11, Lemma 3.3], $G/\Phi(G)\cong
A/\Phi(A)\cong C_{p}\times C_{p},$ and hence $G$ also has two generators. We
now consider a class of two-generator groups: metacyclic groups. We give the
following result.

######  Theorem 2.3.

Let $G$ be a metacyclic group and $A=C_{p^{n}}\times C_{p}$, where $p$ is a
prime. Suppose that $C(G)=C(A).$ Then $G$ is abelian and $G\cong A.$

[Proof of Theorem 2.3] Assume that $G$ is nonabelian. Clearly $G$ is a
$p$-group and $k(G)=k(A)=p^{n+1}.$ Since $p^{2}-1\mid(|G|-k(G))$, we have that
$|G|\geqslant p^{n+3}.$ If $p$ is odd, then it follows from [7, Corollary 2.3]
that $k(G)$ is not a power of $p,$ a contradiction. Hence $p=2.$ Since
$G/\Phi(G)\cong A/\Phi(A)\cong C_{2}\times C_{2}$ and $C(G)=C(A),$
$G/G^{\prime}$ must be isomorphic to a subgroup of $A$. So we may assume that
$G/G^{\prime}\cong C_{2^{a-1}}\times C_{2},$ where $2\leqslant a\leqslant n.$
Since $C(G)=C(A)=\\{(1,1),(2,3),(2^{2},2^{2}),...,(2^{n},2^{n})\\}$ and
$C(G/G^{\prime})=\\{(1,1),(2,3),(2^{2},2^{2}),...,(2^{a-1},2^{a-1})\\},$ we
have that ${\rm cod}\chi\geqslant 2^{a}$ for any nonlinear irreducible $\chi$
of $G$.

We first claim that $|G^{\prime}|\geqslant 2^{2}$ and $a\geqslant 3.$ Let
$|G|=2^{m}.$ If $|G^{\prime}|=2,$ then $G/G^{\prime}\cong C_{2^{m-2}}\times
C_{2}$ and so there is an irreducible character $\chi$ of $G$ such that ${\rm
cod}\chi=2^{m-2}.$ Notice that $m\geqslant n+3$ and so $2^{m-2}\geqslant
2^{n+1}.$ This is impossible because the largest codegree of $G$ is $2^{n}.$
Now assume that $|G:G^{\prime}|=4.$ Notice that nonabelian $2$-groups with
$|G:G^{\prime}|=4$ have been classified (see [1, Proposition 1.6]). In
particular, the number of conjugacy classes of such groups is not a power of
$2.$ Hence $|G:G^{\prime}|>4$ and so the claim holds.

Notice that [10, Theorem 4.6] implies that $G$ has a unique minimal normal
subgroup, say $S$, in its derived group such that $G/S$ splits. Now we
consider the factor group $\overline{G}=G/S.$ Thus we may assume that
$\overline{G}=\overline{N}\cdot\overline{K}$ with
$\overline{N}\cap\overline{K}=1$, where
$\overline{N}\ThisStyle{\mathrel{\stackinset{r}{.75pt+.15\LMpt}{t}{.1\LMpt}{\rule{0.3pt}{1.1pt}}{\SavedStyle\leqslant}}}\overline{G}$
and $\overline{K}\leqslant\overline{G}.$ Clearly,
$\overline{G}^{\prime}\leqslant\overline{N}$ and
$\overline{G}/\overline{G^{\prime}}\cong G/G^{\prime}.$ Hence by the above
claim we have that $|K|>2$ and $|\overline{N}:\overline{G}^{\prime}|=2.$

Based on a Blackburn’s result [3, Lemma 2.2], we let $\overline{X}$ be the
unique maximal subgroup of $\overline{G}^{\prime}$ which is normal in
$\overline{G}.$ Consider the factor group
$\tilde{G}=\overline{G}/\overline{X}=\overline{N}/\overline{X}\cdot\overline{K}\overline{X}/\overline{X}=\tilde{N}\cdot\tilde{K}.$
Clearly, $|\tilde{G}|=2^{a+1},$ $|\tilde{G}^{\prime}|=2$ and
$\tilde{G}/\tilde{G}^{\prime}\cong G/G^{\prime}\cong C_{2^{a-1}}\times C_{2}.$
Since for any irreducible character $\chi\in{\rm Irr}(\tilde{G})$ with
$\chi(1)>1$, ${\rm cod}\chi=\frac{2^{a+1}}{\chi(1)|{\rm ker}\chi|}\geqslant
2^{a}.$ Then $\chi(1)\leqslant 2$ and ${\rm ker}\chi=1.$ This implies that
${\rm cd}(\tilde{G})=\\{1,2\\}$ and all nonlinear irreducible characters of
$\tilde{G}$ are faithful. Hence $\tilde{G}^{\prime}$ is the unique minimal
normal subgroup of $\tilde{G}.$ Since $\tilde{G}$ is a 2-group, we have that
$\Phi(\tilde{G})=\langle x^{2}\mid x\in\tilde{G}\rangle.$ Let
$x,y\in\tilde{G},$ then by the fact $|\tilde{G}^{\prime}|=2$ we have that
$1=[x,y]^{2}=[x,y^{2}]$ and so $y^{2}\in Z(\tilde{G}).$ Hence
$\Phi(\tilde{G})\leqslant Z(\tilde{G}).$ As $\tilde{G}/\Phi(\tilde{G})\cong
C_{2}\times C_{2}$ and $\tilde{G}$ is not abelian, it follows that
$\Phi(\tilde{G})=Z(\tilde{G}).$ If $\tilde{K}\cap Z(\tilde{G})>1,$ then by the
uniqueness of $\tilde{G}^{\prime}$, $\tilde{G}^{\prime}\leqslant\tilde{K}\cap
Z(\tilde{G})\leqslant\tilde{K},$ contrary to the fact
$\tilde{K}\cap\tilde{G}^{\prime}\leqslant\tilde{K}\cap\tilde{N}=1.$ Hence
$\tilde{K}\cap Z(\tilde{G})=1.$ Since
$|\tilde{G}:\tilde{K}Z(\tilde{G})|=(|\tilde{G}|/|Z(\tilde{G})|)/|\tilde{K}|\leqslant
1$ as $|\tilde{K}|=|\overline{K}|\leqslant 2^{2},$
$\tilde{G}=\tilde{K}Z(\tilde{G})$ and so
$\tilde{G}/Z(\tilde{G})\cong\tilde{K}$ is cyclic. It follows that $\tilde{G}$
is abelian. This is a contradiction.

Therefore, $G$ is abelian. Then $G\cong{\rm Irr}(G)$ and so $C(G)$ determines
the number of elements of each order. It follows that $G\cong A.$ Now the
proof is complete.

Next, we give a proof of Theorem 1.2.

[Proof of Theorem 1.2] If $G$ is abelian, then $(1)$ follows. Assume now that
$G$ is nonabelian and $G/G^{\prime}\cong C_{p^{a-1}}\times C_{p},$ where
$2\leqslant a\leqslant n.$ A proof similar to Theorem 2.3 shows that $G$ is a
$p$-group, $k(G)=k(A)=p^{n+1}$ and $|G|\geqslant p^{n+3}.$ Since $G$ is a
nonabelian $p$-group with two generators, by [3, Lemma 2.2] we can let $X$ be
the unique maximal subgroup of $G^{\prime}$ which is normal in $G.$ Consider
the factor group $\overline{G}=G/X.$ Then $|\overline{G}|=p^{a+1}$,
$\overline{G}/\overline{G}^{\prime}\cong G/G^{\prime},$ and
$\overline{G}^{\prime}=G^{\prime}/X$ has order $p.$ Notice that for any
irreducible character $\chi\in{\rm Irr}(\overline{G})$ with $\chi(1)>1$, ${\rm
cod}\chi=\frac{p^{a+1}}{\chi(1)|{\rm ker}\chi|}\geqslant p^{a}.$ Then
$\chi(1)\leqslant p$ and ${\rm ker}\chi=1.$ This implies that ${\rm
cd}(\overline{G})=\\{1,p\\}$ and all nonlinear irreducible characters are
faithful. Hence $\overline{G}^{\prime}$ is the unique minimal normal subgroup
of $\overline{G}.$

Write
$\overline{G}/\overline{G}^{\prime}=\overline{C}/\overline{G}^{\prime}\times\overline{D}/\overline{G}^{\prime},$
where $\overline{C}/\overline{G}^{\prime}\cong C_{p^{a-1}}$ and
$\overline{D}/\overline{G}^{\prime}\cong C_{p}.$ Next, we will discuss in two
cases.

Case 1: $|G:G^{\prime}|>p^{2}.$

We claim that that $G$ is metacylic. By [3, Theorem 2.3], we only need to show
that $\overline{G}$ is metacyclic. If $\Phi(\overline{C})=1,$ then
$\overline{C}$ is elementary abelian and so
$\overline{C}/\overline{G}^{\prime}\cong C_{p}$ and $a=2$, contrary to
$|G:G^{\prime}|>p^{2}.$ As $\Phi(\overline{C})$ char
$\overline{C}\ThisStyle{\mathrel{\stackinset{r}{.75pt+.15\LMpt}{t}{.1\LMpt}{\rule{0.3pt}{1.1pt}}{\SavedStyle\leqslant}}}\overline{G}$,
it follows that
$\Phi(\overline{C})\ThisStyle{\mathrel{\stackinset{r}{.75pt+.15\LMpt}{t}{.1\LMpt}{\rule{0.3pt}{1.1pt}}{\SavedStyle\leqslant}}}\overline{G}.$
Hence by the uniqueness of $\overline{G}^{\prime}$, we have that
$\overline{G}^{\prime}\leqslant\Phi(\overline{C}).$ Notice that
$(\overline{C}/\overline{G}^{\prime})/(\Phi(\overline{C})/\overline{G}^{\prime})\cong\overline{C}/\Phi(\overline{C})$
is cyclic. Then $\overline{C}$ is cyclic. Since $\overline{G}/\overline{C}$ is
cyclic, $\overline{G}$ is metacylic. Hence, the above claim holds. It follows
from Theorem 2.3 that $G$ is abelian, which is a contradiction. Hence, this
case cannot happen.

Case 2: $|G:G^{\prime}|=p^{2}.$

If $p=2,$ then $|G:G^{\prime}|=4$ and such groups have been classified. By the
equation $|G|=|G:G^{\prime}|+(k(G)-|G:G^{\prime}|)\cdot 2^{2}$, it is easy to
see that $k(G)$ is not a power of $2,$ contrary to the hypothesis $C(G)=C(A).$
Hence $p>2.$ Since $\overline{G}/\overline{G}^{\prime}\cong G/G^{\prime}\cong
C_{p}\times C_{p},$ it follows that $\overline{G}$ has order $p^{3}.$ Now we
only need to show that $\overline{G}$ has exponent $p.$ If $\overline{G}$ has
exponent $p^{2}$, then the group $\overline{C}$ defined above is cyclic of
order $p^{2}$ and hence $\overline{G}$ is metacyclic and so $G$ must be
metacylic. It follows from Theorem 2.3 that $G$ is abelian, which is a
contradiction. Hence $\overline{G}$ is of exponent $p$ and so (2) follows.

By Lemma 2.1 and Lemma 2.2, we have that if $A\cong C_{p^{3}}\times C_{p}$ and
$G$ is a group satisfying $C(G)=C(A),$ then $G\cong A.$ Theorem 1.3
immediately follows from Theorem 1.2 and a result of Blackburn. He proved that
if a $p$-group $G$ and its derived subgroup $G^{\prime}$ are generated by two
elements, then $G^{\prime}$ is abelian (see [2, Theorem 4]).

[Proof of Theorem 1.3] If $G$ is abelian, there is nothing to prove. If $G$ is
not isomorphic to $A$, then by Theorem 1.2, we have that
$|G:G^{\prime}|=p^{2}$ and $p>2.$ If $G$ has a metacyclic maximal subgroup
$M$, then $G^{\prime}\leqslant\Phi(G)$ is a subgroup of $M$ and so
$G^{\prime}$ is metacyclic, which indicates that $G^{\prime}$ is generated by
two elements. Hence by Blackburn’s result, $G^{\prime}$ is abelian. Now we
have that $G^{\prime}$ is abelian in all three cases. Notice that
$\chi(1)\mid|G:G^{\prime}|$ for all irreducible characters $\chi$ of $G.$ Then
${\rm cd}(G)$ is a subset of $\\{1,p,p^{2}\\}.$ It follows from Lemma 2.1 and
2.2 that $p=2.$ This is a contradiction. Therefore, $G\cong A,$ as desired.

## References

  * [1] B. Berkovich, Groups of Prime Power Order, Volume 1, Walter de Gruyter, Berlin, 2008
  * [2] N. Blackburn, On prime-power groups in which the derived group has two generators, Proc. Camb. Philos. Soc. 53 (1957), 19-27.
  * [3] N. Blackburn, On prime-power groups with two generators. Math. Proc. Cambridge Philos. Soc. 54(3) (1958), 327-337.
  * [4] N. Du and M. L. Lewis, Codegrees and nilpotence class of $p$-groups, J. Group Theory 19 (2016), 561–567.
  * [5] N. Gavioli, A. Mann, V. Monti, A. Previtali and C. M. Scoppola, Groups of prime power order with many conjugacy classes, J. Algebra 202 (1998), 129-141.
  * [6] C. E. Hempel, Metacyclic groups, Comm. Algebra 28(8) (2000), 3865–3897.
  * [7] L. Hethelyi and B. Kulshammer, Characters, conjugacy classes and centrally large subgroups of $p$-groups of small rank, J. Algebra 340 (2011), 199-210.
  * [8] S. P. Humphries and D. C. Skabelund, Character tables of metacyclic groups, Glasgow Math. J 57(02) (2015), 387-400.
  * [9] I. M. Isaacs, Element orders and character codegrees, Arch. Math. 97 (2011), 499–501.
  * [10] B. King, Presentations of metacyclic groups, Bull. London Math. Soc. 8(1) (1973), 103-131.
  * [11] A. Moretó, Multiplicities of character codegrees of finite groups, Bull. London Math. Soc. 55 (2023), 234-241.
  * [12] G. Qian, Element orders and codegrees, Bull. London Math. Soc. 53 (2021), 820–824.
  * [13] G. Qian, Y. Wang and H. Wei, Co-degrees of irreducible characters in finite groups, J. Algebra 312 (2007), 946-955.
  * [14] Y. Yang and G. Qian, The analog of Huppert’s conjecture on character codegrees, J. Algebra 478 (2017), 215–219.


$\textsc{Opt}\cdot\beta+\frac{24}{7}\cdot\textsc{Opt}\cdot\frac{\left(\frac{3}{4}\left(\beta-1\right)-\beta\cdot
p^{2}\cdot C_{k}\right)}{p}.$ Thus, if there exists some $p$ and $\beta$ such
that
$\beta+\frac{24}{7}\cdot\frac{\left(\frac{3}{4}\left(\beta-1\right)-\beta\cdot
p^{2}\cdot C_{k}\right)}{p}\geq\alpha$ then it is $\mathsf{PSPACE}$-hard to
approximate the optimal online algorithm for instances of the form
$\mathcal{I}_{\phi}$. Take $p=(1-\sqrt{\alpha})\cdot\frac{1}{\frac{24}{7}\cdot
C_{k}}$; this is then equivalent to
$\beta+K\cdot(\beta-1)-\beta\cdot(1-\sqrt{\alpha})\geq\alpha$ for the
universal constant $K=\frac{18}{7p}$. It suffices to take
$\beta=\frac{\alpha+K}{\sqrt{\alpha}+K}$ which is some constant smaller than
1.

##  Appendix G Generalizing to non-Bernoulli arrivals

For simplicity, our previous algorithm and analysis dealt with only the case
of “Bernoulli arrivals,” assuming that each online node $t$ arrived with some
fixed neighborhood with probability $p_{t}$, and with probability $1-p_{t}$
didn’t neighbor anyone. In this section, we show that our main edge-weighted
result (and necessary analysis) extend to the more general non-Bernoulli case.
In particular, we now assume that online node $t$ realizes _type_ $j$ with
probability $p_{j,t}$, where the type $j$ specifies weights
$\\{w_{i,j,t}\\}_{i}$ to offline nodes.

As in [PPSW21, BDL22, NSW23] we can generalize our LP relaxation as follows:

LP Relaxation for General Arrivals.

$\displaystyle\max$ $\displaystyle\sum_{(i,j)\in E}\sum_{t}w_{i,j,t}\cdot
x_{i,j,t}$ s.t. $\displaystyle\sum_{i}x_{i,j,t}\leq p_{j,t}$
$\displaystyle\text{for all }j,t$ (21) $\displaystyle 0\leq x_{i,j,t}\leq
p_{j,t}\cdot\left(1-\sum_{t^{\prime}<t}\sum_{j^{\prime}}x_{i,j^{\prime},t^{\prime}}\right)$
$\displaystyle\text{for all }i,j,t$ (22)

We consider the following algorithm. Here, we do not apply independent
discarding, and hence do not obtain negative cylinder dependence of offline
nodes. However, we do obtain an upper bound on the probability all nodes are
occupied, which suffices to apply the fractional bucketing bound, as we show
below.

Algorithm 4 Online Correlated Proposals (Generalized)

1:Input: A vector $\mathbf{x}$ satisfying (G) constraint (22)

2:$\mathcal{M}\leftarrow\emptyset,\;F_{1}\leftarrow[n]$ $\triangleright$
$\mathcal{M}$ is the output matching

3:for all times $t$ do

4: $F_{t+1}\leftarrow F_{t}$ $\triangleright$ initially, no free node $i\in
F_{t}$ is matched before time $t+1$

5: $j\leftarrow$ arrival at time $t$

6: for all offline nodes $i$ do

7:
$r_{i,j,t}\leftarrow\frac{x_{i,j,t}}{p_{j,t}\cdot\left(1-\sum_{j,t^{\prime}<t}x_{i,j,t^{\prime}}\right)}$

8: Let $\mathbf{v}_{j}$ be the vector $(r_{i,j,t})_{i\in F_{t}}$ indexed by
$i$ sorted in decreasing order of $w_{i,j,t}$

9: Let $I_{j,t}\leftarrow\textsf{PS}(F_{t},\mathbf{v}_{j})$

10: Pick some $i^{*}\in\arg\max_{i\in I_{j,t}}\\{w_{i,j,t}\\}$

11: Add $(i^{*},t)$ to the matching $\mathcal{M}$ and set $F_{t+1}\leftarrow
F_{t+1}\setminus\\{i^{*}\\}$

We first claim that this algorithm is well-defined. Indeed, by Constraint (22)
of our generalized LP we have that each $r_{i,j,t}\leq 1$, so the call to
$\textsf{PS}(\cdot,\cdot)$ in Line 9 is well-defined. Additionally, if in 11
we match an arrival of type $j$ at $t$ to $i^{*}$, we know $i^{*}$ is free at
time $t$, because it is in $I_{j,t}$.

##### Notation.

Generalizing our notation for the Bernoulli algorithm, we define
$y_{i,t}:=\sum_{t^{\prime}<t}\sum_{j}x_{i,j,t^{\prime}}$.

We now prove our upper bound on the probability a subset of offline nodes $I$
are all occupied, proceeding as in [BDL22].

######  Lemma G.1.

For any $t$ and subset of offline nodes $I$ we have

$\Pr\left[\bigwedge_{i\in I}\overline{F_{i,t}}\right]\leq\prod_{i\in
I}y_{i,t}.$

###### Proof.

We proceed by induction on $t$, with the base case being trivial. For the
inductive step, using that at most one node in $I$ is matched to $t$, we have
the following.

$\displaystyle\Pr\left[\bigwedge_{i\in I}\overline{F_{i,t+1}}\right]$
$\displaystyle\leq\Pr[F_{t}\cap I=\emptyset]+\sum_{i\in I}\Pr[F_{t}\cap
I=\\{i\\}]\cdot\sum_{j}p_{j,t}\cdot r_{i,j,t}$ Property (P1)
$\displaystyle\leq\sum_{H\subseteq I}\Pr\left[F_{t}\cap
I=H\right]\cdot\prod_{i\in H}\left(\sum_{j}\frac{x_{i,j,t}}{1-y_{i,t}}\right)$
$\displaystyle=\sum_{H\subseteq I}\Pr[F_{t}\cap I\subseteq H]\cdot\prod_{i\in
H}\left(\sum_{j}\frac{x_{i,j,t}}{1-y_{i,t}}\right)\cdot\prod_{i\in I\setminus
H}\left(1-\sum_{j}\frac{x_{i,j,t}}{1-y_{i,t}}\right)$
$\displaystyle\leq\sum_{H\subseteq I}\prod_{i\in I\setminus
H}\left[y_{i,t}\left(1-\sum_{j}\frac{x_{i,j,t}}{1-y_{i,t}}\right)\right]\prod_{i\in
H}\left(\sum_{j}\frac{x_{i,j,t}}{1-y_{i,t}}\right)$ I.H.
$\displaystyle=\prod_{i\in
I}\left(y_{i,t}\left(1-\sum_{j}\frac{x_{i,j,t}}{1-y_{i,t}}\right)+\sum_{j}\frac{x_{i,j,t}}{1-y_{i,t}}\right)$
Multi-binomial Thm $\displaystyle=\prod_{i\in I}y_{i,t}+\sum_{j}x_{i,j,t}$
$\displaystyle=\prod_{i\in I}y_{i,t+1}.$

The analysis of our algorithm for the Bernoulli case can be extended
syntactically to general distributions, by incorporating an additional index.
In particular we define an _extended type_ to be an ordered pair $(j,t)$.
Scaling as in Section 5.1 generalizes as follows.

######  Definition G.2.

For non-decreasing function $f:[0,1]\mapsto\mathbb{R}_{\geq 0}$ with
$\int_{0}^{1}f(z)\,dz=1$, define for $i,j,t$:

$\displaystyle\hat{x}_{i,j,t}$
$\displaystyle:=\int_{y_{i,t}}^{y_{i,t}+x_{i,j,t}}f(z)\,dz,$ (23)
$\displaystyle\hat{y}_{i,t}$
$\displaystyle:=\sum_{t^{\prime}<t}\sum_{j}\hat{x}_{i,j,t^{\prime}}\leq\int_{0}^{y_{i,t}}f(z)\,dz.$
(24)

Note the inequality in Equation 24 (which is an equality for the Bernoulli
problem) follows from monotonicity of $f(\cdot)$.

Again, the transformation $\mathbf{x}\mapsto\mathbf{\hat{x}}$ preserves
Constraint (22), i.e.,
$\hat{r}_{i,j,t}:=\frac{\hat{x}_{i,j,t}}{p_{t}(1-\hat{y}_{i,t})}$ is in
$[0,1]$ if $r_{i,j,t}\in[0,1]$. Non-negativity is trivial, while the upper
bound is proven in the following.

######  Claim G.3.

If $\mathbf{x}$ satisfies Constraint (22), then $\hat{x}_{i,j,t}\leq
p_{j,t}\cdot\left(1-\hat{y}_{i,t}\right)$ for all $i,j,t$.

###### Proof.

Using the definition of $\hat{x}_{i,j,t}$, monotonicity of $f(\cdot)$,
Constraint (22) and $\int_{0}^{1}f(z)\;dz=1$, and finally that
$\hat{y}_{i,j,t}\leq\int_{0}^{y_{i,t}}f(z)\;dz$, we obtain our desired bound.
(The only change compared to the proof of 5.2 is the final inequality, which
is an equality for the former proof.)

$\displaystyle\hat{x}_{i,j,t}$
$\displaystyle=\int_{y_{i,t}}^{y_{i,t}+x_{i,j,t}}f(z)\,dz\leq\frac{x_{i,j,t}}{1-y_{i,t}}\cdot\int_{y_{i,t}}^{1}f(z)\,dz\leq
p_{j,t}\cdot\left(1-\int_{0}^{y_{i,t}}f(z)\,dz\right)\leq
p_{j,t}\cdot(1-\hat{y}_{i,t}).\qed$

######  Lemma G.4.

For any fixed $w\geq 0$ define $R_{j,t,w}:=\sum_{i:w_{i,j,t}\geq
w}r_{i,j,t}\cdot F_{i,t}.$ Then, if $\mathcal{M}$ denotes the matching
produced by running Algorithm 4 on $\\{\hat{x}_{i,j,t}\\}$, we have

$\mathbb{E}[w(\mathcal{M})]\geq\sum_{j,t}p_{j,t}\cdot\int_{0}^{\infty}\mathbb{E}[\min(1,\hat{R}_{j,t,w})]\,dw.$

###### Proof.

This follows by Property (P2) of the invocation of $\mathsf{PS}(\cdot,\cdot)$
in Line 9. ∎

Thus, following Section 5, it suffices to show

$\mathbb{E}[\min(1,\hat{R}_{j,t,w})]\geq 0.678\cdot\sum_{i:w_{i,t}\geq
w}\frac{x_{i,j,t}}{p_{j,t}}.$

Now, this bound follows by a rather syntactic generalization from the analysis
of that section, provided we establish the desired bounds on
$\mathbb{E}[\min(1,X)]$ for $X$ not necessarily NCD.

It remains to note that our tail expectation bounds, i.e., our lower bound for
$\mathbb{E}[\min(1,X)]$ of Section 4, are still relevant when analyzing this
algorithm, even though the $\\{F_{i,t}\\}_{i}$ are not NCD in this
generalization. However, our upper bound on $\Pr[\wedge_{i\in
I}\overline{F_{i,t}}]\leq\prod_{i\in I}y_{i,t}$ of Lemma G.1 is still
sufficient for the (fractional) bucketing bound to hold.

######  Lemma G.5.

Let $X:=\sum_{i=1}^{n}c_{i}\cdot X_{i}$, with $c_{i}\in[0,1]$ and
$X_{i}\sim\textup{Ber}(q^{\prime}_{i})$ for all $i\in[n]$ and with
$\Pr[\bigwedge_{i\in I}\overline{X_{i}}]\leq\prod_{i\in I}(1-q_{i})$ for all
$I\subset[n]$. Then,

$\displaystyle\mathbb{E}[\min(1,X)]$ $\displaystyle\geq
1-\prod_{i}(1-c_{i}\cdot q_{i}),$ (25) $\displaystyle\mathbb{E}[\min(1,X)]$
$\displaystyle\geq
1-\left(1-(1-\theta)\cdot\Big{\\{}\frac{\mu_{S}}{1-\theta}\Big{\\}}\right)\cdot\theta^{\lfloor\frac{\mu_{S}}{1-\theta}\rfloor}\cdot\prod_{i\notin
S}\left(1-c_{i}\cdot q_{i}\right).$ (26)

###### Proof.

For Equation 25, we can directly confirm that the proof of Lemma 4.2 still
goes through in this more general setting; the only change to the proof is the
justification of (6) by the current lemma’s assumption that $\Pr[\wedge_{i\in
I}\overline{X_{i}}]\leq 1-q_{i}$. (NCD is a sufficient condition for this
condition, but is of coure not necessary for it.)

For Equation 26, we can likewise confirm that the proof of Lemma 4.8 goes
through, as the generalized pivotal sampling step of Lemma 4.6 holds
regardless of the correlations between $\\{X_{i}\\}$, after which the argument
in Equation 26 only requires an application of Equation 25, which we already
established holds for $\\{X_{i}\\}$ as in the current lemma. ∎

Finally, the proof of Lemma 5.5 can be repeated for each $j$: we split the
flow into flow from low-degree and high-degree neighbors,
$x_{L,j}:=\sum_{i:w_{i,t}\geq w,y_{i,t}\leq\theta}\frac{x_{i,j,t}}{p_{j,t}}$
and $x_{H,j}:=\sum_{i:w_{i,t}\geq w,y_{i,t}>\theta}\frac{x_{i,j,t}}{p_{j,t}}$,
and then leveraging Equation 26, we obtain that for $\varepsilon=0.11$ and
$\delta=0.18$ in the step function $f(\cdot)$ as in 5.3, our algorithm
satisfies

$\mathbb{E}[\min(1,\hat{R}_{j,t,w})]\geq 0.678\cdot\sum_{i:w_{i,t}\geq
w}\frac{x_{i,j,t}}{p_{j,t}}.$

By the same arguments as in Theorem 5.4, this then implies our result for
general distributions.

######  Theorem G.6.

Algorithm 4 with input $\hat{\mathbf{x}}$, computed as in Definitions G.2 and
5.3 (with $\varepsilon=0.11$ and $\delta=0.18$) from $\mathbf{x}$ an optimal
solution to (G), is a polynomial-time $0.678$-approximate algorithm for edge-
weighted stochastic online matching.

##  Appendix H A Truthful Mechanism for Matching Markets

In this section, we show our algorithm has implications for Bayesian mechanism
design in matching markets. Consider a setting $n$ offline items $I$ and $T$
buyers who have unit-demand valuations over these items.131313We recall a
_unit-demand valuation_ $v(\cdot)$ is one such that $v(S)=\max_{T\subseteq
S,|T|\leq 1}v(T)$. Each buyer $t\in[T]$ samples his valuation function
$v_{t}(\cdot)$ from a known distribution $\mathcal{D}_{t}$; at time $t$ we
must irrevocably decide which item to assign to $t$. Our goal is to maximize
social welfare, defined as the sum of the valuations of all agents. We refer
to this as an _online Bayesian matching market_.

Note that if the realization of each valuation is revealed to us, this is
equivalent to the setting considered earlier, and Algorithm 4 will in
polynomial-time achieve a $0.678$-approximation to the social welfare
achievable by the optimum online algorithm. In this section, we argue that
this guarantee extends to the case where buyers are strategic agents, and must
not truthfully reveal their valuation. There is an extensive line of work
studying this setting, and generalizations thereof, showing that we can
achieve a (tight) $\nicefrac{{1}}{{2}}$-approximation to the social welfare of
the allocation of optimum offline. This work is the first to explicitly study
the question against the online benchmark.

We achieve our guarantee by using an (adaptive) pricing-based mechanism, which
is easily observed to be dominant-strategy incentive-compatible (DSIC). The
prices are set via a recent result of [BHK+24], which guarantees there is no
decrease in the social welfare. We can further show that these prices are
computable efficiently.

######  Definition H.1.

A matching mechanism is _pricing-based_ if for every buyer $t$, before the
arrival of $t$ it sets a price $\pi_{i}$ for every item $i$, depending only on
the set of items remaining and $\mathcal{D}_{t}$ (not its realization). It
then queries buyer $t$ for his values $v_{t}(i)$ for each item $i\in I$,
assigns buyer $t$ the item given by $i^{*}:=\arg\max_{i\in\\{\emptyset\\}\cup
I}(v_{t}(i)-\pi_{i})$, and charges him a price of $\pi_{i^{*}}$. (We naturally
define $v_{t}(\emptyset)$ and $\pi_{\emptyset}$ to be 0.)

######  Observation H.1.

A pricing-based mechanism is DSIC.

Using [BHK+24], we will show that Algorithm 4 can be converted into one that
is pricing-based with (i) no loss in the expected social welfare and (ii)
prices that are computable in polynomial time.

######  Lemma H.2.

There exists a pricing-based mechanism $\mathcal{M}$ for online Bayesian
matching markets obtaining social welfare is at least a $0.678$-approximation
to that of the optimum online algorithm, which sees the true valuations.
Furthermore, each computation of prices by $\mathcal{M}$ can be done in
polynomial-time.

###### Proof.

We rely on [BHK+24, Theorem 4]. Our setting of an online Bayesian matching
market is a special case of their model where the _outcome space_ of each
agent is the subsets of items of size at most 1, and the _feasible outcomes_
are those that allocate each item at most once (i.e., form a matching). We
note that in our setting the arrival order of online agents is known, unlike
that considered by [BHK+24], but the difference can be handled syntactically.
By [BHK+24, Theorem 4], there hence exists a pricing-based mechanism
$\mathcal{M}$ which achieves social welfare at least that of Algorithm 4 in
expectation, and furthermore maintains the exact distribution over assigned
outcomes (i.e., the joint distribution of $\\{F_{i,t}\\}_{i}$ for each $t$ is
unchanged).

It remains to argue that the prices of $\mathcal{M}$ can be computed
efficiently. Note first that Algorithm 4 is _past-valuation-independent_ , in
the sense that its matching decision for agent $t$ depends only on the set of
free items $\\{F_{i,t}\\}_{i}$, the arriving valuation $v_{t}(\cdot)$, and the
input distributions. This means, that conditioned on a fixed realization $R$
of $\\{F_{i,t}\\}_{i}$, we can efficiently calculate the conditional
probabilities

$x_{i,t}^{R}:=\Pr[(i,t)\in\mathcal{M}\mid\\{F_{i,t}\\}_{i}=R]$

and

$x_{\emptyset}^{R}:=\Pr[t\not\in\mathcal{M}\mid\\{F_{i,t}\\}_{i}=R].$

Thus for any fixed $R$, the linear program [BHK+24, (LP1)] has at most
$|\mathcal{D}_{t}|\cdot(n+1)$ variables, and coefficients that can be computed
efficiently. Hence we can solve this LP in polynomial time. As the reduction
of [BHK+24, Theorem 4] only requires solving this LP at most $t$ times (for
each observed realization of $\\{F_{i,t}\\}_{i}$), we hence can compute all
prices used in one run of the mechanism. ∎