# Cosmological dynamics of interacting dark energy and dark matter in $f(Q)$
gravity

Gaurav N. Gadbail 0000-0003-0684-9702<EMAIL_ADDRESS>Department of
Mathematics, Birla Institute of Technology and Science-Pilani,
Hyderabad Campus, Hyderabad-500078, India. Simran Arora 0000-0003-0326-8945
<EMAIL_ADDRESS>Department of Mathematics, CDOE, Chandigarh
University, Punjab, 140413, India Phongpichit Channuie 0000-0003-4489-1207
<EMAIL_ADDRESS>College of Graduate Studies, Walailak University,
Thasala, Nakhon Si Thammarat, 80160, Thailand School of Science, Walailak
University, Thasala, Nakhon Si Thammarat, 80160, Thailand P.K. Sahoo
0000-0003-2130-8832<EMAIL_ADDRESS>Department of
Mathematics, Birla Institute of Technology and Science-Pilani,
Hyderabad Campus, Hyderabad-500078, India.

###### Abstract

In this work, we explore the behavior of interacting dark energy and dark
matter within a model of $f(Q)$ gravity, employing a standard framework of
dynamical system analysis. We consider the power-law $f(Q)$ model
incorporating with two different forms of interacting dark energy and dark
matter: $3\alpha H\rho_{m}$ and $\frac{\alpha}{3H}\rho_{m}\rho_{DE}$. The
evolution of $\Omega_{m}$, $\Omega_{r}$, $\Omega_{DE}$, $q$, and $\omega$ for
different values of the model parameter $n$ and the interaction parameter
$\alpha$ has been examined. Our results show that the universe was dominated
by matter in the early stages and will be dominated by dark energy in later
stages. Using the observational data, the fixed points are found to be stable
and can be represented the de Sitter and quintessence acceleration solutions.
We discover that the dynamical profiles of the universe in $f(Q)$ dark energy
models are influenced by both the interaction term and the relevant model
parameters.

Keywords: $f(Q)$ Gravity; Dark Energy; Dark Matter; Dynamical Analysis

##  I Introduction

Observational data has confirmed that the universe has entered a period of
accelerated expansion. This evidence comes from various independent sources,
including Supernovae Type Ia (SNe Ia) [1, 2, 3], temperature anisotropies in
the Cosmic Microwave Background (CMB) observed by WMAP [4, 5], and Baryon
Acoustic Oscillations [6, 7]. According to the framework of general relativity
(GR), this accelerated expansion is driven by a new energy density component
with negative pressure, referred to as dark energy (DE). Despite its crucial
role, little is known about DE. Understanding the origin of DE, which causes
the current cosmic acceleration, remains one of the major unresolved issues in
modern cosmology. The standard equation of state $\omega=p/\rho$, where
$\omega\geq 0$, cannot explain this phase of cosmic acceleration. Instead, an
unknown component with negative pressure, characterized by
$\omega<-\tfrac{1}{3}$, is necessary to describe the universe’s acceleration.
However, the exact nature of DE is still a mystery. Numerous attempts have
been made to address this significant problem, as discussed in Refs.[8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]. The most straightforward
candidate for dark energy is the cosmological constant, $\Lambda$. However, as
pointed out in Ref.[23], the cosmological constant is vastly smaller than what
is predicted by modern elementary particle theories. To differentiate between
the cosmological constant and other potential sources of dark energy that
change over time, researchers use dynamical models to study the evolution of
the equation of state of DE. Therefore, a mechanism must be identified to
achieve a small value of $\Lambda$ that aligns with observations.

It is well established that the pure cosmological constant cannot explain the
accelerated expansion of the early universe, as it cannot connect to the
radiation-dominated era. An alternative and compelling candidate for both dark
energy and inflation is a scalar field with a slowly varying potential. In the
realm of dark energy, numerous scalar field models have been proposed,
including quintessence [24, 25, 26, 27, 28, 29] and k-essence [30, 31, 32, 33]
scenarios. These models predict various behaviors for the equation of state of
dark energy. However, current observational data cannot distinguish these
models from the $\Lambda$-cold-dark-matter ($\Lambda$CDM) model. Moreover,
achieving viable scalar-field models within the framework of particle physics
is challenging due to the extremely small scalar mass required for present-day
cosmic acceleration [34, 35]. Another approach to explaining the universe’s
accelerated expansion involves dynamical dark energy models based on modifying
gravity over large distances. Examples of such models include $f(R)$ gravity,
where the Ricci scalar is replaced by a more general function, $f(R)$ [36, 37,
38, 39], as well as scalar-tensor theories [40, 41, 42, 43, 44, 45], Galileon
gravity [46], and Gauss-Bonnet gravity [47, 48]. For several decades,
dynamical system analysis has been used in cosmology to qualitatively study
these models, proving effective in identifying and classifying their
asymptotic behaviors [49, 50]. Recently, this framework has been applied to
investigate various dark energy models, including those based on $f(R)$
gravity [13, 51]. A series of papers [52, 54, 53, 55, 56, 57] has
systematically analyzed $f(R)$ theories, identifying models that provide
correct cosmological evolution from a vast number of possibilities. These
analyses have led to the construction of cosmologically viable $f(R)$ gravity
models, which feature appropriate trajectories in the dynamical system phase
space and are compatible with local gravity constraints [20, 21, 55]. A
notable advantage of these models is that they achieve cosmic acceleration
without requiring a dark energy component. Furthermore, these models impose
stringent constraints from local gravity tests and various observational data,
making them more rigorous compared to modified matter models.

The authors of Refs.[58, 59, 60, 61, 62] initiated and expanded the phase
space analysis of $f(R)$ gravity using the autonomous dynamical systems
approach. While there has been considerable research on dynamical systems in
$f(R)$ gravity involving non-interacting dark energy and dark matter [51], the
study of interacting dark energy within the $f(R)$ gravity framework has
received less attention, particularly in the context of dynamical system
analysis [63, 64, 65, 66, 67, 68]. Investigating interacting dark energy and
dark matter is valuable for understanding the behavior of accelerated scaling
solutions where the energy densities of dark energy ($\Omega_{DE}$) and dark
matter ($\Omega_{DM}$) are approximately equal, and the universe is
accelerating. This research could also elucidate the coupling between dark
matter structure formation and the time evolution of dark energy, potentially
explaining why dark energy dominates over dark matter in the late universe.
Additionally, the impact of interacting dark energy models on the global 21cm
signal was explored in Ref.[70], and some interacting dark energy models and
their potential to cause future singularities have been analyzed in Ref.[71].

The purpose of this work is to investigate the interaction between dark energy
and dark matter within viable models of $f(Q)$ gravity. The $f(Q)$ gravity
theory [72, 73] is one of the most promising approaches to explaining the
accelerated expansion of the universe, involving dynamical dark energy models
that modify gravity at large distances. This theory extends the alternative to
General Relativity known as the symmetric teleparallel theory, which is based
on the nonmetricity scalar $Q$, with both curvature and torsion being absent.
Geometrically, the nonmetricity $Q$ describes the variation in the length of a
vector during parallel transport. $f(Q)$ gravity presents intriguing
applications [74, 75, 76, 77, 78, 79] and easily satisfies the constraints
from gravitational wave observations [80]. At cosmological scales, $f(Q)$ can
create a gravitational interaction that reveals new and interesting patterns
in both the background evolution [72, 73, 81, 82, 83, 84] and the propagation
of scalar and tensor perturbations [73, 81, 74, 85, 86, 87]. Additionally,
certain forms of the $f(Q)$ function have been shown to mitigate the
$\sigma_{8}$ tension [88], while others provide a better fit to cosmological
data [89, 90, 91, 92, 93, 94, 95, 96, 97]. This theory is thus challenging
$\Lambda$CDM from different perspectives [98]. Furthermore, a dynamical system
analysis of both background and perturbation equations is conducted in $f(Q)$
gravity to independently verify the validity of result [87, 99, 100, 101, 102,
103, 104].

The structure of this work is organized as follows: In Section II, we present
the fundamental cosmological equations of the general $f(Q)$ theory and derive
the Friedmann equation corresponding to the FLRW metric. In Section III, we
derive the autonomous dynamical system within the framework of $f(Q)$ gravity
theory, focusing on the interaction between dark energy and dark matter. In
Section IV, we apply the power-law $f(Q)$ model to enclose the dynamical
system and conduct a further study of $f(Q)$ gravity. Finally, we discuss our
findings in Section V.

##  II Formulation of $f(Q)$ gravity theory

In this section, we briefly discuss the formulation of $f(Q)$ gravity, a
simple generalization of symmetric teleparallel gravity theory. This theory
requires a different curvature and torsion-free connection, i.e., it is wholly
dependent on nonmetricity. This formulation introduces new dynamics compared
to General Relativity (GR) by allowing the function $f(Q)$ to dictate how
nonmetricity influences the gravitational interaction. The non-metricity
tensor $Q_{\sigma\mu\nu}$ is defined as

$Q_{\sigma\mu\nu}=\nabla_{\sigma}g_{\mu\nu},$ (1)

which geometrically describes the variation of the length of a vector in the
parallel transport.
With the aid of the nonmetricity tensor, we can define the superpotential
tensor $P_{\,\,\mu\nu}^{\sigma}$ as

$4P_{\,\,\mu\nu}^{\sigma}=-Q^{\sigma}_{\,\,\,\,\mu\nu}+2Q^{\,\,\,\,\,\,\sigma}_{(\mu\,\,\,\,\nu)}-Q^{\sigma}g_{\mu\nu}-\tilde{Q}^{\sigma}g_{\mu\nu}-\delta^{\sigma}_{(\mu}\,Q\,_{\nu)},$
(2)

where $Q_{\sigma}=Q_{\sigma\,\,\,\,\mu}^{\,\,\,\,\mu}$ and
$\tilde{Q}_{\sigma}=Q^{\mu}_{\,\,\,\,\sigma\mu}\,$.
From the above quantities, we can obtain a non-metricity scalar as

$Q=-Q_{\sigma\mu\nu}P^{\sigma\mu\nu}.$ (3)

The action for $f(Q)$ gravity [72]

$S=\int\left[\frac{1}{2\kappa^{2}}f(Q)+\mathcal{L}_{m}\right]\sqrt{-g}\,d^{4}x,$
(4)

where $f(Q)$ represents any function of the scalar $Q$, $g$ denotes the
determinant of $g_{\mu\nu}$, and $\mathcal{L}_{m}$ stands for the matter
Lagrangian density.
The equations of motion in $f(Q)$ gravity are derived by varying the action
with respect to the metric and the connection. This leads to a set of modified
field equations that incorporate the effects of nonmetricity, providing a
richer structure for modeling gravitational phenomena, and it is written as

$\frac{2}{\sqrt{-g}}\nabla_{\sigma}\left(f_{Q}\sqrt{-g}\,P^{\sigma}_{\,\,\mu\nu}\right)+\frac{1}{2}f(Q)\,g_{\mu\nu}\\\
+f_{Q}\left(P_{\mu\sigma\lambda}Q_{\nu}^{\,\,\,\sigma\lambda}-2Q_{\sigma\lambda\mu}P^{\sigma\lambda}_{\,\,\,\,\,\,\nu}\right)=-T_{\mu\nu},$
(5)

where $f_{Q}=\frac{df}{dQ}$. The energy-momentum tensor for matter is now
defined as
$T_{\mu\nu}\equiv-\frac{2}{\sqrt{-g}}\frac{\delta(\sqrt{-g})\mathcal{L}_{m}}{\delta
g^{\mu\nu}}$.
To apply $f(Q)$ gravity in a cosmological context, we consider the spatially
flat Friedmann-Lemaître-Robertson-Walker (FLRW) spacetime, characterized by
the metric

$ds^{2}=-dt^{2}+a^{2}(t)\,\delta_{ij}\,dx^{i}\,dx^{j},\,\,\,\,\,\,(i,j=1,2,3),$
(6)

where $a(t)$ is the cosmological scale factor. For this metric, the
corresponding nonmetricity scalar is given by $Q=6H^{2}$, with
$H=\frac{\dot{a}}{a}$ representing the Hubble parameter and the dot denotes a
derivative with respect to the coordinate time $t$. Applying the FLRW metric
into the general field equation (5), the Friedman equations of $f(Q)$
cosmology read as

$\displaystyle 6H^{2}f_{Q}-\frac{f}{2}$ $\displaystyle=$ $\displaystyle\rho$
(7) $\displaystyle\left(12H^{2}\,f_{QQ}+f_{Q}\right)\dot{H}$ $\displaystyle=$
$\displaystyle-\frac{1}{2}(p+\rho),$ (8)

where $f_{Q}=\frac{df}{dQ}$, and $f_{QQ}=\frac{d^{2}f}{dQ^{2}}$.
To study the interaction between dark energy and dark matter, we have to
modify the conservation equations of the dark energy and the matter given
above by adding some coupling term $\mathcal{U}$ as [68]

$\displaystyle\dot{\rho}_{DE}+3H(p_{DE}+\rho_{DE})=\mathcal{U}\,,$
$\displaystyle\dot{\rho}_{m}+3H\,\rho_{m}=-\mathcal{U}\,,$
$\displaystyle\dot{\rho}_{r}+4H\,\rho_{r}=0\,.$

In addition, the coupling term $\mathcal{U}$ between dark energy and dark
matter can be interpreted as the exchange rate of energy density between these
two components. When $\mathcal{U}>0$, energy is transferred from dark matter
to dark energy, whereas when $\mathcal{U}<0$, energy is transferred from dark
energy to dark matter.

##  III Autonomous dynamical system of interacting dark energy and dark matter

In this section, we derive the autonomous dynamical system within the
framework of $f(Q)$ gravity theory, focusing on the interaction between dark
energy and dark matter. Our approach involves incorporating two interacting
terms. The first term relies solely on the energy density of the matter
sector, the Hubble parameter, and a coupling constant $\alpha$, structured
multiplicatively as $\mathcal{U}=3\alpha\,H\,\rho_{m}$. The second term
encompasses the multiplication of energy densities from both sectors,
capturing the immediate effects of both dark matter and dark energy on the
interaction term, with a dimensionless coupling constant $\alpha$, denoted as
$\mathcal{U}=\frac{\alpha}{3H}\rho_{m}\,\rho_{de}$.
According to the Friedmann equation (7), we can define the dimensionless
variable as

