Jae-baek Lee
J. Lee: University of Victoria, Canada
Jonathan A. Noel
J. Noel: University of Victoria, Canada
Mark Siggers
M. Siggers: Kyungpook National University, Republic of Korea
The last author was supported by Korean NRF Basic Science Research Program (2018-R1D1A1A09083741) funded by the Korean government (MEST)
and the Kyungpook National University Research Fund.

Recolouring Homomorphisms to triangle-free reflexive graphs

[2010]Primary 05C15; Secondary 05C85

For a graph $H$, the $H$-recolouring problem $\operatorname{Recol}(H)$ asks, for two given homomorphisms from a given  graph $G$ to $H$, if one can get between them by a sequence of homomorphisms of $G$ to $H$ in which consecutive homomorphisms differ on only one vertex.  We show that, if $G$ and $H$ are reflexive and $H$ is triangle-free, then this problem can be solved in polynomial time.   This shows, at the same time, that the closely related $H$-reconfiguration problem $\operatorname{Recon}(H)$ of deciding whether two given homomorphisms from a given graph $G$ to $H$ are in the same component of the Hom-graph $\operatorname{{Hom}}(G,H)$, can be solved in polynomial time for triangle-free reflexive graphs $H$.

§ INTRODUCTION

Reconfiguration, in various settings, is the common notion of moving between solutions of a combinatorial problem via small changes; see van den Heuvel [van den Heuvel, 2013] and Nishimura [Nishimura, 2018] for detailed surveys. For example, a reconfiguration, or recolouring, between two graph colourings is a sequence of colourings in which consecutive elements differ on one vertex.

The $k$-recolouring problem is to decide, for two given $k$-colourings of $G$, whether or not there is a
recolouring between them.  Cereceda, van den Heuvel and Johnson [Cereceda et al., 2011] showed that $3$-recolouring is polynomial time solvable, while Bonsma and Cereceda [Bonsma and Cereceda, 2009] showed that $k$-recolouring is $\PSPACE$-complete for $k \geq 4$.  One should compare this to the $k$-colouring problem which is well known to be polynomial time solvable for $k=2$ but $\NP$-complete for $k \geq 3$.

The $k$-colouring problem generalizes to the $H$-colouring problem $\Col(H)$ for a graph $H$ and to the constraint satisfaction problem $\CSP(\cH)$ for a relational structure $\cH$. The computational complexity of $\Col(H)$, and its myriad of generalizations and variations, have been well studied over the last 50 years, culminating in the recent CSP dichotomy theorem of Bulatov [Bulatov, 2017] and Zhuk [Zhuk, 2020], which says that $\CSP(\cH)$ is either
polynomial time solvable or $\NP$-complete for every relational structure $\cH$.

Analogously, the $k$-recolouring problem also generalizes to reconfiguration problems for $H$-colourings and CSP, both of which are well studied; see, e.g., [Wrochna, 2015, Brewster et al., 2016, Lee et al., 2020, Brewster et al., 2020, Brewster et al., 2018] and [Gopalan et al., 2009, Makino et al., 2011, Makino et al., 2010, Cardinal et al., 2020, Mouawad et al., 2017, Bonsma et al., 2014, Schwerdtfeger, 2012, Hatanaka et al., 2018], respectively. In particular, Gopalan et al.  [Gopalan et al., 2009] proved a dichotomy theorem for the reconfiguration variation of $\CSP(\cH)$ for structures $\cH$ with two vertices. In this paper, we focus on the complexity of $H$-colouring reconfiguration in the setting of graphs which are reflexive in the sense that they have a loop on every vertex; graphs with no loops at all are called irreflexive. While such problems are also interesting for digraphs [Brewster et al., 2018], in this paper we restrict our attention mainly to symmetric (i.e. undirected) graphs.

Recall that a homomorphism $\phi:G \to H$ from a graph $G$ to a graph $H$ is an edge-preserving vertex map. It is also known as an $H$-colouring of $G$ due to the fact that a $K_k$-colouring of $G$, for the irreflexive clique $K_k$, is equivalent to a $k$-colouring. A recolouring between two $H$-colourings of an irreflexive graph $G$ is a sequence of $H$-colourings in which consecutive elements differ on one vertex. If $G$ has loops, then a recolouring is defined in the same way, but with the added restriction that, in any given step, the image of a reflexive vertex can only move to a neighbour of its previous image. An instance $(G, \phi, \psi)$ of the $H$-recolouring problem $\recol(H)$ consists of a graph $G$ and two $H$-colourings of $G$; the task is to decided whether or not there is a recolouring between them.

The Hom-graph $\bHom(G,H)$ for two graphs $G$ and $H$ has the set of all homomorphisms from $G$ to $H$ as its vertex set, and two homomorphisms $\phi$ and $\psi$ are adjacent if, for all edges $uv$ in $G$, $\phi(u)\psi(v)$ is an edge in $H$. It has been observed by several authors (e.g. [Wrochna, 2015, Brewster and Noel, 2015]) that, for undirected graphs, the $H$-recolouring problem is essentially the same as asking whether there is a path between a given pair of homomorphisms in $\bHom(G,H)$; we call this the $H$-reconfiguration problem and denote it by $\recon(H)$. In one direction, any path from $\phi$ to $\psi$ in $\bHom(G,H)$ can be converted into a path in which any two consecutive $H$-colourings differ on one vertex by simply changing the colours “one at a time.” In the other direction, if $(G,\phi,\psi)$ is a YES instance for $\recol(H)$, then the sequence of colourings is a path from $\phi$ to $\psi$ in $\bHom(G,H)$ unless there exists an isolated vertex $v$ of $G$ with a loop which is mapped to different components of $H$ by $\phi$ and $\psi$.[In contrast, it is interesting to remark that the problems $\recol(H)$ and $\recon(H)$ are not so closely related in the digraph case. For given $H$ they may have different sets of connected YES instances; though we do not have examples yet where they have different complexity [Brewster et al., 2018].] While we will state our results in terms of $\recol(H)$ in the introductory sections, in the later sections it is convenient to speak in terms of paths in the graph $\bHom(G,H)$,  and when we do so, we talk of $\recon(H)$ and reconfigurations rather than $\recol(H)$ and recolourings.

The diameter of $\bHom(G,H)$ can be superpolynomial in $|V(G)|$ (see, e.g., [Bonsma and Cereceda, 2009]) and so, a priori, a YES instance of $\recol(H)$ may not have a certificate of polynomial size. Thus, the natural complexity class for $\recol(H)$ is $\PSPACE$, rather than  $\NP$.

