# The geodesic transversal problem on some networks

Paul Manuela Boštjan Brešarb,c Sandi Klavžarb,c,d

###### Abstract

A set $S$ of vertices of a graph $G$ is a geodesic transversal of $G$ if every
maximal geodesic of $G$ contains at least one vertex of $S$. We determine a
smallest geodesic transversal in certain interconnection networks such as
meshes of trees, and some well-known chemical structures such as silicate
networks and carbon nanosheets. Some useful general bounds for the
corresponding graph invariant are obtained along the way.

a Department of Information Science, College of Life Sciences, Kuwait
University, Kuwait

<EMAIL_ADDRESS>

b Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

<EMAIL_ADDRESS>

c Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

d Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

<EMAIL_ADDRESS>

Keywords: geodesic transversal problem, geodesic packing problem,
interconnection networks, mesh of trees, silicate networks

2010 Mathematics Subject Classification: 05C12, 05C82.

##  1 Introduction

One of the fundamental concepts in graph theory is that of a shortest path
between two vertices, also called a geodesic. A geodesic is maximal if it is
not a subpath of another geodesic. A set $S$ of vertices of $G$ is a geodesic
transversal of $G$ if every maximal geodesic of $G$ contains at least one
vertex of $S$. We also say that a vertex $x\in S$ hits geodesic $P$ if $x$ is
a vertex of $P$. The geodesic transversal number of $G$, denoted by ${\rm
gt}(G)$, is the minimum cardinality of a geodesic transversal of $G$. A set
$S$ of vertices is a ${\rm gt}$-set of $G$ if $S$ is a minimum cardinality
geodesic transversal of $G$. The geodesic transversal problem of $G$ is to
find a ${\rm gt}$-set of $G$.

Interestingly, this concept was introduced recently by two independent
research groups [11, 13, 14]. The geodesic transversal problem was shown to be
NP-complete [11, 13] and polynomially solvable for trees [11, 13] and some
cactus families [11]. Peterin and Semanišin [14] have shown some interesting
results on the geodesic transversal problem of the join and the lexicographic
product of graphs. A motivation for studying the geodesic transversal problem
was illustrated in [11, 13], where applications in (large-scale) network
theory and complex systems control were indicated. As an additional
motivation, we present another connection of our study to a problem that
arises in networks called the shortest path union cover problem as introduced
by Boothe et al. [1]. If $G$ is a graph, then a set $S$ of vertices is called
a shortest path union cover if the shortest paths that start at the vertices
of $S$ cover all the edges of $G$. The shortest path union cover problem is to
find a shortest path union cover of minimum cardinality. Since all geodesics
that start at the vertices of a geodesic transversal of $G$ cover all the
edges of $G$, every geodesic transversal is a shortest path union cover.
However, the converse is not true. Any leaf of a tree is a shortest path union
cover and hence the shortest path union cover number of a tree is just $1$. On
the other hand, the computation of the geodesic transversal number of a tree
is not straightforward [11, 13].

The geodesic transversal problem is also of applicable nature, which is
another motivation for our study. Notably, shortest paths are the basis of
distance-based topological indices that are extensively studied and applied in
chemical graph theory, let us mention just the notorious Wiener Index. (The
reader can start exploring this vast field by reading, for example, the
following articles [2, 3, 16].) Since, according to Bellman’s principle, each
sub-path of a shortest path will itself be a shortest path, maximal geodesics
have a special distinguished role. To our knowledge, this has not been
investigated in mathematical chemistry, but in our opinion the role of maximal
geodesics would certainly be worth investigating there.

In this paper, we first present two simple, yet useful bounds, an upper and a
lower bound for the geodesic transversal number of an arbitrary graph, and
demonstrate their sharpness. They are given in the following section and are
used in several proofs of later sections. In Section 3, we study meshes of
trees, which are constructed by combining square grids with complete binary
trees, and we determine their geodesic transversal number. In Section 4, we
consider ${\rm gt}$-sets with respect to two operations of attaching leaves to
vertices of a graph. One of the operations is used in Section 5, where we
solve the geodesic transversal problem for the well-known chemical structure
of silicate networks.

##  2 Basic bounds

The following upper bound for the geodesic transversal number follows from the
fact that each (maximal) geodesic has two end-vertices and to hit all maximal
geodesics, it suffices to hit all but one end-vertex of maximal geodesics of a
graph.

######  Observation 1.

If $G$ is a graph, and $X$ is the set of end-vertices of all maximal geodesics
of $G$, then ${\rm gt}(G)\leq|X|-1$. In addition, if there is a subset
$X^{\prime}\subset X$ such that no maximal geodesic lies between two vertices
from $X^{\prime}$, then ${\rm gt}(G)\leq|X|-|X^{\prime}|$.

The second statement of Observation 1 follows from the fact that every maximal
geodesic has an end-vertex in $X-X^{\prime}$, thus vertices of $X-X^{\prime}$
hit all maximal geodesics of $G$. The (first) bound in Observation 1 is sharp
as can be seen by paths $P_{n}$, where ${\rm gt}(P_{n})=1$, and complete
graphs $K_{n}$, where ${\rm gt}(K_{n})=n-1$. On the other hand, the bound need
not be useful, as one can see in stars, since ${\rm gt}(K_{1,n})=1$, while the
bound is $n-1$.

To demonstrate the proof techniques by using also the bound in Observation 1,
we next present a result concerning a structure that arises in mathematical
chemistry [21]. Fig. 1 shows the $3$-layer and the $4$-layer triangular carbon
nanosheet [8, 21], and the definition of the $r$-layer triangular carbon
nanosheet should be clear from these two cases. Next, we establish the exact
value of the geodesic transversal number of the $r$-layer triangular carbon
nanosheet. Recall that a leaf or a pendant vertex in a graph $G$ is a vertex
having one neighbor in $G$, while a support vertex is a vertex adjacent to a
leaf.

Figure 1: (a) A 3-layer triangular carbon nanosheet, (b) A 4-layer triangular
carbon nanosheet.

######  Proposition 2.1.

If $G$ is an $r$-layer triangular carbon nanosheet, then ${\rm gt}(G)=3$.

###### Proof.

We denote by $u$, $v$ and $w$ the three corner vertices of $G$; these are the
only pendant vertices of $G$, and let $Y=\\{u,v,w\\}$. Let $X^{\prime}$ be the
set of vertices of degree $2$. Note that the set of end-vertices of maximal
geodesics of $G$ is $X=Y\cup X^{\prime}$. Indeed, if $x$ is an internal vertex
of degree $3$, then $x$ cannot be an end vertex of a maximal geodesic, since
such a geodesic can be extended through one of the three edges incident with
$x$. Similarly, if $x$ is an external vertex of degree $3$ which lies on a
geodesic $P$, then one of its two neighbors of degree $2$ can be added to $P$
so that the resulting path is still a geodesic. From these facts we readily
infer that there are two types of maximal geodesics in $G$: (1) connecting two
of the corner vertices, and (2) connecting a corner vertex with a vertex of
degree $2$ that lies in the (opposite) geodesic between the other two corner
vertices. (In addition, all the maximal geodesics are of diametral length.)

For the upper bound, ${\rm gt}(G)\leq 3$, we use the second statement of
Observation 1. Indeed, by the previous paragraph, there are no maximal
geodesics between two vertices in $X^{\prime}$, hence ${\rm
gt}(G)\leq|X|-|X^{\prime}|=|Y|=3$. In particular, the vertices of $Y$ form a
geodesic transversal. By a simple case analysis (taking into consideration all
possibilities of positioning two vertices in a potential geodesic
transversal), one finds that ${\rm gt}(G)>2$. ∎

For the lower bound on the geodesic transversal number we introduce the
following concept. A geodesic packing of $G$ is a set of maximal geodesics
$\\{P_{1},\ldots,P_{k}\\}$, which are mutually vertex-disjoint. The geodesic
packing number of $G$ is the maximum cardinality of a geodesic packing of $G$
and is denoted by ${\rm gpack}(G)$. Clearly, every geodesic transversal $S$ of
$G$ must hit each geodesic in a (maximum) geodesic packing $P$ in $G$, and
pairwise distinct vertices from $S$ are needed to hit pairwise distinct
geodesics from $P$. We infer the following result.

######  Observation 2.

Given a graph $G$, ${\rm gt}(G)\geq{\rm gpack}(G)$.

The bound in Observation 2 is again sharp in paths, where ${\rm
gt}(P_{n})={\rm gpack}(P_{n})=1$. It can fail to be useful, like in complete
graphs $K_{n}$, where ${\rm gpack}(K_{n})=\lfloor\frac{n}{2}\rfloor$, while
${\rm gt}(K_{n})=n-1$. A large class of graphs $G$ in which ${\rm gt}(G)={\rm
gpack}(G)$ will be presented in Section 4.

##  3 Mesh of trees

In this section, we establish the geodesic transversal number of mesh of
trees, which are constructed by combining 2-dimensional square grids with
complete binary trees. For this purpose, we first consider the two classes
that present building blocks of a mesh of trees.