$x=\frac{f}{12H^{2}\,F},\,\,\,\,\,y=\frac{\rho_{r}}{6H^{2}\,F}.$ (9)

Invoking the above dimensionless variables, it is straightforward to derive
the autonomous equations which play a key role for studying the dynamical
system for the interacting dark energy and dark matter.

###  III.1 Case I : $\mathcal{U}=3\alpha\,H\,\rho_{m}$

Using Eq.(7), the autonomous dynamical system is given by

$\frac{dx}{dN}=(1-x)\frac{\dot{H}}{H^{2}}+3x-3x^{2}+xy+3\alpha\,x(1-x-y),$
(10) $\frac{dy}{dN}=-\frac{\dot{H}}{H^{2}}\,y-y+y^{2}-3xy+3\alpha\,y(1-x-y).$
(11)

where the variable $N=ln\,a$ is e-folding number and leads to
$\frac{d}{dN}=\frac{1}{H}\frac{d}{dt}$.

###  III.2 Case II : $\mathcal{U}=\frac{\alpha}{3H}\rho_{m}\,\rho_{de}$

For this particular case, the autonomous dynamical system is given by

$\frac{dx}{dN}=(1-x)\frac{\dot{H}}{H^{2}}+3x-3x^{2}+xy+\alpha\,x^{2}(1-x-y),$
(12) $\frac{dy}{dN}=-\frac{\dot{H}}{H^{2}}\,y-y+y^{2}-3xy+\alpha\,xy(1-x-y).$
(13)

where the variable $N=ln\,a$ is e-folding number and leads to
$\frac{d}{dN}=\frac{1}{H}\frac{d}{dt}$.
Furthermore, we obtain the generalized equation for $\frac{\dot{H}}{H^{2}}$ as

$\frac{\dot{H}}{H^{2}}=\frac{-3f_{Q}(1-x+\frac{y}{3})}{2Qf_{QQ}+f_{Q}}.$ (14)

Consequently, the density parameters for individual matter species can be
linked to the dimensionless variables outlined in Eq. (9). These variables
serve as a set of constraint equations:

$\Omega_{m}=1-x-y,\,\,\,\,\,\,\,\Omega_{r}=y,\,\,\,\,\,\,\,\Omega_{DE}=x.$
(15)

Finally, we define the equation of state and deceleration parameters
corresponding to the dimensionless variables to check the appropriate
acceleration expansion of the universe, that is

$\omega=-1+\frac{2f_{Q}(1-x+\frac{y}{3})}{2Qf_{QQ}+f_{Q}}$ (16)

and

$q=-1+\frac{3f_{Q}(1-x+\frac{y}{3})}{2Qf_{QQ}+f_{Q}}.$ (17)

Both $\omega$ and $q$ represent different aspects of cosmic evolution, each
uniquely influencing the large-scale structure of the universe. Grasping the
significance of these parameters is essential for studying the effects of dark
energy across various stages of cosmic evolution. Moreover, these parameters
aid in comparing and differentiating between various dark energy models, each
employing distinct mechanisms to drive cosmic acceleration.

##  IV Model:- $f(Q)=6\gamma\,H_{0}^{2}\left(\frac{Q}{Q_{0}}\right)^{n}$

In the previous section, we derived autonomous dynamical systems, and our
primary objective is to investigate and analyze them. To accomplish this goal,
we will focus on the designated power-law $f(Q)$ model, which has the form
$f(Q)=6\gamma\,H_{0}^{2}\left(\frac{Q}{Q_{0}}\right)^{n}$, where $\gamma$ and
$n$ are free model parameters.
Corresponding to our power-law $f(Q)$ model, Eq. (14) can be simplified to
obtain

$\frac{\dot{H}}{H^{2}}=-\frac{3(1-x+\frac{1}{3}y)}{2n-1}.$ (18)

Now, we will find the critical points and corresponding eigenvalues for both
the dynamical systems. Studying the critical points and assessing their
stability is crucial for a comprehensive understanding of critical aspects in
cosmic evolution driven by dark energy and dark matter interactions, as
explored within the scope of this study. The properties of the dynamical
system depend on the values of the constants $\alpha$ and $n$.

###  IV.1 For case I

The fixed points $(x,y)$ of the general dynamical system are the following:

$\displaystyle P_{1}\mathrel{\mathop{\mathchar
58\relax}}(1,0),\,\,\,\,P_{2}\mathrel{\mathop{\mathchar
58\relax}}\left(\frac{1}{2n},\frac{2n-1}{2n}\right),$ (19) $\displaystyle
P_{3}\mathrel{\mathop{\mathchar
58\relax}}\left(\frac{1}{2n+\alpha(2n-1)},0\right).$ (20)

Furthermore, the corresponding eigenvalues for each fixed point are given by

$\displaystyle P_{1}\mathrel{\mathop{\mathchar
58\relax}}\\{-4,-3(\alpha+1)\\},\,\,\,\,P_{2}\mathrel{\mathop{\mathchar
58\relax}}\\{4,1-3\alpha\\},$ (21) $\displaystyle
P_{3}\mathrel{\mathop{\mathchar 58\relax}}\\{3(\alpha+1),3\alpha-1\\}.$ (22)

Let us now focus on the dynamics of each critical point and its features in
the further subsections.

####  IV.1.1 $P_{1}$: the de Sitter fixed point

We start the discussion with the first fixed point. Here we have

$P_{1}\mathrel{\mathop{\mathchar 58\relax}}(x,y)=(1,0).$

This critical point is independent of both the model and coupling parameters.
Corresponding to this fixed point, the matter density, dark energy density,
and effective EoS parameters are

$\Omega_{m}=0,\,\,\,\,\Omega_{DE}=1,\,\,\,\,\omega=-1.$ (23)

At this point, both dark matter and radiation are absent, and the universe is
dominated by dark energy. The equation of state (EoS) at this fixed point
indicates that the universe is experiencing an accelerated expansion. To study
the stability of this fixed point, we can analyze the eigenvalues of the
Jacobian matrix, which describe the behavior of the fixed point. The
eigenvalues for the fixed point $P_{1}$ read

$\\{-4,\,\,\,-3(\alpha+1)\\}.$ (24)

The stability behavior of this fixed point (which depends on $\alpha$) is
obtained as:

  * •

Stable node for $\alpha>-1$,

  * •

Saddle for $\alpha<-1$,

  * •

Non-hyperbolic for $\alpha=-1$.

####  IV.1.2 $P_{2}$: Non-metricity dominated fixed point

Next, for the second fixed point, we have

$P_{2}\mathrel{\mathop{\mathchar
58\relax}}(x,y)=\left(\frac{1}{2n},\frac{2n-1}{2n}\right).$

The characteristics of this critical point solely depend on the model
parameter $n$. Corresponding to this fixed point, the matter density, dark
energy density, and effective EoS parameters are obtained as

$\Omega_{m}=0,\,\,\,\,\Omega_{DE}=\frac{1}{2n},\,\,\,\,\omega=-1+\frac{4}{3n}.$
(25)

The conditions for an accelerating universe are $n<0$ or $n>2$. When $n<0$,
the universe exhibits phantom-like behavior, i.e., $\omega<-1$. When $n>2$,
the universe exhibits quintessence-like behavior, i.e., $-1<\omega<-1/3$. In
this fixed-point solution, a matter-dominated era occurs for $n=4/3$ and a
radiation-dominated era for $n=1$. The eigenvalues for the fixed point $P_{2}$
are as follows:

$\\{4,\,\,\,1-3\alpha\\}.$ (26)

The stability behavior for this particular fixed point can be obtained for
different $\alpha$, given by

  * •

Saddle node for $\alpha>1/3$,

  * •

Unstable for $\alpha<1/3$,

  * •

Non-hyperbolic for $\alpha=1/3$.

####  IV.1.3 $P_{3}$: scaling solution fixed point

It is worth noting that our result modifies the scaling solution of $f(Q)$
gravity with the interacting dark energy parameter $\alpha$. The fixed point
$P_{3}$ reads

$P_{3}\mathrel{\mathop{\mathchar
58\relax}}(x,y)=\left(\frac{1}{2n+\alpha(2n-1)},0\right).$

The properties of this critical point are influenced by both the model
parameter $n$ and the coupling parameter $\alpha$. Corresponding to this fixed
point, the matter density, dark energy density, and effective EoS parameters
read as

$\Omega_{m}=\frac{1}{\alpha-2(\alpha+1)n}+1,\,\,\,\,\Omega_{DE}=\frac{1}{2n+\alpha(2n-1)},$

and

$\omega=\frac{3\alpha-2(\alpha+1)n+2}{2(\alpha+1)n-\alpha}.$

The conditions for an accelerating universe are shown in Fig. 1.

Figure 1: In this figure, we show the relationship between the model parameter
$n$ and the interacting parameter $\alpha$ for the accelerating universe. The
light blue region represents the quintessence-like behavior of an accelerating
universe (i.e., $-1<\omega<-1/3$), while the golden region represents the
phantom-like behavior of an accelerating universe (i.e., $\omega<-1$).

In this fixed point solution, we obtained a matter-dominated era for
$n=\frac{3\alpha+2}{2(\alpha+1)}$, $1+\alpha\neq 0$, and radiation-dominated
era for $n=\frac{5\alpha+3}{4(\alpha+1)}$, $1+\alpha\neq 0$.
The eigenvalues for the fixed point $P_{3}$ read as

$\\{3(\alpha+1),\,\,3\alpha-1\\}.$ (27)

We determine the stability of this fixed point for various ranges of $\alpha$.
The ranges are as follows:

  * •

Stable node for $\alpha<-1$

  * •

Saddle for $-1<\alpha<1/3$

  * •

Unstable node for $\alpha>1/3$.

In Figs. 2 and 3, we illustrate the evolution of $\Omega_{m}$, $\Omega_{r}$,
$\Omega_{DE}$, $q$, and $\omega$ for different values of the model parameter
$n$ and the interaction parameter $\alpha$. This is done using the numerical
solution of the dynamical system with the initial conditions $x(0)=0.7$ and
$y(0)=0.00005$. The motivation behind the choice of initial conditions is as
follows: $x$ represents the dark energy density, which currently has a value
of $0.7$. Similarly, $y$ represents the radiation density, which currently has
a value of $0.00005$.

Figure 2: The plot on the left displays density parameters for matter
($\Omega_{m}$), dark energy ($\Omega_{DE}$), and radiation ($\Omega_{r}$) as
functions of redshift $z$. The right panel shows the deceleration parameter
$q$ and the equation of state parameter $\omega$ as functions of redshift $z$.
These two panels illustrate the trajectory for the positive coupling
parameter, which can transfer energy from dark matter to dark energy.

Figure 3: The left panel displays density parameters for matter
($\Omega_{m}$), dark energy ($\Omega_{DE}$), and radiation ($\Omega_{r}$) as
functions of redshift $z$. The right panel shows the deceleration parameter
$q$ and the equation of state parameter $\omega$ as functions of redshift $z$.
These two panels illustrate the trajectory for the negative coupling
parameter, which can transfer energy from dark energy to dark matter.

For $n=3/2$ and $\alpha=1/2$ in Fig. 2, $\alpha>0$ indicates that the coupling
term $\mathcal{U}>0$, signifying energy transfer from dark matter to dark
energy. This figure shows that the universe was dominated by matter in the
early stages and will be dominated by dark energy in later stages. Currently,
the universe is dominated by dark energy, with parameter values
$\Omega_{m}=0.3$, $\Omega_{r}=0.00005$, and $\Omega_{DE}=0.7$, $q_{0}=-0.55$,
and $\omega_{0}=-0.70$. For these values, fixed point $P_{1}$ is stable and
represents the de Sitter acceleration solution, while fixed point $P_{2}$ is a
saddle-node, and $P_{3}$ is an unstable node that cannot demonstrate universal
acceleration.
In Fig. 3, with $n=3/2$ and $\alpha=-2$, $\alpha<0$ indicates that the
coupling term $\mathcal{U}<0$, that means energy transfers from dark energy to
dark matter. This figure shows that the universe was dominated by dark energy
in the early stages and will be dominated by dark matter at later stages.
Currently, the universe remains dominated by dark energy, with parameter
values $\Omega_{m}=0.3$, $\Omega_{r}=0.00005$, and $\Omega_{DE}=0.7$,
$q_{0}=-0.563$, and $\omega_{0}=-0.71$. Here, fixed point $P_{3}$ is stable
and exhibits acceleration for the early and present universe but fails to show
acceleration for late times, while fixed point $P_{1}$ is a saddle-node, and
$P_{2}$ is an unstable node. Fig. 4 shows the phase space trajectories of the
fixed points $P_{1}$, $P_{2}$, and $P_{3}$.

Figure 4: Phase plot of $x$ vs $y$. The upper phase plot shows the stable
behavior of $P_{1}$ for $\alpha>0$, and the lower phase plot shows the stable
behavior of $P_{3}$ for $\alpha<-1$.

###  IV.2 For case II

Next, the second case in $f(Q)$ gravity is also investigated in detail for the
interacting dark energy system. The models have been systematically
constructed with possible ranges of their model parameters derived from the
dynamical system analysis within the interacting dark energy framework. It is
important to examine how the interaction affects the cosmological viability of
the $f(Q)$ gravity models.

The fixed points $(x,y)$ of the dynamical system are the following:

$\displaystyle R_{1}\mathrel{\mathop{\mathchar
58\relax}}(1,0),\,\,\,\,R_{2}\mathrel{\mathop{\mathchar
58\relax}}\left(\frac{1}{2n},\frac{2n-1}{2n}\right),R_{3}\mathrel{\mathop{\mathchar
58\relax}}\left(\frac{1}{\alpha},\frac{-3\alpha+8n-1}{\alpha}\right),$
$\displaystyle R_{4}\mathrel{\mathop{\mathchar
58\relax}}\left(\frac{-\sqrt{-3\alpha+9n^{2}+6\alpha n}-3n}{2\alpha
n-\alpha},0\right),$ (28) $\displaystyle R_{5}\mathrel{\mathop{\mathchar
58\relax}}\left(\frac{\sqrt{-3\alpha+9n^{2}+6\alpha n}-3n}{2\alpha
n-\alpha},0\right).$

The corresponding eigenvalues are