Some of the known results for irreflexive graphs are summarized as follows. The case that $H$ is a clique follows from the results of [Bonsma and Cereceda, 2009, Cereceda et al., 2011] for $k$-recolouring discussed earlier. In [Brewster et al., 2016], the dichotomy for cliques was generalized to `circular cliques' $G_{p/q}$; specifically, $\recol(G_{p/q})$ is polynomial time solvable if $p/q < 4$ and $\PSPACE$-complete if $p/q \geq 4$. The polynomial time algorithm for $3$-recolouring in [Cereceda et al., 2011] had a topological flavor which Wrochna distilled and extended in [Wrochna, 2015] to prove the very general result that $\recol(H)$ is polynomial time solvable for any graph $H$ not containing a $4$-cycle. In [Lee et al., 2020], we proved that, if $H$ is a $K_{2,3}$-free quadrangulation of the sphere different from the $4$-cycle, then $\recol(H)$ is $\PSPACE$-complete.

In the current paper, we use several ideas of these earlier papers, and adapt Wrochna's language and many of his ideas, to prove an analogue of his result for reflexive graphs $G$ and $H$. Reflexive graphs are actually a smoother setting for some of these ideas; e.g. the fact that two consecutive vertices in a path in $G$ can map to the same vertex of $H$ eliminates a parity obstruction which turns up in [Wrochna, 2015].  We prove the following.

If $H$ is a reflexive triangle-free graph, then $\recol(H)$ can be solved in polynomial  time for reflexive instances.

In contrast, we recently proved in [Lee et al., 2020] that $\recol(H)$ is $\PSPACE$-complete when $H$ is any $K_4$-free reflexive triangulation of the sphere, other than a triangle itself. We refer to this paper for a deeper suggestion of the connection of topology to the complexity of the reconfiguration problem. We remark that the argument of Wrochna [Wrochna, 2015] directly generalizes to get that $\recol(H)$ is solvable in polynomial time for general instances if $H$ is a graph which may have loops on some vertices which does not contain a $4$-cycle, a triangle with a loop on one vertex, or two adjacent vertices with loops; see the footnote on p. 330 of [Wrochna, 2020].

Before we move on to the proof of the main theorem, we observe that it implies the following result for a less general class of graphs $H$, but more general instances. Recall that the girth of a graph is the length of its shortest cycle.

If $H$ is a reflexive symmetric graph with girth at least $5$, then $\recol(H)$ can be solved in polynomial time for all instances.

Let $(G,\phi,\psi)$ be an instance of $\recol(H)$. If $G$ has isolated vertices, then we can simply change the colour of every such vertex $v$ from $\phi(v)$ to $\psi(v)$ at the beginning without any issues. So, we assume that $G$ has no isolated vertices.

Let $G'$ be the graph obtained from $G$ by adding
all possible loops. We claim that the instance
$(G',\phi,\psi)$ of $\recol(H)$ is a YES  instance if and only if $(G,\phi,\psi)$ is a YES instance.  In one direction, it is clear that if $(G',\phi,\psi)$ is a YES instance, then so is

Now, suppose that $(G,\phi,\psi)$ is a YES instance. Then there is a path from $\phi$ to $\psi$ in $\bHom(G,H)$ in which consecutive $H$-colourings differ on one vertex. It suffices to consider the case that $\phi$ and $\psi$ differ on one vertex $x$, from which the general case follows. If $\phi\psi$ is an edge of $\bHom(G',H)$, then we are done; so, we assume that it is not. Since $\phi$ and $\psi$ only differ on $x$, the only way that $\phi\psi$ can be an edge of $\bHom(G,H)$ and not $\bHom(G',H)$ is if $x$ had no loop in $G$ and $\phi(x) \nsim \psi(x)$. Observe that $\phi(x)\phi(y)\psi(x)$ is walk in $H$ for any
neighbour $y$ of $x$ in $G'$. If there are neighbours $y$ and $z$ of $x$ such that $\phi(y) \neq \phi(z)$, then $\phi(x)\phi(y)\psi(x)\phi(z)$ forms a $4$-cycle in $H$. Therefore, $\phi$ maps all neighbours of $x$ to
the same vertex of $H$. Let $y$ be any neighbour of $x$ in $G$ (which exists, as $x$ is not isolated). Let $\phi'$ be the map obtained from $\phi$ by changing the colour of $x$ to $\phi(y)$. Then we have $\phi \sim \phi' \sim \psi$ in $\bHom(G',H)$. Thus, there is a recolouring between $\phi$ and $\psi$.

§ OUTLINE OF PROOF

We assume, throughout the rest of the paper, that $H$ is a triangle-free reflexive graph and that $G$ is a reflexive graph. We also assume that $G$ and $H$ are connected; otherwise, we could simply deal with each component separately. Let $\phi$ and $\psi$ be two $H$-colourings of $G$. Our goal is to present an algorithm to determine, in polynomial time, whether there is a recolouring between $\phi$ and $\psi$ or, equivalently, whether there is a $(\phi,\psi)$-reconfiguration—a walk from $\phi$ to $\psi$ in $\bHom(G,H)$.

The main obstructions to the existence of a $(\phi,\psi)$-reconfiguration in $\bHom(G,H)$ are related to the ways in which $\phi$ and $\psi$ map the cycles (or, more generally, closed walks) of $G$ into $H$. Of course, for any cycle $C$ of $G$, a $(\phi,\psi)$-reconfiguration in $\bHom(G,H)$ yields a $(\phi_C,\psi_C)$-reconfiguration $W_C$ in $\bHom(C,H)$ between the restrictions $\phi_C$ and $\psi_C$ of $\phi$ and $\psi$ to $C$. If the length of $C$ is equal to $mk$ for some $m\geq1$ and $k\geq4$ and $\phi$ maps $C$ exactly $m$ times around an induced cycle of length $k$ in $H$, then, since $H$ is triangle-free, $\phi_C$ is an isolated vertex of $\bHom(C,H)$; such a cycle $C$ is said to be a tight cycle of $\phi$. All homomorphisms in the same component of $\bHom(G,H)$ as $\phi$ must agree on the vertices of every tight cycle (or, more generally, tight closed walk). If $\psi$ does not agree with $\phi$ on some such vertex, then we can conclude that the desired reconfiguration does not exist.

A more subtle obstruction comes from cycles in $G$ which “wind around” a given induced cycle of $H$ in a non-tight way. As a specific example, for $k\geq4$, imagine that a cycle $C$ of length $3k+100$ is mapped by $\phi$ three times around an induced cycle $C'$ of length $k$ in $H$ in such a way that the final $100$ vertices are all mapped to the same vertex as the $(3k)$th vertex of $C$; note that this is a homomorphism of $C$ to $H$ because $H$ is reflexive. In this case, the cycle $C$ is not tight under $\phi$ and so $\phi_C$ is not isolated in $\bHom(C,H)$. In particular, the “slack” introduced by the 100 extra vertices allows $\phi_C$ to be reconfigured to any homomorphism which wraps $C$ three times around $C'$ in the same direction as $\phi_C$ does. Moreover, unlike in the tight case, the image of $C$ is not constrained to stay within $C'$. However, since $H$ is triangle-free, the ways in which the image of a vertex $v\in V(C)$ can “leave” the set $V(C')$ under a walk in $\bHom(C,H)$ starting with $\phi_C$ are heavily restricted. Any homomorphism in the same component of $\bHom(C,H)$ as $\phi_C$ essentially wraps $C$ three times around the cycle $C'$ in the same direction as $\phi_C$ does, with the exception of a few “excursions” which leave $V(C')$ for a few steps and then return to $C'$ by doubling back along essentially the same route; see Figure <ref> for an illustration and Lemma <ref> for a more formal statement and proof of this fact.

(0,0) node (cprime)$C'$
(90:) node [smallvert,label=[label distance=0pt]90:] (v1)
(162:) node [smallvert,label=[label distance=0pt]162:] (v2)
(234:) node [smallvert,label=[label distance=0pt]234:] (v3)
(306:) node [smallvert,label=[label distance=0pt]306:] (v4)
(378:) node [smallvert,label=[label distance=0pt]378:] (v5)
[very thick](v1)–(v2)–(v3)–(v4)–(v5)–(v1);

(90:) node [smallvert,label=[label distance=0pt]90:] (v11)
(147:) node [smallvert,label=[label distance=0pt]162:] (v20)
(162:) node [smallvert,label=[label distance=0pt]162:] (v21)
(177:) node [smallvert,label=[label distance=0pt]162:] (v22)
(234:) node [smallvert,label=[label distance=0pt]234:] (v31)
(253:) node [smallvert,label=[label distance=0pt]234:] (v32)
(291:) node [smallvert,label=[label distance=0pt]306:] (v40)
(306:) node [smallvert,label=[label distance=0pt]306:] (v41)
(321:) node [smallvert,label=[label distance=0pt]306:] (v42)
(378:) node [smallvert,label=[label distance=0pt]378:] (v51)

(75:) node [smallvert,label=[label distance=0pt]90:] (v110)
(90:) node [smallvert,label=[label distance=0pt]90:] (v111)
(105:) node [smallvert,label=[label distance=0pt]90:] (v112)
(162:) node [smallvert,label=[label distance=0pt]162:] (v210)
(177:) node [smallvert,label=[label distance=0pt]162:] (v221)
(219:) node [smallvert,label=[label distance=0pt]234:] (v310)
(234:) node [smallvert,label=[label distance=0pt]234:] (v311)
(249:) node [smallvert,label=[label distance=0pt]234:] (v312)
(291:) node [smallvert,label=[label distance=0pt]306:] (v401)
(306:) node [smallvert,label=[label distance=0pt]306:] (v411)
(321:) node [smallvert,label=[label distance=0pt]306:] (v421)
(363:) node [smallvert,label=[label distance=0pt]378:] (v510)
(378:) node [smallvert,label=[label distance=0pt]378:] (v511)
(393:) node [smallvert,label=[label distance=0pt]378:] (v512)

(0,0) node (cprime)$C'$
(90:) node [smallvert,label=[label distance=0pt]90:] (v1)
(162:) node [smallvert,label=[label distance=0pt]162:] (v2)
(234:) node [smallvert,label=[label distance=0pt]234:] (v3)
(306:) node [smallvert,label=[label distance=0pt]306:] (v4)
(378:) node [smallvert,label=[label distance=0pt]378:] (v5)
[very thick](v1)–(v2)–(v3)–(v4)–(v5)–(v1);

(90:) node [smallvert,label=[label distance=0pt]90:] (v11)
(147:) node [smallvert,label=[label distance=0pt]162:] (v20)
(162:) node [smallvert,label=[label distance=0pt]162:] (v21)
(177:) node [smallvert,label=[label distance=0pt]162:] (v22)
(234:) node [smallvert,label=[label distance=0pt]234:] (v31)
(253:) node [smallvert,label=[label distance=0pt]234:] (v32)
(291:) node [smallvert,label=[label distance=0pt]306:] (v40)
(306:) node [smallvert,label=[label distance=0pt]306:] (v41)
(321:) node [smallvert,label=[label distance=0pt]306:] (v42)
(378:) node [smallvert,label=[label distance=0pt]378:] (v51)
[very thick](v20)–(v21);

(75:) node [smallvert,label=[label distance=0pt]90:] (v110)
(90:) node [smallvert,label=[label distance=0pt]90:] (v111)
(105:) node [smallvert,label=[label distance=0pt]90:] (v112)
(162:) node [smallvert,label=[label distance=0pt]162:] (v210)
(177:) node [smallvert,label=[label distance=0pt]162:] (v221)
(219:) node [smallvert,label=[label distance=0pt]234:] (v310)
(234:) node [smallvert,label=[label distance=0pt]234:] (v311)
(249:) node [smallvert,label=[label distance=0pt]234:] (v312)
(291:) node [smallvert,label=[label distance=0pt]306:] (v401)
(306:) node [smallvert,label=[label distance=0pt]306:] (v411)
(321:) node [smallvert,label=[label distance=0pt]306:] (v421)
(363:) node [smallvert,label=[label distance=0pt]378:] (v510)
(378:) node [smallvert,label=[label distance=0pt]378:] (v511)
(393:) node [smallvert,label=[label distance=0pt]378:] (v512)

[very thick](v310)–(v311)–(v312);

[very thick](v1)–(v11)

Two homomorphisms from a long cycle $C$ to a graph $H$. The bold edges are the non-loop edges in the image of each homomorphism. The first homomorphism “wraps around” a cycle $C'$ of $H$ a bounded number of times. If $C$ is sufficiently long, then the first homomorphism can be reconfigured to the second. Triangle-freeness of $H$ makes it impossible for the image of $C$ to completely leave cycle $C'$.

We refer to the latter obstruction as a topological obstruction.  To properly describe such obstructions we define an analogue, for triangle-free graphs, of homotopy theory and the fundamental group of a space.  The statement that the images $\phi(C)$ and $\psi(C)$ of a cycle $C$ “wrap around the same cycles of $H$ the same number of times” essentially translates to the closed walks that they trace out being homotopic in the fundamental group of $H$.

The goal is to show that, if no frozen vertex or topological obstructions exist, then there is a $(\phi,\psi)$-reconfiguration.
As it turns out, dealing with obstructions for cycles only is not enough.

It is easy to come up with examples in which there are no tight cycles, and for all cycles $C$ of $G$ the closed walks $\phi(C)$ and $\psi(C)$ are homotopic,  but there is no $(\phi,\psi)$-reconfiguration, even when $H$ is triangle-free; see Figure <ref>.   Indeed, there is a stronger topological obstruction.  If two cycles $C$ and $C'$ of $G$ share a vertex $r$, then a $(\phi,\psi)$-reconfiguration $W$ induces cycle reconfigurations $W_C$ and $W_{C'}$ that agree on $r$.  That is; where the trace
of a vertex $r$ under a reconfiguration $W = \phi_1 \sim \dots \sim \phi_d$ in $\bHom(G,H)$ is the walk
$W_r = \phi_1(r) \sim \dots \sim \phi_d(r)$, $W_C$ and $W_{C'}$ have the same trace $W_r$. For a $(\phi,\psi)$-reconfiguration to exist, we need to be able to reconfigure the homomorphisms of all cycles of $G$ simultaneously in a consistent manner.

(0:) node [smallvert,label=[label distance=0pt]90:] (v1)
(45:) node [smallvert,label=[label distance=0pt]162:] (v2)
(90:) node [smallvert,label=[label distance=0pt]234:] (v3)
(135:) node [smallvert,label=[label distance=0pt]306:] (v4)
(180:) node [smallvert,label=[label distance=0pt]378:] (v5)
(225:) node [smallvert,label=[label distance=0pt]378:] (v6)
(270:) node [smallvert,label=[label distance=0pt]378:] (v7)
(315:) node [smallvert,label=[label distance=0pt]378:] (v8)
(,-1.5cm) node (G)$G$

(0:) node [smallvert,label=[label distance=0pt]90:] (v1)
(45:) node [smallvert,label=[label distance=0pt]162:] (v2)
(90:) node [smallvert,label=[label distance=0pt]234:] (v3)
(135:) node [smallvert,label=[label distance=0pt]306:] (v4)
(180:) node [smallvert,label=[label distance=0pt]378:] (v5)
(225:) node [smallvert,label=[label distance=0pt]378:] (v6)
(270:) node [smallvert,label=[label distance=0pt]378:] (v7)
(315:) node [smallvert,label=[label distance=0pt]378:] (v8)

(0,0) node [smallvert,label=[label distance=0pt]90:] (v1)
(0.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (v4)
(-0.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (v2)
(0,-2cm) node [smallvert,label=[label distance=0pt]90:] (v3)
(1cm,-2.5cm) node (H)$H$

(2cm,0) node [smallvert,label=[label distance=0pt]90:] (u1)
(2.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (u4)
(1.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (u2)
(2cm,-2cm) node [smallvert,label=[label distance=0pt]90:] (u3)

(1cm,0) node [smallvert,label=[label distance=0pt]90:] (w1)
(1cm,-2cm) node [smallvert,label=[label distance=0pt]90:] (w2)

(0,0) node [smallvert,label=[label distance=0pt]90:] (v1)
(0.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (v4)
(-0.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (v2)
(0,-2cm) node [smallvert,label=[label distance=0pt]90:] (v3)
(1cm,-2.5cm) node (H)$\phi$

(2cm,0) node [smallvert,label=[label distance=0pt]90:] (u1)
(2.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (u4)
(1.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (u2)
(2cm,-2cm) node [smallvert,label=[label distance=0pt]90:] (u3)

(1cm,0) node [smallvert,label=[label distance=0pt]90:] (w1)
(1cm,-2cm) node [smallvert,label=[label distance=0pt]90:] (w2)

[very thick]

(0,0) node [smallvert,label=[label distance=0pt]90:] (v1)
(0.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (v4)
(-0.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (v2)
(0,-2cm) node [smallvert,label=[label distance=0pt]90:] (v3)
(1cm,-2.5cm) node (H)$\psi$

(2cm,0) node [smallvert,label=[label distance=0pt]90:] (u1)
(2.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (u4)
(1.5cm,-1cm) node [smallvert,label=[label distance=0pt]90:] (u2)
(2cm,-2cm) node [smallvert,label=[label distance=0pt]90:] (u3)

(1cm,0) node [smallvert,label=[label distance=0pt]90:] (w1)
(1cm,-2cm) node [smallvert,label=[label distance=0pt]90:] (w2)

[very thick]

Two homomorphisms $\phi$ and $\psi$ from a graph $G$ to a triangle-free graph $H$. The bold edges indicate the non-loop edges in the images of the homomorphisms. There are no tight closed walks and the restrictions of these homomorphisms to any given cycle of $G$ can be reconfigured, but $\phi$ cannot be reconfigured to $\psi$.

To deal with this we define, in Section <ref>, an analogue $\pi(H,r)$ of the fundamental group of a topological space. The definition is similar to, but simpler than,  a more sophisticated definition of homotopy theory for digraphs found in [Larose and Tardif, 2004].  We start with a graph $\Pi(H,r)$ whose vertices are closed walks of $H$ starting and ending at the basepoint $r$, and in which two are adjacent if they are adjacent in $\bHom(C,H)$ (where $C$ is a cycle), or if you get one from the other by subdividing an edge and mapping the new vertex to the same vertex as one of its neighbours.  The elements of $\pi(H,r)$ are the components of $\Pi(H,r)$.  The group operation is concatenation: from elements $[C]$ and $[C']$ of $\phi(H,r)$, the element $[C] \con [C']$ is the class of the closed walk $C \con C'$ with basepoint $r$ that you get by traversing $C$ and then $C'$.  We show that when  $H$ is triangle-free, classes of $\pi(H,r)$ have a canonical reduced form that can be computed in polynomial time.

Any cycle $C$ of $H$ with a basepoint $r'$ different from $r$ can be viewed, via a `basepoint change' by a any $(r,r')$-walk $W$, as a cycle $W \con C \con \rev{W}$ in $\pi(H,r)$, where $\rev{W}$ is $W$ traversed in reverse. The trace $W_r$ of $r$ under a $(\phi,\psi)$-reconfiguration in $\bHom(G,H)$ yields a basepoint change that induces equality $[\phi(C)] = [W_r \con \psi(C) \con \rev{W_r}]$ for all cycles $C$ in $\Pi(H,r)$ at the same time.
Following Wrochna, in [Wrochna, 2020], a walk $W_r$ in $H$ that induces this common basepoint change of all cycles is called  'topologically valid'.   Given a topologically valid walk, the only remaining obstructions are tight closed walks.