We start by presenting the class of square grids. First, the Cartesian product
of graphs $G$ and $H$ is the graph with $V(G)\times V(H)$ as its vertex set,
while $(g,h)(g^{\prime},h^{\prime})\in E(G\,\square\,H)$ if and only if
($gg^{\prime}\in E(G)$ and $h=h^{\prime}$) or ($g=g^{\prime}$ and
$hh^{\prime}\in E(H)$. See the monograph [7] for more on graph products. Now,
a square grid is a graph $P_{r}\,\square\,P_{s}$ for some $r,s\in\mathbb{N}$.
In many situations, a graph may have an exponential number of maximal
geodesics. In particular, this holds for square grids $P_{r}\,\square\,P_{r}$.
However, all maximal geodesics in $P_{r}\,\square\,P_{r}$ can be hit by only
two vertices.

A subdivided star is the graph obtained from $K_{1,n}$, $n\geq 1$, by
subdividing each of the edges of $K_{1,n}$ an arbitrary number of times
(possibly zero, and different edges may be subdivided different number of
times). As proved in [11, Proposition 3.2], ${\rm gt}(G)=1$ if and only if $G$
is a subdivided star.

######  Proposition 3.1.

The geodesic transversal number of a $2$-dimensional square grid
$P_{r}\,\square\,P_{s}$ is $2$.

###### Proof.

Recall a well known fact that in any Cartesian product a path $P$ is a
geodesic if and only if the projections of $P$ are geodesics in each of the
factors (where repetitions of vertices in the projected paths are
disregarded). We readily infer that only the corner vertices (that is, the
vertices of degree $2$) are end-vertices of maximal geodesics in
$P_{r}\,\square\,P_{s}$. (By Observation 1, this implies ${\rm
gt}(P_{r}\,\square\,P_{s})\leq 3$.) Moreover, the geodesic between any two
corner vertices in the same row (respectively, same column) is not maximal,
since it can be extended to a diametral path. Hence by using the second
statement of Observation 1 we derive ${\rm gt}(P_{r}\,\square\,P_{s})\leq 2$,
and the corner vertices in the same row (or column, respectively) form a
geodesic transversal. Since the grid is not a subdivided star, we infer ${\rm
gt}(P_{r}\,\square\,P_{s})\geq 2$ by [11, Proposition 3.2]. ∎

Figure 2: (a) A complete binary tree (b) The red bullets form a geodesic
transversal

The complete binary tree of dimension $r$ is the rooted tree in which all
($2^{r}$) leaves have the same depth $r$, and all interior vertices have $2$
children. (Fig. 2(a) presents the complete binary tree of dimension $3$.)

######  Proposition 3.2.

If $G$ is an $r$-dimensional complete binary tree, then ${\rm gt}(G)=2^{r-1}$.

###### Proof.

Consider the set of the maximal geodesics of length $2$ in $G$ which connect
two leaves through their common support vertex. There are $2^{r-1}$ such
maximal geodesics, and they are pairwise disjoint, thus ${\rm gpack}(G)\geq
2^{r-1}$. By Observation 2, ${\rm gt}(G)\geq 2^{r-1}$. Note that the end-
vertices of any maximal geodesic in $G$ are leaves, since (maximal) geodesics
in a tree are all its (maximal) paths. Hence we infer that the set $S$ of
support vertices of $G$ (see Fig. 2(b)) is a geodesic transversal. Thus, ${\rm
gt}(G)\leq|S|=2^{r-1}$. ∎

Figure 3: (a) $2^{2}\times 2^{2}$ square grid. (b) An $N\times N$ mesh of
trees where $N=2^{2}$. The grid vertices are white, the row tree vertices red,
and the column tree vertices are in blue.

A mesh of trees is a well-known interconnection parallel architecture [10,
20]. The advantage of the mesh of trees is that it combines the features of
both $2$-dimensional square grids as well as complete binary trees. The mesh
of trees was originally introduced by Leighton [10]. It is now formally
defined here. Let $MoT(r)$ denote the $N\times N$ mesh of trees where
$N=2^{r}$ and $r$ is a positive integer. The graph $MoT(r)$ is constructed on
top of the $2$-dimensional square grid, where each row and column are replaced
by a complete binary tree (and the original edges of the grid are deleted).
The vertices of the $N\times N$ grid are marked in white and play the role of
leaves of the corresponding complete binary trees both in rows and columns.
The row trees are marked in red and the column trees are marked in blue (with
the exception of their leaves, which are colored white, as mentioned earlier).
See Fig. 3. Let us now identify some geodesic transversal of $MoT(r)$.

######  Lemma 3.3.

Let $MoT(r)$ be the $N\times N$ mesh of trees, where $N=2^{r}$. For each
maximal geodesic $P$ of $MoT(r)$ there exists an $8$-cycle $C$ such that $P$
contains at least one blue vertex and one red vertex of $C$.

###### Proof.

Similarly as in the proof of Proposition 3.2 we note that no internal vertex
of a complete binary tree (either blue or red) is an end-vertex of a maximal
geodesic of $MoT(r)$. Therefore, end-vertices of any maximal geodesic of
$MoT(r)$ must lie in $8$-cycles of $MoT(r)$. Given a maximal geodesic $P$, we
distinguish the following three cases.

  * Case I - $P$ lies entirely inside an $8$-cycle $C$. Since $P$ is maximal, it must be of length 4. Thus, $P$ contains at least one blue vertex and one red vertex of $C$.

  * Case II - $P$ intersects exactly two $8$-cycles $C_{1}$ and $C_{2}$. In other words, $P$ starts in $C_{1}$, passes through vertices of a complete binary tree and ends in $C_{2}$. It is clear that both cycles $C_{1}$ and $C_{2}$ are in a single row or in a single column (see Fig. 4, where (a) and (b) represent the cases, where two cycles are in the same row and column, respectively). Without loss of generality, suppose that $P$ connects the cycles $C_{1}$ and $C_{2}$ via vertices of a red complete binary tree (case (a) in the figure). If no blue vertex in $C_{1}$ is contained in $P$, then at most two vertices in $C_{1}$ are contained in $P$ (a red vertex and possibly a white vertex). However, since $P$ is a maximal geodesic, this implies that at least four vertices from $C_{2}$ are contained in $P$, one of which is blue. In either case, a blue and a red vertex of some $8$-cycle are contained in $P$. (For the case (b) in the figure one uses symmetric arguments.)

Figure 4: Case II of Lemma 3.3.

  * Case III - $P$ intersects more than two $8$-cycles. In this case, the cycles $C_{1}$ and $C_{2}$, which contain end-vertices of $P$, are not in the same column nor in the same row. Indeed, if $C_{1}$ and $C_{2}$ are in the same row (respectively column), then all maximal geodesics that go from a vertex in $C_{1}$ to a vertex in $C_{2}$ pass through red (respectively, blue) vertices of the corresponding complete binary tree that connects $C_{1}$ with $C_{2}$. Consequently, we are in Case II, where only two $8$-cycles are involved in $P$. Therefore, there exists an $8$-cycle $C$, different from $C_{1}$ and $C_{2}$, such that $P$ enters into $C$ through a red (respectively, blue) vertex of $C$ and exits $C$ in a blue (respectively, red) vertex of $C$.

This concludes the proof. ∎

######  Theorem 3.4.

If $MoT(r)$ is an $N\times N$ mesh of trees, where $N=2^{r}$, then ${\rm
gt}(G)=2^{2r-1}$.

###### Proof.

As noted in the proof of Lemma 3.3, end-vertices of any maximal geodesic in
the graph lie in $8$-cycles. There are $2^{r-1}\cdot 2^{r-1}$ such vertex-
disjoint $8$-cycles in $G$. Each $8$-cycle $C$ contains four maximal geodesics
between white vertices, two connecting each pair of antipodal white vertices.
Clearly, to hit these four maximal geodesics of $C$, one needs at least two
vertices in $C$. Since the $8$-cycles are vertex-disjoint, we infer ${\rm
gt}(G)\geq 2\cdot(2^{r-1}\cdot 2^{r-1})$ = $2^{2r-1}$.

Let $R$ denote the set of all red vertices of all $8$-cycles in $MoT(r)$. By
Lemma 3.3, $R$ is a geodesic transversal of $MoT(r)$. There are $2^{r}$ row
(red) complete binary trees in $MoT(r)$, and each of the binary trees contains
$2^{r-1}$ red vertices in $8$-cycles. Hence, $|R|=2^{r}\cdot
2^{r-1}=2^{2r-1}$, and we infer ${\rm gt}(G)\leq 2^{2r-1}$. ∎

##  4 Geodesic transversal and leaf attachment operations

In this section, we consider two operations of attaching leaves to vertices of
a graph, which behave nicely with respect to geodesic packing. In particular,
the second operation will be applied in the next section for determining the
geodesic transversal number of silicate networks.

The first operation, known as corona of the graph, is defined as follows.
Given a graph $G$, let ${\rm cor}(G)$ be the graph with $V({\rm
cor}(G))=V(G)\cup\\{v^{\prime}:\,v\in V(G)\\}$ and $E({\rm
cor}(G))=E(G)\cup\\{vv^{\prime}:\,v\in V(G)\\}$. In other words, to each
vertex $v$ of $G$ we attach a leaf $v^{\prime}$ and get the corona, ${\rm
cor}(G)$, of $G$. Note that in the literature one can also find the notation
$G\circ K_{1}$ for the corona of $G$.

Using the notation of West [18], $\alpha^{\prime}(G)$ stands for the matching
number of a graph $G$, that is, the size of a largest matching in $G$. Also,
$\beta(G)$ is the standard notation for the vertex cover number of $G$, which
is the smallest set of vertices that hit all edges of $G$.

######  Proposition 4.1.

If $G$ is a graph, then ${\rm gpack}({\rm cor}(G))=\alpha^{\prime}(G)$ and
${\rm gt}({\rm cor}(G))=\beta(G)$.

###### Proof.

Let $M$ be a maximum matching in $G$. Then the collection of paths

${\cal P}=\\{(x^{\prime},x,y,y^{\prime}):\,xy\in M,\textrm{ and
}x^{\prime}\textrm{ (}y^{\prime})\textrm{ is the leaf neighbor of }x\textrm{
(}y,\textrm{ respectively)}\\}$

is a geodesic packing of ${\rm cor}(G)$. This implies ${\rm gpack}({\rm
cor}(G))\geq\alpha^{\prime}(G)$. For the reverse inequality, note that the
end-vertices of every maximal geodesic in ${\rm cor}(G)$ are leaves that are
attached to distinct vertices of $G$. Now, if $P$ and $Q$ are two disjoint
maximal geodesics in ${\rm cor}(G)$, then they pass two distinct edges of $G$,
which have no end-vertex in common. Hence, the size of a geodesic packing of
${\rm cor}(G)$ is not larger than the size of a maximum matching in $G$, which
proves the first equality of the proposition.

For the second equality note that the set of vertices forming a vertex cover
in $G$ is a geodesic transversal in ${\rm cor}(G)$. Hence, ${\rm gt}({\rm
cor}(G))\leq\beta(G)$. If a set $S\subset V({\rm cor}(G))$ is smaller than
$\beta(G)$, then it is easy to see that there exists an edge $xy\in E(G)$,
such that $\\{x,y,x^{\prime},y^{\prime}\\}\cap S=\emptyset$, where
$x^{\prime}$ ($y^{\prime}$) is the leaf attached to $x$ ($y$, respectively).
Since $(x^{\prime},x,y,y^{\prime})$ is a maximal geodesic in ${\rm cor}(G)$,
we infer that $S$ is not a geodesic transversal in ${\rm cor}(G)$. Thus, ${\rm
gt}({\rm cor}(G))\geq\beta(G)$, and the proof is complete. ∎

By the famous König-Egervary theorem, which states that
$\alpha^{\prime}(G)=\beta(G)$ in any bipartite graph $G$, we get the following
consequence of Proposition 4.1.

######  Corollary 4.2.

If $G$ is a bipartite graph, then ${\rm gpack}({\rm cor}(G))={\rm gt}({\rm
cor}(G))$.

The second operation of this section is defined as follows. Given a graph $G$,
let $M$ be a (not necessarily maximum) matching in $G$, $V(M)$ the set of end-
vertices of edges from $M$, and let $N$ = $V(G)-V(M)$. See Fig. 5. Let $G_{M}$
be the graph obtained from $G$ by attaching a single leaf to each vertex in
$V(M)$, and attaching two leaves to each vertex of $N$. In other words,
$V(G_{M})$ = $V(G)\cup\\{x^{\prime}:\,x\in
V(M)\\}\cup\\{u^{\prime},u^{\prime\prime}:\,u\in N\\}$, while
$E(G_{M})=E(G)\cup$ $\\{xx^{\prime}:\,x\in
V(M)\\}\cup\\{uu^{\prime},uu^{\prime\prime}:\,u\in N\\}$.

Figure 5: (a) An example graph $G$. (b) The red edges form a matching $M$. (c)
Graph $G_{M}$: to each vertex incident with an edge of $M$ a leaf is attached,
to other vertices two leaves are attached.

######  Proposition 4.3.

If $G$ is a graph, and $M$ a matching in $G$, then ${\rm
gpack}(G_{M})=|V(G)|-|M|$. If, in addition, there exists $M^{\prime}\subset
V(M)$ such that each edge in $M$ has exactly one end-vertex in $M^{\prime}$,
and $M^{\prime}$ is independent in $G$, then ${\rm gt}(G_{M})=|V(G)|-|M|$.

###### Proof.

First, we present maximal geodesics that partition $V(G_{M})$. There are two
types of these maximal geodesics. First, for any $xy\in M$, let
$P_{xy}=(x^{\prime},x,y,y^{\prime})$ be the path from the leaf neighbor of $x$
to the leaf neighbor of $y$. Second, for any $u\in N$, let
$P_{u}=(u^{\prime},u,u^{\prime\prime})$ be the path from one leaf neighbor of
$u$ to the other leaf neighbor of $u$. Clearly, $P_{xy}$ and $P_{u}$ are
maximal geodesics for every $xy\in M$ and every $u\in N$. In addition, ${\cal
P}=\\{P_{xy}:\,xy\in M\\}\cup\\{P_{u}:\,u\in N\\}$ is a collection of vertex
disjoint maximal geodesics such that each vertex of $G_{M}$ belongs to exactly
one of these geodesics. Clearly, $|{\cal P}|=|M|+|N|$, which implies ${\rm
gpack}(G_{M})\geq|M|+|N|$. On the other hand, note that any geodesic between
any pair of distinct leaves is a maximal geodesic of $G_{M}$. Since there are
$2|M|+2|N|$ leaves in $G_{M}$, we get ${\rm gpack}(G_{M})\leq|M|+|N|$.
Combining both inequalities, we infer

${\rm gpack}(G_{M})=|M|+|N|.$

Since $2|M|+|N|=|V(G)|$, we get ${\rm gpack}(G_{M})=|V(G)|-|M|$.

By Observation 2, we immediately get ${\rm gt}(G_{M})\geq|M|+|N|$. To prove
the second statement in the proposition we present a geodesic transversal of
$G_{M}$ with $|M|+|N|$ vertices. By the assumption of the statement, there
exists $M^{\prime}\subset V(M)$ such that each edge in $M$ has exactly one
end-vertex in $M^{\prime}$, and $M^{\prime}$ is independent in $G$. Let
$M^{\prime\prime}=V(M)\setminus M^{\prime}$, and we claim that $N\cup
M^{\prime\prime}$ gives the desired result.

######  Claim 4.4.

$N\cup M^{\prime\prime}$ is a geodesic transversal of $G_{M}$.

###### Proof.

(of Claim) Let $P$ be a maximal geodesic in $G_{M}$, and let $v$ be one of its
end-vertices. As noted earlier in this proof, $v$ is a leaf. If $v$ is
adjacent to a vertex in $M^{\prime\prime}\cup N$, then we are done. Otherwise,
the neighbor $v_{1}$ of $v$ is an end-vertex of an edge in $M$, and $v_{1}\in
M^{\prime}$. Since $v_{1}$ is adjacent to only one leaf, we infer that the
neighbor $v_{2}$ of $v_{1}$ that lies on $P$ is not a leaf. Since $M^{\prime}$
is independent, we infer that $v_{2}\in M^{\prime\prime}\cup N$. Hence $P$ is
hit by $v_{2}$, which proves the claim. $(\blacksquare)$

By Claim 4.4, we infer ${\rm gt}(G_{M})\leq|M|+|N|$, implying ${\rm
gt}(G_{M})=|M|+|N|=|V(G)|-|M|$. ∎

##  5 Hexagonal silicate sheets

An $SiO_{4}$ tetrahedron consists of one silicon atom and 4 oxygen atoms,
where the silicon atom is bonded to the 4 oxygen atoms. See Fig. 6. A silicate
sheet is a $2$-dimensional array of $SiO_{4}$ tetrahedra [4]. Two tetrahedra
of a silicate sheet are linked together through a shared oxygen atom. In a
silicate sheet, every silicon atom has exactly 4 oxygen bonds and every oxygen
atom has at most 2 silicon bonds. A silicate sheet is formed by linking each
tetrahedron to at most three other tetrahedra. In Fig. 6, the oxygen nodes are
in red color and the silicon nodes are in light blue color. Chemists [9, 17]
do not consider the “bond between two oxygen nodes” as an edge because the
bond is weak. An edge of a silicate sheet is the bond between a silicon node
and an oxygen node. The bonds between two oxygen nodes are ignored and are not
considered as edges.

Figure 6: (a) Hexagonal carbon nanosheet (b) Silicate sheet derived from
hexagonal carbon nanosheet. Red vertices are oxygen atoms and blue vertices
are silicon atoms.

An $r$-layer hexagonal carbon nanosheet was defined and studied by Deng et al.
[6]. Three examples of hexagonal carbon nanosheets are displayed in Fig. 7.
Formally, a hexagonal carbon nanosheet consists of the central hexagon and
$r-1$ layers of hexagons around it. We mention that Deng et al. [6] call the
hexagonal carbon nanosheet as zigzag-graphene (6-Z-HGNS), while Xiaoxiao and
Zhang [19] call it a hexagonal model with alternate B- and N-terminated edges.

Figure 7: (a) 1-layer hexagonal carbon nanosheet, denoted by $C$. (b)
$2$-layer hexagonal carbon nanosheet. (c) $3$-layer hexagonal carbon
nanosheet.

Next, we present the smoothing operation, which is used in the definition of
the main concept of this section. Given a vertex $v$ of degree $2$ in $G$, let
$x$ and $y$ be the neighbors of $v$ in $G$. Smoothing a vertex $v$ is the
operation of removing the vertex $v$ and adding edge $xy$ to the graph $G$
[11].

######  Definition 5.1.

Let $H$ denote a silicate sheet (Fig. 6), and let ${\rm SM}(H)$ be the graph
obtained from $H$ by smoothing all $2$-degree vertices of $H$. If the graph
obtained from ${\rm SM}(H)$ by deleting all the pendant vertices of ${\rm
SM}(H)$ is an $r$-layer hexagonal carbon nanosheet (see Fig. 7), then $H$ is
an $r$-layer hexagonal silicate sheet.

Figure 8: The $3$-layer hexagonal carbon nanosheet $G$ with $C$ as the central
hexagon of $G$. The edges of the matching $M$ are red.

######  Theorem 5.2.

If $H$ is an $r$-layer hexagonal silicate sheet, then ${\rm gpack}(H)={\rm
gt}(H)$.

###### Proof.

Let $G$ be the $r$-layer hexagonal carbon nanosheet, where $C$ is the central
hexagon of $G$ (see Fig. 7). Let us consider the following matching in $G$:
$M$ = {$xy\in E(G):d(x,C)=2k$ and $d(y,C)$ = $2k+1$, where
$k\in\\{0,1,\dots,r-1\\}$} (see Fig. 8). Given a graph $G$ and a matching $M$,
the respective graph $G_{M}$ is defined in Section 4. Note that $G_{M}$ and
${\rm SM}(H)$ are isomorphic graphs. In addition, the set $M^{\prime}=\\{x\in
V(M):\,d(x,C)\textrm{ is odd}\\}$ is independent, hence enjoying the
conditions in Proposition 4.3. Thus, ${\rm gpack}(G_{M})$ = ${\rm gpack}({\rm
SM}(H))$ = ${\rm gt}(G_{M})$ = ${\rm gt}({\rm SM}(H))$. Since ${\rm gt}({\rm
SM}(H))$ = ${\rm gt}(H)$ and ${\rm gpack}({\rm SM}(H))$ = ${\rm gpack}(H)$, we
conclude that ${\rm gpack}(H)$ = ${\rm gt}(H)$. ∎

Let $G$ be an $r$-layer hexagonal carbon nanosheet, and $M$ the matching as
defined above. Then $|M|=6(1+\ldots+r-1)=3(r^{2}-r)$. In addition,
$|V(H)|=6r^{2}$, cf. also [5]. Now, it is straightforward to see:

${\rm gt}(H)=|V(H)|-|M|=6r^{2}-3(r^{2}-r)=3(r^{2}+r).$

##  6 Conclusion

In this paper, we solved the geodesic transversal problem for the well-known
parallel architecture mesh of trees and some important chemical structures
such as silicate networks and carbon nanosheets. We demonstrated some of the
challenges of this combinatorial problem. In addition, see Fig. 9, which
presents three basic types of grids (of size $7\times 5$) in which the problem
behaves very differently. The geodesic transversal problem is trivial for the
$2$-dimensional square grids, where the geodesic transversal number equals $2$
(see Proposition 3.1). But the geodesic transversal problems for semi-diagonal
grids and diagonal grids seem to be more difficult and remain open. We believe
that ${\rm gt}(G)=r+s-1$ where $G$ is an $r\times s$-dimensional semi-diagonal
or diagonal grid.

Figure 9: (a) Square grid. (b) Semi-diagonal grid. (c) Diagonal grid.

While we believe these two cases are solvable, the geodesic transversal
problem in more complex product graphs and many other relevant classes of
graphs offer further challenging problems.

In addition, the complexity status of this problem is unknown for intersection
graphs such as chordal graphs, circular-arc graphs, permutation graphs etc and
Cayley graphs such as wrapped butterfly, circulant graphs, shuffle-exchange
etc.

## Acknowledgments

This work was supported and funded by Kuwait University, Research Grant No.
(QI 01/20).

## References

  * [1] P. Boothe, Z. Dvořák, A. Farley, A. Proskurowski, Graph covering via shortest paths, Congressus Numerantium 87 (2007) 145–155.
  * [2] M. Cavaleri, D. D’Angeli, A. Donno, S. Hammer, Wiener, edge-Wiener, and vertex-edge-Wiener index of Basilica graphs, Discrete Appl. Math. 307 (2022) 32–49.
  * [3] H. Chen,L. Chao, The expected values of Wiener indices in random polycyclic chains, Discrete Appl. Math. 315 (2022) 104–109.
  * [4] E. Chigo, A. Bautista-Hernández, M. Castro, G.H. Cocoletzi, Investigating the electronic properties of silicon nanosheets by first-principles calculations, Journal of Molecular Modeling 18 (2011) 2147–2152.
  * [5] M.-S. Chen, K.G. Shin, D. Kandlur, Addressing, routing, and broadcasting in hexagonal mesh multiprocessors, IEEE Transactions on Computers 39 (1990) 10–18.
  * [6] J.-P. Deng, W.-H Chen, S.P. Chiu, C.-H. Lin, B.-C. Wang, Edge-termination and core-modification effects of hexagonal nanosheet graphene, Molecules 19 (2014) 2361–2373.
  * [7] R. Hammack, W. Imrich, S. Klavžar, Handbook of product graphs, 2nd ed., Boca Raton (FL), CRC Press, 2011.
  * [8] A.E. Holroyd, I. Marcovici, J.B. Martin, Percolation games, probabilistic cellular automata, and the hard-core model, Probability Theory and Related Fields 174(3) (2019) 1187–1217.
  * [9] V. Kahlenberg, R. Kaindl, D.M. Többens, The crystal structure of the interrupted framework silicate K9.6Ca1.2Si12O30 determined from laboratory X-ray diffraction data, Journal of Solid State Chemistry 179(7) (2006) 1948–1956.
  * [10] F.T. Leighton, Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, Morgan Kaufmann, San Mateo (Ca), 1991.
  * [11] P. Manuel, B. Brešar, S. Klavžar, The geodesic-transversal problem, Applied Mathematics and Computation 413 (2022) 126621.
  * [12] P. Manuel, B. Rajan, I. Rajasingh, A. Alaguvel, Tree Spanners, Cayley Graphs and Diametrically Uniform Graphs, Lecture Notes in Computer Science 2280 (2003) 333–345.
  * [13] I. Peterin, G. Semanišin, On maximal shortest paths cover, Mathematics 9 (2021) 1592.
  * [14] I. Peterin, G. Semanišin, On maximal shortest paths cover number of join and lexicographic product of graphs, manuscript, September 17, 2020.
  * [15] Z.-Y. Shi, H. Tang, Z. Feng, Y. Wang, Z.-M. Li, J. Gao, Y.-J. Chang, T.-Y. Wang, J.-P. Dou, Z.-Y. Zhang, Z.-Q. Jiao, W.-H. Zhou, X.-M. Jin, Quantum fast hitting on glued trees mapped on a photonic chip, Optica 7 (2020) 613–618.
  * [16] S. Spiro, The Wiener index of signed graphs, Appl. Math. Comput. 416 (2022) 126755.
  * [17] S. Tesson, M. Salanne, B. Rotenberg, S. Tazi, V. Marry, A Classical Polarizable Force Field for Clays: Pyrophyllite and Talc. Journal of Physical Chemistry C, American Chemical Society 120(7) (2016) 3749–3758.
  * [18] D.B. West, Introduction to graph theory, Prentice Hall, Upper Saddle River (N.J), 2001.
  * [19] F. Xiaoxiao, R.-Q. Zhang, Energetics of hexagonal boron nitride nanostructures: edge dependence and truncation effects, Nanoscale 9 (2017) 6734–6740.
  * [20] J. Xu, Topological Structure and Analysis of Interconnection Networks, Springer, 2001.
  * [21] J. Xu, D. Li, Y. Chen, L. Tan, B. Kou, F. Wan, W. Jiang, F. Li, Carbon Nitride/Reduced Graphene Oxide/Layered MnO2 Ternary Nanocomposite with Outstanding Catalytic Properties on Thermal Decomposition of Ammonium Perchlorate, Nanomaterials 7 (2017) 450.


#  Isospectral deformation of the reduced quasi-classical self-dual Yang–Mills
equation

Oleg I. Morozov<EMAIL_ADDRESS>Faculty of Applied Mathematics,AGH
University of Science and Technology,
Mickiewicza 30, Cracow 30-059, Poland

###### Abstract

We derive new four-dimensional partial differential equation with the
isospectral Lax representation by shrinking the symmetry algebra of the
reduced quasi-classical self-dual Yang–Mills equation. Then we find a
recursion operator for the obtained equation and construct Bäcklund
transformations between this equation and the reduced quasi-classical self-
dual Yang–Mills equation as well as the four-dimensional Martínez
Alonso–Shabat equation

###### keywords:

integrable partial differential equation, Lax representation , symmetry
algebra , extension of Lie algebra

###### MSC:

[2010] 17B65 , 17B80 , 17B56 , 22E70

##  1 Introduction

Integrable partial differential equations (pdes) play an important role in
modern physics and mathematics. While there are many non-equivalent
definitions of integrability (see discussion in [48, 31]), the most universal
perspective seems to be one based on the construction of Lax representations,
which is the starting point for a number of powerful techniques for studying
pdes such as inverse scattering transformations for solitonic equations,
Bäcklund transformations, recursion operators, nonlocal symmetries and
conservation laws, Darboux transformations, see [46, 47, 37, 11, 1, 30, 40, 3]
and references therein. The systematic and convenient framework for dealing
with these nonlocal geometric structures is provided by the theory of
differential coverings introduced by A.M. Vinogradov in [44] and then
elaborated in [20, 21], see also [16, 45, 19].

From both theoretical and practical viewpoints, of the most significance are
pdes that admit isospectral Lax representations, in other words, differential
coverings with non-removable (spectral) parameter. Such equations are quite
rare, especially in the multi-dimensional case, i.e., when the number of
independent variables is greater than 2. For examples of four-dimensional pdes
with isospectral Lax representations see [6, 4, 7, 10, 32, 36, 2, 42, 5] and
references therein.

The challenging unsolved problem in the theory of integrable equations is to
find conditions that are formulated in inherent terms of a pde under study and
ensure existence of a Lax representation. Recently, an approach to this
problem has been proposed in [33, 34, 35], where we show that for some pdes
their Lax representations can be inferred from the second twisted cohomology
group of the contact symmetry algebras. In paricular, paper [35] contains
examples exhibiting that for some multi-dimensional pdes their isospectral Lax
representations are related to the distinguished structure of the symmetry
algebras. Namely, in these examples the symmetry algebra of the pde is of the
form
$\mathfrak{a}_{\diamond}\ltimes(\mathbb{R}_{n}[h]\otimes\mathfrak{a}_{\infty})$,
where $\mathfrak{a}_{\diamond}$ is a finite-dimensional Lie algebra with
nontrivial second twisted cohomology group, $\mathfrak{a}_{\infty}$ is an
infinite-dimensional Lie algebra, and
$\mathbb{R}_{n}[h]=\mathbb{R}[h]/(h^{n+1}=0)$ is the (commutative associative
unital) algebra of truncated polynomials of the formal variable $h$. Moreover,
in [35] we show that the series of extensions of the symmetry algebra
generated by maps
$\mathbb{R}_{n}[h]\mapsto\mathbb{R}_{n+1}[h]\mapsto\mathbb{R}_{n+2}[h]\mapsto\dots$
produces the integrable hierarchy associated with the pde under the study. It
is natural to ask what happens when one shrinks the symmetry algebra of this
type via replacing $\mathbb{R}_{n}[h]$ by $\mathbb{R}_{n-1}[h]$. This idea was
exploited in [22], where for some four-dimensional integrable Monge–Ampère
equations of Hirota type we have derived a number of their “symmetric
deformations”, that is, equations whose symmetry algebras are constructed by
omitting some graded components of the symmetry algebra of the initial
equation. The obtained equations turn out to admit Lax representations of both
isospectral and and non-isospectral types.

In the present paper we combine the techniques of [22] and [33, 34, 35] and
consider the reduced quasi-classical self-dual Yang–Mills equation

$u_{yz}=u_{tx}+u_{y}\,u_{xx}-u_{x}\,u_{xy},$ (1)

which admits the isospectral Lax representation

$\left\\{\begin{array}[]{lcl}s_{t}&=&\lambda\,s_{y}-u_{y}\,s_{x},\\\
s_{z}&=&(\lambda-u_{x})\,s_{x}\end{array}\right.$ (2)

derived in [6]. In [35] we show that this Lax representation can be inferred
from the structure of the Lie algebra of contact symmetries of this equation.
This algebra is isomorphic to the semi-direct product
$\mathfrak{q}_{3}=\mathfrak{q}_{\diamond}\ltimes\mathfrak{q}_{3,\infty}$ of
the 6-dimensional Lie algebra $\mathfrak{q}_{\diamond}$ and the infinite-
dimensional ideal $\mathfrak{q}_{3,\infty}$, which is the tensor product
$\mathbb{R}_{2}[h]\otimes\mathfrak{w}[t,z]$ of the (associative commutative
unital) algebra of truncated polynomials
$\mathbb{R}_{2}[h]=\mathbb{R}[h]/(h^{3}=0)$ and the Lie algebra
$\mathfrak{w}[t,z]=\langle
t^{i}z^{j}\,\partial_{z}\,\,|\,\,i,j\in\mathbb{N}_{0}\rangle$. The subalgebra
$\mathfrak{q}_{\diamond}$ has one-dimensional second twisted cohomology group,
and the non-trivial 2-cocycle generates an extension
$\widehat{\mathfrak{q}}_{3}$ for $\mathfrak{q}_{3}$. The Maurer–Cartan (mc)
forms of this extension provide the Wahlquist–Estabrook form for the Lax
representation (2).

In this paper we construct the pde that is defined by the shrunk Lie algebra
$\mathfrak{q}_{2}=\mathfrak{q}_{\diamond}\ltimes\left(\mathbb{R}_{2}[h]\otimes\mathfrak{w}[t,z]\right)$.
This Lie algebra admits the extension $\widehat{\mathfrak{q}}_{2}$ generated
by non-trivial twisted 2-cocycle of $\mathfrak{q}_{\diamond}$. We show that
the mc forms of $\widehat{\mathfrak{q}}_{2}$ provide Lax representations that
define equation

$u_{ty}=u_{y}\,u_{xz}-u_{z}\,u_{xy}+y\,u_{yz}.$ (3)

This equation, to the best of our knowledge, has not yet appeared in the
literature. We show that one of the the Lax representations of (3) contains
non-removable spectral parameter. This allowed us to find a recursion operator
for symmetries of (3).

By the construction, equation (3) can be considered as an integrable
deformation of equation (1). Notice that (3) is not invariant with respect to
the translation $y\mapsto y+\epsilon$, while (1) admits this transformation as
a symmetry. Likewise, equation (3) can be considered as a deformation of the
four-dimensional Martínez Alonso–Shabat equation [25, 26, 32]

$u_{ty}=u_{y}\,u_{xz}-u_{z}\,u_{xy}.$ (4)

This equation is related to equation (1) by the Bäcklund transformation [22].
We construct a Bäcklund transformation between equations (3) and (1) and thus
we show that equations (3) and (4) are related by a Bäcklund transformation.
Notice that the contact symmetry algebras of equations (1), (3), and (4) are
pairwise non-isomorphic, therefore these equations are pairwise non-equivalent
with respect to the pseudogroup of contact transformations.

##  2 Preliminaries

###  2.1 Symmetries and differential coverings

The presentation in this subsection closely follows [17, 18], see also [20,
21, 45]. Let
$\pi\colon\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$,
$\pi\colon(x^{1},\dots,x^{n},u^{1},\dots,u^{m})\mapsto(x^{1},\dots,x^{n})$, be
a trivial bundle, and $J^{\infty}(\pi)$ be the bundle of its jets of the
infinite order. The local coordinates on $J^{\infty}(\pi)$ are
$(x^{i},u^{\alpha},u^{\alpha}_{I})$, where $I=(i_{1},\dots,i_{n})$ are multi-
indices, and for every local section
$f\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}\times\mathbb{R}^{m}$ of $\pi$
the corresponding infinite jet $j_{\infty}(f)$ is a section
$j_{\infty}(f)\colon\mathbb{R}^{n}\rightarrow J^{\infty}(\pi)$ such that
$u^{\alpha}_{I}(j_{\infty}(f))=\displaystyle{\frac{\partial^{\\#I}f^{\alpha}}{\partial
x^{I}}}=\displaystyle{\frac{\partial^{i_{1}+\dots+i_{n}}f^{\alpha}}{(\partial
x^{1})^{i_{1}}\dots(\partial x^{n})^{i_{n}}}}$. We put
$u^{\alpha}=u^{\alpha}_{(0,\dots,0)}$. Also, we will simplify notation in the
following way, e.g., in the case of $n=4$, $m=1$: we denote $x^{1}=t$,
$x^{2}=x$, $x^{3}=y$, $x^{4}=z$ and $u^{1}_{(i,j,k,l)}=u_{{t\dots t}{x\dots
x}{y\dots y}{z\dots z}}$ with $i$ times $t$, $j$ times $x$, $k$ times $y$, and
$l$ times $z$.

The vector fields

$D_{x^{k}}=\frac{\partial}{\partial x^{k}}+\sum\limits_{\\#I\geq
0}\sum\limits_{\alpha=1}^{m}u^{\alpha}_{I+1_{k}}\,\frac{\partial}{\partial
u^{\alpha}_{I}},\qquad k\in\\{1,\dots,n\\},$

$(i_{1},\dots,i_{k},\dots,i_{n})+1_{k}=(i_{1},\dots,i_{k}+1,\dots,i_{n})$, are
called total derivatives. They commute everywhere on $J^{\infty}(\pi)$.

The evolutionary vector field associated to an arbitrary vector-valued smooth
function $\varphi\colon J^{\infty}(\pi)\rightarrow\mathbb{R}^{m}$ is the
vector field

$\mathbf{E}_{\varphi}=\sum\limits_{\\#I\geq
0}\sum\limits_{\alpha=1}^{m}D_{I}(\varphi^{\alpha})\,\frac{\partial}{\partial
u^{\alpha}_{I}}$

with $D_{I}=D_{(i_{1},\dots\,i_{n})}=D^{i_{1}}_{x^{1}}\circ\dots\circ
D^{i_{n}}_{x^{n}}$.

A system of pdes $F_{r}(x^{i},u^{\alpha}_{I})=0$ of the order $s\geq 1$ with
$\\#I\leq s$, $r\in\\{1,\dots,R\\}$ for some $R\geq 1$, defines the
submanifold $\mathcal{E}=\\{(x^{i},u^{\alpha}_{I})\in
J^{\infty}(\pi)\,\,|\,\,D_{K}(F_{r}(x^{i},u^{\alpha}_{I}))=0,\,\,\\#K\geq
0\\}$ in $J^{\infty}(\pi)$.

A function $\varphi\colon J^{\infty}(\pi)\rightarrow\mathbb{R}^{m}$ is called
a (generator of an infinitesimal) symmetry of equation $\mathcal{E}$ when
$\mathbf{E}_{\varphi}(F)=0$ on $\mathcal{E}$. The symmetry $\varphi$ is a
solution to the defining system

$\ell_{\mathcal{E}}(\varphi)=0,$ (5)

where $\ell_{\mathcal{E}}=\ell_{F}|_{\mathcal{E}}$ with the matrix
differential operator

$\ell_{F}=\left(\sum\limits_{\\#I\geq 0}\frac{\partial F_{r}}{\partial
u^{\alpha}_{I}}\,D_{I}\right).$

The symmetry algebra $\mathrm{Sym}(\mathcal{E})$ of equation $\mathcal{E}$ is
the linear space of solutions to (5) endowed with the structure of a Lie
algebra over $\mathbb{R}$ by the Jacobi bracket
$\\{\varphi,\psi\\}=\mathbf{E}_{\varphi}(\psi)-\mathbf{E}_{\psi}(\varphi)$.
The algebra of contact symmetries $\mathrm{Sym}_{0}(\mathcal{E})$ is the Lie
subalgebra of $\mathrm{Sym}(\mathcal{E})$ defined as
$\mathrm{Sym}(\mathcal{E})\cap C^{\infty}(J^{1}(\pi))$.

Consider $\mathcal{W}=\mathbb{R}^{\infty}$ with coordinates $w^{s}$,
$s\in\mathbb{N}_{0}$. A differential covering of $\mathcal{E}$ locally is a
trivial bundle $\tau\colon J^{\infty}(\pi)\times\mathcal{W}\rightarrow
J^{\infty}(\pi)$ equipped with extended total derivatives

$\widetilde{D}_{x^{k}}=D_{x^{k}}+\sum\limits_{s=0}^{\infty}T^{s}_{k}(x^{i},u^{\alpha}_{I},w^{j})\,\frac{\partial}{\partial
w^{s}}$

such that $[\widetilde{D}_{x^{i}},\widetilde{D}_{x^{j}}]=0$ for all $i\not=j$
whenever $(x^{i},u^{\alpha}_{I})\in\mathcal{E}$. Define the partial
derivatives of $w^{s}$ by $w^{s}_{x^{k}}=\widetilde{D}_{x^{k}}(w^{s})$. This
yields the system of covering equations

$w^{s}_{x^{k}}=T^{s}_{k}(x^{i},u^{\alpha}_{I},w^{j})$ (6)

that is compatible whenever $(x^{i},u^{\alpha}_{I})\in\mathcal{E}$. Dually,
the differential covering is defined by the Wahlquist–Estabrook forms

$dw^{s}-\sum\limits_{k=1}^{m}T^{s}_{k}(x^{i},u^{\alpha}_{I},w^{j})\,dx^{k}$
(7)

as follows: when $w^{s}$ and $u^{\alpha}$ are considered to be functions of
$x^{1}$, … , $x^{n}$, forms (7) are equal to zero whenever system (6) holds.

###  2.2 Twisted cohomology of Lie algebras

For a Lie algebra $\mathfrak{g}$ over $\mathbb{R}$, its representation
$\rho\colon\mathfrak{g}\rightarrow\mathrm{End}(V)$, and $k\geq 1$ let
$C^{k}(\mathfrak{g},V)=\mathrm{Hom}(\Lambda^{k}(\mathfrak{g}),V)$ be the space
of all $k$–linear skew-symmetric mappings from $\mathfrak{g}$ to $V$. Then the
Chevalley–Eilenberg differential complex

$V=C^{0}(\mathfrak{g},V)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}C^{1}(\mathfrak{g},V)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\dots\stackrel{{\scriptstyle
d}}{{\longrightarrow}}C^{k}(\mathfrak{g},V)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}C^{k+1}(\mathfrak{g},V)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\dots$