$\displaystyle R_{1}\mathrel{\mathop{\mathchar
58\relax}}\\{-4,-3-\alpha\\},\,\,\,\,R_{2}\mathrel{\mathop{\mathchar
58\relax}}\\{4,1-\frac{\alpha}{2n}\\},$ $\displaystyle
R_{3}\mathrel{\mathop{\mathchar
58\relax}}\\{\mathcal{A}_{1}-\frac{4n}{\alpha}+4,-\mathcal{A}_{1}-\frac{4n}{\alpha}+4\\},$
$\displaystyle R_{4}\mathrel{\mathop{\mathchar
58\relax}}\left\\{\frac{5n-1+\mathcal{A}_{2}}{1-2n},\frac{-2\mathcal{A}_{2}^{2}-2(3n-\alpha+2n\alpha)\mathcal{A}_{2}}{(2n-1)^{2}\alpha}\right\\},$
$\displaystyle R_{5}\mathrel{\mathop{\mathchar
58\relax}}\left\\{\frac{-2\mathcal{A}_{2}^{2}+2(3n-\alpha+2n\alpha)\mathcal{A}_{2}}{(2n-1)^{2}\alpha},\frac{1-5n+\mathcal{A}_{2}}{2n-1}\right\\}.$

where
$\mathcal{A}_{1}=\frac{2\sqrt{(2n-1)\left(3(\alpha-1)\alpha^{2}+8n^{3}-4n^{2}-6(\alpha-1)\alpha
n\right)}}{\alpha-2\alpha n}$ and
$\mathcal{A}_{2}=\sqrt{9n^{2}-3\alpha+6n\alpha}$.

####  IV.2.1 $R_{1}$: the de Sitter fixed point

Corresponding to fixed point $R_{1}\mathrel{\mathop{\mathchar
58\relax}}(x,y)=(1,0)$, the matter density, dark energy density, and effective
EoS parameters are

$\Omega_{m}=0,\,\,\,\,\Omega_{DE}=1,\,\,\,\,\omega=-1.$ (29)

At this point, both dark matter and radiation are absent, and the universe is
dominated by dark energy. The EoS at this fixed point indicates that the
universe is experiencing an accelerated expansion. To study the stability of
this fixed point, we can analyze the eigenvalues of the Jacobian matrix, which
describe the behavior of the fixed point. The eigenvalues for the fixed point
$R_{1}$ read

$\\{{-4,\,\,\,-\alpha-3\\}}.$ (30)

The stability behavior of this fixed point is as follows:

  * •

Stable node for $\alpha>-3$,

  * •

Saddle for $\alpha<-3$,

  * •

Non-hyperbolic for $\alpha=-3$.

####  IV.2.2 $R_{2}$: Non-metricity dominated fixed point

The fixed point $R_{2}$ can be used to explain the late-time accelerating
expansion of the universe in $f(Q)$ gravity. The point is given by

$R_{2}\mathrel{\mathop{\mathchar
58\relax}}(x,y)=\left(\frac{1}{2n},\frac{2n-1}{2n}\right)$

The characteristics of this critical point solely depend on the model
parameter $n$. Corresponding to this fixed point, the matter density, dark
energy density, and effective EoS parameters are obtained as

$\Omega_{m}=0,\,\,\,\,\Omega_{DE}=\frac{1}{2n},\,\,\,\,\omega=-1+\frac{4}{3n}.$
(31)

The conditions for an accelerating universe are $n<0$ or $n>2$. When $n<0$,
the universe exhibits phantom-like behavior, i.e., $\omega<-1$. When $n>2$,
the universe exhibits quintessence-like behavior, i.e., $-1<\omega<-1/3$. In
this fixed-point solution, we have obtained a matter-dominated era for $n=4/3$
and a radiation-dominated era for $n=1$.
The corresponding eigenvalues for the fixed point $R_{2}$ are as follows:

$\\{{4,\,\,1-\frac{\alpha}{2n}\\}}.$ (32)

We determine the stability of this fixed point for various ranges of $\alpha$.
The ranges are as follows:

  * •

Saddle node for $\alpha>2n$,

  * •

Unstable for $\alpha<2n$,

  * •

Non-hyperbolic for $\alpha=2n$.

####  IV.2.3 $R_{3}$: Scaling solution point

The fixed point $R_{3}$ represents a scaling solution for the universe. This
scaling solution makes the ratio $\Omega_{m}/\Omega_{DE}$ constant. The fixed
point in this case is given by

$R_{3}\mathrel{\mathop{\mathchar
58\relax}}(x,y)=\left(\frac{1}{\alpha},\frac{-3\alpha+8n-1}{\alpha}\right).$

Corresponding to this fixed point, the matter density, dark energy density,
and effective EoS parameters read as

$\Omega_{m}=4-\frac{8n}{\alpha},\,\,\,\,\Omega_{DE}=\frac{1}{\alpha},\,\,\,\,\omega=\frac{8}{3\alpha}-1.$
(33)

The conditions for an accelerating universe are $\alpha<0$ or $\alpha>4$. When
$\alpha<0$, the universe exhibits phantom-like behavior, i.e., $\omega<-1$.
When $\alpha>4$, the universe exhibits quintessence-like behavior, i.e.,
$-1<\omega<-1/3$. In this fixed-point solution, we have obtained a matter-
dominated era for $\alpha=8/3$ and a radiation-dominated era for $\alpha=2$.
The stability conditions are shown in Fig. 5.

Figure 5: The region plot illustrates the stable, unstable, and saddle
behaviors associated with the fixed point $R_{3}$. In this plot, the stable
region is very small $\left(\frac{1}{8}<n\leq
0.4393\,\,\text{and}\,\,0<\alpha<\frac{1}{3}(8n-1)\right)$.

####  IV.2.4 $R_{4}$: Scaling solution point

The fixed point $R_{4}$ represents the scaling solution point of the universe.
In addition, it is worth noting that our result modifies the scaling solution
with the interacting dark energy parameter $\alpha$. The point $R_{4}$ is

$R_{4}\mathrel{\mathop{\mathchar
58\relax}}(x,y)=\left(\frac{-\sqrt{-3\alpha+9n^{2}+6\alpha n}-3n}{2\alpha
n-\alpha},0\right).$

Corresponding to this fixed point, the matter density, dark energy density,
and effective EoS parameters are obtained as

$\displaystyle\Omega_{m}=\frac{-\alpha+\sqrt{-3\alpha+9n^{2}+6\alpha
n}+(2\alpha+3)n}{\alpha(2n-1)}\,,$
$\displaystyle\Omega_{DE}=\frac{-\sqrt{3}\sqrt{-\alpha+3n^{2}+2\alpha
n}-3n}{2\alpha n-\alpha}\,,\,\,\text{and}$ $\displaystyle
w=\frac{-3\alpha-4\alpha n^{2}+2\sqrt{-3\alpha+9n^{2}+6\alpha
n}+(8\alpha+6)n}{\alpha(1-2n)^{2}}\,.$

One can note that all three parameters depend on the model parameter $n$ as
well as the interacting parameter $\alpha$. Check appendix A for calculations.
The conditions for an accelerating universe and the stability are shown in
Figs. 6 and 7.

Figure 6: This plot shows the relationship between the model parameter $n$ and
the interacting parameter $\alpha$ for the accelerating universe. The light
blue region represents the quintessence-like behavior of an accelerating
universe (i.e., $-1<\omega<-1/3$), while the golden region represents the
phantom-like behavior of an accelerating universe (i.e., $\omega<-1$). Figure
7: The region plot illustrates the stable, unstable, and saddle behaviors
associated with the fixed point $R_{4}$.

####  IV.2.5 $R_{5}$: Additional scaling solution point

Corresponding to the fixed point $R_{5}$, that is

$R_{5}\mathrel{\mathop{\mathchar
58\relax}}(x,y)=\left(\frac{\sqrt{3}\sqrt{-\alpha+3n^{2}+2\alpha
n}-3n}{2\alpha n-\alpha},0\right)$

the matter density, dark energy density, and effective EoS parameters are
given by

$\displaystyle\Omega_{m}=\frac{3n-\sqrt{-3\alpha+9n^{2}+6\alpha
n}}{\alpha(2n-1)}+1\,,$
$\displaystyle\Omega_{DE}=\frac{\sqrt{-3\alpha+9n^{2}+6\alpha
n}-3n}{\alpha(2n-1)}\,,\,\,$ $\displaystyle w=\frac{-3\alpha-4\alpha
n^{2}-2\sqrt{-3\alpha+9n^{2}+6\alpha n}+(8\alpha+6)n}{\alpha(1-2n)^{2}}\,.$

The conditions for an accelerating universe and the stability are depicted in
Figs. 8 and 9.

Figure 8: The plot show the relationship between the model parameter $n$ and
the interacting parameter $\alpha$ for the accelerating universe. The light
blue region represents the quintessence-like behavior of an accelerating
universe (i.e., $-1<\omega<-1/3$), while the golden region represents the
phantom-like behavior of an accelerating universe (i.e., $\omega<-1$). Figure
9: The region plot illustrates the stable, unstable, and saddle behaviors
associated with the fixed point $R_{5}$.

In Figures 10 and 11, we illustrate the evolution of $\Omega_{m}$,
$\Omega_{r}$, $\Omega_{DE}$, $q$, and $\omega$ for different values of the
model parameter $n$ and the interaction parameter $\alpha$. For $n=3/2$ and
$\alpha=4$ in Figure 10, $\alpha>0$ indicates that the coupling term
$\mathcal{U}>0$, signifying energy transfer from dark matter to dark energy.
This figure shows that the universe was dominated by matter in the early
stages and will be dominated by dark energy in later stages. Currently, the
universe is dominated by dark energy, with parameter values $\Omega_{m}=0.3$,
$\Omega_{r}=0.00005$, and $\Omega_{DE}=0.7$, $q_{0}=-0.548$, and
$\omega_{0}=-0.696$. For these values, the fixed points $R_{1}$ and $R_{4}$
are stable and represent the de Sitter and quintessence acceleration
solutions, respectively.
In Figure 11, with $n=3/2$ and $\alpha=-4$, $\alpha<0$ indicates that the
coupling term $\mathcal{U}<0$, meaning energy transfers from dark energy to
dark matter. This figure shows that the universe was dominated by dark energy
in the early stages and will be dominated by dark matter in later stages.
Currently, the universe remains dominated by dark energy, with parameter
values $\Omega_{m}=0.3$, $\Omega_{r}=0.00005$, and $\Omega_{DE}=0.7$,
$q_{0}=-0.55$, and $\omega_{0}=-0.70$. For these values, the fixed points
$R_{4}$ and $R_{5}$ have imaginary values, and the remaining point cannot
exhibit stable behavior.

Figure 10: The upper panel displays density parameters for matter
($\Omega_{m}$), dark energy ($\Omega_{DE}$), and radiation ($\Omega_{r}$) as
functions of redshift $z$. The lower panel shows the deceleration parameter
$q$ and the equation of state parameter $\omega$ as functions of redshift $z$.
These two panels illustrate the trajectory for the positive coupling
parameter, which can transfer energy from dark matter to dark energy.

Figure 11: The left panel displays density parameters for matter
($\Omega_{m}$), dark energy ($\Omega_{DE}$), and radiation ($\Omega_{r}$) as
functions of redshift $z$. The right panel shows the deceleration parameter
$q$ and the equation of state parameter $\omega$ as functions of redshift $z$.
These two panels illustrate the trajectory for the negative coupling
parameter, which can transfer energy from dark energy to dark matter.

Figure 12: Phase plot of $x$ vs $y$. The phase plot above shows the stable
behavior of $R_{1}$ and $R_{4}$ for $\alpha>0$.

##  V Conclusion

In this work, we have explored the behavior of interacting dark energy and
dark matter within $f(Q)$ gravity, employing a standard framework of dynamical
system analysis. We have considered the power-law
$f(Q)=6\gamma\,H_{0}^{2}\left(\tfrac{Q}{Q_{0}}\right)^{n}$ model incorporating
with two different forms of interacting dark energy and dark matter: $3\alpha
H\rho_{m}$ and $\frac{\alpha}{3H}\rho_{m}\rho_{DE}$. The parameter $\alpha$ in
the interacting terms plays a crucial role in determining the viable
conditions and estimating the transition from the matter-dominated era (saddle
point) to the dark energy-dominated era (stable node) in viable gravity models
at late times. As a result, we have discovered fixed points that can be
represented as the late-time accelerating universe in $f(Q)$ gravity. For the
form of ${\cal U}=3\alpha H\rho_{m}$, we have illustrated the evolution of
$\Omega_{m}$, $\Omega_{r}$, $\Omega_{DE}$, $q$, and $\omega$ for different
values of the model parameter $n$ and the interaction parameter $\alpha$. For
$n=3/2$ and $\alpha=1/2$ and $\alpha>0$, we found that the coupling term
$\mathcal{U}>0$, signifying energy transfer from dark matter to dark energy
implying that the universe was dominated by matter in the early stages and
would be dominated by dark energy in later stages. With the current data,
fixed point $P_{1}$ is stable and represents the de Sitter acceleration
solution, while fixed point $P_{2}$ is a saddle node, and $P_{3}$ is an
unstable node that cannot demonstrate universal acceleration. Moreover, we
have considered another situation of which $n=3/2$ and $\alpha=-2$,
$\alpha<0$. We discovered for the coupling term $\mathcal{U}<0$ that energy
transfers from dark energy to dark matter. In this case, the universe was
dominated by dark energy in the early stages and will be dominated by dark
matter in later stages. With the current data, fixed point $P_{3}$ is stable
and exhibits acceleration for the early and present universe but fails to show
acceleration for late times, while fixed point $P_{1}$ is a saddle node, and
$P_{2}$ is an unstable node.

For the form of ${\cal U}=\frac{\alpha}{3H}\rho_{m}\rho_{DE}$, the evolution
of $\Omega_{m}$, $\Omega_{r}$, $\Omega_{DE}$, $q$, and $\omega$ for different
values of the model parameter $n$ and the interaction parameter $\alpha$ have
been examined. We have considered $n=3/2$ and $\alpha=4$ ($\alpha>0$) and
found that the coupling term $\mathcal{U}>0$, signifying energy transfer from
dark matter to dark energy. Our results show that the universe was dominated
by matter in the early stages and would be dominated by dark energy in later
stages. Using the observational data, the fixed points $R_{1}$ and $R_{4}$
were stable and would represent the de Sitter and quintessence acceleration
solutions. Additionally, for $n=3/2$ and $\alpha=-4$ ($\alpha<0$), we found
that the coupling term $\mathcal{U}<0$, meaning energy transfers from dark
energy to dark matter implying that the universe was dominated by dark energy
in the early stages and would be dominated by dark matter in later stages.
Employing the current data, the fixed points $R_{4}$ and $R_{5}$ have
imaginary values, and the remaining point cannot exhibit stable behavior.