In Section  <ref>,
following the approach refined by Wrochna, give several useful equivalent conditions for the existence of a walk that is topologically valid for $\phi$ and $\psi$.  This allows us to give a polynomial time algorithm to determine if a given $(\phi(r),\psi(r))$-walk is topologically valid.

Determining whether a given $(\phi(r),\psi(r))$-walk is topologically valid, and determining whether there exists a topologically valid $(\phi(r),\psi(r))$-walk are different problems.  For the later problem, we consider a basepoint-free version of homotopy theory in Section <ref>.  Using this basepoint-free homotopy theory we give a polynomial time algorithm to determine whether or not there is a topologically valid walk $W_r$ for given $\phi$ and $\psi$.  This is the main technical part of the paper.

In Section <ref> we define tight closed walks, and show that given a topologically valid walk $W_r$ one can determine in polynomial time if there are any tight closed walks that obstruct a $(\phi,\psi)$-reconfiguration that uses $W_r$.

All these ideas are brought together in Section <ref> to give the formal proof of Theorem <ref>. This is more descriptive version of Theorem <ref> and yields it as an immediate corollary.

§ DISCRETE ANALOGUE OF THE FUNDAMENTAL GROUP

For this section, and all following sections, $H$ is a triangle-free reflexive graph.   All algorithms are about a given instance $(G, \phi, \psi)$ of $\recon(H)$, and running times are given in terms of $|V(G)|$.

§.§ The fundamental group of a reflexive graph

For any integer $\l \geq 1$ let $P_\l$ be the reflexive path on $\l+1$ vertices.
We refer to elements of $\bHom(P_\l,H)$ as walks of $H$, and represent them as
$(x_0 x_1 \dots x_\l)$. If $x_0 = a$ and $x_\l = b$ the walk is an $(a,b)$-walk.

Let $\Pi(H;a,b)$ be the graph whose vertices are $(a,b)$-walks in $H$, and in which a walk $Y$ is adjacent to a walk $X = (x_0, \dots, x_\ell)$ if either of the following are true:

$Y = (x_0,x_1, \dots, x_{i-1},x_i,x_i,x_{i+1},\dots, x_\l)$ for any $i$, or