is generated by the differential $d\colon\theta\mapsto d\theta$ such that

$d\theta(X_{1},...,X_{k+1})=\sum\limits_{q=1}^{k+1}(-1)^{q+1}\rho(X_{q})\,(\theta(X_{1},...,\hat{X}_{q},...,X_{k+1}))$
$\quad+\sum\limits_{1\leq p<q\leq
k+1}(-1)^{p+q+1}\theta([X_{p},X_{q}],X_{1},...,\hat{X}_{p},...,\hat{X}_{q},...,X_{k+1}).$

The cohomology groups of the complex $(C^{*}(\mathfrak{g},V),d)$ are referred
to as the cohomology groups of the Lie algebra $\mathfrak{g}$ with
coefficients in the representation $\rho$. For the trivial representation
$\rho_{0}\colon\mathfrak{g}\rightarrow\mathbb{R}$, $\rho_{0}\colon X\mapsto
0$, the cohomology groups are denoted by $H^{*}(\mathfrak{g})$.

Consider a Lie algebra $\mathfrak{g}$ over $\mathbb{R}$ with non-trivial first
cohomology group $H^{1}(\mathfrak{g})$ and take a closed 1-form $\alpha$ on
$\mathfrak{g}$ such that $[\alpha]\neq 0$. Then for any $c\in\mathbb{R}$
define new differential $d_{c\alpha}\colon
C^{k}(\mathfrak{g},\mathbb{R})\rightarrow C^{k+1}(\mathfrak{g},\mathbb{R})$ by
the formula