Although many viable $f(Q)$ models explain the dark energy problem in
cosmology, our qualitative results from this work can serve as guidelines for
more detailed studies. They can also be used as complementary constraints on
viable $f(Q)$ models, alongside other cosmological constraints on $f(Q)$
theories. Our framework, based on the cosmological dynamics of interacting
dark energy and dark matter in $f(Q)$ gravity, constitutes the natural
template for beyond the standard gravity model, for example, Teleparallel
gravity and Gauss-Bonnet gravity, or even more generalizations.

## Data Availability Statement

There are no new data associated with this article.

## Acknowledgments

GNG acknowledges University Grants Commission (UGC), New Delhi, India for
awarding a Senior Research Fellowship (UGC-Ref. No.: 201610122060). PKS
acknowledges Science and Engineering Research Board, Department of Science and
Technology, Government of India for financial support to carry out Research
project No.: CRG/2022/001847 and IUCAA, Pune, India for providing support
through the visiting Associateship program.

##  Appendix A Appendix

The conditions of stability for the fixed point $R_{3}$ are as follows:

  * •

For Stable Node:

$\displaystyle\frac{1}{8}<n\leq
0.4393\,\,\text{and}\,\,0<\alpha<\frac{1}{3}(8n-1).$ (34)

  * •

For Unstable Node:

$\displaystyle
n=0\,\,\text{and}\,\,\left(-\frac{1}{3}<\alpha<0\,\,\text{or}\,\,0<\alpha\leq
1\right),$ (35) $\displaystyle
n<0\,\,\text{and}\,\,\left(\frac{1}{3}(8n-1)<\alpha<2n\right),$ (36)
$\displaystyle
0<n\leq\frac{1}{8}\,\,\text{and}\,\,\left(\frac{1}{3}(8n-1)<\alpha<0\right),$
(37) $\displaystyle
n>\frac{1}{2}\,\,\text{and}\,\,2n<\alpha<\frac{1}{3}(8n-1).$ (38)

  * •

While the saddle point is otherwise.

The conditions of stability for the fixed point $R_{4}$ are as follows:

  * •

For Stable node:

$\displaystyle
0<n\leq\frac{1}{8}\,\,\text{and}\,\,0<\alpha<-\frac{3n^{2}}{2n-1},$ (39)
$\displaystyle\frac{1}{8}<n<\frac{1}{5}\,\,\text{and}\,\,\frac{1}{3}(8n-1)<\alpha<-\frac{3n^{2}}{2n-1},$
(40) $\displaystyle\frac{1}{2}<n\leq 1\,\,\text{and}\,\,\alpha>0,$ (41)
$\displaystyle
n>1\,\,\text{and}\,\,\left(-\frac{3n^{2}}{2n-1}<\alpha<-3\,\,\text{or}\,\,\alpha>0\right).$
(42)

  * •

For Unstable node:

$\displaystyle n\leq\frac{1}{8}\,\,\text{and}\,\,\alpha<\frac{1}{3}(8n-1),$
(43) $\displaystyle\frac{1}{8}<n<\frac{1}{2}\,\,\text{and}\,\,\alpha<0.$ (44)

  * •

While the saddle point is otherwise.

The conditions of stability for the fixed point $R_{5}$ are as follows:

  * •

For Stable node:

$\displaystyle n\leq
0\,\,\text{and}\,\,\left(\alpha<-3\,\,\text{or}\,\,0<\alpha<-\frac{3n^{2}}{2n-1}\right),$
(45) $\displaystyle 0<n<\frac{1}{2}\,\,\text{and}\,\,\alpha<-3,$ (46)
$\displaystyle\frac{1}{2}<n<1\,\,\text{and}\,\,-\frac{3n^{2}}{2n-1}<\alpha<-3.$
(47)

  * •

For Unstable node:

$\displaystyle\frac{1}{5}<n<\frac{1}{2}\,\,\text{and}\,\,\frac{1}{3}(8n-1)<\alpha<-\frac{3n^{2}}{2n-1},$
(48) $\displaystyle n>\frac{1}{2}\,\,\text{and}\,\,\alpha>\frac{1}{3}(8n-1).$
(49)

  * •

While the saddle point is otherwise.

## References

  * [1] A. G. Riess et al. [Supernova Search Team], Astron. J. 116, 1009-1038 (1998)
  * [2] A. G. Riess, R. P. Kirshner, B. P. Schmidt, S. Jha, P. Challis, P. M. Garnavich, A. A. Esin, C. Carpenter, R. Grashius and R. E. Schild, et al. Astron. J. 117, 707-724 (1999)
  * [3] S. Perlmutter et al. [Supernova Cosmology Project], Astrophys. J. 517, 565-586 (1999)
  * [4] D. N. Spergel et al. [WMAP], Astrophys. J. Suppl. 148, 175-194 (2003)
  * [5] E. Komatsu et al. [WMAP], Astrophys. J. Suppl. 192, 18 (2011)
  * [6] D. J. Eisenstein et al. [SDSS], Astrophys. J. 633, 560-574 (2005)
  * [7] W. J. Percival et al. [SDSS], Mon. Not. Roy. Astron. Soc. 401, 2148-2168 (2010)
  * [8] V. Sahni and A. A. Starobinsky, Int. J. Mod. Phys. D 9, 373 (2000).
  * [9] S. M. Carroll, Living Rev. Rel. 4, 1 (2001).
  * [10] T. Padmanabhan, Phys. Rept. 380, 235 (2003).
  * [11] P. J. E. Peebles and B. Ratra, Rev. Mod. Phys. 75, 559 (2003).
  * [12] V. Sahni, Lect. Notes Phys. 653, 141 (2004).
  * [13] E. J. Copeland, M. Sami and S. Tsujikawa, Int. J. Mod. Phys. D 15, 1753 (2006).
  * [14] S. Nojiri and S. D. Odintsov, eConf C0602061, 06 (2006) [Int. J. Geom. Meth. Mod. Phys. 4, 115 (2007)].
  * [15] R. P. Woodard, Lect. Notes Phys. 720, 403 (2007).
  * [16] R. Durrer and R. Maartens, Gen. Rel. Grav. 40, 301 (2008).
  * [17] F. S. N. Lobo, arXiv:0807.1640 [gr-qc].
  * [18] T. P. Sotiriou and V. Faraoni, Rev. Mod. Phys. 82, 451 (2010).
  * [19] P. Brax, arXiv:0912.3610 [astro-ph.CO].
  * [20] A. De Felice and S. Tsujikawa, Living Rev. Rel. 13, 3 (2010).
  * [21] S. Tsujikawa, arXiv:1004.1493 [astro-ph.CO] (Published in ’Dark Matter and Dark Energy: A Challenge for Modern Cosmology’ Series: Astrophysics and Space Science Library, Vol. 370, ISBN: 978-90-481-8684-6, 2011).
  * [22] S. Nojiri and S. D. Odintsov, Phys. Rept. 505 (2011), 59-144 [arXiv:1011.0544 [gr-qc]].
  * [23] S. Weinberg, Rev. Mod. Phys. 61 (1989), 1-23
  * [24] Y. Fujii, Phys. Rev. D 26, 2580 (1982).
  * [25] L. H. Ford, Phys. Rev. D 35, 2339 (1987).
  * [26] C. Wetterich, Nucl. Phys B. 302, 668 (1988).
  * [27] B. Ratra and J. Peebles, Phys. Rev D 37, 321 (1988).
  * [28] R. R. Caldwell, R. Dave and P. J. Steinhardt, Phys. Rev. Lett. 80, 1582 (1998).
  * [29] G. R. Dvali and M. Zaldarriaga, Phys. Rev. Lett. 88 (2002), 091303
  * [30] T. Chiba, T. Okabe and M. Yamaguchi, Phys. Rev. D 62, 023511 (2000).
  * [31] C. Armendariz-Picon, V. F. Mukhanov and P. J. Steinhardt, Phys. Rev. Lett. 85, 4438 (2000).
  * [32] S. X. Tian and Z. H. Zhu, Phys. Rev. D 103 (2021) no.4, 043518
  * [33] S. D. Odintsov, V. K. Oikonomou and F. P. Fronimos, Phys. Dark Univ. 29 (2020), 100563
  * [34] S. M. Carroll, Phys. Rev. Lett. 81, 3067 (1998).
  * [35] C. F. Kolda and D. H. Lyth, Phys. Lett. B 458, 197 (1999).
  * [36] S. Capozziello, Int. J. Mod. Phys. D 11, 483, (2002).
  * [37] S. Capozziello, V. F. Cardone, S. Carloni and A. Troisi, Int. J. Mod. Phys. D, 12, 1969 (2003).
  * [38] S. M. Carroll, V. Duvvuri, M. Trodden and M. S. Turner, Phys. Rev. D 70, 043528 (2004).
  * [39] S. Nojiri and S. D. Odintsov, Phys. Rev. D 68, 123512 (2003).
  * [40] L. Amendola, Phys. Rev. D 60, 043501 (1999).
  * [41] J. P. Uzan, Phys. Rev. D 59, 123510 (1999).
  * [42] T. Chiba, Phys. Rev. D 60, 083508 (1999).
  * [43] N. Bartolo and M. Pietroni, Phys. Rev. D 61 023518 (2000).
  * [44] F. Perrotta, C. Baccigalupi and S. Matarrese, Phys. Rev. D 61, 023507 (2000).
  * [45] A. Riazuelo and J. P. Uzan, Phys. Rev. D 66, 023525 (2002).
  * [46] A. Nicolis, R. Rattazzi and E. Trincherini, Phys. Rev. D 79, 064036 (2009).
  * [47] S. Nojiri, S. D. Odintsov and M. Sasaki, Phys. Rev. D 71, 123509 (2005).
  * [48] S. Nojiri and S. D. Odintsov, Phys. Lett. B 631, 1 (2005).
  * [49] J. Wainwright and G. F. R. Ellis, Dynamical Systems in Cosmology, Cambridge University Press (1997).
  * [50] A. A. Coley, Dynamical systems and cosmology, Kluwer Academic Publishers (2003).
  * [51] S. Bahamonde, C. G. Böhmer, S. Carloni, E. J. Copeland, W. Fang and N. Tamanini, Phys. Rept. 775-777 (2018), 1-122 [arXiv:1712.03107 [gr-qc]].
  * [52] L. Amendola, D. Polarski and S. Tsujikawa, Phys. Rev. Lett. 98 (2007), 131302 [arXiv:astro-ph/0603703 [astro-ph]].
  * [53] L. Amendola, D. Polarski and S. Tsujikawa, Int. J. Mod. Phys. D 16 (2007), 1555-1561 doi:10.1142/S0218271807010936 [arXiv:astro-ph/0605384 [astro-ph]].
  * [54] L. Amendola, R. Gannouji, D. Polarski and S. Tsujikawa, Phys. Rev. D 75, 083504 (2007) [arXiv:gr-qc/0612180 [gr-qc]].
  * [55] S. Tsujikawa, Lect. Notes Phys. 800, 99-145 (2010) [arXiv:1101.0191 [gr-qc]].
  * [56] L. Amendola and S. Tsujikawa, Phys. Lett. B 660 (2008), 125-132 [arXiv:0705.0396 [astro-ph]].
  * [57] S. Tsujikawa, Phys. Rev. D 77 (2008), 023507 [arXiv:0709.1391 [astro-ph]].
  * [58] S. D. Odintsov and V. K. Oikonomou, Phys. Rev. D 96 (2017) no.10, 104049
  * [59] V. K. Oikonomou, Phys. Rev. D 99 (2019) no.10, 104042
  * [60] N. Chatzarakis and V. K. Oikonomou, Annals Phys. 419 (2020), 168216
  * [61] V. K. Oikonomou, Int. J. Mod. Phys. D 27 (2018) no.05, 1850059
  * [62] S. D. Odintsov and V. K. Oikonomou, Phys. Rev. D 99 (2019) no.10, 104070
  * [63] N. J. Poplawski, Phys. Rev. D 74 (2006), 084032 [arXiv:gr-qc/0607124 [gr-qc]].
  * [64] N. J. Poplawski, [arXiv:gr-qc/0608031 [gr-qc]].
  * [65] J. H. He, B. Wang and E. Abdalla, Phys. Rev. D 84 (2011), 123526 [arXiv:1109.1730 [gr-qc]].
  * [66] J. H. He and B. Wang, Int. J. Mod. Phys. A 30 (2015) no.28&29, 1545012
  * [67] B. L’Huillier, H. A. Winther, D. F. Mota, C. Park and J. Kim, Mon. Not. Roy. Astron. Soc. 468 (2017) no.3, 3174-3183 [arXiv:1703.07357 [astro-ph.CO]].
  * [68] D. Samart, B. Silasan and P. Channuie, Phys. Rev. D 104, no.6, 063517 (2021)
  * [69] S. D. Odintsov and V. K. Oikonomou, Phys. Rev. D 98 (2018) no.2, 024013 [arXiv:1806.07295 [gr-qc]].
  * [70] A. Halder and M. Pandey, [arXiv:2101.05228 [astro-ph.CO]].
  * [71] J. Beltrán Jiménez, D. Rubiera-Garcia, D. Sáez-Gómez and V. Salzano, Phys. Rev. D 94 (2016) no.12, 123520
  * [72] J. B. Jimenez et al., Phys. Rev. D 98, 044048 (2018).
  * [73] J. B. Jimenez et al., Phys. Rev. D 101, 103507 (2020).
  * [74] N. Frusciante, Phys. Rev. D 103, 044021 (2021).
  * [75] K. F. Dialektopoulos, T. S. Koivisto and S. Capozziello, Eur. Phys. J. C 79(7), 606 (2019).
  * [76] K. Flathmann and M. Hohmann, Phys. Rev. D 103, 044030 (2021).
  * [77] I. Ayuso, R. Lazkoz and V. Salzano, Phys. Rev. D 103, 063505 (2021).
  * [78] B. J. Barros, T. Barreiro, T. Koivisto and N. J. Nunes, Phys. Dark Univ. 30, 100616 (2020).
  * [79] F. Bajardi, D. Vernieri and S. Capozziello, Eur. Phys. J. Plus 135, 912 (2020).
  * [80] I. Soudi et al., Phys. Rev. D 100, 044008 (2019).
  * [81] J.B. Jimenez, L. Heisenberg, and T. S. Koivisto, Universe 5, 173 (2019).
  * [82] T. Harko et al., Phys. Rev. D 98, 084043 (2018).
  * [83] Y. Xu, G. Li, T. Harko, and S.D. Liang, Eur. Phys. J. C 79, 708 (2019).
  * [84] L. Jarv, M. Runkla, M. Saal, and O. Vilson, Phys. Rev. D 97, 124025 (2018).
  * [85] R. Lazkoz et al., Phys. Rev. D 100, 104027 (2019).
  * [86] I. Ayuso, R. Lazkoz, and V. Salzano, Phys. Rev. D 103, 063505 (2021).
  * [87] W. Khyllep, A. Paliathanasis and J. Dutta, Phys. Rev. D 103, 103521 (2021).
  * [88] Bruno J. Barros et al., Phys. Dark Univ. 30, 100616 (2020).
  * [89] F. K. Anagnostopoulos, S. Basilakos, and E. N. Saridakis, Phys. Lett. B 822, 136634 (2021).
  * [90] S. Mandal, P. K. Sahoo, Phys. Lett. B 823, 136786 (2021).
  * [91] L. Atayde, N. Frusciante, Phys. Rev. D 104, 064052 (2021).
  * [92] I. Soudi et al., Phys. Rev. D 100, 9044008 (2019).
  * [93] Ruth Lazkoz et al., Phys. Rev. D 100, 104027 (2019).
  * [94] I. Ayuso, R. Lazkoz, and V. Salzano, Phys. Rev. D 103, 063505 (2021).
  * [95] N. Frusciante, Phys. Rev. D 103, 044021 (2021).
  * [96] F. A. Anagnostopoulos et al., Eur. Phys. J. C 83, 58 (2023).
  * [97] O. Sokoliuk et al., Mon. Not. Roy. Astron. Soc. 522, 252–267 (2023).
  * [98] Gaurav N Gadbail, S. Mandal, P.K. Sahoo, Phys. Lett. B, 835, 137509 (2022).
  * [99] Jianbo Lua, Xin Zhao, and Guoying Chee, Eur. Phys. J. C 79, 530 (2019).
  * [100] W. Khyllep et al., Phys. Rev. D 107, 044022 (2023).
  * [101] A. Paliathanasis, Phys. Dark Univ. 41, 101255 (2023).
  * [102] S.A. Narawade, S. P. Singh, and B. Mishra, Phys. Dark Univ. 42, 101282 (2023).
  * [103] C. Bohmer, E. Jensko 1 and R. Lazkoz, Universe 9, 166 (2023).
  * [104] S. Ghosh, R. Solanki, and P.K. Sahoo, Phys. Scr. 99, 055021 (2024).