$Y = (x_0,x_1, \dots, x_{i-1},x'_i,x_{i+1}, \dots, x_\l)$ for some $i \notin \{0,\ell\}$, where $x_i' \sim x_i$.

Of course, $Y$ is also adjacent to $X$ if $X$ is adjacent to $Y$ via this definition.   For an $(a,b)$-walk $X$, let $[X]$ be the component of $\Pi(H; a,b)$ containing $X$.

As suggested in the previous section, we will build from this a version of $\bHom(C,H)$ in which edges of $C$ can be subdivided.
Property <ref> allows  subdivision.  Property <ref> mimics adjacency in $\bHom(C,H)$; here we use the fact mentioned in the introduction that even in $\bHom(C,H)$ one need only change one colour at a time.

The concatenation operation  builds a $(a,c)$-walk $X_1 \con X_2$ from an $(a,b)$-walk $X_1$ and a $(b,c)$-walk $X_2$ by identifying the last vertex of $X_1$ with the first vertex of $X_2$.  The reversal operation  changes an $(a,b)$-walk $X_1$ to a $(b,a)$-walk $\rev{X_1}$ by reversing the order of the vertices.
Though concatentation is only a partial operation on the set of walks in $H$,  it is easy to check that both operations pass to $\Pi(H;a,b)$ in the following sense: for $X_1 \in  \Pi(H;a,b)$ and $X_2 \in \Pi(H;b,c)$, if   $Y_1 \in \ec{X_1}$ and $Y_2 \in \ec{X_2}$ then
$\rev{Y_1} \in \ec{\rev{X_1}}$ and $Y_1 \con Y_2 \in \ec{X_1 \con X_2}$; so we can apply them to components of $\Pi(H; a,b)$.  Moreover $\ec{X_1 \con \rev{X_1}}$ contains the empty $(a,a)$ walk $0_a$ (or just $0$ when $a$ is understood) at $a$, which acts as an identity with respect to concatenation. Thus restricting to closed walks with a fixed first vertex, or basepoint, $r$,  it is easy to see then that concatenation is a group operation on the components of $\Pi(H;r,r)$.    We thus define the following `fundamental group' of a graph $H$.

The fundamental group of a reflexive  graph $H$, with basepoint $r$, is the set $\pi(H;r)$ of components of $\Pi(H;r,r)$ under the concatenation operation.

§.§ The fundamental group of a triangle-free graph

The above construction and definition is agrees with a more general construction in  [Larose and Tardif, 2004], where the authors go on to show that $\pi(H;a)$ is isomorphic to the fundamental group of the clique complex of $H$.  Without formalizing this, we simply view $\pi(H,r)$ as an analogue of the homotopy group of a space. In light of this analogy, if $\ec{C} = \ec{C'}$ we say that $C$ and $C'$ are homotopic, and if $[C] = 0$ we call it contractible.   Under this analogy, a triangle-free graph $H$ corresponds to a purley one dimensional space—a $1$-manifold, so several things become simpler.  In fact, the simplification begins with the observation that in property <ref> of Defintion <ref>, such $x'_i$ can exist in a triangle-free graph $H$ only if $x_{i-1} = x_{i+1}$ and this is either $x_i$ or $x'_i$.  It is not hard to see then that  the following version of Definition <ref> yields an $\Pi(H;a,b)$ with the same components, and so yields the same $\pi(H;r)$.

Let $\Pi(H;a,b)$ be the graph whose vertices are $(a,b)$-walks in $H$, and in which a walk $Y$ is adjacent to a walk $X = (x_0, \dots, x_\ell)$ if either of the following are true:

$Y = (x_0,x_1, \dots, x_{i-1},x_i,x_i,x_{i+1},\dots, x_\l)$ for any $i$, or

$Y = (x_0,x_1, \dots, x_{i-1},x'_i,x_{i+1}, \dots, x_\l)$ for some $i \notin \{0,\ell\}$, where $x_{i-1}=x'_i = x_{i+1}$.

For an $(a,b)$-walk $X$, let $[X]$ be the component of $\Pi(H; a,b)$ containing $X$.

A closed walk with a basepoint other then $r$ can be viewed as a closed walk with basepoint $r$ via what is known as a basepoint change.   For an $(r,b)$-walk $X$ and a closed walk $C$ in based at $b$ define the closed walk
$\beta_X(C) := X \con C \con \rev{X}$. It is standard, and easily shown, that the map $\pi(H;b) \to \pi(H;r): \ec{C} \mapsto \ec{\beta_X(C)}$ is a group isomorphism.
We observed that if $C$ is a closed walk with basepoint $r$, then a $(\phi,\psi)$-path $W$ in $\bHom(C,H)$ induces a $(\phi(r),\psi(r))$-walk $W_r$ in $\bHom(r,H)$.  In fact, it induces a homotopy between $\phi(C)$ and the cycle $\psi(C)$ with basepoint changed
by  the trace $W_r$ of $r$.  This gives us our basic topological obstruction to a $(\phi,\psi)$-reconfiguration.  The following would hold for non triangle-free $H$ as well, but the proof would be a bit longer.

For triangle-free $H$, if there is a $(\phi,\psi)$-path $W$ in $\bHom(C,H)$ for some cycle $C$ with basepoint $r$, then $\ec{\psi(C)} = \ec{\beta_{W_r}(\phi(C))}$ in $\pi(H;\phi(r))$.

Recall that if there is a path from $\phi$ to $\psi$ in $\bHom(C,H)$, then there is a path in which any two consecutive elements differ on one vertex. By induction on the length of this path, it suffices to consider the case  that $\phi$ and $\psi$ differ on only one vertex.

If they differ on any vertex but their basepoint, then there is nothing to prove, as then $\ec{\psi(C)} = \ec{\phi(C)}$ by <ref>, and so we are done with empty $W_r$.  So we may assume that they differ on the first vertex. That is, we have

\[ \psi(C) = (x_0, x_1, \dots x_{\l}, x_0) \mbox{ and }
\phi(C) = (x'_0, x_1, \dots x_{\l}, x'_0).     \]

In this case take $W_r = (x_0,x'_0)$, we will show that

\[ \ec{\psi(C)} = \ec{(x_0,x_1, \dots, x_{\l},x_0)}  = \ec{(x_0,x'_0, x_1, \dots, x_{\l}, x'_0,x_0)} = \ec{\beta_{W_r}(\phi(C))}.   \]

Well, $x_0, x'_0$ are adjacent (as $C$ is reflexive) and are both adjacent to $x_1$ and $x_{\ell-1}$. So, as $H$ is triangle-free, we have that $x_0' = x_1$ or $x_0 = x_1$.  In the first case we have

\[ [(x_0,x_1, \dots, x_{\l},x_0)] =  [(x_0,x'_0 x_1, \dots, x_{\l}, x_0)] \]

by <ref> and in the second case we have it by <ref>.
Similarly $x'_0 = x_\ell$ or $x_0 = x_\ell$, and we get the second equality that we need to finish the lemma by transitivity.

§.§ Computation of reduced cycles

We say that a walk $X$ in $\Pi(H;r)$ is reduced if it is a shortest walk in $\ec{X}$.

Let $H$ be a triangle-free graph. Any class $\ec{X}$ in $\pi(H;r)$ has a unique reduced walk, and it can be found in linear time.

We prove the result more generally for walks in $\Pi(H;a,b)$ using the topological notion of a covering space—the idea is to define a graph $\cU$ for which the result is trivial, and to show that walks in $H$ `lift' uniqely to walks in $\cU$ in such a way that components of $\Pi$ are preserved.

For a graph $H$ and a vertex $r$, the universal cover $\cU$ is the infinite graph whose vertices are walks in $H$ starting at $r$, and having no occurrences of the same vertex at distance $1$ or $2$.  Two walks $X$ and $Y$ are adjacent in $\cU$ if we can get one from the other by dropping the last vertex. See Figure <ref> for an example.

(90:) node [vert,label=[label distance=0pt]90:$a$] (v1)
(162:) node [vert,label=[label distance=0pt]162:$e$] (v2)
(234:) node [vert,label=[label distance=0pt]234:$d$] (v3)
(306:) node [vert,label=[label distance=0pt]306:$c$] (v4)
(378:) node [vert,label=[label distance=0pt]378:$b$] (v5)

(90:) node [vert,label=[label distance=0pt]85:$r$] (u1)
(234:) node [vert,label=[label distance=0pt]180:$u$] (u2)
(378:) node [vert,label=[label distance=0pt]80:$s$] (u3)
(522:) node [vert,label=[label distance=0pt]100:$v$] (u4)
(666:) node [vert,label=[label distance=0pt]360:$t$] (u5)

(0,0) node [vert,label=[label distance=0pt]85:$r$] (r)
(90:) node [vert,label=[label distance=0pt]90:$ra$] (ra)
(210:) node [vert,label=[label distance=0pt]90:$ru$] (ru)
(330:) node [vert,label=[label distance=0pt]90:$rt$] (rt)

(60:) node [vert,label=[label distance=-2pt]350:$rab$] (rab)
(120:) node [vert,label=[label distance=-2pt]190:$rae$] (rae)
(180:) node [vert,label=[label distance=0pt]90:$rud$] (rud)
(240:) node [vert,label=[label distance=-2pt]170:$rus$] (rus)
(300:) node [vert,label=[label distance=-2pt]10:$rtv$] (rtv)
(360:) node [vert,label=[label distance=0pt]90:$rtc$] (rtc)

(45:) node [vert,label=[label distance=0pt]90:$rabc$] (rabc)
(75:) node [vert,label=[label distance=0pt]90:$rabs$] (rabs)
(105:) node [vert,label=[label distance=0pt]90:$raev$] (raev)
(135:) node [vert,label=[label distance=0pt]90:$raed$] (raed)
(165:) node [vert,label=[label distance=0pt]180:$rude$] (rude)
(195:) node [vert,label=[label distance=0pt]180:$rudc$] (rudc)
(225:) node [vert,label=[label distance=0pt]270:$rusv$] (rusv)
(255:) node [vert,label=[label distance=0pt]270:$rusb$] (rusb)
(285:) node [vert,label=[label distance=0pt]270:$rtve$] (rtve)
(315:) node [vert,label=[label distance=0pt]270:$rtvs$] (rtvs)
(345:) node [vert,label=[label distance=0pt]0:$rtcd$] (rtcd)
(15:) node [vert,label=[label distance=0pt]0:$rtcb$] (rtcb)

The Petersen graph and a finite portion of its universal cover.

Because $\cU$ is a tree, it is easy to see that $\Pi(\cU; (r),(r,x_1,x_2, \dots, x_\ell))$ is connected for any vertex $(r,x_1,x_2, \dots, x_\ell)$ and that its unique shortest walk is

\[ (r)(r,x_1)(r,x_1,x_2)  \dots (r,x_1,x_2 \dots, x_\ell). \]

Now, the map

\[ \phi: \cU \to H: (r,x_1, \dots, x_\ell) \mapsto x_\ell \]

is a locally bijective homomorphism; i.e., induces a bijection between closed neighbourhoods $\{x\} \cup N(x)$ of vertices in $\cU$ and vertices in $H$.

It follows that the map

\[ \Phi: (r,x_1, \dots, x_\ell) \mapsto
(\phi(r),\phi(r,x_1), \dots, \phi(r,x_1, \dots, x_\ell)) \]

is a bijective homomorphism  between the set $\Pi(\cU; (r))$ of walks in $\cU$ starting at $(r)$ and the set $\Pi(H; r)$ of walks in $H$ starting at $r$.
Indeed the lift $\Phi^{-1}(X)$ of a walk $X = (rx_1 \dots x_n)$ of $H$ from $\Pi(H;r)$ to $\Pi(\cU;(r))$ can be given explicitly: its first vertex is $\Phi^{-1}(X)_0 := (r)$ and its $i^{th}$ vertex is
\[ \Phi^{-1}(X)_i :=   \Phi^{-1}(X)_{i-1} \con \phi_{x_{i-1}}^{-1}(x_i) \]
where $\phi^{-1}_x$ is the bijective restriction of $\phi^{-1}$ to the closed neighbourhood of $x$.  Observe that for $x_{i-1} \sim x_i$ we have  $\phi^{-1}_{x_{i-1}}(x_i) = \phi^{-1}_{x_i}(x_i)$.

Now, not all $(r,b)$-walks of $H$ must lift to walks of $\cU$ with the same endpoint, but those in a component of $\Pi(H;r,b)$ should; in fact, we show now that for triangle-free $H$, a component of $\Pi(H; r,b)$ lifts isomorphically to  $\Pi(\cU;(r),B)$
for some walk $B$, by showing $\Phi^{-1}$ is a homomorphism.   Indeed let $X$ and $X'$ be adjacent in $\Pi(H;r,b)$.
If $X$ and $X'$ are related by <ref>, then we may assume  $X = (r,v_1, \dots, v_n)$ while $X' = (r,v_1, \dots, v_{i-1},v_i,v_i,v_{i+1}, \dots, v_n)$.  These lift to $W \con U$ and $W \con \phi^{-1}_{v_i}(v_i) \con U$ respectively where
$W = \Phi^{-1}(r,v_1, \dots, v_i)$ as $\phi^{-1}_{v_i}(v_i)$ is equal to the last vertex $\phi^{-1}_{v_{i-1}}(v_i)$ of $W$.  But as these vertices are equal $W\con U$ and $W \con \phi^{-1}_{v_i}(v_i) \con U$  are adjacent in $\Pi(H;(r),B)$ by <ref>.
Similar arguments about <ref> complete the proof that adjacent walks in  $H$ lift to adjacent walks in $\cU$.  Thus $\Phi^{-1}$ maps a component of $\Pi(H;r,b)$ isomorphically to $\Pi(\cU,(r), B)$ for some $B$.
Clearly  $\Phi$ takes the shortest walk  in $\Pi(\cU;(r),B)$ to a unique shortest wak in $\Pi(H;r,b)$, so $\Pi(H;r,b)$ has a unique shortest walk.

One can lift to $\cU$ to easily find the unique shortest walk, but the fact that it is unique means that one can simply apply <ref> or <ref> to greedily shorten a walk, and so find
its reduced form in linear time.

§.§ Computational Tools

We finish this section by observing some simple computational tools that are familiar from homotopy theory which we will use several times.
It is easy to show, for $(a,b)$-walks $X_1$ and $X_2$,  that

\begin{equation}\label{eq:homwalks}
\ec{X_1} = \ec{X_2} \iff \ec{ X_1 \con \rev{X_2}} = 0.
\end{equation}

Taking $I$ as some initial segment of a closed walk $C$, it is not hard to see that
the cyclic shift $\sigma_I(C)$ of $C$ by $|I|$ vertices is in $\ec{\beta_{\rev{I}}(C)}$,
and so

\begin{equation}\label{eq:perm}
\ec{C} = [0] \iff \ec{\sigma_I(C)} = [0].
\end{equation}

Thus $\ec{C}$ is contractible if and only if all cyclic shifts of it are contractible. Breaking a cycle up as the concatenation of walks, this yield identities such as the following:

\begin{equation}\label{eq:perm2}
\ec{ X_1 \con X_2 \con X_3 \con X_4 } = [0] \iff \ec{ X_2 \con X_3 \con X_4 \con X_1 } = [0]
\end{equation}

or using (<ref>):

\begin{equation}\label{eq:permedge}
\ec{\rev{X_1}} = \ec{X_2 \con X_3 \con X_4} \iff \ec{\rev{X_2}} = \ec{X_3 \con X_4 \con X_1}.
\end{equation}

There is one more simple observation which allows us to apply these notions succinctly.

When $C_1 = U_1 \con X \con V_1$ and $C_2 = U_2 \con \rev{X} \con V_2$ are closed walks
as in Figure <ref>,  let $C_1 \con_X C_2  = U_1 \con V_2 \con U_2 \con V_1$.

(0,0) node [vert] (v1);
(0,1.5) node [smallvert] (v2);
(0,3) node [vert] (v3);
(5,3) node [empty] (v4);
(5,1.5) node [smallvert] (v5);
(5,0) node [empty] (v6);

(v1) – (v3) – (v4.center) – (5,0) – (v1);
[dashed] (v2)–(v5);

at (-.4,.6) $U_1$;  [-stealth] (-.1, .5) – (-.1,.8);
at (-.4,2.1) $V_2$; [-stealth] (-.1, 2) – (-.1, 2.3);
at (5.2,3.3) $U_2$; [-stealth] (4.8,3.1) – (5.1,3.1) – (5.1 , 2.8);
at (2.5,1.8) $X$;   [-stealth] (2.4,1.6) – (2.7,1.6);
at (5.2,-.3) $V_1$; [-stealth] (5.1,.2) – (5.1,-.1) – (4.8 ,-.1);

at (1.4,2.2) $C_2$;

at (1.4,.7) $C_1$;

The cycle $C = C_1 \con_X C_2$ where $C_1 = U_1 \con X \con V_1$
and $C_2 = U_2 \con \rev{X} \con V_2$

With this definition, we have the following.

Let $C = C_1 \con_X C_2$. If two of $\ec{C_1}, \ec{C_2}$ and $\ec{C}$ are contractible, then they all are.

Taking shifts $C'_1 = V_1 \con U_1 \con X$ of $C_1$ and $C'_2 = \rev{X} \con V_2 \con U_1$ we have
that $\ec{C'_1 \con C'_2} = \ec{C'}$ where $C'$ is the shift $V_1 \con U_1 \con V_2 \con U_1$
of $C = C_1 \con_X C_2$.  It is easy to see therefore that two of $\ec{C'_1}, \ec{C'_2}$ and $\ec{C'}$ are contractible if and only if the third of them is.  The result follows by (<ref>).

§ TOPOLOGICALLY VALID SYSTEM OF WALKS

From Lemma <ref> we see a reconfiguration of $\phi$ to $\psi$ in $\bHom(G,H)$ induces for each cycle $C$ of $G$ fixed-basepoint  homotopy from $\phi(C)$ to $\beta_{W_r}(\psi(C))$ with a common basepoint change $W_r$.
Not only is such a walk  $W_r$  necessary for a reconfiguration it is almost sufficient.  If it exists, the only obstructions a reconfiguration will be non-topological (tight closed walks).  So recognizing the existence of such a
basepoint change is key.  This task is simplified by the fact that choice of the basepoint $r$ is unimportant.    We address this in this section.

A system of walks for $\phi$ and $\psi$ is a vector $(W_v):= (W_v)_{v \in V(G)}$ of walks in $H$ such that $W_v$ is a $(\phi(v),\psi(v))$-walk.  A walk $W_v$ is  topologically valid if for  every  closed walk
$C$ of $G$ with basepoint $v$ we have

\begin{equation}\label{eq:TV}
\ec{\phi(C)} = \ec{\beta_{W_v}(\psi(C))}.
\end{equation}

The system of walks is topologically valid if all walks in it are topologically valid.

As suggested above, we get a topologically valid sytem of walks from a reconfiguration.

Let $W$ be a reconfiguration from $\phi$ to $\psi$ in $\bHom(G,H)$. Where for every vertex $v$ of $G$,  $W_v$ is the trace of $v$, the system $(W_v)$ of walks is topologically valid for $\phi$ and $\psi$.

In Section <ref> we observed that $W$ induces a $(\phi(C),\psi(C))$-walk in $\bHom(C,H)$ for any closed walk $C$ of $G$.  In Lemma <ref> we observed that where $v$ is the basepoint of $C$ this implies $\ec{\psi(C)} = \ec{\beta_{W_v}(\phi(C)}$ in $\pi(H; \phi(v))$. Thus any reconfiguration $W$ from $\phi$ to $\psi$  yields a system $(W_v)$ of walks that is topologically valid for $\phi$ and $\psi$.

Generalizing the condition for closed walks, a $uv$-walk $U$ in $G$ is (topologically) preserved by a system $(W_v)$ of walks for $\phi$ and $\psi$ if

\begin{equation}\label{eq:TV1}
\ec{\phi(U)} = \ec{W_u \con \psi(U) \con \rev{W_v}}.
\end{equation}

By (<ref>) and (<ref>) we can write in the following form:

\begin{align}
% \ec{\phi(U)} = \ec{W_u \con \psi(U) \con \rev{W_v}} & \label{eq:TV2}\tag{\ref{eq:TV1}$'$} \\
\ec{\phi(U) \con W_v \con \rev{\psi(U)} \con \rev{W_u}} = 0  &     \label{eq:TV3}\tag{\ref{eq:TV1}$'$}
\end{align}

Now, for a $uw$-walk $U$ and a $wv$-walk $V$ we have

\begin{multline*}%\label{eq:TVext}
\phi(U \con V) \con W_v \con \rev{\psi(U \con V)} \con \rev{W_u}  = \\
\left( \phi(U) \con W_w \con \rev{\psi(U)} \con \rev{W_u} \right) \con_{W_w}
\left( \phi(V) \con W_v \con \rev{\psi(V)} \con \rev{W_w} \right),
\end{multline*}

so by Lemma <ref> and form (<ref>), we get that if two of $U, V$ and $U \con V$ are preserved by $(W_v)$, then so is the third of them. This yields the following alternate definition.

A system of walks $(W_v)$ is topologically valid for $\phi$ and $\psi$ if and
only if every edge in $G$ is topologically preserved by $(W_v)$ if and only if
every walk in $G$ is toplogically preserved by  $(W_v)$.

The topologically valid system of walks $(W_v)$ we get from a reconfiguration $W$ is not generally unique, indeed each walk in general may have many repeated vertices, but it is unique up to homotopy classes.

Let $W_r$ be a reduced topoligically valid  $(\phi(r),\psi(r))$-walk in $H$.  There is a unique topologically valid system $(W_v)$ of reduced walks for $\phi$ and $\psi$ that contains $W_r$.

First we show that there is a topologically valid system $(W_v)$ of walks containing $W_r$.  Choose a spanning tree $T$ of $G$ with root $r$.  Inductively build $(W_v)$ by setting $W_v$ to be the reduction of $\phi(vu) \con W_u \con \psi(uv)$, where the $(\phi(u),\psi(u))$-walk $W_u$ is already defined for the precursor $u$ of $v$ in $T$.

By construction any edge in $T$, so any path in $T$ is preserved by $(W_v)$.  Thus the system $(W_v)$ is topologically valid if and only if every edge $e$ in $G \setminus T$ is also preserved by $(W_v)$.

If there is some edge $e = uv$ that is not preserved by $(W_v)$.  Letting $T_v$ denote the unique path in $T$ from $r$ to $v$, we clearly have then that the closed walk $C =  T_u \con e \con \rev{T_v}$ is not preserved by $(W_v)$, so $\ec{\phi(C)} \neq \ec{\beta_{W_r}(\psi(C))}$, contradicting the fact that $W_r$ was topologically valid.

In light of this fact, we make the following definition.

A topologically valid $(\phi(r),\psi(r))$-walk $W_r$ contained in a topologically valid system $(W_v) = (W_v)_{v \in V(G)}$ of walks,  generates the system $(W_v)$.

Actually our proof of Lemma <ref> did more.  Defining $(W_v)$ as we did in the proof can clearly be done in polynomial time.  Once we have done so, checking that  at most quadratic number of edges not in $T$ are preserved can be done in polynomial time.
Thus we showed the following.

Let $W_r$ be reduced walk from $\phi(r)$ to $\psi(r)$. We can determine in polynomial time if $W_r$ is topologically valid. If it is, we produce the system $(W_v)$ it generates, if not, we provide a closed walk $C$ of $G$ such that $\ec{\phi(C)} \neq \ec{\beta_{W_r}(\psi(C)}$.

§ BASEPOINT-FREE HOMOTOPY

Fact <ref> tells us that there is a $(\phi,\psi)$-reconfiguration in $\bHom(G,H)$  only if there is a topologically valid walk $W_r$ between the basepoints $\phi(r)$ and $\psi(r)$,
and Corollary <ref> tells us how to decide if a given $W_r$ is topologically valid.
Our main result in this section, Lemmma <ref>, tells us how to decide if there is any
walk $W_r$ that is topolocially valid for $\phi$ and $\psi$.
If a randomly chose $(\phi(r),\psi(r))$ walk $W_r$ is not valid, then Corollary <ref> gives us a non-contractible closed walk $C$ such that $\ec{\phi(C)} \neq \ec{\beta_{W_r}(\psi(C)}$. This $C$ is our starting point in this section, as it greatly limits the possibilites for a valid $W_r$.  To characterise the possibilites, we use a version of $\Pi(H,r)$ in which we let the basepoint move freely.

Let $\Pi(H)$ be the graph we get from the disjoint union, over all $r \in V(H)$, of $\Pi(H;r)$
by adding an edge between walks $y$ and $x = (x_0,x_1, \dots,x_{\ell-1},x_0)$ if

P3(P3) $y = (x_1, \dots, x_{\l-1})$ and $x_1 = x_{\l-1}.$

Let $\pi(H)$ be the set of components of $\Pi(H)$, and let $\cl{C}$ be the component of $\Pi(H)$ containing $C$.   Clearly we have that

\begin{equation}\label{eq:equivhom}
\ec{C} = \ec{C'}  \mbox{ implies }   \cl{C} = \cl{C'}.
\end{equation}

The converse is not true in general, indeed not even heuristically, as $C$ and $C'$ may satisfy $\cl{C} = \cl{C'}$ and have different basepoints.   However, if we have a walk $W$ from $C$ to $C'$ in $\Pi(H)$, then it is not hard to see that $\ec{C} = \ec{\beta_{W_r}(C')}$ where $W_r$ is the trace of the basepoint $r$ of $C$.

If $C$ is a closed walk with basepoint $r$, then it is trivial to see that $\cl{C} = \cl{\beta_W(C)}$ for any walk $W$ ending  at $r$, and so from Lemma <ref> we get that if there is a $(\phi,\psi)$-path in $\bHom(C,H)$
then $\cl{\phi(C)} = \cl{\psi(C)}$. A closed walk $C$ is free-reduced if it is a shortest closed walk in $\cl{C}$.  Though any class in $\pi(H;r)$ contains a unique reduced closed walk, this does not hold for free-reduced closed walks in classes of $\pi(H)$. Indeed, if $C$ is free-reduced, any cyclic shift of it is also free reduced. However, any non-contractible reduced closed walk $C$, `contains' a unique free-reduced closed walk.

If $C$ is a non-contractible reduced closed walk with basepoint $r$, then $C$ decomposes uniquely as
$C = \beta_T(C_f)$ for some free reduced closed walk $C_f$, and some reduced walk $T$ from $r$ to the first vertex of $C_f$.

Indeed, as $C = (x_0,x_1, \dots, x_{\l-1},x_0)$ is reduced with respect to operations <ref> and <ref> the only possible reduction is operation <ref>, meaning $x_{\l-1} = x_1$ and it reduces to $C_1 = (x_1, x_2 \dots, x_{\l-1})$.  Where $T_1 = (x_0,x_1)$ we have $C_1 = \beta_{T_1}(C_1)$.  By induction we get the fact.

As the reduced form of $C$ is unique and can be found in linear time, so can its decomposition
into $\beta_T(C_f)$.  We call this its free decomposition and call $T$ its tail.

This free decomposition does not change by much under basepoint change. To show this we start with a somewhat technical calculation. The intuition for this lemma is perhaps aided by first reading the corollaries that follow it.

A walk $I$ is initial in a walk $X$ if $X = I \con J$ for some $J$.  A walk is terminal in $X$ if it is initial in $\rev{X}$.

Let $A$ and $B$ be non-contractible reduced closed walks with respective free decompositions
$\beta_T(A_f)$ and $\beta_S(B_f)$.  If $\ec{A} = \ec{\beta_W(B)}$ for a walk $W$
then there is an integer $d$ and initial $I$ of $A_f^d$ such that $B_f = \sigma_I(A_f)$ is a cyclic shift of $A_f$, and $\ec{W} = \ec{T \con I \con \rev{S}}$. This is reduced unless $T$ and $S$ end in a common walk.

As $\ec{A} = \ec{\beta_W(B)}$ we have $\ec{A^d} = \ec{\beta_W(B^d)}$ so $\ec{A^dW} = \ec{WB^d}$ for any integer $d$. While $A^dW$ and $WB^d$ are not generally reduced, $A^d$ and $B^d$ reduce to $\beta_T(A_f^d)$ and $\beta_S(B_f^d)$, and so by taking $d$ large enough, we can say $A^dW = WB^d$ reduces to

\begin{equation}\label{eq:com}
I_A \con T_W = I_W \con T_B\tag{*}
\end{equation}

for some initial $I_A$ of $\beta_T(A_f^d)$,  some termimal $T_W$ of $W$, some initial $I_W$ of $W$ and some terminal $T_B$ of $\beta_S(B_f^d)$.  As (<ref>) holds for all large enough $d$,  and $I_A$ and $T_B$ grow with $d$, we have that $|A_f| = |B_f|$, and that by taking $d$ large enough,  $I_A$ and $T_B$ can be assured to have an arbitrarily long overlap, so $B_f$ is some shift of $A_f$, as needed.  We now just have to verify the decomposition of $W$.

Again from (<ref>) for large enough $d$ we get that the end $T_W$ of $W$ is terminal in $T_B$ so in $B_f^d \con \rev{S}$, and as $\beta_T(A_f^d) \con W$ reduced to $I_A \con T_W$, we get that $W = W' \con T_W$ for some $W'$ which cancels with the end of $A_f^d \con \rev{T}$.  Thus $W'$ is initial in $T \con A_f^{-d}$.

Now, $W'$ ends where $T_W$ starts. If $T$ and $S$ end in a common walk, then it is possible that $W' \con T_W$ is the reduction of $T \con S$.  Otherwise $W'$ contains $T$ and $T_W$ contains $S$.  In this case $W'$ begins with $T$ and then contains some initial walk of $A_f^{-d}$.  So $W' \con T_W$ is $T \con I \con \rev{S}$ for some initial $I$ of $A^d_f$ or $A_f^{-d}$, as needed. That $B_f = \beta_I(A_f)$ now follows from the fact that $B_f$ is a shift of $A$, and that $I$ is an initial walk in $A_f$ or its inverse that has the right endpoints.

From this we get a couple of immediate corollaries.

If $A_f$ and $B_f$ are free reduced non-contractible closed walks with $\cl{A_f} = \cl{B_f}$
then $B_f$ is a cyclic shift of $A_f$.

As $\cl{A_f} = \cl{B_f}$ we have $B_f \in [\beta_{W_r}(A_f)]$ where $W_r$ is the trace of the basepoint $r$ under the walk $W$ from $A_f$ to $B_f$ in $\Pi(H)$.  By the lemma $B_f$ is a shift of $A_f$.

For a reduced closed walk $C$, let $\sqrt{C}$ be the shortest initial walk of $C$ such that $\sqrt{C}^d = C$ for some positive $d$.

If $A$ and $B$ are non-contractible reduced closed walks with free decompositions $A = \beta_T(A_f)$ and $B = \beta_S(B_f)$, then $\ec{A} = \ec{\beta_W(B)}$ if and only if $W$ is of the form

\[ W_d = \sqrt{A}^d \con T \con I \con \rev{S} \]

for some integer $d$, where $I$ is an initial walk of $A$.

The `if' part is trivial as $\ec{W_d} = T \con \sqrt{A_f}^d \con I \con \rev{S}$ and this is the trace of the path from $A$ to $B$ that we get by composing the reduction of $A$ to $A_f$ with the
cyclic shift of $A_f$ by $A_f^d \con I$ to $B_f$, and then composing this with the inverse of the reduction of $B$ to this shift of $B_f$.  The `only if' is from Lemma <ref> the lemma.

Let $A$ and $B$ be reduced closed walks in $G$ with basepoint $r$ having respective free decompositions
$\beta_T(A_f)$ and $\beta_S(B_f)$, and such that $\sqrt{A} \neq \pm \sqrt{B}$.
If there exists a walk $W_r$ such that $\ec{\phi(A)} = \ec{ \beta_{W_r}{\psi(A)}}$ and $\ec{\phi(B)} = \ec{ \beta_{W_r}{\psi(B)}}$,
then there is a unique reduced such walk and it is the reduction of either $T \con I \con \rev{S}$
for some initial $I$ of $A_f$  or $T' \con I' \con \rev{S'}$ for some initial $I'$ of $B_f$.

Let $A$ and $B$ and $W$ be as in the premise of the corollary.
By Corollary <ref> we have then

\[ \ec{\sqrt{A}^d \con T \con I \con \rev{S}} = \ec{\sqrt{B}^{d'} \con T' \con I' \con \rev{S'}} \]

for some $d$ and $d'$ where $I$ and $I'$ (and all other components) are fixed.
Reducing these, we get

\[ \ec{T \con \sqrt{A_f}^d \con I \con \rev{S}} = \ec{T' \con \sqrt{B}_f^{d'} \con I' \con \rev{S'}} \]

where $A_f$ is the free reduction of $A$ and $B_f$ is the free reduction of $B$.  As $\sqrt{A} \neq \sqrt{B}$ we have either $T \neq T'$ or $\sqrt{A_f} \neq \sqrt{B}_f$.  Either way, the only possible solution has $d = 0$ or $d' = 0$.
These cannot yield different solutions by considerations of length.

We are now ready to prove the main result of the section.

Let $r$ be a vertex of $G$. We can determine in polynomial time if there is a $(\phi(r),\psi(r))$-walk $W_r$ that is topologically valid for
$\phi, \psi$ in $\bHom(G,H)$.  If there is, one with length at most $2n$ is provided.

Let $W_r$ be any shortest $(\phi(r),\psi(r))$-walk in $H$. By Corollary <ref> we can determine in polynomial time if $W_r$ is  topologically valid. If it is, we are done, so we may assume that it is not, and the algorithm returns a closed walk
$C$ of $G$ such that $\ec{\phi(C)} \neq \ec{\beta_{W_r}(\psi(C))}$, so necessarily $\phi(C)$ is non-contractible.

By Lemma <ref>, (and Fact <ref>) we can find the free decompositions  $\phi(C) = \beta_T(C_f)$ and $\psi(C)=\beta_S(C'_f)$ in polynomial time.
We can check in polynomial time if $C'_f$ is a shift of $C_f$. If it is not, then $\cl{\phi(C)} \neq \cl{\psi(C)}$ by Corollary <ref>, and so by (<ref>), we have

\[         \ec{\phi(C)} \neq \ec{\beta_W(\psi(C))}\]

for any $W$. Thus there can be no topologically valid $W_r$, and we are done.

We may assume, therefore, that $C'_f$ is the shift $\sigma_I(C_f)$ for some initial walk $I$ of $C_f$.  By Corollary <ref> we thus have that the only reduced walks $W$ that preserve $C$ are reductions of

\[ W_d:= \sqrt{\phi(C)}^d \con T \con I \con \rev{S} \]

for integers $d$.

By Corollary <ref> we can  decide if $W_0$ is topologically valid. If it is we return it and are done, so we may assume that it is not, and Corollary <ref> yields another closed walk $C'$ with $\ec{\phi(C')} \neq \ec{\beta_{W_0}(\psi(C'))}$.
By Corollary <ref> we get that $\sqrt{C'} \neq \pm\sqrt{C}$ and so by Corollary <ref>  the only walks $W$ that can preserve both $C$ and $C'$ are the reductions of $T \con I \con \rev{S}$ and $T' \con I' \con \rev{S'}$ where $\beta_{T'}(C_f)$ is the reduction of $\phi(C')$ and $\beta_{S'}(\sigma_{I'}(C_f))$ is the reduction of $\psi(C')$.   Both of these have length at most $2n$ so we can check them for topological validity in polynomial time by Corollary <ref>, and return the shortest one that is valid if any are.

§ TIGHT CLOSED WALKS

Though having a topologically valid $(\phi(r),\psi(r))$-walk in $H$ guarantees there are no topological obstructions to a $(\phi,\psi)$-reconfiguration, there may still be non-topogical obstructions.

A system of walks $(W_v)$ is realizable if (by possibly adding repeated vertices into walks) we get a system of walks that is induced by a reconfiguration.

A closed walk $C$ of $G$ is tight under $\phi$ if $\phi(C)$ is  free reduced in $\pi(H)$.
Any vertex of a tight closed walk is fixed under $\phi$.

It is not hard to see that if $C$ is tight under $\phi$, then any neighbour of $\phi$ in $\bHom(G,H)$ must agree with $\phi$ on $C$. Thus a fixed vertex is one that cannot change under a reconfiguration. A walk is constant if all vertices are the same.

If the system of walks $(W_v)$ is realizable for $\phi$ and $\psi$ in $\bHom(G,H)$ and $c$ is fixed under $\phi$, then $W_c$ is constant.

For a given system $(W_v)$ of paths that is topologically valid for  $\phi, \psi \in \bHom(G,H)$, we can decide in time linear in the sum of the lengths of the paths if $(W_v)$ is realizable.

If it is not realizable, we give a closed walk $C$ on which $\phi$ is tight.

Let homomorphisms $\phi, \psi :G \to H$ and a system of walks $(W_v)_{v \in G}$
that is topologically valid for $\phi$ and $\psi$ be given.  Starting with $\phi$ we attempt to construct a reconfiguration $W$ from $\phi$ to $\psi$, by changing one vertex $v$ at a time from its current position $W_v$ to its next position. If we succeed, this witnesses the realizability of $(W_v)$.

As any edge $e = uv$ of $G$ is topologically valid under the system of walks,

\[ [W_u] =  [ \phi(e) \con W_v \con \rev{\phi(e)}], \]

and as by Lemma <ref> there is a unique reduced walk in $[W_u]$, we have, where a superscript of $i$ on the walk designates that $i^{th}$ vertex of the walk, either  $W_u^i = W_v^{i-1}$ for all $i$ except maybe $i = |V(W_u)|$,
or      $W_v^i = W_u^{i-1}$ for all $i$ except maybe $i = |V(W_v)|$.

Construct an auxillary digraph $A$ on $V(G)$ by setting $u \to v$ if

\begin{equation}\label{eq:aux}
W_v^1 = W_u^0 \mbox{ and } W_v^0 \nadj W_u^1.
\end{equation}

(Interpret this as '$u$ wants to move to $W_u^1$, but $v$ has to move first'.)
Observe that if $uv$ is an edge, and $|W_u| = 0$, then $|W_v| \leq 1$, and $W_v^1 \sim W_u^0$,
so $u$ has no arcs in $A$.

If $A$ has any sink $v$, then on moving $v$ to $W_v^1$, we still have a homomorphism. Append this
homomorphism to $W$, and relabelling $W_v$ by removing its first vertex. As each relabelling reduces the length of a walk in $(W_v)$ by one, we either complete in time linear in the sum of the lengths of the paths, (and we are done) or at some step $A$ has no sinks, so contains a directed cycle.

Assume that $A$ has a directed cycle $C = a_1 \to a_2 \to \dots \to a_t$.
By construction, every arc $a_i \to a_{i+1}$ of $C$ is an edge $a_i \sim a_{i+1}$ of $G$, and (<ref>) ensures that $\phi(a_{i}) \notin \{ \phi(a_{i-1}), \phi(a_{i-2}) \}$,  (indices modulo $t$) for all $i$.
Thus is $C$ is a tight closed walk under $\phi$.

§ FULL STATEMENT AND PROOF OF THE MAIN THEOREM

We are now ready to state and prove the main technical theorem,  from which Theorem <ref> follows immediately.

Let $H$ be a reflexive symmetric triangle-free graph, and $(G, \phi, \psi)$ be an instance of $\recol(H)$.  There is a reconfiguration from $\phi$ to $\psi$ if and only if
there is a system of walks $(W_v)_{v \in V(G)}$ that is topologically valid for $\phi$ and $\psi$, such that $W_c$ is a constant walk for any vertex $c$ in closed walk $C$ that is tight under $\phi$.

Moreover, these validity of this conditions can be determined by an algorithm that runs in time that is polynomial in $|V(G)|$.

The `only if' part of the first statement of the theorem is proved in Facts <ref> and <ref>.   The `suffciency' is proved in Lemma <ref>.
The validity algorithm comes from Lemma <ref> and Lemma <ref>.

Indeed, choosing a vertex $r$ of $G$,  by Lemma <ref> we determine if there is a topologically valid $(\phi(r),\psi(r))$-path.  If there is not, we are done, and if there is, we get one with $W_r$ of length at most $2n$.
In fact we get the system $(W_v)$ of walks that it generates, and no path in this system can have length greater than $4n$ so the sum of the lengths of these paths are polynomial in $n$.   By Lemma <ref> we determine
if this system of walks is realizable in polynomial time.  If it is we are done,  and if it is not, then the lemma returns a tight closed walk.  Choosing new $r$ in $C$, any realizable system of paths is constant on $r$.
If  $\phi(r) \neq \psi(r)$ there is no such system, and we are done.  If  $\phi(r) = \psi(r)$, set $W_r$ to be constant, and apply Corollary <ref> to determine if  it is topolgically valid.  If it is apply Lemma <ref> we determine if it is  realizable.

[Bonsma and Cereceda, 2009]
P. Bonsma and L. Cereceda.
Finding paths between graph colourings: PSPACE-completeness and
superpolynomial distances.
Theoret. Comput. Sci., 4100 (50):0 5215–5226,

[Bonsma et al., 2014]
P. Bonsma, A. Mouawad, N. Nishimura, and V. Raman.
The complexity of bounded length graph recoloring and CSP
In Parameterized and exact computation, volume 8894 of
Lecture Notes in Comput. Sci., pages 110–121. Springer, Cham, 2014.

[Brewster and Noel, 2015]
R. Brewster and J. Noel.
Mixing homomorphisms, recolorings, and extending circular
J. Graph Theory, 800 (3):0 173–198, 2015.

[Brewster et al., 2016]
R. Brewster, S. McGuinness, B. Moore, and J. Noel.
A dichotomy theorem for circular colouring reconfiguration.
Theoret. Comput. Sci., 639:0 1–13, 2016.

[Brewster et al., 2018]
R. Brewster, J. Lee, and M. Siggers.
Recolouring reflexive digraphs.
Discrete Math., 3410 (6):0 1708–1721, 2018.

[Brewster et al., 2020]
R. Brewster, J. Lee, B. Moore, J. A. Noel, and M. Siggers.
Graph homomorphism reconfiguration and frozen $H$-colorings.
J. Graph Theory, 940 (3):0 398–420, 2020.

[Bulatov, 2017]
A. Bulatov.
A dichotomy theorem for nonuniform CSPs.
In 58th Annual IEEE Symposium on Foundations of
Computer Science—FOCS 2017, pages 319–330. IEEE Computer Soc., Los
Alamitos, CA, 2017.

[Cardinal et al., 2020]
J. Cardinal, E. Demaine, D. Eppstein, R. Hearn, and A. Winslow.
Reconfiguration of satisfying assignments and subset sums: easy to
find, hard to connect.
Theoret. Comput. Sci., 806:0 332–343, 2020.

[Cereceda et al., 2011]
L. Cereceda, J. van den Heuvel, and M. Johnson.
Finding paths between 3-colorings.
J. Graph Theory, 670 (1):0 69–82, 2011.

[Gopalan et al., 2009]
P. Gopalan, P. Kolaitis, E. Maneva, and C. H. Papadimitriou.
The connectivity of Boolean satisfiability: computational and
structural dichotomies.
SIAM J. Comput., 380 (6):0 2330–2355, 2009.

[Hatanaka et al., 2018]
T. Hatanaka, T. Ito, and X. Zhou.
Complexity of reconfiguration problems for constraint satisfaction,
URL <1812.10629>.

[Larose and Tardif, 2004]
B. Larose and C. Tardif.
A discrete homotopy theory for binary reflexive structures.
Adv. Math., 1890 (2):0 268–300, 2004.

[Lee et al., 2020]
J. Lee, J. Noel, and M. Siggers.
Reconfiguring graph homomorphisms on the sphere.
European J. Combin., 86:0 103086, 21, 2020.

[Makino et al., 2010]
K. Makino, S. Tamaki, and M. Yamamoto.
On the Boolean connectivity problem for Horn relations.
Discrete Appl. Math., 1580 (18):0 2024–2030,

[Makino et al., 2011]
K. Makino, S. Tamaki, and M. Yamamoto.
An exact algorithm for the Boolean connectivity problem for
Theoret. Comput. Sci., 4120 (35):0 4613–4618,

[Mouawad et al., 2017]
A. Mouawad, N. Nishimura, V. Pathak, and V. Raman.
Shortest reconfiguration paths in the solution space of Boolean
SIAM J. Discrete Math., 310 (3):0 2185–2200,

[Nishimura, 2018]
N. Nishimura.
Introduction to reconfiguration.
Algorithms (Basel), 110 (4):0 Paper No. 52,
25, 2018.

[Schwerdtfeger, 2012]
K. Schwerdtfeger.
A computational trichotomy for connectivity of Boolean
J. Satisf. Boolean Model. Comput., 80 (3-4):0
173–195, 2012/14.

[van den Heuvel, 2013]
J. van den Heuvel.
The complexity of change.
In Surveys in combinatorics 2013, volume 409 of London
Math. Soc. Lecture Note Ser., pages 127–160. Cambridge Univ. Press,
Cambridge, 2013.

[Wrochna, 2015]
M. Wrochna.
Homomorphism reconfiguration via homotopy.
In 32nd International Symposium on Theoretical Aspects
of Computer Science, volume 30 of LIPIcs. Leibniz Int. Proc.
Inform., pages 730–742. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern,

[Wrochna, 2020]
M. Wrochna.
Homomorphism reconfiguration via homotopy.
SIAM J. Discrete Math., 340 (1):0 328–350,

[Zhuk, 2020]
D. Zhuk.
A proof of the CSP dichotomy conjecture.
J. ACM, 670 (5):0 Art. 30, 78, 2020.


# Non-injectivity of the lattice map for non-mixed Anderson t-motives

A. Grishkov, D. Logachev111E-mails: shuragrigmail.com; logachev94gmail.com
(corresponding author)**************** First author: Departamento de
Matemática e estatistica Universidade de São Paulo. Rua de Matão 1010, CEP
05508-090, São Paulo, Brasil, and Omsk State University n.a. F.M.Dostoevskii.
Pr. Mira 55-A, Omsk 644077, Russia. Second author: Departamento de Matemática,
Universidade Federal do Amazonas, Manaus, Brasil

Let $M$ be an uniformizable Anderson t-motive and $L(M)$ its lattice. We prove
by an explicit construction that for non-mixed $M$ the lattice map $M\mapsto
L(M)$ is not injective.

Anderson t-motives; Lattice map

###### :

11G09

††support: Thanks: The first author is grateful to SNPq, Brazil, to RFBR,
Russia, grant 16-01-00577a (Secs. 1-4), and to Russian Science Foundation,
project 16-11-10002 (Secs. 5-8) for a financial support. The second author is
grateful to YoungJu Choie for the kind invitation to POSTECH. The paper grew
out of a discussion of its topic with students of a course given by the author
at POSTECH.

0\. Introduction. Let $M$ be an uniformizable Anderson t-motive of rank $r$,
dimension $n$, having its nilpotent operator $N$ equal to 0. Let
$L(M)\subset\mathbb{C}_{\infty}^{n}$ be its lattice, it is isomorphic to
$\mathbb{F}_{q}[\theta]^{r}$. Is the lattice map $M\mapsto L(M)$ an injection;
a surjection? Unlike the case of abelian varieties where there is a 1 – 1
correspondence between abelian varieties and lattices having a Riemann form,
in the functional field case we know much less. First, for the case of
Drinfeld modules, i.e. for $n=1$, we have a 1 – 1 correspondence between
Drinfeld modules and lattices in $\mathbb{C}_{\infty}$ ([D76]). By the theory
of duality (see [GL07]), we have a complete information for the case of pure
Anderson t-motives of rank $r$, dimension $r-1$, because they are duals of
Drinfeld modules (see Remark 3.7 for details). Further, there is a result (see
[GL17]) on a local surjectivity of the lattice map near $M=\goth C_{2}^{\oplus
n}$, where $\goth C_{2}$ is the rank 2 Carlitz module (see 2.1 for its
definition). The most important result is the injectivity of the lattice map
on the set of mixed uniformizable Anderson t-motives ([HJ20]). Recall that a
t-motive is called mixed if it has a filtration such that its quotients are
pure, of increasing weight. See [HJ20], Definition 3.5b for an exact
definition of mixedness, and [G96], Definition 5.5.2 for the definition of
purity. We prove in the present paper that the condition of mixedness is
necessary. Namely, we give an explicit construction of families of non-
isomorphic non-mixed $M$ such that their lattices coincide. The paper is
organized as follows. In Section 1 we give necessary definitions and
notations. Section 2 contains the proof, and Section 3 contains some comments,
remarks and possibilities of further research. 1\. Definitions and notations.
We use standard definitions for Anderson t-motives. Let $q$ be a power of a
prime, $\mathbb{F}_{q}$ the finite field of order $q$, $\theta$ a
transcendental element, $\mathbb{R}_{\infty}:=\mathbb{F}_{q}((1/\theta))$ the
finite characteristic analog of $\mathbb{R}$. It has a valuation $v$ defined
by $v(\theta)=-1$. Let $\overline{\mathbb{R}_{\infty}}$ be an algebraic
closure of $\mathbb{R}_{\infty}$. Let
$\mathbb{C}_{\infty}:=\widehat{\overline{\mathbb{R}_{\infty}}}$ be the
completion of $\overline{\mathbb{R}_{\infty}}$ with respect to (the only
continuation of) $v$. It is the finite characteristic analog of $\mathbb{C}$.
The Anderson ring $\mathbb{C}_{\infty}[T,\tau]$ is the ring of non-commutative
polynomials over $\mathbb{C}_{\infty}$ in two variables $T$, $\tau$ with the
following relations (here $a\in\mathbb{C}_{\infty}$):

$aT=Ta;\ \ \tau T=T\tau;\ \ \tau a=a^{q}\tau$

It has subrings $\mathbb{C}_{\infty}[T]$, $\mathbb{C}_{\infty}\\{\tau\\}$. Let
$A$ be a matrix with entries in $\mathbb{C}_{\infty}[T,\tau]$. We denote by
$A^{(k)}$, where $k\in\mathbb{Z}$, the matrix obtained by elevation of all
coefficients of all entries of $A$ to the $q^{k}$-th power ($T$ and $\tau$ are
not elevated to a power). Definition 1.1. An Anderson t-motive $M$ is a left
$\mathbb{C}_{\infty}[T,\tau]$-module satisfying conditions: 1.1.1. $M$ as a
$\mathbb{C}_{\infty}[T]$-module is free of finite dimension (denoted by $r$);
1.1.2. $M$ as a $\mathbb{C}_{\infty}\\{\tau\\}$-module is free of finite
dimension (denoted by $n$); 1.1.3. The action of $T-\theta$ on $M/\tau M$ is
nilpotent. Let $e_{*}:=\left(\begin{matrix}e_{1}\\\ \dots\\\
e_{n}\end{matrix}\right)$ be a basis of $M$ over
$\mathbb{C}_{\infty}\\{\tau\\}$. In order to define $M$, we need to define the
product $Te_{*}$:

$Te_{*}=A_{0}e_{*}+A_{1}\tau e_{*}+...+A_{k}\tau^{k}e_{*}$ $None$

where $A_{i}\in M_{n\times n}(\mathbb{C}_{\infty})$. Condition 1.1.3 is
equivalent to $A_{0}=\theta I_{n}+N$ where $N\in M_{n\times
n}(\mathbb{C}_{\infty})$ is nilpotent. We shall consider only $M$ having
$N=0$. Let $V=\mathbb{C}_{\infty}^{n}$ and $L\subset V$ is isomorphic to
$\mathbb{F}_{q}[\theta]^{r}$. Definition 1.3. $L$ is called a lattice of rank
$r$ if: 1.3.1. The $\mathbb{C}_{\infty}$-span of $L$ is $V$; 1.3.2. The
$\mathbb{R}_{\infty}$-span of $L$ has dimension $r$ over $\mathbb{R}_{\infty}$
(i.e. elements of a basis of $L$ over $\mathbb{F}_{q}[\theta]$ are linearly
independent over $\mathbb{R}_{\infty}$). Two lattices $L_{1}\subset V_{1}$,
$L_{2}\subset V_{2}$ are isomorphic if there exists a
$\mathbb{C}_{\infty}$-linear isomorphism $\varphi:V_{1}\to V_{2}$ such that
$\varphi(L_{1})=L_{2}$. 1.4. Lattice of a t-motive. Let us fix a basis $e_{*}$
of $M$ over $\mathbb{C}_{\infty}\\{\tau\\}$, and let $A_{i}$ be from (1.2).
The basis $e_{*}$ defines the following action of $T$ on
$\mathbb{C}_{\infty}^{n}$:

$T(Z)=\theta Z+A_{1}Z^{(1)}+...+A_{k}Z^{(k)}$

where $Z\in\mathbb{C}_{\infty}^{n}$ is a matrix column (recall that $N=0\
\implies\ A_{0}=\theta I_{n}$). The below theorems are proved in [D76] for the
case $n=1$, and in [A86] for the case of any $n$. Theorem 1.4.1. For a fixed
$e_{*}$ there exists the only map
$exp=exp_{M}:\mathbb{C}_{\infty}^{n}\to\mathbb{C}_{\infty}^{n}$ defined by the
formula

$exp(Z)=Z+C_{1}Z^{(1)}+C_{2}Z^{(2)}+...$ $None$

where $Z\in\mathbb{C}_{\infty}^{n}$ is a matrix column and $C_{i}\in
M_{n\times n}(\mathbb{C}_{\infty})$, making the following diagram commutative:

$\begin{matrix}\mathbb{C}_{\infty}^{n}&\overset
exp\to{\to}&\mathbb{C}_{\infty}^{n}&\\\ \\\
\theta\downarrow&&\downarrow&Z\mapsto T(Z)\\\ \\\
\mathbb{C}_{\infty}^{n}&\overset
exp\to{\to}&\mathbb{C}_{\infty}^{n}&\end{matrix}$ $None$

Theorem 1.4.2. $L(M):=\hbox{Ker }exp$ is a $\mathbb{F}_{q}[\theta]$-submodule
of $\mathbb{C}_{\infty}^{n}$ of dimension $\leq r$. Definition 1.4.3. $M$ is
called uniformizable if the dimension of $L(M)$ as a
$\mathbb{F}_{q}[\theta]$-module is $r$. Theorem 1.4.4. If $M$ is uniformizable
then $L(M)$ is a lattice in $\mathbb{C}_{\infty}^{n}$. It is well-defined,
i.e. if we change the basis $e_{*}$ by another basis $e^{\prime}_{*}$ then we
get an isomorphic lattice. We see that $L$ is a functor (a map on the level of
sets) from the set of uniformizable t-motives to the set of lattices, both up
to isomorphisms. Is it injective or surjective? The purpose of the present
paper is to show that it is not injective: we construct explicitly a set of
non-isomorphic uniformizable t-motives such that their lattices are
isomorphic. 2\. Construction. We need more notations and definitions. First,
the Carlitz module $\goth C$ is a t-motive having $n=r=1$, it is defined by
the formula

$Te=\theta e+\tau e$

where $e$ is the only element of a basis of $\goth C$ over
$\mathbb{C}_{\infty}\\{\tau\\}$. Let us denote
$\theta_{ij}:=\theta^{q^{i}}-\theta^{q^{j}}$ and for $j\geq 1$

$c_{j}:=\frac{1}{\theta_{j,j-1}\theta_{j,j-2}\cdot...\cdot\theta_{j1}\theta_{j0}}$

We have (Carlitz):

$exp_{\goth}C(z)=z+c_{1}z^{q}+c_{2}z^{q^{2}}+...$

We denote by $\pi_{1}$ a generator of the lattice $L(\goth C)$, it is unique
up to multiplication by $\mathbb{F}_{q}^{*}$. It is the finite characteristic
analog of $2\pi i\in\mathbb{C}$ which is defined up to $\pm 1$. 2.1. Further,
the Carlitz module of rank 2 (denoted by $\goth C_{2}$) is a t-motive having
$n=1,\ r=2$ (i.e. it is a Drinfeld module of rank 2) defined by the formula

$Te=\theta e+\tau^{2}e$

For even $j\geq 2$ we denote

$c_{2,j}:=\frac{1}{\theta_{j,j-2}\theta_{j,j-4}\cdot...\cdot\theta_{j2}\theta_{j0}}$

We have:

$exp_{\goth C_{2}}(z)=z+c_{2,1}z^{q^{2}}+c_{2,2}z^{q^{4}}+...$

We denote by $\pi_{2}$ a generator of the lattice $L(\goth C_{2})$, it is
unique up to multiplication by $\mathbb{F}_{q^{2}}^{*}$.

We choose and fix $\omega\in\mathbb{F}_{q^{2}}-\mathbb{F}_{q}$, i.e.
$(1,\omega)$ is a basis of $\mathbb{F}_{q^{2}}$ over $\mathbb{F}_{q}$. We
choose and fix $\pi_{1}$, $\pi_{2}$, hence $(\pi_{2},\omega\pi_{2})$ is a
basis of $L(\goth C_{2})$ over $\mathbb{F}_{q}[\theta]$. Let $M_{0}:=\goth
C_{2}\oplus\goth C$, and let $L_{0}:=L(M_{0})\subset\mathbb{C}_{\infty}^{2}$
be its lattice. We have: elements

$l_{1}:=\left(\begin{matrix}0\\\ \pi_{1}\end{matrix}\right),\ \ \
l_{2}:=\left(\begin{matrix}\pi_{2}\\\ 0\end{matrix}\right),\ \ \
l_{3}:=\left(\begin{matrix}\omega\pi_{2}\\\ 0\end{matrix}\right)$ $None$

is a basis of $L_{0}$ over $\mathbb{F}_{q}[\theta]$.

Let $a\in\mathbb{C}_{\infty}$ and $M(a)$ be a t-motive of rank 2, dimension 3,
defined by

$T\left(\begin{matrix}e_{1}\\\
e_{2}\end{matrix}\right)=\left(\begin{matrix}\theta&0\\\
0&\theta\end{matrix}\right)\left(\begin{matrix}e_{1}\\\
e_{2}\end{matrix}\right)+\left(\begin{matrix}0&a\\\
0&1\end{matrix}\right)\tau\left(\begin{matrix}e_{1}\\\
e_{2}\end{matrix}\right)+\left(\begin{matrix}1&0\\\
0&0\end{matrix}\right)\tau^{2}\left(\begin{matrix}e_{1}\\\
e_{2}\end{matrix}\right)$ $None$

It is reducible and non-mixed, see Remark 3.1. We shall prove: Proposition
2.4. There exists a neighborhood $U$ of $0\in\mathbb{C}_{\infty}$ such that
$\forall\ a\in U$ we have: $M(a)$ is uniformizable and $L(M(a))=L_{0}$.
Proposition 2.5. For a fixed $a$ there are only finitely many $a^{\prime}$
such that $M(a)=M(a^{\prime})$. This implies that the lattice map is not
injective. Proof of Proposition 2.4. We need the notion of a Siegel matrix of
a lattice. It is defined exactly like in the case of abelian varieties. Let
$l_{1},\dots,l_{r}$ be a basis of $L$ over $\mathbb{F}_{q}[\theta]$ such that
$l_{1},\dots,l_{n}$ is a basis of $V$ over $\mathbb{C}_{\infty}$. The Siegel
matrix $S\in M_{(r-n)\times n}(\mathbb{C}_{\infty})$ of $L$ with respect to a
basis $l_{1},\dots,l_{r}$ is defined by the formula

$\left(\begin{matrix}l_{n+1}\\\ \dots\\\
l_{r}\end{matrix}\right)=S\left(\begin{matrix}l_{1}\\\ \dots\\\
l_{n}\end{matrix}\right)$

Two lattices $L_{1}$, $L_{2}$ are isomorphic if there exist bases $l_{1*},\
l_{2*}$ of $L_{1}$, $L_{2}$ such that their Siegel matrices $S_{1}$, $S_{2}$
are equal. (2.2) implies that $S$ of $L_{0}$ is $(0,\omega)$. Let us show that
$\forall\ a\in\mathbb{C}_{\infty}$ a Siegel matrix of $L(M(a))$ is the same.
$C_{i}$ from (1.4.1a) for $M(a)$ satisfy the recurrence relation

$C_{m}=\frac{A_{1}C^{(1)}_{m-1}+A_{2}C^{(2)}_{m-2}}{\theta_{m0}}$

where $C_{m}=0$ for $m<0$, $C_{0}=I_{2}$, $A_{1},\ A_{2}$ are from (2.3), i.e.
$A_{1}=\left(\begin{matrix}0&a\\\ 0&1\end{matrix}\right)$,
$A_{2}=\left(\begin{matrix}1&0\\\ 0&0\end{matrix}\right)$. We get by induction
that

$C_{m}=\left(\begin{matrix}c_{2,m}&*\\\ 0&c_{m}\end{matrix}\right)\hbox{ for
$m$ even, }C_{m}=\left(\begin{matrix}0&*\\\ 0&c_{m}\end{matrix}\right)\hbox{
for $m$ odd. }$

For sufficiently small $a$ we have: $M(a)$ is uniformizable.222Most likely
$M(a)$ is uniformizable for all $a$. We do not need this fact. We see that
there is a basis $l_{1}(a),\ l_{2}(a),\ l_{3}(a)$ of $L(M(a))$ over
$\mathbb{F}_{q}[\theta]$ such that
$l_{2}(a)=l_{2}=\left(\begin{matrix}\pi_{2}\\\ 0\end{matrix}\right),\ \ \
l_{3}(a)=l_{3}=\left(\begin{matrix}\omega\pi_{2}\\\ 0\end{matrix}\right)$,
while $l_{1}(a)\neq l_{1}=\left(\begin{matrix}0\\\
\pi_{1}\end{matrix}\right)$. We get that the Siegel matrix of $L(M(a))$ with
respect to $l_{1}(a),\ l_{2}(a),\ l_{3}(a)$ is the same $(0,\omega)$.
$\square$ Proof of Proposition 2.5. We need a few facts on
$GL_{2}(\mathbb{C}_{\infty}\\{\tau\\})$. Let

$X:=X_{0}+X_{1}\tau+...+X_{k}\tau^{k}\in M_{2\times
2}(\mathbb{C}_{\infty}\\{\tau\\}),$ $None$

where $X_{i}=\left(\begin{matrix}x_{i11}&x_{i12}\\\
x_{i21}&x_{i22}\end{matrix}\right)\in M_{2\times 2}(\mathbb{C}_{\infty}).$ We
have: $\exists\ Y\in M_{2\times 2}(\mathbb{C}_{\infty}\\{\tau\\})$ such that
$XY=1\implies|X_{0}|\neq 0\implies X$ is not a zero divisor from both right
and left $\implies YX=1$, i.e. $X\in GL_{2}(\mathbb{C}_{\infty}\\{\tau\\})$.
Further, if for $X\in GL_{2}(\mathbb{C}_{\infty}\\{\tau\\})$ we have $\forall\
i\ \ x_{i21}=0$ then

$\sum_{i=0}^{k}x_{i11}\tau^{i},\
\sum_{i=0}^{k}x_{i22}\tau^{i}\in\mathbb{C}_{\infty}\\{\tau\\}^{*}\implies\forall\
i>0\ \ x_{i11}=x_{i22}=0.$ $None$

Let us assume that $M(a)=M(a^{\prime})$. Multiplication by $T$ in
$M(a^{\prime})$ is given by

$T\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)=\left(\begin{matrix}\theta&0\\\
0&\theta\end{matrix}\right)\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)+\left(\begin{matrix}0&a^{\prime}\\\
0&1\end{matrix}\right)\tau\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)+\left(\begin{matrix}1&0\\\
0&0\end{matrix}\right)\tau^{2}\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)$ $None$

An isomorphism between $M(a)$ and $M(a^{\prime})$ is given by a matrix $X$
from (2.7) of change of basis (where $x_{***}$ are indeterminate
coefficients), i.e.

$\left(\begin{matrix}e_{1}\\\
e_{2}\end{matrix}\right)=X\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right).$ $None$