$d_{c\alpha}\theta=d\theta-c\,\alpha\wedge\theta.$

From $d\alpha=0$ it follows that $d_{c\alpha}^{2}=0$. The cohomology groups of
the complex

$C^{1}(\mathfrak{g},\mathbb{R})\stackrel{{\scriptstyle
d_{c\alpha}}}{{\longrightarrow}}\dots\stackrel{{\scriptstyle
d_{c\alpha}}}{{\longrightarrow}}C^{k}(\mathfrak{g},\mathbb{R})\stackrel{{\scriptstyle
d_{c\alpha}}}{{\longrightarrow}}C^{k+1}(\mathfrak{g},\mathbb{R})\stackrel{{\scriptstyle
d_{c\alpha}}}{{\longrightarrow}}\dots$

are referred to as the twisted cohomology groups [38, 39] of $\mathfrak{g}$
and denoted by $H^{*}_{c\alpha}(\mathfrak{g})$.

##  3 Lie algebra $\mathfrak{q}_{2}$, its extension, and Lax representations
for equation (3)

As it was shown in [35], the structure equations for the Lie algebra of
contact symmetries of equation (1) have the form

$\left\\{\begin{array}[]{lcl}d\alpha&=&0,\\\ dB&=&\nabla_{1}(B)\wedge B,\\\
d\Gamma&=&\alpha\wedge\Gamma+\nabla_{1}(\Gamma)\wedge
B+\textstyle{\frac{1}{2}}\,\nabla_{1}(B)\wedge\Gamma,\\\
d\Theta&=&\nabla_{2}(\Theta)\wedge\Theta+h_{0}\,\nabla_{0}(\Theta)\wedge\left(\textstyle{\frac{1}{2}}\,\nabla_{1}(B)+h_{0}\,\nabla_{1}(\Gamma)-\alpha\right)\\\
&&+\nabla_{1}(\Theta)\wedge(B+h_{0}\,\Gamma),\end{array}\right.$ (8)

where

$B=\beta_{0}+h_{1}\,\beta_{1}+\textstyle{\frac{1}{2}}\,h_{1}^{2}\beta_{2},\qquad\Gamma=\gamma_{0}+h_{1}\,\gamma_{1},$
$\Theta=\sum\limits_{k=0}^{2}\sum\limits_{i=0}^{\infty}\sum\limits_{j=0}^{\infty}\frac{h_{0}^{k}h_{1}^{i}h_{2}^{j}}{i!j!}\,\theta_{k,i,j},$
(9)

and $\alpha$, $\beta_{i}$, $i\in\\{0,1,2\\}$, $\gamma_{l}$, $l\in\\{0,1\\}$,
$\theta_{k,i,j}$, $k\in\\{0,1,2\\}$, $i,j\in\mathbb{N}_{0}$, are the mc forms
of the Lie algebra $\mathfrak{q}_{3}$, while $h_{0}$, $h_{1}$, $h_{2}$ are
formal parameters such that $dh_{i}=0$ and $h_{0}^{k}=0$ for $k>2$.

Now we shrink the Lie algebra $\mathfrak{q}_{3}$ by imposing the condition
$h_{0}^{k}=0$ for $k>1$. Thus we have

$\Theta=\sum\limits_{k=0}^{1}\sum\limits_{i=0}^{\infty}\sum\limits_{j=0}^{\infty}\frac{h_{0}^{k}h_{1}^{i}h_{2}^{j}}{i!j!}\,\theta_{k,i,j}$
(10)

instead of (9) and

$\left\\{\begin{array}[]{lcl}d\alpha&=&0,\\\ dB&=&\nabla_{1}(B)\wedge B,\\\
d\Gamma&=&\alpha\wedge\Gamma+\nabla_{1}(\Gamma)\wedge
B+\textstyle{\frac{1}{2}}\,\nabla_{1}(B)\wedge\Gamma,\\\
d\Theta&=&\nabla_{2}(\Theta)\wedge\Theta+h_{0}\,\nabla_{0}(\Theta)\wedge\left(\textstyle{\frac{1}{2}}\,\nabla_{1}(B)-\alpha\right)\\\
&&+\nabla_{1}(\Theta)\wedge(B+h_{0}\,\Gamma)\end{array}\right.$ (11)

instead of (8).

System (11) implies that $H^{1}(\mathfrak{q}_{2})=\langle\,\alpha\,\rangle$,

$H_{c\,\alpha}^{2}(\mathfrak{q}_{\diamond})=\left\\{\begin{array}[]{lcl}\langle\,[\gamma_{0}\wedge\gamma_{1}]\,\rangle,&\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode\hfil&c=2,\\\
\\{[0]\\},&&c\neq 2,\end{array}\right.$

and $H_{2\,\alpha}^{2}(\mathfrak{q}_{\diamond})\subseteq
H_{2\,\alpha}^{2}(\mathfrak{q}_{2})$. Equation

$d\sigma=2\,\alpha\wedge\sigma+\gamma_{0}\wedge\gamma_{1}$ (12)

with unknown 1-form $\sigma$ is compatible with the structure equations (11).
System (11), (12) defines the structure equations for the extension
$\widehat{\mathfrak{q}}_{2}$ of the Lie algebra $\mathfrak{q}_{2}$.

Frobenius’ theorem allows one to integrate equations (11), (12) step by step.
In particular, we have

$\alpha=\frac{dq}{q},\quad\beta_{0}=a_{0}^{2}\,dt,\quad\beta_{1}=2\,\frac{da_{0}}{a_{0}}+a_{1}\,dt,\quad\beta_{2}=\frac{1}{a_{0}^{2}}\,\left(da_{1}+\textstyle{\frac{1}{2}}\,a_{1}^{2}\,dt\right),$
$\gamma_{0}=a_{0}\,q\,\,\left(dz+y\,dt\right),\quad\gamma_{1}=\frac{q}{a_{0}}\,\left(dy+\textstyle{\frac{1}{2}}\,a_{1}\,(dz+y\,dt)\right),$
$\sigma=q^{2}\,(dv-y\,dz-\textstyle{\frac{1}{2}}\,y^{2}\,dt),\quad\theta_{0,0,0}=b_{0}\,dt+b_{1}\,dx,$
$\theta_{1,0,0}=\frac{q\,b_{1}}{a_{0}}\,\left(du+b_{2}\,dt+b_{3}\,dx+b_{0}b_{1}^{-1}\,dz\right),$

where $t$, $x$, $y$, $z$, $u$, $q\neq 0$, $a_{0}\neq 0$, $a_{1}$, $b_{0}\neq
0$, $b_{1}\neq 0$, $b_{2}$, and $b_{3}$ are free parameters (‘constants of
integration’). We do not need explicit expressions for the other mc forms in
what follows.

Now we impose the condition for form $\theta_{1,0,0}-\gamma_{0}$ to be a
multiple of the contact form $du-u_{t}\,dt-u_{x}\,dx-u_{y}\,dy-u_{z}\,dz$ on
the bundle of jets of sections of the bundle
$\pi\colon\mathbb{R}^{4}\times\mathbb{R}\rightarrow\mathbb{R}^{4}$,
$\pi\colon(t,x,y,z,u)\mapsto(t,x,y,z)$, that is, we require

$\theta_{1,0,0}-\gamma_{0}=\frac{q\,b_{1}}{a_{0}}\,(du-u_{t}\,dt-u_{x}\,dx-
u_{y}\,dy-u_{z}\,dz).$

To achieve this, we rename the integration parameters as
$b_{0}=-u_{z}\,u_{y}^{-1}+\textstyle{\frac{1}{2}}\,a_{1}$, $b_{1}=u_{y}^{-1}$,
$b_{2}=-u_{t}+\textstyle{\frac{1}{2}}\,a_{1}\,y\,u_{y}$, and $b_{3}=-u_{x}$.

Then we consider form

$\tau=\sigma+c_{1}\,\beta_{0}+c_{2}\,\gamma_{0}+c_{3}\,\gamma_{1}+c_{4}\,\theta_{0,0,0}$
$=q^{2}\,\left(dv+K\,dt+\frac{c_{4}}{q^{2}\,u_{y}}\,dx+\frac{c_{3}}{a_{0}q}\,dy+\frac{c_{3}a_{1}+2\,a_{0}\,(c-2a_{0}-q\,y)}{a_{0}q}\,dz\right),$

where
$K=-2\,c_{4}a_{0}\,u_{z}+2\,c_{1}a_{0}^{3}+2\,c-2a_{0}^{2}y\,q+c-3\,a_{1}q\,y+c_{4}a_{0}a_{1}-a_{0}q^{2}y^{2}$
and $c_{1}$, … , $c_{4}\in\mathbb{R}$ are constants. Without loss of
generality we put $c_{3}=c_{4}=-1$. Then we rename the integration parameters
as

$a_{0}=-\frac{w}{u_{y}^{1/2}v_{x}^{1/2}},\quad
a_{1}=-\frac{2\,w\,(v_{z}+y-c_{2}\,w)}{u_{y}v_{x}},\quad
q=\frac{1}{u_{y}^{1/2}v_{x}^{1/2}}$

and obtain

$\tau=u_{y}\,v_{x}\,\left(dv-(u_{z}\,v_{x}+(w+y)\,v_{z}-(c_{2}+c_{1})\,w^{2}+y\,w+\textstyle{\frac{1}{2}}\,y^{2})\,dt\right.$
$\qquad\left.-v_{x}\,dx-v_{z}\,dz+u_{y}\,v_{x}\,w^{-1}\,dy\right).$

This is the restriction of the multiple of the contact form $dv-v_{t}\,dt-
v_{x}\,dx-v_{y}\,dy-v_{z}\,dz$ from the bundle of jets of sections of the
bundle $\mathbb{R}^{4}\times\mathbb{R}^{2}\rightarrow\mathbb{R}^{4}$,
$(t,x,y,z,u,v)\mapsto(t,x,y,z)$, to the submanifold defined by the over-
determined system

$\left\\{\begin{array}[]{lcl}v_{t}&=&u_{z}\,v_{x}+(w+y)\,v_{z}-(c_{2}+c_{1})\,w^{2}+y\,w+\textstyle{\frac{1}{2}}\,y^{2},\\\
v_{y}&=&-u_{y}\,v_{x}\,w^{-1}.\end{array}\right.$ (13)

The compatibility condition of this system reads $(v_{t})_{y}=(v_{y})_{t}$.
This equation entails $c_{2}+c_{1}=-\textstyle{\frac{1}{2}}$ and the following
system for $w$:

$\left\\{\begin{array}[]{lcl}w_{t}&=&u_{z}\,w_{x}+(w+y)\,w_{z}+E\,w\,u_{y}^{-1},\\\
w_{y}&=&-u_{y}\,w_{x}\,w^{-1}+1,\end{array}\right.$ (14)

where $E=u_{ty}-u_{z}\,u_{xy}+u_{y}\,u_{xz}-y\,u_{yz}$. The compatibility
condition $(w_{t})_{y}=(w_{y})_{t}$ of system (14) gives new over-determined
system

$\left\\{\begin{array}[]{lcl}E_{x}&=&(u_{xy}+1)\,u_{y}^{-1}\,E,\\\
E_{y}&=&u_{yy}\,u_{y}^{-1}\,E,\end{array}\right.$

and them condition $(E_{x})_{y}=(E_{y})_{x}$ yields $E=0$, that is, (3).
Substituting this into (14) and renaming $w=p-y$ gives the Lax representation

$\left\\{\begin{array}[]{lcl}p_{t}&=&\displaystyle{u_{z}\,p_{x}+p\,p_{z},\phantom{\frac{-u_{y}\,p_{x}}{p-y}}}\\\
p_{y}&=&\displaystyle{\frac{-u_{y}\,p_{x}}{p-y}}\end{array}\right.$ (15)

for equation (3). Notice that $p=\lambda=\mathrm{const}$ is a solution to
(15). Substituting for $w=\lambda-y$, $c_{1}+c_{2}=-\textstyle{\frac{1}{2}}$
and renaming $v=r+\textstyle{\frac{1}{2}}\,\lambda^{2}\,t$ produces another
Lax representation

$\left\\{\begin{array}[]{lcl}r_{t}&=&\displaystyle{u_{z}\,r_{x}+\lambda\,r_{z},\phantom{\frac{-u_{y}\,p_{x}}{p-y}}}\\\
r_{y}&=&\displaystyle{\frac{u_{y}\,r_{x}}{y-\lambda}}\end{array}\right.$ (16)

for (3).

Remark 1. Systems (15) and (16) are not contact equivalent, instead, they are
related in the following sense, c.f. [41, 13]: suppose that function
$P(t,x,y,z,s)$ defines function $R(t,x,y,z)$ implicitly by equation

$P(t,x,y,z,R(t,x,y,z))\equiv\lambda.$

Then $R$ is a solution to (16) iff $P$ is a solution to (15). $\diamond$

Remark 2. Parameter $\lambda$ in the Lax representation (16) is non-removable,
that is, there is no change of variable $r\mapsto\tilde{r}=f(t,x,y,z,r)$ that
elinimates $\lambda$. In accordance with [21, §§ 3.2, 3.4], [12, 8, 28, 9], to
ensure this claim it is sufficient to notice that symmetry
$\phi=u_{y}-t\,u_{z}$ of equation (3) has no lift to a symmetry of system
(16), while for the associated vector field $V=-\partial_{y}+t\,\partial_{z}$
there holds

$\mathrm{e}^{\lambda\,V}\left(dr-u_{z}\,r_{x}\,dt-
r_{x}\,dx-\frac{u_{y}\,r_{x}}{y}\,dy-r_{z}\,dz\right)$
$\qquad=dr-(u_{z}\,r_{x}+\lambda\,r_{z})\,dt-
r_{x}\,dx-\frac{u_{y}\,r_{x}}{y-\lambda}\,dy-r_{z}\,dz.$

$\diamond$

##  4 Recursion operator for symmetries

To construct a recursion operator for equation (3) we use the considerations
based on ideas of [43], cf. [14, 15, 28, 24, 29, 36, 22] also. We find shadows
for (3) in the covering defined by system (16). One of the shadows is
$s=r_{x}^{-1}$. Differentiating (16) by $x$ and substituting for
$r_{x}=s^{-1}$ yields another Lax representation

$\left\\{\begin{array}[]{lcl}s_{t}&=&\displaystyle{u_{z}\,s_{x}+\lambda\,s_{z}-u_{xz}\,s,\phantom{\frac{-u_{y}\,p_{x}}{p-y}}}\\\
s_{y}&=&\displaystyle{\frac{u_{y}\,s_{x}-u_{xy}\,s}{y-\lambda}}\end{array}\right.$
(17)

for (3). Note that $s$ is a solution to the linearization

$\widetilde{D}_{t}\widetilde{D}_{y}(\phi)=u_{z}\,\widetilde{D}_{x}\widetilde{D}_{y}(\phi)+u_{xy}\,\widetilde{D}_{z}(\phi)-u_{y}\,\widetilde{D}_{x}\widetilde{D}_{z}(\phi)-u_{xz}\,\widetilde{D}_{y}(\phi)$
$\qquad\qquad\qquad+y\,\widetilde{D}_{y}\widetilde{D}_{z}(\phi)$ (18)

of (3) with the extended total derivatives $\widetilde{D}_{t}$, … ,
$\widetilde{D}_{z}$ from the covering defined by (16). Now we put

$s=\sum\limits_{n=-\infty}^{\infty}\lambda^{n}\,s_{n}.$ (19)

Since equation (18) is independent of $\lambda$, each $s_{n}$ is a solution to
this equation as well. Substitution for (19) into (17) yields

$\left\\{\begin{array}[]{lcl}\widetilde{D}_{t}(s_{n+1})&=&\displaystyle{u_{z}\,\widetilde{D}_{x}(s_{n+1})+\widetilde{D}_{z}(s_{n})-u_{xz}\,s_{n+1},\phantom{\frac{-u_{y}\,p_{x}}{p-y}}}\\\
y\,\widetilde{D}_{y}(s_{n+1})&=&\displaystyle{u_{y}\,\widetilde{D}_{x}(s_{n+1})+\widetilde{D}_{y}(s_{n})-u_{xy}\,s_{n+1}}\end{array}\right.$

for each $n\in\mathbb{Z}$. Fixing $n$ and renaming $s_{n+1}=\psi$,
$s_{n}=\phi$, we get the recursion operators $\psi=\mathcal{R}(\phi)$ and
$\phi=\mathcal{R}^{-1}(\psi)$ defined by systems

$\left\\{\begin{array}[]{lcl}\widetilde{D}_{t}(\psi)&=&\displaystyle{u_{z}\,\widetilde{D}_{x}(\psi)-u_{xz}\,\psi+\widetilde{D}_{z}(\phi),\phantom{\frac{-u_{y}\,p_{x}}{p-y}}}\\\
\widetilde{D}_{y}(\psi)&=&\displaystyle{\frac{1}{y}\,\left(u_{y}\,\widetilde{D}_{x}(\psi)-u_{xy}\,\psi+\widetilde{D}_{y}(\phi)\right)}\end{array}\right.$
(20)

and

$\left\\{\begin{array}[]{lcl}\widetilde{D}_{y}(\phi)&=&\displaystyle{y\,\widetilde{D}_{y}(\psi)+u_{y}\,\widetilde{D}_{x}(\psi)-u_{xy}\,\psi,\phantom{\frac{-u_{y}\,p_{x}}{p-y}}}\\\
\widetilde{D}_{z}(\phi)&=&\displaystyle{\widetilde{D}_{t}(\psi)+u_{z}\,\widetilde{D}_{x}(\psi)-u_{xy}\,\psi,}\end{array}\right.$
(21)

respectively. Direct computations show that systems (20) and (21) are
compatible iff $\phi$ and $\psi$ are shadows of symmetries of equation (3) in
the covering (16).

##  5 Bäcklund transformations

Consider equation (3) written in variables $\tilde{t}$, $\tilde{x}$,
$\tilde{y}$, $\tilde{z}$, $\tilde{u}$,

$\tilde{u}_{\tilde{t}\tilde{y}}=\tilde{u}_{\tilde{y}}\,\tilde{u}_{\tilde{x}\tilde{z}}-\tilde{u}_{\tilde{z}}\,\tilde{u}_{\tilde{x}\tilde{y}}+\tilde{y}\,\tilde{u}_{\tilde{y}\tilde{z}},$
(22)

and make the following point transformation:

$\tilde{t}=t,\qquad\tilde{x}=z,\qquad\tilde{y}=q,\qquad\tilde{z}=y,\qquad\tilde{u}=-x.$
(23)

The second prolongation of this transformation maps equation (22) to equation

$q_{yz}=q_{tx}+\frac{q\,q_{y}-q_{t}}{q_{x}}\,q_{xx}+\frac{q_{z}-q\,q_{x}}{q_{x}}\,q_{xy}.$
(24)

This equation is related to the reduced quasi-classical self-dual Yang–Mills
equation (1) by a Bäcklund transformation

$\left\\{\begin{array}[]{lcl}q_{t}&=&\displaystyle{q\,q_{y}-u_{y}\,q_{x},}\\\
q_{z}&=&\displaystyle{(q-u_{x})\,q_{x}}.\end{array}\right.$ (25)

Indeed, compatibility condition $(q_{t})_{z}=(q_{z})_{t}$ of system (25)
yields (1), while from (25) we have

$\left\\{\begin{array}[]{lcl}u_{x}&=&q-q_{z}\,q_{x}^{-1},\\\
u_{y}&=&(q_{t}-q\,q_{y})\,q_{x}^{-1},\end{array}\right.$ (26)

and then $(u_{x})_{y}=(u_{y})_{x}$ gives equation (24). Thus the superposition
of transformations (23) and (25) provides the Bäcklund transformation between
equations (3) and (1).

As we have shown in [23], equation (1) is related by a Bäcklund transformation
to equation (4). Therefore equations (3) and (4) are related by a Bäcklund
transformation as well. To write this transformation explicitly we substitute
(26) into (2). The resulting system

$\left\\{\begin{array}[]{lcl}s_{t}&=&\displaystyle{\lambda\,s_{y}-\frac{q_{t}-q\,q_{y}}{q_{x}}\,s_{x},\phantom{\frac{\frac{A}{A}}{\frac{A}{A}}}}\\\
s_{z}&=&\displaystyle{\left(\lambda-\frac{q\,q_{x}-q_{z}}{q_{x}}\right)\,s_{x}\phantom{\frac{\frac{A}{A}}{\frac{A}{A}}}}\end{array}\right.$
(27)

defines a Bäcklund transformation between equation (24) and

$s_{yz}=s_{tx}+\frac{\lambda\,s_{y}-s_{t}}{s_{x}}\,s_{xx}+\frac{s_{z}-\lambda\,s_{x}}{s_{x}}\,s_{xy}.$
(28)

Then the point transformation

$t=\hat{t},\qquad x=-\hat{u},\qquad y=\hat{z}-\lambda\,\hat{t},\qquad
z=\hat{x},\qquad s=\hat{y}$ (29)

maps equation (28) to equation (4) written as

$\hat{u}_{\hat{t}\hat{y}}=\hat{u}_{\hat{y}}\,\hat{u}_{\hat{x}\hat{z}}-\hat{u}_{\hat{z}}\,\hat{u}_{\hat{x}\hat{y}}.$

Thus the superposition of transformations (23), (27), and (29) maps equation
(3) to (4).

## Acknowledgments

This work was partially supported by the Faculty of Applied Mathematics of AGH
UST statutory tasks within subsidy of Ministry of Science and Higher Education
(Poland). The author thanks UiT—the Arctic University of Norway and the TFS
project Pure Mathematics in Norway for the financial support of his visit to
Tromsø, where a part of the work was performed. I am very grateful to
professor Boris Kruglikov for his warm hospitality in Tromsø.

## References

## References

  * [1] M.J. Ablowitz, P.A. Clarkson. Solitons, Nonlinear Evolution Equations and Inverse Scattering. Cambridge University Press, Cambridge, 1991
  * [2] D. M. J. Calderbank, B. Kruglikov. Integrability via geometry: dispersionless differential equations in three and four dimensions. arXiv:1612.02753
  * [3] A. Coley, D. Levi, R. Milson, C. Rogers, P. Winternitz (eds). Bäcklund and Darboux Transformations. The Geometry of Solitons. CRM Proceedings and Lecture Notes, 28, AMS, Providence, 2001
  * [4] B. Doubrov, E.V. Ferapontov. On the integrability of symplectic Monge–Ampère equations. J. Geom. Phys., 60 (2010), 1604–1616
  * [5] B. Doubrov, E.V. Ferapontov, B. Kruglikov, V.S. Novikov. On a class of integrable systems of Monge–Ampère type. J. Math. Phys., 58 (2017), 063508
  * [6] Ferapontov E.V., Khusnutdinova K.R. Hydrodynamic reductions of multi-dimensional dispersionless PDEs: the test for integrability. J. Math. Phys., 45 (2004), 2365–2377
  * [7] E.V. Ferapontov, K.R. Khusnutdinova, C. Klein. On linear degeneracy of integrable quasilinear systems in higher dimensions. Lett. Math. Phys., 96 (2011), 5–35
  * [8] S. Igonin, J. Krasil′shchik. On one-parametric families of Bäcklund transformations. In: T. Morimoto, H. Sato, K. Yamaguchi (eds.), Lie Groups, Geometric Structures and Differential Equations — One Hundred Years After Sophus Lie. Advanced Studies in Pure Mathematics, 37, pp. 99–114. Math. Soc. Japan, Tokyo, 2002
  * [9] S. Igonin, P. Kersten, I. Krasil′shchik. On one-parametric families of Bäcklund transformations. Preprint arXiv:nlin/0010040 (2000)
  * [10] S. Igonin, M. Marvan. On construction of symmetries and recursion operators from zero- curvature representations and the Darboux–Egoroff system. J. Geom. Phys., 85 (2014), 106–123
  * [11] B.G. Konopelchenko. Nonlinear Integrable Equations. Lecture Notes in Physics, 270, Springer, 1987
  * [12] I.S. Krasil′shchik. On one-parametric families of Bäcklund transformations. Preprint DIPS-1/2000, The Diffiety Institute, Pereslavl-Zalessky (2000)
  * [13] I. Krasil′shchik. Integrability in differential coverings. J. Geom. Phys. 87 (2015), 296–304
  * [14] I. S. Krasil′shchik, P. H. M. Kersten. Deformations and recursion operators for evolution equations. in Geometry in Partial Differential Equations, World Scientific, River Edge, 1994, pp. 114–154
  * [15] I. S. Krasil′shchik, P. H. M. Kersten. Graded differential operators and their deformations: A computational theory for recursion operators. Acta Appl. Math. 41 (1995), 167–191
  * [16] I.S. Krasil′shchik, V.V. Lychagin, A.M. Vinogradov. Geometry of Jet Spaces and Nonlinear Differential Equations. Gordon and Breach, N.Y., 1986
  * [17] J. Krasil′shchik, A. Verbovetsky. Geometry of jet spaces and integrable systems. J. Geom. Phys. 61 (2011), 1633–1674
  * [18] J. Krasil′shchik, A. Verbovetsky, R. Vitolo. A unified approach to computation of integrable structures. Acta Appl. Math. 120 (2012), 199–218
  * [19] J. Krasil′shchik, A. Verbovetsky, R. Vitolo. The Symmbolic Computation of Integrability Structures for Partial Differential Equations. Springer 2017
  * [20] I.S. Krasil′shchik, A.M. Vinogradov. Nonlocal symmetries and the theory of coverings. Acta Appl. Math. 2 (1984), 79–86
  * [21] I.S. Krasil′shchik, A.M. Vinogradov. Nonlocal trends in the geometry of differential equations: symmetries, conservation laws, and Bäcklund transformations. Acta Appl. Math. 15 (1989), 161–209
  * [22] B.S. Kruglikov, O.I. Morozov. Integrable dispersionless PDEs in 4D, their symmetry pseudogroups and deformations. Lett. Math. Phys. 105 (2015), 1703–1723
  * [23] B.S. Kruglikov, O.I. Morozov. A Bäcklund transformation between the four-dimensional Martínez Alonso – Shabat and Ferapontov–Khusnutdinova equations. Theor. Math. Phys. 188 (3) (2016), 1358–1360
  * [24] A.A. Malykh, Y. Nutku, M.B. Sheftel. Partner symmetries and non-invariant solutions of 4-dimensional heavenly equations. J. Phys. A 37 (2004), 7527–7546
  * [25] L. Martínez Alonso, A.B. Shabat. Energy-dependent potentials revisited: A universal hierarchy of hydrodynamic type. Phys. Lett. A 299 (2002), 359–365
  * [26] L. Martínez Alonso, A.B. Shabat. Hydrodynamic reductions and solutions of a universal hierarchy. Theor. Math. Phys. 140 (2004), 1073–1085
  * [27] M. Marvan. Another look on recursion operators. in: Differential Geometry and Applications. (Brno 28 August – 1 September 1995, J. Janyška, I. Kolář, and J. Slovák, eds.), Masaryk Univ., Brno (1996), pp. 393–402
  * [28] M. Marvan. On the horizontal gauge cohomology and nonremovability of the spectral parameter. Acta Appl. Math. 72 (2002), 51–65
  * [29] M. Marvan, A. Sergyeyev. Recursion operators for dispersionless integrable systems in any dimension. Inverse Problems 28 (2) (2012), 025011
  * [30] V.B. Matveev, M.A. Salle. Darboux Transformations and Solitons. Springer, 1991
  * [31] A. Mikhailov (ed.) Integrability. Lecture Notes in Physics 767, Springer: Berlin, 2009
  * [32] O.I. Morozov. The four-dimensional Martínez Alonso–Shabat equation: Differential coverings and recursion operators J. Geom. Phys. 85 (2014), 75 – 80
  * [33] O.I. Morozov. Deformed cohomologies of symmetry pseudo-groups and coverings of differential equations. J. Geom. Phys. 113 (2017), 215–225
  * [34] O.I. Morozov. Deformations of infinite-dimensional Lie algebras, exotic cohomology, and integrable nonlinear partial differential equations. J. Geom. Phys. 128 (2018), 20–31
  * [35] O.I. Morozov. Lax representations with non-removable parameters and integrable hierarchies of PDEs via exotic cohomology of symmetry algebras. J. Geom. Phys. 143 (2019), 150–163
  * [36] O.I. Morozov, A. Sergyeyev. The four-dimensional Martínez Alonso–Shabat equation: reductions and nonlocal symmetries. J. Geom. Phys. 85 (2014), 40–45
  * [37] S.P. Novikov, S.V. Manakov, L.P. Pitaevskii, V.E. Zakharov. Theory of Solitons. Plenum Press, N.Y., 1984
  * [38] S.P. Novikov. On exotic De-Rham cohomology. Perturbation theory as a spectral sequence. arXiv:math-ph/0201019, 2002
  * [39] S.P. Novikov. On metric-independent exotic homology. Proc. Steklov Inst. Math. 251 (2005), 206–212
  * [40] P.J. Olver. Applications of Lie Groups to Differenial Equations. 2nd Edition, Springer, 1993
  * [41] M.V. Pavlov, J.-H. Chang, Y.-T. Chen. Integrability of the Manakov–Santini hierarchy. arXiv: 0910.2400
  * [42] M.V. Pavlov, N. Stoilov. Three dimensional reductions of four-dimensional quasilinear systems. J. Math. Phys. 58 (2017), 111510
  * [43] A. Sergyeyev. A simple construction of recursion operators for multidimensional dispersionless integrable systems. J. Math. Anal. Appl. 454 (2017), 468–480
  * [44] A.M. Vinogradov. Category of partial differential equations, in: Lecture Notes in Mathematics, 1108 (1984), Springer-Verlag, Berlin, 77–102
  * [45] A.M. Vinogradov, I.S. Krasil′shchik (eds.) Symmetries and Conservation Laws for Differential Equations of Mathematical Physics [in Russian], Moscow: Factorial, 2005; English transl. prev. ed.: I.S. Krasil′shchik, A.M. Vinogradov (eds.) Symmetries and Conservation Laws for Differential Equations of Mathematical Physics. Transl. Math. Monogr., 182, Amer. Math. Soc., Providence, RI, 1999
  * [46] H.D. Wahlquist, F.B. Estabrook F.B. Prolongation structures of nonlinear evolution equations. J. Math. Phys., 16 (1975), 1–7
  * [47] V.E. Zakharov. Integrable systems in multidimensional spaces. Lect. Notes Phys., 153 (1982), 190–216
  * [48] V. E. Zakharov (ed.) What is integrability? Springer-Verlag, Berlin, 1991


# Are PPO-ed Language Models Hackable?

Suraj Anand  David Getzen

###### Abstract

Numerous algorithms have been proposed to align language models to remove
undesirable behaviors. However, the challenges associated with a very large
state space and creating a proper reward function often result in various
jailbreaks. Our paper aims to examine this effect of reward in the controlled
setting of positive sentiment language generation. Instead of online training
of a reward model based on human feedback, we employ a statically learned
sentiment classifier. We also consider a setting where our model’s weights and
activations are exposed to an end-user after training. We examine a pretrained
GPT-2 through the lens of mechanistic interpretability before and after
proximal policy optimization (PPO) has been applied to promote positive
sentiment responses. Using these insights, we (1) attempt to "hack" the PPO-ed
model to generate negative sentiment responses and (2) add a term to the
reward function to try and alter ‘negative’ weights.

##  1 Introduction

Large language models have powerful emergent capabilities from self-supervised
training on natural datasets (Brown et al., 2020; Wei et al., 2022). This
training results in high performance next-word prediction; however, as most
are trained on large internet corpuses (Gao et al., 2020; Zhu et al., 2015),
vanilla training results in a number of undesirable behaviors such as
toxicity, bias, negative sentiment, and instruction-following failure (Sheng
et al., 2019; Gehman et al., 2020). These shortcomings have led to the use of
post-training patching to correct undesirable behaviors. Namely, various
algorithms have been proposed to align language models under the hood of
reinforcement learning from human feedback (RLHF) (Kaufmann et al., 2024).

RLHF introduces a critical online, human-in-the-loop component to the standard
language model learning paradigm. In standard reinforcement learning, an agent
attempts to make optimal decisions based off a reward function that it aims to
maximize Sutton and Barto (2018). However, specifying this reward function is
often quite challenging; sparse rewards result in the need for reward shaping
and loopholes result in the issue of reward hacking (Ng et al., 1999; Skalse
et al., 2022).

The challenges associated with creating a proper reward function often result
in various jailbreaks (Rao et al., 2024; Li et al., 2023). Our paper aims to
examine this effect of reward in the controlled setting of positive sentiment
language generation. Instead of online training of a reward model based on
human feedback, we employ a statically learned sentiment classifier. We also
consider a setting where our model’s weights and activations are exposed to an
end-user after training.

We rely on recent insights from the field of mechanistic interpretability to
jailbreak an aligned model (Olah, 2022). This field focuses on reverse-
engineering model components into human understandable algorithms, and usually
involves neuron, weight, and activation level analysis to do so. In this
discipline, we view a model as a computational graph based on soft cause-and-
effect relationships (Geiger et al., 2021). In this research, we examine a
pretrained GPT-2 through this perspective before and after reinforcement
learning has been applied. From this, we glean a causal understanding of model
changes and insight into how to potentially "hack" an aligned GPT-2. Moreover,
we attempt to utilize these insights to modify our reward function by adding a
loss term that targets certain weights in our model.

Our main contributions are:

  1. 1.

We analyze what causal changes PPO results in on GPT-2 at an activation and
weight level.

  2. 2.

We attempt to engineer a methodology that circumvents these changes to output
negative sentiment sequences.

  3. 3.

We experiment with the reward function to try and mitigate this jailbreak.

Figure 1: Our controlled setup employs a pretrained GPT-2 model to generate
sequences (rollouts) and a DistilBERT classifier to evaluate the sentiment
(reward).

##  2 Related Works

Our contributions build upon recent and concurrent research in the field.
(Gehman et al., 2020) establishes the urgency of toxicity avoidance as a
problem space, showcasing the ease with which pre-trained language models
generate outputs reflecting toxic sentiment given prompts of any kind.

A framework for leveraging word vectors to capture sentiment is presented in
(Maas et al., 2011b), wherein sentiment polarity annotations, such as metrics
that correspond to reviews or critiques, are utilized in the generation of
sentiment predictions with significant success. This project additionally
introduces a sizable dataset of movie reviews extracted from the service IMDb
to be used within the context of sentiment classification.

We are motivated by the mechanistic unalignment methodology found in (Lee et
al., 2024). This research discovered that a model aligned with Direct
Preference Optimization to avoiding toxicity in its outputs accomplishes
favorable returns only by learning an offset. As such, the model avoids
internal representations of vectors that would trigger output toxicity rather
but does not remove toxic weights altogether. We extend this research to (1)
consider positive sentiment generation, (2) examine PPO, and (3) introduce a
loss function to attempt to remedy this shortcoming.

We build off internal representation translation work that began with
nostalgebraist (2020), which introduced a "Logit Lens", or an un-embedding
mechanism that allows the projection of token representations from an
intermediate embedding space to a final vocabulary space, enabling the
observation of tokens that are generated in each subsequent embedding layer
within a transformer-based language model. A closer glimpse at the internal
behavior of a transformer-based language model is found in (Geva et al., 2022)
where it was observed that tokens are hierarchically ordered through each sub-
update in the feed-forward embedding layers of transformer-based language
models, with each intermediary output token being assigned a certain value-
vector $v_{\mathbf{i}}$ corresponding to the probability of its expression in
the next embedding layer.

Within the context of our project, we aimed to leverage the method proposed by
Geva et al. (2022) as a means of finding weights with negative sentiment, then
inflating their corresponding activations to promote their associated concepts
within the final output of a pretrained, transformer-based language model, un-
aligning the impact of PPO on fitting it to the task of output toxicity.

##  3 Preliminaries

We borrow much of the transformer and vocabulary space notation from Lee et
al. (2024) and Geva et al. (2022) to express our experiments.

###  3.1 Transformers

We employ an encoder-only transformer-based language model. Transformers
consist of an embedding layer, $E\in\mathbb{R}^{|V|\times d}$, a series of $L$
transformer layers, and then an unembedding layer $U\in\mathbb{R}^{|V|\times
d}$ which can be tied to the embedding layer (Vaswani et al., 2023). Each
layer $\ell$ consists of multiple attention heads as well as a multilayer
perceptron (MLP) layer.

Given a sequence of input $w=\\{w_{0},\ldots,w_{t}\\}$, the transformer first
applies $E$ to create an embedding $x_{i}\in\mathbb{R}^{d}$ for each token
$w_{i}\in w$.

This representation is then updated by attention heads and MLP blocks each
layer that follows:

$x_{i+1}^{\ell}=x_{i}^{\ell}+\mathrm{MLP}^{\ell}(x_{i}^{\ell}+\mathrm{Att}^{\ell}(x_{i}^{\ell}))$

We denote this token-wise representation as the "residual stream," following
previous literature. In our encoder-only GPT structure, the updates to the
residual stream from each MLP block are able to be further decomposed into two
linear transformations with nonlinear activations in between:

$\mathrm{MLP}^{\ell}(x^{e})=\sigma\left(\mathbf{W}_{K}^{\ell}x^{e}\right)\mathbf{W}_{V}^{\ell}$

where
$\mathbf{W}_{K}^{\ell},\mathbf{W}_{V}^{\ell}\in\mathbb{R}^{d_{\mathrm{mlp}}\times
d}$. We call the $i$-th row in $\mathbf{W}_{K}^{\ell}$ as
$\mathrm{MLP}_{i}^{\ell}x^{e}$ and refer to them as key-vectors, and the
$i$-th column in $\mathbf{W}_{V}^{\ell}$ as value-vectors (we sometimes omit
“MLP” and just use $k_{i}^{\ell},v_{i}^{\ell}$). The output of MLP blocks is
the sum of its value vectors $v_{i}$, each scaled by a coefficient value
$m_{i}^{\ell}$, where
$m_{i}^{\ell}=\sigma\left(\mathbf{W}_{K}^{\ell}x^{e}\right)_{i}$.

###  3.2 Vocabulary Space Translation

Geva et al. (2022) demonstrate that as the residual stream is processed, each
value vector $v_{i}$ either promotes or suppresses the likelihood of a token
$w$ to be generated:

$p\left(w\mid
x^{e}+m_{i}^{\ell}v_{i}^{\ell},E\right)\propto\exp\left(e_{w}\cdot
x^{e}\right)\cdot\exp\left(e_{w}\cdot m_{i}^{\ell}v_{i}^{\ell}\right)$

where $e_{w}$ is the embedding of $w$. As such, when $e_{w}\cdot
m_{i}^{\ell}v_{i}^{\ell}>0$ we see that the likelihood of $w$ increases, while
$e_{w}\cdot m_{i}^{\ell}v_{i}^{\ell}<0$ decreases the likelihood of
$w$.111Note that $e_{w}\cdot v_{i}^{\ell}$ does not depend on the input and it
is only when $v_{i}^{\ell}$ is scaled by $m_{i}^{\ell}$ result in any change
to output distribution.

###  3.3 Reward Function for PPO

The objective of Proximal Policy Optimization (PPO) is to maximize a reward
function $r(\theta)$ using a policy $\pi_{\theta}$ parameterized by $\theta$
(Schulman et al., 2017b). Given a static reward model $R(w)$ (our sentiment
classifier) on GPT-2, where $w$ represents a sequence of tokens generated by
the model, the reward function can be defined as follows:

$r(\theta)=\mathbb{E}_{w\sim\pi_{\theta}}[R(w)]$

PPO seeks to maximize this reward while keeping the policy changes between
updates constrained, to avoid large deviations from the existing policy. The
probability of generating a sequence $w$ under policy $\pi_{\theta}$ is
denoted as $\pi_{\theta}(w)$.

####  3.3.1 PPO Objective

The PPO objective $L(\theta)$ can be expressed as:

$L(\theta)=\mathbb{E}_{w\sim\pi_{\theta_{\mathrm{old}}}}\left[\min\left(\frac{\pi_{\theta}(w)}{\pi_{\theta_{\mathrm{old}}}(w)}A(w),\mathrm{clip}\left(\frac{\pi_{\theta}(w)}{\pi_{\theta_{\mathrm{old}}}(w)},1-\epsilon,1+\epsilon\right)A(w)\right)\right]$

where:

  * •

$A(w)$ is an advantage function that estimates how much better $w$ is compared
to other possible sequences.

  * •

$\epsilon$ is a hyperparameter controlling the clipping range.

The above objective ensures that policy updates are made conservatively to
prevent large changes, which aligns the PPO policy to the static reward model
without major changes to output distribution. The rewards as rollout is
calculated are KL penalties and the final reward after the EOS token adds the
sample score. This is a simpler and more efficient way to limit policy changes
compared to TRPO (Schulman et al., 2017a).

###  3.4 Combined PPO Reward Function

To combine the reward function $r(\theta)$ with the PPO objective, the final
reward function can be expressed as:

$r_{\text{ppo}}(\theta)=L(\theta)+\lambda_{1}\mathbb{E}_{w\sim\pi_{\theta}}[R(w)]$

where $\lambda_{1}$ is a hyperparameter balancing the two components of the
reward function.

Figure 2: Histogram of sentiment of responses in heldout test set pre and post
PPO the GPT-2.

##  4 Sentiment in GPT-2

Throughout our experimental process, we used a GPT2 model fine-tuned on the
Stanford Natural Language Processing Large Movie Review Dataset, which
consisted of 50,000 highly polar film reviews extracted from the service IMDb.
The dataset assessed the sentiment of a review as either "positive" or
"negative".

###  4.1 Negative Weights

With section 3.2 as a preface, we assessed negativity in weights by examining
the value-vectors corresponding to each token.

To do so, we trained a linear probe to discern negativity on the last-layer
internal representations of sentences (created by token-wise averaging) from
the IMDb sentiment dataset (Maas et al., 2011a). We extracted the vector
$W_{\text{neg}}$ from the probe weight. This is the vector orthogonal to the
hyperplane that separates negative and positive sentiment representations. To
find the value-vectors $v_{l}^{i}$ affiliated with the most negative tokens
consisted of finding those with the highest cosine similarity to
$W_{\text{neg}}$ generated from the $k$ most negative value weights within the
leveraged dataset.

Consulting table 1, it can be discerned that a group of the most negative
weights, or those with the highest cosine similarity with our negative probe
vector, correspond to sets of tokens comprised of phrases that reflect
significantly negative sentiment. Each token-set has a negatively-ranked
value-vector assignment, and this particular group of the most negative token-
sets are positioned across layers 6 through 9 of our pre-trained, un-aligned
GP2 model. Interestingly, we found that the vast majority of ‘negative’ value
vectors were located in the second half of the layers in the model.

Table 1: ‘Negative’ Weights in GPT-2 and the PPO-ed GPT-2 mapped into the vocabulary space by using the method proposed by Geva et al. (2022) Layer | Index | GPT-2 | PPO-ed GPT-2
---|---|---|---
7 | 2394 | useless, mediocre, worthless | useless, mediocre, worthless
6 | 2360 | unus, disastrous, deteriorated | unus, disastrous, deteriorated
9 | 3047 | negligible, diminished, fewer | negligible, diminished, fewer
7 | 2464 | fail, Fail, Wrong | fail, Fail, Wrong
8 | 2635 | bad, horrendous, problematic | bad, horrendous, problematic
9 | 484 | insufficientlessness, inability, incorrect | insufficientlessness, inability, incorrect

##  5 Promoting Positivity with PPO

We perform PPO (described in section 3.3) in order to promote positive
sentiment responses by GPT-2. In our formulation, we employ a DistilBERT (Sanh
et al., 2020) finetuned on the IMDb sentiment dataset to classify sentiment as
our reward model. We employ the trlx library to perform this reinforcement
learning (Havrilla et al., 2023). We find that the average sentiment score
across a heldout prompt set was 0.27 for the original model and 0.80 on the
PPO-ed model. This shows that our model can now successfully generate positive
sentiment responses to a diverse set of input prompts.

To get a better understanding of what changed under the hood, we perform a
mechanistic analysis of the pre and post PPO-ed model. This helps us causally
determine how the model was changed, and whether its alignment with the task
of output toxicity occured only due to learning an offset that would enable
the avoidance of toxicity-activating vectors. With a finer glimpse into how
positivity is promoted by a PPO-finetuned GPT-2, a foundation for efforts
toward preventing its mechanistic un-alignment with respect to a given task
can be formed.

Figure 3: Weights are minimally changed by Proximal Policy Optimization of the
full GPT-2 model.

###  5.1 Weights are Minimally Altered

As evident by fig. 3, the weights of GPT-2 are only very slightly modified by
PPO. In fact, almost all modified weights remain at a cosine similarity of
$\geq 0.9998$ with their original values. It was surprising to us that this
little of a change to weights can cumulatively result in a change in behavior
toward positive sentiment results. Additionally, we ran experiments where only
a subset of layers were allowed to change with PPO (2 layers, 4 layers). In
these experiments, the cosine similarity values were slightly lower, but still
well over 0.9995 for the significant majority.

###  5.2 Negative Weights Remain

We find that the ‘negative’ weights discovered earlier in our research remain
almost completely unchanged in table 1. This suggests that PPO learns a
wrapper around the model that is similar to the offset that is found in Lee et
al. (2024). This is suboptimal as it means that negative concepts may still be
stored within the model’s weights which are not removed from PPO. However, it
is expected as PPO used a clipped objective that tries to make only very small
changes to the policy.

Moreover, this suggests that we might be able to still promote concepts in the
negative sentiment space by simplying scaling up the coefficients $m_{i}^{l}$
that correspond to each negative value vector (or similarly by increasing the
activation after this vector). We test this intervention in the following
section.

Figure 4: (Left) Logit lens shows that negative concept activations scaled
down across model residual stream (this is specifically for the word sh*t).
(Right) The activation differences for the ten most ‘negative’ value vectors.

###  5.3 Activations Change

We utilize the logit lens method to determine the extent of negative concept
activation change over time (nostalgebraist, 2020). Essentially, to do this,
we take the softmax of $Ux^{l}_{i+1}$ (i.e. the unembedding matrix multiplied
by the residual stream of the next token at layer $i$). We find a common trend
that concepts overall were less promoted in the residual stream after PPO.
This is consistent with the fact that our PPO successfully results in positive
sentiment changes. Interestingly, we find that this change in concept
promotion happens throughout the model when all layers are fine-tuned, rather
than simply in the last couple of layers.

In addition, we quantify how much the activations change from before and after
PPO for a heldout set of the negative response generating prompts for the top
$k$ ‘negative’ value vectors. To do this, we simply take the delta of the two
values. The results can be seen in fig. 4. Surprisingly, the activations are
not consistently lower magnitude, but instead some ‘negative’ weights are
activated to a higher degree. We hypothesize that this might be due to the
fact that there is some randomness in the weight selection; moreover, we still
find that overall ‘negative’ concepts are promoted less in the residual
stream. Thus, even though some activations might be higher, in total they
result in less strength in the residual stream.

###  5.4 Activation Scaling

To "hack" PPO, we try scaling the key values that correspond to each of the
top $k$ negative value vectors by a factor of 10 to promote negative concepts
in the unembeddings space to be added to the residual stream. We were slightly
unsure whether this would work due to our strange results in section 5.3. What
we found was that this did effectively promote negative concepts and revert
the positive changes of PPO. The mean sentiment on our heldout test set went
from 0.80 to 0.43, which signifies that we effectively jailbroke the model to
generate negative sentiment outputs. Note that this required access to the
weights a priori.

###  5.5 Regularization

To mitigate the issue that our model simply wraps computation to avoid stored
‘negative’ weights rather than removing ‘negative’ weights, we add a term to
the reward function that rewards this behavior. In a simple depiction, this
can be thought of as

$r=r(\mathbf{\Theta})-\lambda_{1}r_{KL}$

$\downarrow$

$r=r(\mathbf{\Theta})-\lambda_{1}r_{KL}+\lambda_{2}\sum_{w\in\mathbf{N}}\|w-w_{\text{original}}\|$

where $w\in\mathbf{N}$ are the negative weights in the negative weight set,
where this set has a cardinality of 10. We altered trlx code in our to get
this functionality possible. We chose a $\lambda_{2}=10^{-4}$, but played
around with it a little bit. We added this reward to the end of the rollout
(at the same time the positive sentiment reward is calculated). We were able
to achieve results that altered the weights, but were not able to find a
stable hyperparameter that was a good medium between (1) altering the weights
enough to meaningfully store remove the negative information and (2)
maintaining the stability of the output distribution. When the parameter for
removing negative weights was too high, it would cause instability in the
output generation and break natural language function. Overall, we think that
this is a good approach, but need to better conduct a more rigorous and fine-
grained search over the hyperparameter space of $\lambda_{2}$

##  6 Discussion

In this work, we studied a mechanistic account of how reinforcement learning
alignment algorithms alter models. We specifically took PPO, and its use as an
alignment algorithm in fitting a pre-trained GPT2 to the task of avoiding
negative sentiment, as a case study. To do so, we uncovered how negative
sentiment is represented and elicited in a pre-trained language model.
Applying the insights provided into the use of value-vectors within the
context of transformer-based language models by (Geva et al., 2022), we found
numerous vectors in MLP blocks that promote negative sentiment, for which
subtracting these vectors from the residual stream can suppress negative
outputs. We then applied PPO to our language model to alter model weights to
promote positive sentiment outputs successfully. Finally, we studied how our
aligned GPT-2 averts negative sentiment. Rather than removing ‘negative’
weights, the PPO-ed GPT-2 alters the activations of a number of very, very
small changes to the weights, but in a manner that is somewhat surprising to
us. That is, the activations of a few negative weights were somewhat higher
after the application of PPO. However, with this as an exception, weights that
corresponded to toxicity were, on average, promoted less throughout the
progression of the residual stream. While the specific behavior of the PPO-ed
GPT2 differed somewhat from the DPO-centered findings of (Lee et al., 2024),
the overall potential for un-alignment, or "hackability", was demonstrated
nonetheless in our findings due to a similar tendency of PPO to facilitate
only an avoidance of toxic activation regions in a transformer-based language
model.

This enables the model to preserve its pretrained behavior while averting
negative outputs. This is expected as PPO results in small policy changes that
minimally change the output distribution.

Given this understanding, we show how to "hack" the alignment of the PPO-ed
GPT-2. That is, we simply increase the regions that elicit negative sentiment
by scaling their corresponding key vectors. We find this hack successful.
Finally, we attempt to alter the reward signal with mechanistic information to
remove negative stored weights from our model. This methodology showed
promise, but a more intensive hyperparameter search is necessary in order to
balance stability of natural language output distribution generation and
removing negative weights.

Overall, this was a mechanistic case study for how Proximal Policy
Optimization alters models, whether we can jailbreak these models, and one
simple attempt to patch this. We hope that in the future this can act as a
stepping stone to more robust alignment algorithms.

## Acknowledgements

We conducted this research as the final project for CSCI2951F: Learning and
Sequential Decision Making at Brown University. This research was conducted
using computational resources and services at the Center for Computation and
Visualization, Brown University.

## References

  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  _CoRR_ , abs/2005.14165, 2020.  URL https://arxiv.org/abs/2005.14165.
  * Gao et al. (2020) Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy.  The pile: An 800gb dataset of diverse text for language modeling, 2020.
  * Gehman et al. (2020) Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A. Smith.  RealToxicityPrompts: Evaluating neural toxic degeneration in language models.  In Trevor Cohn, Yulan He, and Yang Liu, editors, _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 3356–3369, Online, November 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.findings-emnlp.301.  URL https://aclanthology.org/2020.findings-emnlp.301.
  * Geiger et al. (2021) Atticus Geiger, Hanson Lu, Thomas Icard, and Christopher Potts.  Causal abstractions of neural networks, 2021.
  * Geva et al. (2022) Mor Geva, Avi Caciularu, Kevin Wang, and Yoav Goldberg.  Transformer feed-forward layers build predictions by promoting concepts in the vocabulary space.  In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 30–45, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.emnlp-main.3.  URL https://aclanthology.org/2022.emnlp-main.3.
  * Havrilla et al. (2023) Alexander Havrilla, Maksym Zhuravinskyi, Duy Phung, Aman Tiwari, Jonathan Tow, Stella Biderman, Quentin Anthony, and Louis Castricato.  trlX: A framework for large scale reinforcement learning from human feedback.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 8578–8595, Singapore, December 2023. Association for Computational Linguistics.  doi: 10.18653/v1/2023.emnlp-main.530.  URL https://aclanthology.org/2023.emnlp-main.530.
  * Kaufmann et al. (2024) Timo Kaufmann, Paul Weng, Viktor Bengs, and Eyke Hüllermeier.  A survey of reinforcement learning from human feedback, 2024.
  * Lee et al. (2024) Andrew Lee, Xiaoyan Bai, Itamar Pres, Martin Wattenberg, Jonathan K. Kummerfeld, and Rada Mihalcea.  A mechanistic understanding of alignment algorithms: A case study on dpo and toxicity, 2024.
  * Li et al. (2023) Haoran Li, Dadi Guo, Wei Fan, Mingshi Xu, Jie Huang, Fanpu Meng, and Yangqiu Song.  Multi-step jailbreaking privacy attacks on chatgpt, 2023.
  * Maas et al. (2011a) Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts.  Learning word vectors for sentiment analysis.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 142–150, Portland, Oregon, USA, June 2011a. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/P11-1015.
  * Maas et al. (2011b) Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts.  Learning word vectors for sentiment analysis.  In Dekang Lin, Yuji Matsumoto, and Rada Mihalcea, editors, _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 142–150, Portland, Oregon, USA, June 2011b. Association for Computational Linguistics.  URL https://aclanthology.org/P11-1015.
  * Ng et al. (1999) A. Ng, Daishi Harada, and Stuart J. Russell.  Policy invariance under reward transformations: Theory and application to reward shaping.  In _International Conference on Machine Learning_ , 1999.  URL https://api.semanticscholar.org/CorpusID:5730166.
  * nostalgebraist (2020) nostalgebraist.  Interpreting gpt: The logit lens, 2020.  Accessed on 2024-04-06.
  * Olah (2022) Chris Olah.  Mechanistic interpretability, variables, and the importance of interpretable bases.  https://www.transformer-circuits.pub/2022/mech-interp-essay, 2022.
  * Rao et al. (2024) Abhinav Rao, Sachin Vashistha, Atharva Naik, Somak Aditya, and Monojit Choudhury.  Tricking llms into disobedience: Formalizing, analyzing, and detecting jailbreaks, 2024.
  * Sanh et al. (2020) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter, 2020.
  * Schulman et al. (2017a) John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel.  Trust region policy optimization, 2017a.
  * Schulman et al. (2017b) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms, 2017b.
  * Sheng et al. (2019) Emily Sheng, Kai-Wei Chang, Premkumar Natarajan, and Nanyun Peng.  The woman worked as a babysitter: On biases in language generation.  In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan, editors, _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3407–3412, Hong Kong, China, November 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-1339.  URL https://aclanthology.org/D19-1339.
  * Skalse et al. (2022) Joar Skalse, Nikolaus Howe, Dmitrii Krasheninnikov, and David Krueger.  Defining and characterizing reward gaming.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 9460–9471. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/3d719fee332caa23d5038b8a90e81796-Paper-Conference.pdf.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement Learning: An Introduction_.  The MIT Press, second edition, 2018.  ISBN 978-0-262-03924-6.
  * Vaswani et al. (2023) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need, 2023.
  * Wei et al. (2022) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus.  Emergent abilities of large language models, 2022.
  * Zhu et al. (2015) Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , pages 19–27, 2015.  doi: 10.1109/ICCV.2015.11.