UGC

# An approximation algorithm for Maximum DiCut vs. Cut††thanks: This work was
supported by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. For the
purpose of Open Access, the authors have applied a CC BY public copyright
licence to any Author Accepted Manuscript version arising from this
submission. All data is provided in full in the results section of this paper.

Tamio-Vesa Nakajima
University of Oxford
<EMAIL_ADDRESS>Stanislav Živný
University of Oxford
<EMAIL_ADDRESS>
(28th August 2024)

###### Abstract

Goemans and Williamson designed a 0.878-approximation algorithm for Max-Cut in
undirected graphs [JACM’95]. Khot, Kindler, Mosel, and O’Donnel showed that
the approximation ratio of the Goemans-Williamson algorithm is optimal
assuming Khot’s Unique Games Conjecture [SICOMP’07]. In the problem of maximum
cuts in _directed_ graphs (Max-DiCut), in which we seek as many edges going
from one particular side of the cut to the other, the situation is more
complicated but the recent work of Brakensiek, Huang, Potechin, and Zwick
showed that their 0.874-approximation algorithm is tight under the Unique
Games Conjecture (up to a small delta) [FOCS’23].

We consider a promise version of the problem and design an SDP-based algorithm
which, if given a directed graph $G$ that has a directed cut of value $\rho$,
finds an undirected cut in $G$ (ignoring edge directions) with value at least
$\rho$.

##  1 Introduction

The maximum cut problem in _undirected_ graphs (Max-Cut) is a fundamental
problem, seeking a partition of the vertex set into two parts while maximising
the number of edges going across. While Max-Cut is -complete [Kar72], a random
assignment leads to a $1/2$-approximation algorithm. In their influential
work, Goemans and Williamson gave the first improvement and presented an SDP-
based $\alpha_{\text{GW}}$-approximation algorithm [GW95], where
$\alpha_{\text{GW}}\approx 0.878$. Under Khot’s Unique Games Conjecture ()
[Kho02], this approximation factor is optimal [KKMO07, MOO10]. The currently
best known inapproximability result not relying on is $16/17\approx 0.941$
[TSSW00] (obtained by a gadget from Håstad’s optimal inapproximability result
[Hås01]).

The maximum cut problem in _directed_ graphs (Max-DiCut) is a closely related
and well-studied -complete problem, seeking a partition of the vertex set into
two parts while maximising the number of edges going across in the prescribed
direction. A random assignment leads to a $1/4$-approximation algorithm. In
the first improvement over the random assignment, Goemans and Williamson
presented an SDP-based $0.796$-approximation algorithm [GW95]. By considering
a stronger SDP formulation (with triangle inequalities), Feige and Goemans
later presented an $0.859$-approximation algorithm for Max-DiCut [FG95],
building on the work of Feige and Lovász [FL92]. Follow-up works by Matuura
and Matsui [MM03] and by Lewin, Livnat, and Zwick [LLZ02] further improved the
approximation factor. On the hardness side, the best inapproximability factor
under -hardness is $12/13\approx 0.923$ [TSSW00] (again, via a gadget from a
result in [Hås01]). In recent work, Brakensiek, Huang, Potechin, and Zwick
gave an $0.874$-approximation algorithm for Max-DiCut, also showing that the
approximation factor is -optimal (up to a small delta) [BHPZ23].

### Contributions

Our main contribution is an SDP-based algorithm for Max-DiCut-vs.-Cut. This
algorithm achieves the best possible performance on the problem: given a
directed graph $G$ that has a directed cut of value $\rho$, it finds a cut in
$G$ (ignoring directions) of value at least $\rho$.111No better approximation
ratio than $1$ is possible. For example, given a directed graph $G$ with a
directed cut of value $2/3$, it is not possible to find a cut of value greater
than $2/3$ in general, since we might get the input graph $([5],\\{1\to 2,3\to
4,5\to 5\\})$, which doesn’t have such a cut.

For the following, we define $\operatorname{\textsc{DiCut}}(G)$ to be the
maximum value of any directed cut in $G$, and $\operatorname{\textsc{Cut}}(c)$
to be the value of a cut $c$ of $G$. (These and other notations will be
defined fully in Section 2.) We prove our result in two steps. First we
provide a randomised algorithm.

######  Theorem 1.

There is a randomised algorithm which, if given a directed graph $G$ and
$\varepsilon\in(0,1)$, finds a cut $c$ in $G$ with expected value at least
$\operatorname{\textsc{DiCut}}(G)-\varepsilon$ in polynomial time in $|G|$ and
$\log(1/\varepsilon)$.

Second, we derandomise the algorithm from Theorem 1.

######  Theorem 2.

There is a deterministic algorithm which, if given a directed graph $G$, finds
a cut $c$ of $G$ with
$\operatorname{\textsc{Cut}}(c)\geq\operatorname{\textsc{DiCut}}(G)$ in
polynomial time in $|G|$.

We note that the guarantee of the algorithm from Theorem 2 does not have an
$\varepsilon$ and is exact. Indeed, as the value of a cut is a number of the
form $k/|E(G)|$, this can be achieved by setting the error parameter in
Theorem 1 small enough.

Our algorithm in Theorem 2 uses a $\mathcal{THRESH}$ rounding scheme (indeed,
our rounding scheme, as we shall discuss later, can be seen as a distribution
of $\mathcal{ROT}$ rounding schemes — these are a subfamily of the
$\mathcal{THRESH}$ family). The $\mathcal{THRESH}$ rounding scheme was
introduced in [LLZ02], whereas the $\mathcal{ROT}$ rounding scheme was first
introduced in [FG95], but named in [LLZ02]. They have been used ever since
then; for instance, recently to create an (almost) optimal algorithm for Max-
DiCut [BHPZ23]. That we use such a rounding scheme is not surprising: it is
known by a slight generalisation of [Aus10] established in [BHPZ23] that,
assuming and Austrin’s _positivity conjecture_ [Aus10, Conjecture 1.3], the
optimal algorithm for approximately solving _any_ Boolean 2-CSP uses such a
rounding scheme; and this result can be easily extended to promise CSPs. The
challenge is specifying precisely _which_ rounding scheme in the
$\mathcal{THRESH}$ family to use: each member of this family is specified by
an enormous amount of information. This family of rounding schemes is
extremely vast, including the state-of-the-art algorithms for, e.g., Max-Cut
[GW95], Max-DiCut [BHPZ23], Max-2Sat [LLZ02] and Max-2And [BHPZ23]. We remark
that, whereas many of the algorithms using such a rounding scheme have a
numerical flavour [LLZ02, BHPZ23], i.e., their rounding scheme is often given
by a distribution over a set of functions that linearly interpolate some
points, our algorithm has a more analytic flavour. We also find it more
natural and self-contained to explain the rounding scheme by itself, rather
than as an instance of the $\mathcal{THRESH}$ family; thus we will take this
direct, self-contained approach.

We now give a brief, informal overview of our algorithm from Theorem 1. Given
a directed graph $G=(V,E)$ with a directed cut of value $\rho$, we will try to
place each vertex $u\in V$ at a point $\mathbf{x}_{u}\in\mathbb{R}^{N}$, for
some large enough $N$, such that $||\mathbf{x}_{u}||_{2}^{2}=1$. In
$\mathbb{R}^{N}$ we select a distinguished direction, given by a unit vector
$\mathbf{x}_{0}$. We will place these points so as to maximise an objective
function that is a sum, over $(u,v)\in E$, of a linear combination between
$||\mathbf{x}_{u}-\mathbf{x}_{v}||_{2}^{2}=2-\mathbf{x}_{u}\cdot\mathbf{x}_{v}$
and $\mathbf{x}_{0}(\mathbf{x}_{v}-\mathbf{x}_{u})$; in addition the placement
must satisfy some extra constraints known as the “triangle inequalities”. This
the standard SDP relaxation of the problem with triangle inequalities. The
main novelty comes from our rounding procedure and its proof of correctness:
if a vertex $u$ has $|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$ large, then we round
it to $\operatorname{sgn}(\mathbf{x}_{u}\cdot\mathbf{x}_{0})$; whereas if it
has $|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$ small, we round it according to the
sides of a uniformly random hyperplane (as in the Goemans-Williamson rounding
[GW95]).

The justification for this idea is the following. The vector $\mathbf{x}_{0}$
represents the value $+1$ in our SDP. Thus, if $\mathbf{x}_{u}$ is very close
to $\mathbf{x}_{0}$ or $-\mathbf{x}_{0}$ i.e., if
$|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$ is large, then we ought to prioritise
the $\mathbf{x}_{0}$ component in $\mathbf{x}_{u}$ and round according to
$\operatorname{sgn}(\mathbf{x}_{u}\cdot\mathbf{x}_{0})$. Conversely, consider
an edge $(u,v)$ where $|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$ and
$|\mathbf{x}_{v}\cdot\mathbf{x}_{0}|$ are both small. Then the contribution of
$\mathbf{x}_{0}(\mathbf{x}_{v}-\mathbf{x}_{u})$ to the objective will likewise
be small, and we care more about the contribution of
$||\mathbf{x}_{u}-\mathbf{x}_{v}||_{2}^{2}$. But this is precisely the
contribution given by the vectors in the SDP relaxation for Max-Cut; we
intuitively want, therefore, to round as dictated by the best known algorithm
[GW95], i.e., to round according to a random hyperplane. In the case where we
mix the sizes of $|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$ and
$|\mathbf{x}_{v}\cdot\mathbf{x}_{0}|$, it can be seen that the contribution of
the edge to the objective is approximately $1/2$. Also, the probability of
properly cutting the edge is $1/2$. We have not specified the meaning of
“large” or “small” in this description: it turns out to be sufficient to
simply select the threshold between “large” and “small” values uniformly at
random in $[0,1]$!

To help visualise this algorithm, we briefly explain it as a distribution of
$\mathcal{ROT}$ rounding schemes. In such a rounding scheme, one specifies a
_rotation function_ $f:[0,\pi]\to[0,\pi]$, and then considers every vector
$\mathbf{x}_{u}$. One then rotates $\mathbf{x}_{u}$ to
$\mathbf{x}_{u}^{\prime}$ within the plane spanned by $\mathbf{x}_{u}$ and
$\mathbf{x}_{0}$ so that
$\arccos(\mathbf{x}_{u}^{\prime}\cdot\mathbf{x}_{0})=f(\arccos(\mathbf{x}_{u}^{\prime}\cdot\mathbf{x}_{0}))$,
and finally rounds according to the sides of a random hyperplane. Our rounding
scheme defines $f_{a}:[0,\pi]\to[0,\pi]$ as in Fig. 1, selects $a$ uniformly
at random in $[0,1]$, then rounds according to the $\mathcal{ROT}$ family of
rounding schemes with rotation function $f_{a}$. By analysing this rounding
scheme carefully, we then determine that it has the advertised performance. We
contain the key required bound of this analysis within Lemma 5, stated and
proved in Section 4.

Figure 1: Rotation function $f_{a}$$\arccos a$$\pi-\arccos
a$$\pi$$\pi/2$$\pi$$x$$f_{a}(x)$

We finish with mentioning a related (and in some sense dual) problem, which we
call the Cut-Orient problem. Suppose we are given an undirected graph $G$
which has a maximum cut of value $\rho$. The problem asks us to orient the
edges of $G$ so that the resulting oriented graph has a directed cut of as
large a value as possible. Observe that this problem has a simple algorithm
which produces an oriented graph with a directed cut of size
$\alpha_{\text{GW}}\rho$: find a cut in $G$ of size $\alpha_{\text{GW}}\rho$
using the Goemans-Williamson algorithm, then orient the edges according to
that cut. Our deterministic algorithm for Max-DiCut-vs.-Cut shows that,
assuming , nothing better is possible as our algorithm reduces Max-Cut to Cut-
Orient.