We substitute (2.10) to (2.3), and we multiply (2.9) by $X$ from the left. We
get matrix equalities:

$TX\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)=\left(\begin{matrix}\theta&0\\\
0&\theta\end{matrix}\right)X\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)+AX^{(1)}\tau\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)+\left(\begin{matrix}1&0\\\
0&0\end{matrix}\right)X^{(2)}\tau^{2}\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)$ $None$
$XT\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)=X\left(\begin{matrix}\theta&0\\\
0&\theta\end{matrix}\right)\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)+XA^{\prime}\tau\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)+X\left(\begin{matrix}1&0\\\
0&0\end{matrix}\right)\tau^{2}\left(\begin{matrix}e^{\prime}_{1}\\\
e^{\prime}_{2}\end{matrix}\right)$ $None$

where $A=\left(\begin{matrix}0&a\\\ 0&1\end{matrix}\right)$,
$A^{\prime}=\left(\begin{matrix}0&a^{\prime}\\\ 0&1\end{matrix}\right)$.
Equality of coefficients at $\tau^{m}$ of (2.11) and (2.12) is

$\theta X_{m}+AX_{m-1}^{(1)}+\left(\begin{matrix}1&0\\\
0&0\end{matrix}\right)X_{m-2}^{(2)}=\theta^{q^{m}}X_{m}+X_{m-1}{A^{\prime}}^{(m-1)}+X_{m-2}\left(\begin{matrix}1&0\\\
0&0\end{matrix}\right)$ $None$