### Related work

Max-Cut is one of the simplest examples of a Constraint Satisfaction Problems
(CSPs) [KSTW00]. A celebrated result of Raghavendra showed that the basic SDP
relaxation gives an optimal approximation algorithm to every CSP (assuming )
[Rag08]. While a breakthrough result, there are some caveats as as already
discusses earlier in this Introduction and also discussed in more detail,
e.g., in [MM17, BHPZ23]. In particular, the universal rounding scheme of
Raghavendra can only go arbitrarily close to the integrality gap (in
polynomial time), not match it exactly — thus it would only be able to have an
approximation ratio of $1-\varepsilon$ for any fixed $\varepsilon$, not
exactly 1 as in our algorithm here. The exact performance of this rounding
scheme is also nontrivial to find e.g. separating the optimal approximation
ratio for Max-Cut and Max-DiCut was only recently shown in [BHPZ23]. Indeed,
the algorithm of Raghavendra and Steurer [RS09] computes a gap instance for an
SDP to error $\varepsilon$ in _doubly exponential time in
$\poly(1/\varepsilon)$_.

The studied Max-DiCut-vs.-Cut problem falls within the framework of so-called
valued promise CSPs, recently investigated systematically by Barto et al.
[BBK+24]. Another valued promise CSP recently studied is the Max-$k$-Col-
vs.-$\ell$-Col problem [NŽ23], in which one seeks an $\ell$-colouring of a
given graph $G$ with as many edges coloured properly as possible given that a
$k$-colouring of $G$ exists with many edges coloured properly.

##  2 Preliminaries

### Notation

We use the Iverson bracket $[\phi]$, which is 1 when $\phi$ is true and 0
otherwise. We write $[n]=\\{1,\ldots,n\\}$. Whenever we write an expectation
such as $\operatorname*{\mathbb{E}}_{x\in X}[f(x)]$, we implicitly mean that
$x$ is uniformly distributed in $X$.

We shall use two trigonometric functions: the cosecant function, defined by
$\csc(x)=1/\sin(x)$, and its inverse, denoted by $\operatorname{arccsc}$.
Recall that $\operatorname{arccsc}$ is decreasing and, for $x\geq 1$, we have
$0<\operatorname{arccsc}(x)\leq\pi/2$.

A _hyperplane_ is a function $H:\mathbb{R}^{n}\to\\{-1,0,1\\}$ of the form
$H(\mathbf{x})=\operatorname{sgn}(\mathbf{x}\cdot\mathbf{a})$. A _uniformly
random_ hyperplane is one in which $\mathbf{a}$ is selected from a
rotationally symmetric distribution uniformly at random e.g. from the standard
multivariate normal distribution. It is well known (cf. [GW95]) that
$\Pr_{H}[H(\mathbf{x})\neq
H(\mathbf{y})]=(1/\pi)\arccos(\mathbf{x}\cdot\mathbf{y})$ and that
$\Pr_{H}[H(\mathbf{x})=0]=0$. It is not difficult to see that this is the case
even if we condition that, for some fixed vector $\mathbf{x}_{0}$, we have
$H(\mathbf{x}_{0})=1$ (this just standardises which side of $H$ is $+1$ and
which is $-1$).

For a vector $\mathbf{x}\in\mathbb{R}^{N}$, we let
$\langle\mathbf{x}\rangle\subseteq\mathbb{R}^{N}$ denote the subspace spanned
by $\mathbf{x}$. For a linear subspace $S\subseteq\mathbb{R}^{N}$, we let
$S^{\perp}$ denote the subspace of vectors perpendicular to $S$.

### Problem definitions

Consider a directed graph $G=(V,E)$. A _cut_ in $G$ is a partition of $V$ into
two parts $A,B$. The _undirected value_ of this cut is $|(A\times B\cup
B\times A)\cap E|/|E|$. The _directed value_ of the cut is $|(A\times B)\cap
E|/|E|$. In other words, the directed value of a cut is the proportion of
edges from $A$ to $B$, and the undirected value of a cut is the proportion of
edges between $A$ and $B$ ignoring orientation.

While these definitions are the most natural, it will be more convenient (and
is standard in the literature) to work with the following equivalent ones
instead. We define, for $x,y\in\mathbb{R}$,

$\displaystyle\operatorname{\textsc{Cut}}(x,y)$
$\displaystyle=\frac{1-xy}{2},$
$\displaystyle\operatorname{\textsc{DiCut}}(x,y)$
$\displaystyle=\frac{1-xy+y-x}{4}.$

For a graph $G=(V,E)$, a cut is a function $c:V\to\\{\pm 1\\}$. The undirected
value of $c$ is

$\operatorname{\textsc{Cut}}(c)=\operatorname*{\mathbb{E}}_{(u,v)\in
E}[\operatorname{\textsc{Cut}}(c(u),c(v))]=\frac{1}{2}\operatorname*{\mathbb{E}}_{(u,v)\in
E}[1-c(u)c(v)].$

The directed value of $c$ is

$\operatorname{\textsc{DiCut}}(c)=\operatorname*{\mathbb{E}}_{(u,v)\in
E}[\operatorname{\textsc{DiCut}}(c(u),c(v))]=\frac{1}{4}\operatorname*{\mathbb{E}}_{(u,v)\in
E}[1-c(u)c(v)+c(v)-c(u)].$

Now, we define the (directed/undirected) value of a directed graph $G$ as
follows

$\displaystyle\operatorname{\textsc{Cut}}(G)$
$\displaystyle=\max_{c:V\to\\{\pm 1\\}}\operatorname{\textsc{Cut}}(c).$
$\displaystyle\operatorname{\textsc{DiCut}}(G)$
$\displaystyle=\max_{c:V\to\\{\pm 1\\}}\operatorname{\textsc{DiCut}}(c).$

The Max-Cut and Max-DiCut problems are simple to describe: given a directed
graph $G$, find or approximate $\operatorname{\textsc{Cut}}(G)$ or
$\operatorname{\textsc{DiCut}}(G)$ respectively.222In the way we have defined
our problems, the instance of Max-Cut is a directed graph, but the directions
are arbitrary and do not matter for the problem. The problem we are interested
in is a promise problem bridging the gap between the two, which we now define.

######  Definition 3.

The Max-DiCut-vs.-Cut problem is defined as follows. Given a directed graph
$G=(V,E)$, for which $\operatorname{\textsc{DiCut}}(G)=\rho$, find a cut
$c:V\to\\{\pm 1\\}$ such that $\operatorname{\textsc{Cut}}(c)\geq\rho$.

We observe that such a cut must exist; indeed, a cut $c$ witnessing
$\operatorname{\textsc{DiCut}}(G)=\rho$ works as
$\operatorname{\textsc{DiCut}}(c)\leq\operatorname{\textsc{Cut}}(c)$ for every
cut $c$.

### Semidefinite programming

We derive the basic SDP relaxation for Max-DiCut, including triangle
constraints. This SDP has been used many times before, e.g. in [BHPZ23], and
was first used in [FG95].

Max-DiCut can be formulated as a quadratic program, as follows. We introduce
variables $x_{v}\in\mathbb{R}$ for $v\in V$; then we solve the following
maximisation problem.

—l— x_v E_(u, v) ∈E[DiCut(x_u, x_v)] = E_(u, v) ∈E[1 - xuxv\+ xv\- xu4] x_v^2
= 1 ∀v ∈V

We change this program in two ways. First, we add the so-called triangle
constraints (which hold for $x_{v}\in\\{\pm 1\\}$), to get the following:

—l— x_v E_(u, v) ∈E[1 - xuxv\+ xv\- xu4] x_v^2 = 1∀v ∈V (1 ±x_u)(1 ±x_v) ≥0
∀(u, v) ∈E

The main problem with this formulation is that it is not homogeneous i.e.
there are linear terms. In order to fix this, we introduce a variable
$x_{0}\in\\{\pm 1\\}$,333Assume without loss of generality that $0\not\in V$.
with which we multiply all linear factors. The solutions to this new program
will correspond to the solutions to the old program (2), where the
correspondence is given by dividing by $x_{0}$ or by setting $x_{0}=1$.

—l— x_v, t E_(u, v) ∈E[1 - xuxv\+ x0xv\- x0xu4] x_v^2= 1∀v ∈V ∪{ 0 } (x_0
±x_u) (x_0 ±x_v) ≥0 ∀(u, v) ∈V

Unfortunately, (2) is a quadratic programming problem, which is -hard to solve
in general (and in particular, solving this SDP would solve Max-DiCut, which
is not possible assuming $\P\neq\NP$). Thus we get the canonical SDP
relaxation by allowing $x_{u}$ to be vectors in an arbitrarily high-
dimensional vector space, replacing products between real numbers with inner
products. From the way we have derived this program it is clear that its value
is at least as large as $\operatorname{\textsc{DiCut}}(G)$.

—l— $\mathbf{x}$_v, $\mathbf{x}_{0}$ E_(u, v) ∈E[1 -
$\mathbf{x}$u⋅$\mathbf{x}$v\+ $\mathbf{x}_{0}$⋅$\mathbf{x}$v\-
$\mathbf{x}_{0}$⋅$\mathbf{x}$u4] —— $\mathbf{x}$_v ——^2 = 1∀v ∈V ∪{ 0 }
($\mathbf{x}_{0}$±$\mathbf{x}$_u) ⋅($\mathbf{x}_{0}$±$\mathbf{x}$_v) ≥0 ∀(u,
v) ∈E

This semidefinite program can be solved with error at most
$\varepsilon\in(0,1)$ in polynomial time in $|G|$ and $\log(1/\varepsilon)$,
either by the ellipsoid method [GLS81] or by interior point methods
[dKV16].444For simplicity we will ignore issues of real precision.

##  3 Results

In this section, we prove our main results.

See 1 See 2

In order to prove this, we will need the following technical lemma, which is
proved in Section 4.

######  Lemma 4 (Configuration lemma).

Suppose we have three unit vectors
$\mathbf{x}_{u},\mathbf{x}_{v},\mathbf{x}_{0}\in\mathbb{R}^{N}$ such that
$(\mathbf{x}_{0}\pm\mathbf{x}_{u})\cdot(\mathbf{x}_{0}\pm\mathbf{x}_{v})\geq
0$. Let $\mathbf{y}_{u},\mathbf{y}_{v}$ be the normalised projection of
$\mathbf{x}_{u},\mathbf{x}_{v}$ onto $\langle\mathbf{x}_{0}\rangle^{\perp}$
(if $\mathbf{x}_{w}\in\langle\mathbf{x}_{0}\rangle$ then set $\mathbf{y}_{w}$
to be some vector perpendicular to all other vectors in the problem). Suppose
$a$ is selected uniformly at random from $[0,1]$, and $H$ is a hyperplane
selected uniformly at random such that $H(\mathbf{x}_{0})=1$. Suppose
$c(u),c(v)$ are defined as follows: $c(w)=1$ if
$\mathbf{x}_{w}\cdot\mathbf{x}_{0}\geq a$ or if
$\mathbf{x}_{w}\cdot\mathbf{x}_{0}>-a$ and $H(\mathbf{y}_{w})=1$; otherwise
$c(w)=-1$. Then, we have

$\Pr_{a,H}[c(u)\neq
c(v)]\geq\frac{1-\mathbf{x}_{u}\cdot\mathbf{x}_{v}+\mathbf{x}_{0}\cdot\mathbf{x}_{v}-\mathbf{x}_{0}\cdot\mathbf{x}_{u}}{4}.$

###### Proof of Theorem 1.

Suppose we are given an input graph $G$ with
$\operatorname{\textsc{DiCut}}(G)=\rho$. Then, we first solve the semidefinite
program (2), with error $\varepsilon$; suppose that the solution vectors we
get are $\mathbf{x}_{u}\in\mathbb{R}^{N}$ for $u\in V\cup\\{0\\}$, where $N$
can be taken to be equal to the number of vectors in the problem i.e.
$|V|+1$.555Indeed, the SDP algorithm actually computes the inner products
between all vectors $\mathbf{x}_{0},\mathbf{x}_{v}$ — the actual vectors can
be reconstituted using a Cholesky decomposition i.e. writing a positive
semidefinite matrix $A\in\mathbb{R}^{n\times n}$ as a product $X^{T}X$ for
$X\in\mathbb{R}^{n\times n}$. If $A$ is the matrix containing the inner
products, then the columns of $X$ form the vectors
$\mathbf{x}_{0},\mathbf{x}_{v}$ in the solution. The value of these vectors is
at least $\rho-\varepsilon$. Now, we randomly round this SDP solution into a
solution to our original problem. We first intuitively explain our rounding
scheme.

Observe that the vector $\mathbf{x}_{0}$ corresponds to $+1$ in our problem,
whereas the vector $-\mathbf{x}_{0}$ corresponds to $-1$. If some vector
$\mathbf{x}_{u}$ were equal exactly to $\mathbf{x}_{0}$ or $-\mathbf{x}_{0}$,
then intuitively we should round it to $\pm 1$ accordingly. Now, similarly, if
$|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$ is large enough, then we should also
round $\mathbf{x}_{u}$ according to
$\operatorname{sgn}(\mathbf{x}_{u}\cdot\mathbf{x}_{0})$. On the other hand, if
$|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$ is small enough, then we may as well
throw away the component of $\mathbf{x}_{u}$ parallel to $\mathbf{x}_{0}$.
Thus, we set $\mathbf{y}_{u}$ to be the normalised projection of
$\mathbf{x}_{u}$ onto $\langle\mathbf{x}_{0}\rangle^{\perp}$. In the case
$\mathbf{x}_{u}\in\langle\mathbf{x}_{0}\rangle$, then of course
$|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$ is large, so the value we assign
$\mathbf{y}_{u}$ shouldn’t matter; we set it to some vector perpendicular to
all other vectors seen so far for simplicity. (This requires increasing the
dimension of all the vectors by $|V|$, but this does not affect the
complexity.)

Consider now an edge $(u,v)$ where both $|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$
and $|\mathbf{x}_{v}\cdot\mathbf{x}_{0}|$ are small. In this case, we see that
$\mathbf{x}_{v}\cdot\mathbf{x}_{0}-\mathbf{x}_{u}\cdot\mathbf{x}_{0}$ does not
contribute much to the objective function. Indeed, the major contribution is
by
$1-\mathbf{x}_{u}\cdot\mathbf{x}_{v}=2\operatorname{\textsc{Cut}}(\mathbf{x}_{u},\mathbf{x}_{v})$.
Thus, it intuitively makes sense to round these vectors by a random
hyperplane.