where $m=0,\dots,k+2$ and $X_{i}=0$ if $i\not\in 0,\dots,k$. (2.13) shows that
if $x_{m21}=x_{m-1,21}=0$ then $x_{m-2,21}=0$. By induction from up to down we
get that $\forall\ m\ x_{m21}=0$. Hence, (2.8) implies that if $k\geq 1$ then
$X_{k}=\left(\begin{matrix}0&*\\\ 0&0\end{matrix}\right)$. Further, for
$m=k+2$ (2.13) becomes

$X_{k}\left(\begin{matrix}1&0\\\
0&0\end{matrix}\right)=\left(\begin{matrix}1&0\\\
0&0\end{matrix}\right)X_{k}^{(2)}\iff x_{k11}\in\mathbb{F}_{q^{2}},\
x_{k12}=x_{k21}=0$

This means that $k=0$, $X=X_{0}=\left(\begin{matrix}x_{011}&0\\\
0&x_{022}\end{matrix}\right)$. Finally, (2.13) for $m=1$ is

$X_{0}\left(\begin{matrix}0&a\\\
0&1\end{matrix}\right)=\left(\begin{matrix}0&a\\\
0&1\end{matrix}\right)X_{0}^{(1)},\hbox{ i.e. }\left(\begin{matrix}0&x_{011}\
a^{\prime}\\\ 0&x_{022}\end{matrix}\right)=\left(\begin{matrix}0&x_{022}^{q}\
a\\\ 0&x_{022}^{q}\end{matrix}\right)$

This means that $x_{022}\in\mathbb{F}_{q}$ and $M(a)$ is isomorphic to
$M(a^{\prime})$ iff $a^{\prime}/a\in\mathbb{F}_{q^{2}}$. $\square$ 3\.
Comments and remarks. Remark 3.1. $M(a)$ enters in an exact sequence

$0\to\goth C\to M(a)\to\goth C_{2}\to 0$ $None$

Arguments similar to [HJ20], Example 3.9 show that $M(a)$ is not mixed (if
$a\neq 0$), because $\hbox{wt }(\goth C)=1>\hbox{wt }(\goth
C_{2})=\frac{1}{2}$.

We can consider t-motives $M_{m}(a)$ (subscript $m$ means mixed) defined by
the same (2.3) but with $A_{m}(a):=\left(\begin{matrix}0&0\\\
a&1\end{matrix}\right)$ instead of $A=\left(\begin{matrix}0&a\\\
0&1\end{matrix}\right)$. These $M_{m}(a)$ enter in an exact sequence

$0\to\goth C_{2}\to M_{m}(a)\to\goth C\to 0$ $None$

hence they are mixed. Arguments similar to the ones of the proof of
Proposition 2.4 show that the Siegel matrices333For sufficiently small $a$ the
notion of the Siegel matrix of $M_{m}(a)$ is well-defined: it is the Siegel
matrix of the basis which is the nearest to $l_{1},\ l_{2},\ l_{3}$. of
$M_{m}(a)$ are different. 3.4. The set of these Siegel matrices of $M_{m}(a)$
is one-dimensional. Apparently it is the simplest - after the case of Drinfeld
modules of rank 2 - family of Siegel matrices of t-motives. Hence, it looks as
a generalization of the Drinfeld upper half plane. Maybe it will be possible
to generalize the theory of the Drinfeld upper half plane to this case? Remark
3.5. We can expect that there are irreducible non-pure t-motives having non-
injective lattice map. Really, let us consider the family of $M=M(a_{**})$
defined by (1.2) where $A_{0}=\theta I_{2},\
A_{1}=\left(\begin{matrix}a_{11}&a_{12}\\\ a_{21}&1\end{matrix}\right),\
A_{2}=\left(\begin{matrix}1&0\\\ 0&0\end{matrix}\right)$. They have $r=3$,
$n=2$, they are uniformizable for small $a_{**}$, non-pure and irreducible for
almost all $a_{**}$. Conjecturally, for generic $a_{**}$ there are only
finitely many $a^{\prime}_{**}$ such that $M(a_{**})$ is isomorphic to
$M(a^{\prime}_{**})$, hence the set of $M(a_{**})$ has dimension 3 over
$\mathbb{C}_{\infty}$. Clearly the set of lattices of $M(a_{**})$ has
dimension 2 over $\mathbb{C}_{\infty}$, because it is defined by a $1\times 2$
Siegel matrix. We get that fibers of the lattice map have dimension 1.
Conjecturally, they are analytic curves in the space $<a_{11},a_{12},a_{21}>$.
Remark 3.6. The set of $M(a)$ of (3.2) is
$\hbox{Ext}^{1}_{\mathbb{C}_{\infty}[T,\tau]}(\goth C_{2},\goth C_{1})$. We
have: $\hbox{Ext}^{1}_{\mathbb{C}_{\infty}[T,\tau]}(\goth C_{2},\goth C_{1})$
is a module over $Z(\mathbb{C}_{\infty}[T,\tau])=\mathbb{F}_{q}[T]$. We showed
in Proposition 2.5 that $\hbox{Ext}^{1}_{\mathbb{C}_{\infty}[T,\tau]}(\goth
C_{2},\goth C_{1})$ can be considered as having dimension 1 over
$\mathbb{C}_{\infty}$. Hence, it is meaningful to consider a new invariant of
a non-uniformizable t-motive $M$, namely the dimension of
$\hbox{Ext}^{1}_{\mathbb{C}_{\infty}[T,\tau]}(M,Z_{1})$ (here
$Z_{1}=\mathbb{C}_{\infty}\\{T\\}$ is from [G96], (5.9.22)) over
$\mathbb{C}_{\infty}$. Recall that $M$ is uniformizable
$\iff\hbox{Ext}^{1}_{\mathbb{C}_{\infty}[T,\tau]}(M,Z_{1})=0$. As a
$\mathbb{F}_{q}[T]$-module, most likely,
$\hbox{Ext}^{1}_{\mathbb{C}_{\infty}[T,\tau]}(M,Z_{1})$ is infinite-
dimensional, but we can expect that over $\mathbb{C}_{\infty}$ the dimension
is finite and gives us an invariant of $M$. The same question holds for Coker
$\exp_{M}\subset\hbox{Ext}^{1}_{\mathbb{C}_{\infty}[T,\tau]}(M,Z_{1})$. Remark
3.7. What is the image of the lattice map? We mentioned in the Introduction
that pure Anderson t-motives of rank $r$, dimension $r-1$ are duals of
Drinfeld modules. Hence, by the theory of duality ([GL07]), there is a 1 – 1
correspondence between pure Anderson t-motives of rank $r$, dimension $r-1$,
and lattices of rank $r$ in $\mathbb{C}_{\infty}^{r-1}$ having duals. Not all
these lattices have dual. Really, a matrix $S=\left(\begin{matrix}s_{1}\\\
\dots\\\ s_{r-1}\end{matrix}\right)\in M_{(r-1)\times 1}(\mathbb{C}_{\infty})$
is a Siegel matrix of a lattice of rank $r$ in $\mathbb{C}_{\infty}$ iff