We are now ready to describe precisely the operation of the algorithm. First
we sample a threshold $a\in[0,1]$ uniformly at random. (This threshold
separates “large” from “small” values in the informal discussion above.) If
$|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|\geq a$ then set
$c(u)=\operatorname{sgn}(\mathbf{x}_{u}\cdot\mathbf{x}_{0})$. For all $u$,
compute $\mathbf{y}_{u}$ as described above, namely set

$\mathbf{y}_{u}=\frac{\mathbf{x}_{u}-(\mathbf{x}_{u}\cdot
t)\mathbf{x}_{0}}{\sqrt{1-(\mathbf{x}_{u}\cdot\mathbf{x}_{0})^{2}}}$

whenever $|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|<1$, and otherwise
$\mathbf{y}_{u}$ is set perpendicular to all other vectors seen so far. Sample
a hyperplane $H$ uniformly at random such that $H(\mathbf{x}_{0})=1$. Now, for
all $u$ for which $|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|<a$, we set
$c(u)=H(\mathbf{y}_{u})$.

For any edge $(u,v)\in E$, what is the probability that this edge is correctly
cut by our method? We observe that the rounding method we described is exactly
the same as the one mentioned in Lemma 4, hence

$\Pr_{a,H}[c(u)\neq
c(v)]\geq\frac{1-\mathbf{x}_{u}\cdot\mathbf{x}_{v}+\mathbf{x}_{0}\cdot\mathbf{x}_{v}-\mathbf{x}_{0}\cdot\mathbf{x}_{u}}{4}.$

Thus, noting that
$\operatorname*{\mathbb{E}}_{a,H}[\operatorname{\textsc{Cut}}(c(u),c(v))]=\Pr_{a,H}[c(u)\neq
c(v)]$, we have

$\operatorname*{\mathbb{E}}_{a,H}[\operatorname{\textsc{Cut}}(c)]\geq\operatorname*{\mathbb{E}}_{(u,v)\in
E}\left[\frac{1-\mathbf{x}_{u}\cdot\mathbf{x}_{v}+\mathbf{x}_{0}\cdot\mathbf{x}_{v}-\mathbf{x}_{0}\cdot\mathbf{x}_{u}}{4}\right]\geq\rho-\varepsilon,$

as required. ∎

We now derandomise our algorithm. This derandomisation scheme essentially uses
the fact that our rounding scheme is a family of $\mathcal{ROT}$ rounding
schemes i.e. schemes that essentially rotate our vectors by some angle
towards/away from $\mathbf{x}_{0}$.

###### Proof of Theorem 2.

We first slightly modify our algorithm. For every vector $\mathbf{x}_{u}$
where $|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|<a$ we set
$\mathbf{z}_{u}=\mathbf{y}_{u}$; otherwise we set
$\mathbf{z}_{u}=\operatorname{sgn}(\mathbf{x}_{u}\cdot\mathbf{x}_{0})\mathbf{x}_{0}$.

For any hyperplane where $H(\mathbf{x}_{0})=1$ and any $u\in V$ where
$|\mathbf{x}_{u}\cdot t|\geq a$, we have that
$H(\mathbf{z}_{u})=\operatorname{sgn}(\mathbf{x}_{u}\cdot\mathbf{x}_{0})$.
Thus, the following algorithm has the exact same characteristics as the
algorithm from Theorem 2: compute an SDP solution
$\mathbf{x}_{0},\mathbf{x}_{u}$, then select a uniformly random threshold
$a\in[0,1]$ and compute $\mathbf{y}_{u},\mathbf{z}_{u}$ as described. Now,
select a uniformly random hyperplane $H$, with $H(\mathbf{x}_{0})=1$. Finally,
set $c(u)=H(\mathbf{z}_{u})$. This algorithm will in fact output exactly the
same cut $c$ as our original one as long as the same values of $a,H$ are
selected.

Now, observe that the performance bound on our original algorithm says that
the expected value of a cut $c$ created by selecting $a$ uniformly at random
from $[0,1]$ and setting $c(u)=H(\mathbf{z}_{u})$ is at least
$\rho-\varepsilon$. First, we observe that the exact value of $a$ doesn’t
matter, only its value relative to $|\mathbf{x}_{u}\cdot\mathbf{x}_{0}|$ for
$u\in V$. Thus there are essentially $O(|V|)$ choices for $a$, and we can try
all of them. Now, for the best $a$, we know that the expected value of the cut
given by $c(u)=H(\mathbf{z}_{u})$ is at least $\rho-\varepsilon$. It is well
known that given such vectors $\mathbf{z}_{u}$ we can compute a colouring of
$G$ with value at least $\rho-\varepsilon-\varepsilon^{\prime}$ in polynomial
time in $|G|$ and $\log(1/\varepsilon^{\prime})$ for $\varepsilon\in(0,1)$ —
indeed this amounts to derandomising the original Goemans-Williamson Max-Cut
algorithm. One classic algorithm for this is given in [MR99], whereas a
simpler and more optimised algorithm is given in [BK05].

Thus, by setting $\varepsilon+\varepsilon^{\prime}=1/2|E|$, we get a cut $c$
with value at least $\rho-1/2|E|=\operatorname{\textsc{DiCut}}(G)-1/2|E|$. But
observe that $\operatorname{\textsc{DiCut}}(G)=k/|E|$, where $k$ is the number
of edges in the optimal directed cut in $G$, and also
$\operatorname{\textsc{Cut}}(c)=k^{\prime}/|E|$, where $k^{\prime}$ is the
number of edges properly cut by $c$. It follows therefore, as
$k,k^{\prime}\in\mathbb{N}$ and $k^{\prime}/|E|\geq k/|E|-1/2|E|$ i.e.
$k^{\prime}\geq k-1/2$ that $k^{\prime}\geq k$, and hence
$\operatorname{\textsc{Cut}}(c)\geq\operatorname{\textsc{DiCut}}(G)$. ∎

##  4 Analysis

In this section we prove the following lemma.

See 4

We define the value $\rho_{xyz}$. When $x=\pm 1$ or $y=\pm 1$, we define
$\rho_{xyz}=0$; otherwise,

$\rho_{xyz}=\frac{z-xy}{\sqrt{1-x^{2}}\sqrt{1-y^{2}}}.$

In order to prove Lemma 4, we will need the following fact.

######  Lemma 5.

Consider $x,y\in[-1,1]$ with $|x|\leq y$, and take $z\in[x+y-1,1-y+x]$. Then

$\frac{1-y}{\pi}\arccos\rho_{xyz}\geq\frac{1-z+x-y}{4}.$ (1)

To prove this fact we define the following functions:

$\displaystyle F(x,y,z)$
$\displaystyle=\arccos\rho_{xyz}-\frac{\pi}{4}\frac{1-z+x-y}{1-y},$
$\displaystyle\Delta_{xy}$
$\displaystyle=4\pi^{4}(1-x^{2})(1-y^{2})-64\pi^{2}(1-y)^{2},$
$\displaystyle\alpha_{xy}$
$\displaystyle=\frac{\pi}{4}\frac{\sqrt{1-x^{2}}\sqrt{1-y^{2}}}{1-y},$
$\displaystyle G(x,y)$
$\displaystyle=\pi-\operatorname{arccsc}\alpha_{xy}-\frac{\pi}{4}(1+x)-\sqrt{\alpha_{xy}^{2}-1}.$

For the function $G(x,y)$ to be defined (over the reals), it is necessary for
$|\alpha_{xy}|\geq 1$; in particular this is certainly true when
$\Delta_{xy}\geq 0$, which is the only case when we will use this function.
For many other of these functions, we require $y<1$; this will also always be
the case when they are invoked.

######  Lemma 6.

Assume $x,y\in(-1,1)$, $y\geq|x|$, $\Delta_{xy}\geq 0$ and
$xy-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}\geq x+y-1$. Then $G(x,y)\geq 0$.

###### Proof.

We observe that for $xy-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}\geq x+y-1$ to be
true, we must have

$0\leq 1+xy-
x-y-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}=(1-x)(1-y)-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}=\\\
\frac{1}{(1-x)(1-y)+\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}}\left({(1-x)^{2}(1-y)^{2}-\frac{\Delta_{xy}}{4\pi^{4}}}\right)=\\\
\frac{2(1-y)}{\pi^{2}(1-x)(1-y)+\frac{\sqrt{\Delta_{xy}}}{2}}\left(8(1-y)-\pi^{2}(1-x)(x+y)\right).$

This is true if and only if $8(1-y)\geq\pi^{2}(1-x)(x+y)$. Thus
$y\leq(\pi^{2}x-\pi^{2}x^{2}-8)/(\pi^{2}x-8-\pi^{2})$.

We observe now that $\alpha_{xy}$ is an increasing function of $y$ on
$(-1,1)$, hence by taking $y=(\pi^{2}x-\pi^{2}x^{2}-8)/(\pi^{2}x-8-\pi^{2})$,
we find that

$\alpha_{xy}\leq\sqrt{1+\frac{\pi^{2}}{16}(1-x)^{2}}.$

Furthermore, note that

$\frac{\partial}{\partial\alpha_{xy}}G(x,y)=-\frac{\sqrt{\alpha_{xy}^{2}-1}}{\alpha_{xy}}<0.$

Hence we minimise $G$ by selecting $y$ so as to maximise $\alpha_{xy}$. Thus,
taking $y$ so that $\alpha_{xy}=\sqrt{1+\frac{\pi^{2}}{16}(1-x)^{2}}$, we find
that

$G(x,y)\geq\pi-\operatorname{arccsc}\left(\sqrt{1+\frac{\pi^{2}}{16}(1-x)^{2}}\right)-\frac{\pi}{4}(1+x)-\sqrt{\sqrt{1+\frac{\pi^{2}}{16}(1-x)^{2}}^{2}-1}=\\\
\pi-\operatorname{arccsc}\left(\sqrt{1+\frac{\pi^{2}}{16}(1-x)^{2}}\right)-\frac{\pi}{2}\geq
0,$

as required. ∎

######  Lemma 7.

Assume $x,y\in(-1,1)$ and $\Delta_{xy}\geq 0$. If
$z=xy-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}$, then
$\arccos\rho_{xyz}=\pi-\operatorname{arccsc}\alpha_{xy}$.

###### Proof.

Observe that $z-xy=-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}$. So

$\rho_{xyz}=-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}\sqrt{1-x^{2}}\sqrt{1-y^{2}}}=-\frac{1}{2\pi^{2}}\sqrt{\frac{4\pi^{4}(1-x^{2})(1-y^{2})-64\pi^{2}(1-y)^{2}}{(1-x^{2})(1-y^{2})}}=\\\
-\frac{1}{2\pi^{2}}\sqrt{4\pi^{4}-64\pi^{2}\frac{(1-y)^{2}}{(1-x^{2})(1-y^{2})}}=-\sqrt{1-\frac{16}{\pi^{2}}\frac{(1-y)^{2}}{(1-x^{2})(1-y^{2})}}=-\sqrt{1-1/\alpha_{xy}^{2}}.$

Thus recalling the trigonometric identity
$\arccos(-\sqrt{1-1/\alpha^{2}})+\operatorname{arccsc}\alpha=\pi$, we have

$\arccos\rho_{xyz}=\arccos(-\sqrt{1-1/\alpha_{xy}^{2}})=\pi-\operatorname{arccsc}\alpha_{xy}.\qed$

######  Lemma 8.

Assume $x,y\in(-1,1)$ and $\Delta_{xy}\geq 0$. If
$z=xy-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}$, then

$\frac{\pi}{4}\frac{1-z+x-y}{1-y}=\frac{\pi}{4}(1+x)+\sqrt{\alpha^{2}_{xy}-1}.$

###### Proof.

We have

$\frac{\pi}{4}\frac{1-z+x-y}{1-y}=\frac{\pi}{4}\frac{1-xy+x-y}{1-y}+\frac{1}{8\pi(1-y)}\sqrt{4\pi^{4}(1-x^{2})(1-y^{2})-64\pi^{2}(1-y)^{2}}=\\\
\frac{\pi}{4}\frac{(1+x)(1-y)}{1-y}+\sqrt{\frac{\pi^{2}}{16}\frac{(1-x^{2})(1-y^{2})}{(1-y)^{2}}-1}=\frac{\pi}{4}(1+x)+\sqrt{\alpha_{xy}^{2}-1},$

as required. ∎

######  Lemma 9.

Take $x,y\in(-1,1)$ such that $|x|\leq y$, and $x+y-1\leq z\leq 1-y+x$. Then
$F(x,y,z)\geq 0$.

For the purpose of illustration, we plot $F(x,y,z)$ for $x=0.14,y=0.36$ and
$z\in[x+y-1,1-y+x]$ in Fig. 2; these values for $x$ and $y$ have been chosen
to highlight the more difficult case in our proof i.e. when there is a local
minimum. We observe that the triangle inequalities (i.e. $z\in[x+y-1,1-y+x]$)
seem to be necessary for our rounding scheme to work; for example,
$x=0.03,y=0.99,z=-0.01$ leads to $F(x,y,z)\approx-2.07$.

Figure 2: Plot of
$F(0.14,0.36,z)$$-0.5$$-0.4$$-0.3$$-0.2$$-0.1$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.64$$0.66$$0.68$$0.7$$0.72$$z$$F(0.14,0.36,z)$

###### Proof.

Fixing $x,y$, we want to find the $z$ that minimises the value of $F(x,y,z)$.
We consider the extreme values of $z$, then inspect the local minima.

Case 1: $\bm{z=x+y-1}$.

In this case, $1-z+x-y=2-2y$, so

$\frac{\pi}{4}\frac{1-z+x-y}{1-y}=\frac{\pi}{2}.$

Furthermore, $z-xy=-1+x+y-xy=-(1-x)(1-y)$, so

$\rho_{xyz}=-\frac{(1-x)(1-y)}{\sqrt{1-x^{2}}\sqrt{1-y^{2}}}<0.$

Thus in this case $\arccos\rho_{xyz}>\pi/2$, so $F(x,y,z)>0$.

Case 2: $\bm{z=1-y+x}$.

In this case $1-z+x-y=0$, so

$F(x,y,z)=\arccos\rho_{xyz}-0\geq 0.$