$1,s_{1},\dots,s_{r-1}\hbox{ are linearly independent over
}\mathbb{R}_{\infty}$ $None$

while its transposed
$S^{t}=\left(\begin{matrix}s_{1}&\dots&s_{r-1}\end{matrix}\right)\in
M_{1\times(r-1)}(\mathbb{C}_{\infty})$ is a Siegel matrix of a lattice of rank
$r$ in $\mathbb{C}_{\infty}^{r-1}$ iff

$\exists\ i\hbox{ such that }s_{i}\not\in\mathbb{R}_{\infty}$ $None$

For $r>2$ (3.7.2) is weaker than (3.7.1), i.e. not all lattices of rank $r$ in
$\mathbb{C}_{\infty}^{r-1}$ have duals. Most likely the same phenomenon occurs
for Siegel matrices of other sizes. For example, we expect that $\exists\ S\in
M_{2\times 2}(\mathbb{C}_{\infty})$ such that $S$ is a Siegel matrix of a
lattice while $S^{t}$ is not. We think that it is necessary to modify the
Definition 1.3 of a lattice, in order to get the surjectivity of the lattice
map. References [A86] Anderson, G.W. t-motives. Duke Math. J., 1986, vol. 53,
No. 2, p. 457 – 502. [D76] V.G. Drinfeld, Elliptic modules. Math. USSR Sb. 4
(1976) 561 – 592. [GL07] Grishkov A., Logachev, D. Duality of Anderson
t-motives. 2007.

http://arxiv.org/pdf/math/0711.1928.pdf [GL17] Grishkov A., Logachev, D.
Lattice map for Anderson t-motives: first approach. J. of Number Theory. 2017,
vol. 180, p. 373 – 402.

http://arxiv.org/pdf/math/1109.0679.pdf [HJ20] Hartl U.; Juschka A.-K. Pink’s
theory of Hodge structures and the Hodge conjecture over function fields.
”t-motives: Hodge structures, transcendence and other motivic aspects”,
Editors G. Böckle, D. Goss, U. Hartl, M. Papanikolas, European Mathematical
Society Congress Reports 2020, and https://arxiv.org/pdf/1607.01412.pdf