Case 3: $\bm{x+y-1<z<1-y+x}$.

We are now looking for local minima of $F(x,y,z)$ with respect to $z$. Thus,
we compute

$\frac{\partial}{\partial
z}F(x,y,z)=\frac{\pi^{2}(1-x^{2}-y^{2}-z^{2}+2xyz)-16(1-y)^{2}}{4(1-y)\sqrt{1-x^{2}-y^{2}-z^{2}+2xyz}(\pi\sqrt{1-x^{2}-y^{2}-z^{2}+2xyz}+4(1-y))}.$

We observe that the denominator of this fraction is always positive, and thus
the sign of $\frac{\partial}{\partial z}F(x,y,z)$ is given be the numerator,
namely

$\pi^{2}(1-x^{2}-y^{2}-z^{2}+2xyz)-16(1-y)^{2}.$

We compute the discriminant of this quadratic, and observe that it equals
$\Delta_{xy}$. Thus, if $\Delta_{xy}<0$ there are no stationary points; if
$\Delta_{xy}=0$ then there is one stationary point but it is neither a local
minimum nor a local maximum; and if $\Delta_{xy}>0$ there are two stationary
points, located at

$z=xy\pm\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}.$

The first of these is a local minimum, and the second is a local maximum. Thus
we are interested in $z=xy-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}$. Of course if
this value does not satisfy our boundary conditions, then there are no local
minima; so we can assume that $xy-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}\geq
x+y-1$. By Lemmas 7 and 8, when $z=xy-\frac{\sqrt{\Delta_{xy}}}{2\pi^{2}}$, we
have

$F(x,y,z)=\pi-\operatorname{arccsc}\alpha_{xy}-\frac{\pi}{4}(1+x)-\sqrt{\alpha^{2}_{xy}-1}=G(x,y).$

By Lemma 6, $G(x,y)\geq 0$, so in this case it follows that $F(x,y,z)\geq 0$
also.

Thus, our conclusion follows in all cases. ∎

###### Proof of Lemma 5.

We first deal with the edge cases, when $x,y=\pm 1$, then with the typical
case. As $y\geq|x|\geq 0$, for either $x$ or $y$ to be $\pm 1$, it must be the
case that $y=1$, so suppose this is the case. Then the left side of (1) is
$0$, whereas the right side is $(x-z)/4$. By assumption $x+y-1\leq z$, but
since $y=1$ this is the same as $x\leq z$, hence $(x-z)/4\leq 0$ as required.
We can thus assume that $y<1$ and thus $x,y\in(-1,1)$. In this case, (1) is
equivalent to $F(x,y,z)\geq 0$, which is implied by Lemma 9. ∎

Having proved Lemma 5, we return to the proof of Lemma 4.

###### Proof of Lemma 4.

Suppose we let $x=\mathbf{x}_{u}\cdot\mathbf{x}_{0}$,
$y=\mathbf{x}_{v}\cdot\mathbf{x}_{0}$ and
$z=\mathbf{x}_{u}\cdot\mathbf{x}_{v}$. Then
$(\mathbf{x}_{0}\pm\mathbf{x}_{u})\cdot(\mathbf{x}_{0}\pm\mathbf{x}_{v})\geq
0$ amounts to

$\displaystyle 1+x+y+z$ $\displaystyle\geq 0,$ $\displaystyle 1-x-y+z$
$\displaystyle\geq 0,$ $\displaystyle 1-x+y-z$ $\displaystyle\geq 0,$
$\displaystyle 1+x-y-z$ $\displaystyle\geq 0,$

or equivalently $|x+y|-1\leq z\leq 1-|y-x|$. With this reformulation, we must
show that

$\Pr_{a,H}[c(u)\neq c(v)]\geq\frac{1-z+y-x}{4}.$ (2)

We first consider the effect of swapping $u$ and $v$, and/or negating
$\mathbf{x}_{0}$ has on the problem. Observe that all of these transformations
maintain the requirement
$(\mathbf{x}_{0}\pm\mathbf{x}_{u})\cdot(\mathbf{x}_{0}\pm\mathbf{x}_{v})\geq
0$. These transformations do not change $z$, but they have the effect of
mapping $(x,y)\mapsto(y,x)$ (for swapping) and $(x,y)\mapsto(-x,-y)$ (for
negating). Thus, by swapping we can achieve $(x,y)\mapsto(y,x)$, and by
swapping and negating we can achieve $(x,y)\mapsto(-y,-x)$.

We claim that these transformations mean we can consider only the case $x\leq
y$, $|x|\leq|y|$. Indeed, if $x>y$ then by swapping $\mathbf{x}_{u}$ and
$\mathbf{x}_{v}$ we can reduce to the case $x\leq y$ while increasing the
right side of (2) (i.e. reducing to a necessary subcase). Furthermore, once we
are in this case, if $|x|>|y|$, then by both swapping and negating we can get
to the case $|x|\leq|y|$ while remaining in the case $x\leq y$ (and not
changing the values in (2)). Henceforth we assume that $x\leq y$ and
$|x|\leq|y|$.

Observe that $x\leq y$ and $|x|\leq|y|$ are equivalent to $|x|\leq y$; hence
we know that $y-x\geq 0$ and $x+y\geq 0$, so $|x+y|-1\leq z\leq 1-|y-x|$
becomes $x+y-1\leq z\leq 1-y+x$.

Now, what is the inner product of $\mathbf{y}_{u}$ and $\mathbf{y}_{v}$? We
observe that, as long as $|\mathbf{x}_{w}\cdot\mathbf{x}_{0}|<1$, we have

$\mathbf{y}_{w}=\frac{\mathbf{x}_{w}-(\mathbf{x}_{w}\cdot\mathbf{x}_{0})\mathbf{x}_{0}}{\sqrt{1-(\mathbf{x}_{w}\cdot\mathbf{x}_{0})^{2}}}.$

Hence in this case we have

$\mathbf{y}_{u}\cdot\mathbf{y}_{v}=\frac{(\mathbf{x}_{u}-(\mathbf{x}_{u}\cdot\mathbf{x}_{0})\mathbf{x}_{0})(\mathbf{x}_{v}-(\mathbf{x}_{v}\cdot\mathbf{x}_{0})\mathbf{x}_{0})}{\sqrt{1-(\mathbf{x}_{u}\cdot\mathbf{x}_{0})^{2}}\sqrt{1-(\mathbf{x}_{v}\cdot\mathbf{x}_{0})^{2}}}=\frac{\mathbf{x}_{u}\cdot\mathbf{x}_{v}-(\mathbf{x}_{u}\cdot\mathbf{x}_{0})(\mathbf{x}_{v}\cdot\mathbf{x}_{0})}{\sqrt{1-(\mathbf{x}_{u}\cdot\mathbf{x}_{0})^{2}}\sqrt{1-(\mathbf{x}_{v}\cdot\mathbf{x}_{0})^{2}}}=\\\
\frac{z-xy}{\sqrt{1-x^{2}}\sqrt{1-y^{2}}}.$

Conversely if $|\mathbf{x}_{w}\cdot t|=1$, then $\mathbf{y}_{w}$ is
perpendicular to all other vectors $\mathbf{y}_{w^{\prime}}$, so we have
$\mathbf{y}_{u}\cdot\mathbf{y}_{v}=0$. Hence we observe that in all cases
$\mathbf{y}_{u}\cdot\mathbf{y}_{v}=\rho_{xyz}$.

Now, let us investigate what $\Pr_{a,H}[c(u)\neq c(v)]$ is. There are two main
cases, depending on the sign of $x$.

Case 1: $\bm{x\leq 0}$.

In this case, with probability $-x$ we have that $a\leq|x|\leq|y|$, and hence
$c(u)=-1,c(v)=1$. With probability $|y|-|x|=x+y$, we have $|x|<a\leq|y|$, in
which case $c(v)=1$ but $c(u)$ is uniformly randomly distributed in $\\{\pm
1\\}$. With probability $1-|y|=1-y$ we have $a>|y|\geq|x|$, in which case
$\mathbf{y}_{u},\mathbf{y}_{v}$ are separated by the random hyperplane $H$
with probability $(1/\pi)\arccos\rho_{xyz}$. So

$\Pr_{a,H}[c(u)\neq c(v)]=-x+\frac{x+y}{2}+\frac{1-y}{\pi}\arccos\rho_{xyz}.$

By Lemma 5, we have $((1-y)/\pi)\arccos\rho_{xyz}\geq(1-z+x-y)/4$, so

$\Pr_{a,H}[c(u)\neq
c(v)]\geq-x+\frac{x+y}{2}+\frac{1-z+x-y}{4}=\frac{1-z+y-x}{4}.$

Case 2: $\bm{x>0}$.

In this case, with probability $x$ we have $a\leq|x|\leq|y|$, and hence
$c(u)=1,c(v)=1$. With probability $|y|-|x|=y-x$, we have $|x|<a\leq|y|$, in
which case $c(v)=1$ but $c(u)$ is uniformly randomly distributed in $\\{\pm
1\\}$. With probability $1-|y|=1-y$ we have $a>|y|\geq|x|$, in which case
$\mathbf{y}_{u},\mathbf{y}_{v}$ are separated by $H$ with probability
$(1/\pi)\arccos\rho_{xyz}$. So, applying Lemma 5 as before, we have

$\Pr_{a,H}[c(u)\neq
c(v)]=\frac{y-x}{2}+\frac{1-y}{\pi}\arccos\rho_{xyz}\geq\frac{y-x}{2}+\frac{1-z+x-y}{4}\geq\frac{1-z+y-x}{4}.$

Hence our conclusion follows in all cases. ∎

## References

  * [Aus10] Per Austrin.  Towards Sharp Inapproximability for Any 2-CSP.  SIAM J. Computing, 39(6):2430–2463, 2010.  doi:10.1137/070711670.
  * [BBK+24] Libor Barto, Silvia Butti, Alexandr Kazda, Caterina Viola, and Stanislav Živný.  Algebraic approach to approximation, 2024.  arXiv:2401.15186.
  * [BHPZ23] Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick.  Separating MAX 2-and, MAX DI-CUT and MAX CUT.  In Proc. 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS’23), pages 234–252. IEEE, 2023.  arXiv:2212.11191, doi:10.1109/FOCS57990.2023.00023.
  * [BK05] Ankur Bhargava and S. Rao Kosaraju.  Derandomization of dimensionality reduction and SDP based algorithms.  In Proc. 8th International Workshop on Algorithms and Data Structures (WADS’05), pages 396–408. Springer Berlin Heidelberg, 2005.  doi:10.1007/11534273\\_35.
  * [dKV16] Etienne de Klerk and Frank Vallentin.  On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming.  SIAM J. Optim., 26(3):1944–1961, 2016.  doi:10.1137/15M103114X.
  * [FG95] Uriel Feige and Michel X. Goemans.  Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT.  In Proc. 3rd Israel Symposium on Theory of Computing and Systems (ISTCS’95), pages 182–189. IEEE Computer Society, 1995.  doi:10.1109/ISTCS.1995.377033.
  * [FL92] Uriel Feige and László Lovász.  Two-prover one-round proof systems: Their power and their problems (extended abstract).  In Proc. 24th Annual ACM Symposium on Theory of Computing (STOC’92), pages 733–744. ACM, 1992.  doi:10.1145/129712.129783.
  * [GLS81] Martin Grötschel, László Lovász, and Alexander Schrijver.  The ellipsoid method and its consequences in combinatorial optimization.  Comb., 1(2):169–197, 1981.  doi:10.1007/BF02579273.
  * [GW95] Michel X. Goemans and David P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  J. ACM, 42(6):1115–1145, 1995.  doi:10.1145/227683.227684.
  * [Hås01] Johan Håstad.  Some optimal inapproximability results.  J. ACM, 48(4):798–859, jul 2001.  doi:10.1145/502090.502098.
  * [Kar72] Richard M. Karp.  Reducibility among combinatorial problems.  In Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, pages 85–103. Springer US, 1972.  doi:10.1007/978-1-4684-2001-2_9.
  * [Kho02] Subhash Khot.  On the power of unique 2-prover 1-round games.  In Proc. 34th Annual ACM Symposium on Theory of Computing (STOC’02), pages 767–775. ACM, 2002.  doi:10.1145/509907.510017.
  * [KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell.  Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?  SIAM J. Comput., 37(1):319–357, 2007.  doi:10.1137/S0097539705447372.
  * [KSTW00] Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson.  The approximability of constraint satisfaction problems.  SIAM J. Comput., 30(6):1863–1920, 2000.  doi:10.1137/S0097539799349948.
  * [LLZ02] Michael Lewin, Dror Livnat, and Uri Zwick.  Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems.  In Proc. 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO’02), volume 2337 of Lecture Notes in Computer Science, pages 67–82. Springer, 2002.  doi:10.1007/3-540-47867-1\\_6.
  * [MM03] Shiro Matuura and Tomomi Matsui.  New approximation algorithms for MAX 2SAT and MAX DICUT.  Journal of the Operations Research Society of Japan, 46(2):178–188, 2003.  doi:10.15807/jorsj.46.178.
  * [MM17] Konstantin Makarychev and Yury Makarychev.  Approximation Algorithms for CSPs.  In Andrei A. Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 287–325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/DFU.VOL7.15301.11.
  * [MOO10] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz.  Noise stability of functions with low influences: invariance and optimality.  Ann. of Math. (2), 171(1):295–341, 2010.  doi:10.4007/annals.2010.171.295.
  * [MR99] Sanjeev Mahajan and H. Ramesh.  Derandomizing approximation algorithms based on semidefinite programming.  SIAM J. Comput., 28(5):1641–1663, 1999.  doi:10.1137/S0097539796309326.
  * [NŽ23] Tamio-Vesa Nakajima and Stanislav Živný.  Maximum $k$\- vs. $\ell$-colourings of graphs, 2023.  arXiv:2311.00440.
  * [Rag08] Prasad Raghavendra.  Optimal algorithms and inapproximability results for every CSP?  In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC’08), pages 245–254, 2008.  doi:10.1145/1374376.1374414.
  * [RS09] Prasad Raghavendra and David Steurer.  How to round any CSP.  In Proc. 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS’09), pages 586–594. IEEE Computer Society, 2009.  doi:10.1109/FOCS.2009.74.
  * [TSSW00] Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson.  Gadgets, approximation, and linear programming.  SIAM J. Comput., 29(6):2074–2097, 2000.  doi:10.1137/S0097539797328847.