\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\OneNumberAllTheorems
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\DeclarePairedDelimiter\abs{\lvert}{\rvert}
%\equalenv{definition}{defi}
%\equalenv{remark}{rema}
%\equalenv{corollary}{coro}
%\theoremstyle{definition}
%\newtheorem{definition}{Definition}
\newenvironment{claim}{\begin{enonce} {Claim}}{\end{enonce}}
\newcommand{\Z}{\mathbb Z}
\newcommand{\0}{\mathbf 0}
\newcommand{\wt}[1]{\widetilde{#1}}
\newcommand{\ii}{\mathrm{i}}
\newcommand{\iii}{\mathrm{i}}
\DeclareMathOperator{\expe}{e}
\DeclareMathOperator{\modrm}{mod}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% a placer avant \begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
%%%1
\author{\firstname{Ada} \lastname{Chan}}
\address{Department of Mathematics and Statistics\\
York University\\
Toronto\\
ON\\
Canada}
\email{ssachan@yorku.ca}
%%%2
\author{\firstname{Whitney} \lastname{Drazen}}
\address{Department of Mathematics\\
Northeastern University\\
Boston\\
MA\\
USA}
\email{drazen.w@husky.neu.edu}
%%%3
\author{\firstname{Or} \lastname{Eisenberg}}
\address{Department of Mathematics\\
Harvard University\\
Cambridge\\
MA\\
USA}
\email{oreisenberg@college.harvard.edu}
%%%4
\author{\firstname{Mark} \lastname{Kempton}}
\address{Department of Mathematics\\
Brigham Young University\\
Provo\\
UT\\
USA}
\email{mkempton@mathematics.byu.edu}
%%%5
\author{\firstname{Gabor} \lastname{Lippner}}
\address{Department of Mathematics\\
Northeastern University\\
Boston\\
MA\\
USA}
\email{g.lippner@northeastern.edu}
\thanks{G.~L. was supported by NSF/DMS-1800738 and the Simons Foundation Collaboration Grant. O.~E. was supported by the Herchel Smith Harvard Undergraduate Research Program.
}
%%%%% Sujet
\keywords{Fractional revival, state transfer, quantum, graph}
\subjclass{05E30, 05C50, 33C05, 15A16, 81P40}
%%%%% Titre et résumé
\title
{Pretty good quantum fractional revival in paths and cycles}
\begin{abstract}
We initiate the study of pretty good quantum fractional revival in graphs,
a generalization of pretty good quantum state transfer in graphs. We give a complete characterization of pretty good fractional revival in a graph in terms of the eigenvalues and eigenvectors of the adjacency matrix of a graph. This characterization follows from a lemma due to Kronecker on Diophantine approximation, and is similar to the spectral characterization of pretty good state transfer in graphs. Using this, we give complete characterizations of when pretty good fractional revival can occur in paths and in cycles.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%% Abstracts must be placed before \maketitle
\maketitle
%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%
In recent years, tools and methods from algebraic and spectral graph theory have found important application in quantum information theory regarding the transfer of information through a quantum network. Namely, given a graph that represents a network of interacting qubits, information transfer in this network can be modeled by a \emph{quantum walk} on the graph. A quantum walk is a process governed by the transition matrix
\[
U(t) \coloneqq \expe^{\iii tA}
\]
where $A$ is the adjacency matrix of the graph. We say that there is \emph{perfect state transfer} at time $t$ between nodes $u$ and $v$ of such a network when the $(u,v)$-entry of $U(t)$ has absolute value 1. The study of perfect state transfer in graphs was initiated by Bose in 2003~\cite{Bose2003}, and since then, the problem has attracted considerable attention, both from the quantum information community and from the algebraic graph theory community (see for instance~\cite{christandl2005,godsil,godsil2,kay2010,us,kay2011} and references therein).
It has been shown that in simple, unweighted graphs, perfect state transfer is very difficult to achieve and occurs only rarely~\cite{godsil2}. Known constructions that achieve perfect state transfer involve either highly specialized unweighted graphs or highly non-uniform edge weights. For instance, in simple unweighted path graphs, perfect state transfer occurs only in paths of length 2 and 3, and not in paths of any higher length~\cite{godsil}. As such, various relaxations and generalizations of perfect state transfer have been studied. Most notably, the notion of \emph{pretty good state transfer} was introduced by Godsil~\cite{godsil} and Vinet et al.~\cite{Vinet2012}. There is pretty good state transfer from node $u$ to node $v$ in a graph if for all $\epsilon>0$ there is a $t>0$ such that $|U(t)(u,v)|>1-\epsilon$. Pretty good state transfer has been extensively studied~\cite{Coutinho:PGST,eisenberg2019pretty,godsil,Godsil2012,invol,Vinet2012}. Work in~\cite{Godsil2012}, \cite{Coutinho2016}, and~\cite{vanBommel2016} gives a complete characterization of when pretty good state transfer occurs in simple, unweighted paths.
\looseness-1
Another generalization of perfect state transfer that has been studied recently is \emph{fractional revival} in graphs~\cite{ChanCoutinhoTamonVinetZhan}. For nodes $u,v$ in a graph, there is fractional revival at time $t$ from $u$ to $v$, if \[|U(t)(u,u)|^2 + |U(t)(u,v)|^2 = 1.\] %with $|U(t)(u,v)|\neq0$.
It was shown in~\cite{ChanCoutinhoTamonVinetZhan} that if there is fractional revival from $u$ to $v$, then there is fractional revival from $v$ to $u$ at the same time. Thus, we will simply say there is fractional revival between $u$ and $v$ at time $t$. Where perfect state transfer represents the exact transfer of a quantum state between two nodes, fractional revival represents the transfer of a quantum state to a superposition over exactly two nodes. Fractional revival is important in the study of entanglement generation~\cite{ChanCoutinhoTamonVinetZhan}. Fractional revival in weighted paths is studied in~\cite{bernard2018graph,ChanCoutinhoTamonVinetZhan,chen2007fractional,christandl2017analytic,GenestVinetZhedanov1,GenestVinetZhedanov}.
In simple, unweighted paths, it has been shown that fractional revival can occur between two nodes only in paths of length 2, 3, or 4~\cite{ChanCoutinhoTamonVinetZhan}.
It is natural, then, to relax the condition for fractional revival to get an approximation, in the same way that perfect state transfer is relaxed to pretty good state transfer. That is, we say there is \emph{pretty good fractional revival} between nodes $u$ and $v$ in a graph if, for all $\epsilon >0$ there is a $t>0$ such that $U(t)$ is within $\epsilon$ of exhibiting fractional revival. We formulate this more precisely in Section~\ref{sec:PGFR}. %\[|U(t)(u,u)|^2+|U(t)(u,v)|^2 > 1-\epsilon.\]
In~\cite{ChanCoutinhoTamonVinetZhan}, the study of pretty good fractional revival is listed as a major open area of research in the study of fractional revival on graphs.
The main results of this paper are complete characterizations of when pretty good fractional revival can occur in simple, unweighted paths, and in simple, unweighted cycles. Specifically, we prove the following theorems.
\begin{theorem}\label{thm:main}
Let $P_n$ denote the path on $n$ vertices, and label the vertices $1,\dots,n$. Then pretty good fractional revival occurs between nodes of $P_n$ if and only if we are in one of the following cases:
\begin{itemize}
%\item (all symmetric nodes) $n=p-1, 2p-1,$ or $2^k-1$ for some prime $p$. Here fractional revival occurs between any pair of symmetric nodes.
\item (symmetric nodes) $n=p\cdot 2^k-1$ for $p$ a prime. Here fractional revival occurs between nodes $a$ and $p\cdot 2^k-a$ when $a$ is a multiple of $2^{k-1}$.
\item (asymmetric nodes) $n=5\cdot 2^k-1$. Here fractional revival occurs between nodes $2^k$ and $3\cdot 2^k$ (or, by symmetry, between $2\cdot 2^k$ and $4\cdot 2^k$).
\end{itemize}
\end{theorem}
\begin{theorem}\label{thm:main2}
Let $C_n$ denote the cycle on vertices $1,\dots, n$. Pretty good fractional revival occurs between vertices $a$ and $b$ in $C_n$ if and only if
$n=2p^k$, for some prime $p$, for $k\geq 1$,
and $b=a+n/2$.
\end{theorem}
In paths, we observe that between pairs of symmetric nodes, pretty good fractional revival occurs exactly when there is pretty good state transfer (see~\cite{vanBommel2016}). Surprisingly, there are instances of pretty good fractional revival between pairs of asymmetric nodes as well. We also remark that pretty good state transfer occurs in $C_n$ if and only if $n=2^k$ for some $k$ (see~\cite{MR3665556}). Thus we extend to a larger infinite family where pretty good fractional revival occurs. In the case of cycles, pretty good fractional revival only occurs between antipodal nodes.
It is well-known~\cite{godsil,Godsil2012} that a necessary condition for both perfect and pretty good state transfer between two nodes $u$ and $v$ is that they be \emph{strongly cospectral}, namely, that $\phi(u) = \pm\phi(v)$ for any eigenvector $\phi$ of the adjacency matrix. In~\cite{chan2020fundamentals}, we have generalized the notion of strong cospectrality to that of \emph{strong fractional cospectrality}. That is, two vertices $u$ and $v$ are strongly fractionally cospectral if there is some constant $C\neq0$ such that either $\phi(u) = C\phi(v)$ or $\phi(u) = (-1/C)\phi(v)$ for all eigenvectors $\phi$ of the adjacency matrix. We showed in~\cite{chan2020fundamentals} that strong fractional cospectrality is a necessary condition for fractional revival. In this paper, we show that strong fractional cospectrality is also a necessary condition for pretty good fractional revival. In addition, work in~\cite{chan2020fundamentals} characterizes fractional cospectrality in terms of a condition on walk counts at the vertices $u$ and $v$, analogous to the walk count condition for cospectrality (see~\cite{godsil,godsil_smith_2017}). One of the main steps in our proof of the Theorem~\ref{thm:main} is to analyze the counts of closed walks in a path to characterize when two nodes of a path are fractionally cospectral.
In~\cite{Godsil2012,invol} a characterization for pretty good state transfer between two cospectral nodes was given in terms of a number-theoretic condition on the eigenvalues of the adjacency matrix. This number-theoretic condition arises as a consequence of a lemma due to Kronecker on Diophantine approximation. Our primary tool in the proof of Theorems~\ref{thm:main} and~\ref{thm:main2}, and one of the major contributions of this paper, is a generalization of this spectral characterization for pretty good fractional revival, again relying on the Kronecker Diophantine approximation lemma (see Theorem~\ref{thm:kronecker} below).
%%%%%%%%%%%%%%
\section{Pretty good fractional revival}\label{sec:PGFR}
%%%%%%%%%%%%%%
%\begin{definition}
%We say there is \emph{pretty good fractional revival} between nodes $u$ and $v$ in $G$ if, for all $\epsilon>0$ there is some time $t>0$ such that
%\[
%|e^{itA}(u,u)|^2+|e^{itA}(u,v)|^2 > 1-\epsilon.
%\]
%\end{definition}
We remark that fractional revival at $u$ and $v$ is equivalent to saying that $U(t)$ is block diagonal at time $t$:
\[
U(t) = \begin{bmatrix}
H&0\\0&M
\end{bmatrix}
\]
where $H = \begin{bmatrix}
\alpha&\beta\\\beta&\gamma
\end{bmatrix}$ is some unitary $2\times 2$ matrix indexed by $u$ and $v$. Perfect state transfer is the special case where $\alpha=\gamma=0$. Pretty good fractional revival can be formulated in the same terms. We say there is \emph{pretty good fractional revival} (PGFR) between $u$ and $v$ if for all $\epsilon>0$ there is a $t_\epsilon>0$ where $U(t_\epsilon)$ has the block form
\[
U(t_\epsilon) = \begin{bmatrix}
H(t_\epsilon) & X_\epsilon\\X_\epsilon&M_\epsilon
\end{bmatrix}
\]
with each row of $X_\epsilon$ having magnitude at most $\epsilon$, and where $H(t_\epsilon)$ is $2\times 2$ and corresponds to vertices $u$ and $v$.
A necessary condition for pretty good state transfer between $u$ and $v$ is that $u$ and $v$ be strongly cospectral (see~\cite{godsil}). In~\cite{chan2020fundamentals}, a generalization of the notion of cospectrality is given in the framework of fractional revival. This concept is called fractional cospectrality, which we now define.
\begin{definition}
Let $H$ be a non-diagonal $2\times2$ symmetric unitary matrix, and let $u,v$ be vertices of a graph $G$ with adjacency matrix $A$. Given a vector $x$ indexed by vertices of $G$, let $\widetilde{x}$ be the restriction of $x$ to only vertices $u$ and $v$.
\begin{enumerate}
\looseness-1
\item\label{defi1.1_1} We say that $u$ and $v$ are \emph{fractionally cospectral} with respect to $H$ if there is a basis $\varphi_1,\ldots,\varphi_n$ of eigenvectors of $A$ such that $\widetilde \varphi_i$ is either 0 or an eigenvector $H$.
\item\label{defi1.1_2} We say that $u$ and $v$ are \emph{strongly fractionally cospectral} with respect to $H$, if for every eigenvector $\varphi$ of $A$, either $\widetilde\varphi = 0$ or $\widetilde\varphi$ is an eigenvector of $H$.
\end{enumerate}
\end{definition}
The following theorem comes from~\cite{chan2020fundamentals} and gives a characterization of fractional cospectrality in terms of walk counts at $u$ and $v$ (recall that $A^k(x,y)$ enumerates walks of length $k$ between $x$ and $y$ in $G$).
\begin{theorem}[{\cite[Theorem 8.3]{chan2020fundamentals}}]\label{thm:frac_cosp}
Let $u$ and $v$ be vertices of $G$, and $H$ be a $2\times 2$ non-diagonal unitary symmetric matrix with eigenvectors $\psi_1 = [p,q]^T$ and $\psi_2 = [-q,p]^T$. Then the following are equivalent:
\begin{enumerate}
\item\label{Theo2.2_1} $u$ and $v$ are fractionally cospectral with respect to $H$.
%\item $\langle E_r(pe_u+qe_v),E_r(-qe_u+pe_v)\rangle=0$ for all $r$.
%\item There exists a basis of eigenvectors $\varphi_1,\ldots,\varphi_n$ of $M$ that satisfies either $\varphi_k(u)=\frac{p}{q}\varphi_k(v)$ or $\varphi_k(u)=-\frac{q}{p}\varphi(v)$ for all $k$.
%\item $(E_r)_{u,u} -\left(\frac{p}{q} - \frac{q}{p}\right)(E_r)_{u,v}- (E_r)_{v,v}=0$ for all $r$.
\item\label{Theo2.2_2} $A^k(u,u)-A^k(v,v) = \left(\frac{p}{q} - \frac{q}{p}\right)A^k(u,v)$ for all $k$.
%\item $\phi_{A_u}-\phi_{A_v} = \left(\frac{p}{q} - \frac{q}{p}\right)\phi_{u,v}$.
\end{enumerate}
\end{theorem}
This characterization allows us to investigate fractional cospectrality via the combinatorics of walks in a graph. We will use this tool in Section~\ref{sec:cosp}
Note that fractional cospectrality only requires the existence of a particular basis of eigenvectors whose restrictions are eigenvectors of $H$, while strong cospectrality requires this of all possible eigenvectors of $H$. Thus, if all the eigenvalues are simple, then fractional cospectrality immediately implies strong fractional cospectrality. Observe that when $H$ is not a multiple of the identity, $H$ has two distinct eigenvalues. Fractional cospectrality with respect to $H$ naturally groups the eigenvalues of $A$ into two groups: one group is the eigenvalues for which the eigenvectors from our particular basis restrict to a certain eigenvector of $H$, and the other group is the eigenvalues for which the eigenvectors in the basis restrict to the other eigenvector of $H$. Thus if two nodes are fractionally cospectral but not strongly fractionally cospectral, then it must be the case that $A$ has an eigenvalue with multiplicity at least two, and this grouping puts this eigenvalue into both groups.
%FR COSP NATURALLY GROUPS EIGENVECTORS INTO TWO GROUPS, DISJOINT IF STR FR COSP
Notice that fractional revival includes the case that $H$ is the identity matrix, in which case the vertices $u$ and $v$ are \emph{periodic}. However, approximate periodicity, or pretty good periodicity, by a standard compactness argument, occurs for every vertex simultaneously (see~\cite[Section 6]{fan2013pretty}), and thus its study for pairs is uninteresting. Hence, in our discussion of pretty good fractional revival, we will exclude the case where two vertices are approximately periodic.
%DISCUSSION OF PGFR VS "PRETTY PERIODIC"
%%%%%%%%
\subsection{A spectral characterization}
%%%%%%%%
In this section we will give a spectral characterization of pretty good fractional revival, analogous to that for pretty good state transfer (see~\cite{Godsil2012,invol,vanBommel2016}). This characterization is based on the number theoretic lemma due to Kronecker.
\begin{lemma}[Kronecker]\label{lem:Kron}
Let $\theta_0,\ldots,\theta_d$ and $\zeta_0,\ldots,\zeta_d$ be arbitrary real numbers. For an arbitrarily small $\epsilon$, the system of inequalities
\[
|\theta_ry - \zeta_r| < \epsilon~~ (\modrm 2\pi),~~ (r=0,\ldots,d),
\]
has a solution $y$ if and only if, for integers $\ell_0,\ldots,\ell_d$,
\[
\ell_0\theta_0+\cdots+\ell_d\theta_d = 0,
\]
implies
\[
\ell_0\zeta_0 + \cdots + \ell_d\zeta_d \equiv 0~~ (\modrm 2\pi).
\]
\end{lemma}
\begin{theorem}\label{thm:kronecker}
There is pretty good fractional revival between $u$ and $v$ if and only if the following two conditions are satisfied:
\begin{enumerate}
\item\label{Theo2.4_1} $u$ and $v$ are fractionally cospectral;
\item\label{Theo2.4_2} let $\Pi_1,\Pi_2$ be the two groups of eigenvalues coming from the grouping on the eigenvalues given by the fractional cospectrality (see the comment after Theorem~\ref{thm:frac_cosp}). For any integers $\ell_i$,
\begin{align*}
\sum_{i\in\Pi_1}\ell_i\lambda_i + \sum_{j\in\Pi_2}\ell_j\lambda_j &= 0\\
\sum_i\ell_i&=0
\end{align*}
implies
\[
\sum_{i\in\Pi_1}\ell_i\neq\pm1.
\]
\end{enumerate}
\end{theorem}
We will first prove the following lemmas before proceeding with the proof of the theorem.
\begin{lemma}\label{lem:pgfr-strfrcsp}
If there is pretty good fractional revival between $u$ and $v$, then $u$ and $v$ are strongly fractionally cospectral.
\end{lemma}
\begin{proof}
Since we have PGFR from $u$ to $v$, then for every $\epsilon>0$, there is a $t_\epsilon>0$ such that we can write
\[
U(t_\epsilon) = \begin{bmatrix}
H(t_\epsilon)&X_\epsilon\\X_\epsilon^T&M_\epsilon
\end{bmatrix}
\]
where $H(t_\epsilon)$ is a $2\times 2$ matrix corresponding to $u$ and $v$, and $X_\epsilon$ is such that each row has magnitude at most $\epsilon$. Let $H$ be a subsequential limit of $H(t_\epsilon)$ as $\epsilon\rightarrow0$. Now let $\phi$ be a unit eigenvector of the adjacency matrix $A$, $A\phi= \lambda\phi$, and hence an eigenvector of $U(t)$ (namely $U(t)\phi = \expe^{\iii t\lambda}\phi$). Let $\widetilde\phi$ be the restriction of $\phi$ to $u$ and $v$. Then since the rows of $X_\epsilon$ have magnitude bounded by $\epsilon$, we see that
\[
\Vert H(t_\epsilon)\widetilde\phi - \expe^{\iii t_\epsilon\lambda}\widetilde\phi \Vert < 2\epsilon.
\]
Letting $\epsilon\rightarrow0$ we see that
\[
H\widetilde\phi = \rho\widetilde\phi
\]
for some subsequential limit $\rho$ of $\expe^{\iii t_\epsilon\lambda}$. Hence, either $\widetilde\phi$ is an eigenvector of $H$, or it is~0. This shows that $u$ and $v$ are strongly fractionally cospectral.
\end{proof}
We will now see that for fractionally cospectral vertices, condition~\eqref{Theo2.4_2} of Theorem~\ref{thm:kronecker} actually implies strong fractional cospectrality.
\begin{lemma}\label{lem:strcosp}
If conditions~\eqref{Theo2.4_1} and~\eqref{Theo2.4_2} of Theorem~\ref{thm:kronecker} are satisfied, then $u$ and $v$ are strongly fractionally cospectral.
\end{lemma}
\begin{proof}
Suppose that $u$ and $v$ are not strongly fractionally cospectral. Then there is some eigenvalue of $A$ with multiplicity at least two that belongs to both groups in the grouping of eigenvalues. That is $\lambda_k = \lambda_r$ for some $k\in\Pi_1,r\in\Pi_2$. Then in condition~\eqref{Theo2.4_2}, let us choose $\ell_k=1$, $\ell_r=-1$ and $\ell_i=0$ for $i\neq k,r$. Then clearly we have
\begin{align*}
\sum_{i\in\Pi_1}\ell_i\lambda_i + \sum_{j\in\Pi_2}\ell_j\lambda_j &= 0\\
\sum_i\ell_i&=0
\end{align*}
but
\[
\sum_{i\in\Pi_1} \ell_i = 1
\]
contradicting condition~\eqref{Theo2.4_2}.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:kronecker}]
By Lemmas~\ref{lem:pgfr-strfrcsp} and~\ref{lem:strcosp}, we need to show that for a pair of fractionally cospectral vertices $u$ and $v$, we have pretty good fractional revival if and only if condition~\eqref{Theo2.4_2} is satisfied.
%First, let us assume that there is pretty good fractional revival between $u$ and $v$. Then Lemma~\ref{lem:pgfr-strfrcsp} implies that $u$ and $v$ are fractionally cospectral. It remains to prove condition 2.
From fractional cospectrality, we obtain a grouping of the eigenvalues and eigenvectors into two groups. Let us denote these groups $\Pi_1$ and $\Pi_2$. From the proof of Lemma~\ref{lem:pgfr-strfrcsp}, pretty good fractional revival occurs if and only if there is a $2\times2$ symmetric unitary $H$ with eigenvalues $\rho_1,\rho_2$ such that for all $\epsilon>0$, there is a $t_\epsilon>0$ such that $\expe^{\iii t_\epsilon\lambda_i}$ is close to $\rho_1$ for $i\in\Pi_1$, and $\expe^{\iii t_\epsilon\lambda_j}$ is close to $\rho_2$ for $j\in\Pi_2$. To have true pretty good fractional revival (and not approximate periodicity) we must have $\rho_1\neq\rho_2$. This holds if and only if there is some $\delta_1,\delta_2$ with $\delta_1\not\equiv\delta_2~(\modrm 2\pi)$ such that the system
\begin{align*}
|t\lambda_i - \delta_1| &< \epsilon~(\modrm 2\pi) \text{ for } i\in\Pi_1\\
|t\lambda_j - \delta_2| &< \epsilon~(\modrm 2\pi) \text{ for } j\in\Pi_2
\end{align*}
has a solution $t_\epsilon$ for all $\epsilon >0$. We need to show that this condition is equivalent to condition~\eqref{Theo2.4_2}.
Assume that we have integers $\ell_1,\ldots,\ell_n$ with
\[
\sum_{i=1}^m\ell_i\lambda_i = 0~ \text{ and }~\sum_{i=1}^n\ell_i = 0.
\]
By the Kronecker approximation theorem (Lemma~\ref{lem:Kron}), we thus have that
\[
\sum_{i\in\Pi_1} \ell_i\delta_1 + \sum_{j\in\Pi_2}\ell_j\delta_2 = (\delta_1 - \delta_2)\sum_{i\in\Pi_1}\ell_i \equiv 0~(\modrm 2\pi).
\]
If
\[
\sum_{i\in\Pi_1}\ell_i = \pm1,
\]
then this would imply $\delta_1\equiv\delta_2~(\modrm 2\pi)$, which would in turn imply that $\rho_1=\rho_2$. But we are assuming pretty good fractional revival, and hence not approximate periodicity, so $\rho_1\neq\rho_2$. Thus we conclude that
\[
\sum_{i\in\Pi_1}\ell_i \neq \pm1.
\]
For the converse, we assume that for all $\ell_1,\ldots,\ell_n\in\Z$,
\[
\sum_{i=1}^m\ell_i\lambda_i = 0~ \text{ and }~\sum_{i=1}^n\ell_i = 0
\]
implies that
\[
\sum_{i\in\Pi_1}\ell_i\neq\pm1.
\]
Define $\widetilde\lambda_i = \lambda_i - \lambda_1$
for each $i\geq2$. Our condition is equivalent to saying
\[
\sum_{i=2}^n\ell_i\widetilde\lambda_i = 0
\]
implies
\[
\sum_{j\in\Pi_2}\ell_j \neq \pm1.
\]
Define
\[
\mathcal S = \left\{\sum_{j\in\Pi_2}\ell_j~\in \Z~:~ \sum_{i=2}^n\ell_i\widetilde\lambda_i=0\right\}.
\]
Note that $\mathcal S$ is an additive subgroup of $\Z$ and is not all of $\Z$ since $\sum_{j\in\Pi_2}\ell_j$ cannot be $\pm1$. Therefore
\[
\mathcal S = q\Z
\]
for some integer $q\neq\pm1$. Define
\[
\widetilde\delta_1\coloneqq 0~\text{ and }~ \widetilde\delta_2 \coloneqq \frac{2\pi}{q} ,
\]
then
\[
\widetilde\delta_1\sum_{i\in\Pi_1,i>1}\ell_i + \widetilde\delta_2\sum_{j\in\Pi_2}\ell_j \equiv 0~(\modrm 2\pi)
\]
for any integers $\ell_2,\ldots,\ell_n$ with $\sum_{i=2}^n\ell_i\widetilde\lambda_i = 0$. Then by Lemma~\ref{lem:Kron}, for all $\epsilon>0$, the system
\begin{align*}
|t\widetilde\lambda_i - \widetilde\delta_1| &< \epsilon~(\modrm 2\pi) \text{ for } i\in\Pi_1\setminus\{1\}\\
|t\widetilde\lambda_j - \widetilde\delta_2| &< \epsilon~(\modrm 2\pi) \text{ for } j\in\Pi_2
\end{align*}
has a solution $t=t_\epsilon$.
Now choose $\delta_1$ so that $t_\epsilon\lambda_1\rightarrow\delta_1$ as $\epsilon\rightarrow0$, and set $\delta_2 = \delta_1+\widetilde\delta_2$. Then it becomes clear that
\begin{align*}
|t\lambda_i - \delta_1| &< \epsilon~(\modrm 2\pi) \text{ for } i\in\Pi_1\\
|t\lambda_j - \delta_2| &< \epsilon~(\modrm 2\pi) \text{ for } j\in\Pi_2
\end{align*}
has a solution for $t$, and $\delta_1\not\equiv\delta_2~(\modrm 2\pi)$ as desired. This completes the proof of Theorem~\ref{thm:kronecker}.
%\qed
\end{proof}
\begin{remark}
We note that condition~\eqref{Theo2.4_2} of Theorem~\ref{thm:kronecker} is a generalization of the eigenvalue condition necessary for PGST, which requires that $\sum_i\ell_i$ be even. See~\cite[Lemma 1]{invol} and~\cite[Lemma 3]{vanBommel2016}.
\end{remark}
%%%%%%%%%%%%%%
\section{Paths}
%%%%%%%%%%%%%%
\begin{theorem}
Let $P_n$ denote the path on $n$ vertices labeled $1,\ldots,n$. Then PGFR occurs in $P_n$ in the following cases:
\begin{enumerate}
\item\label{theo3.1_1} %[(1)]
between symmetric pairs of vertices if and only if there is PGST between those points {\upshape(}characterized in~\cite{vanBommel2016}{\upshape)};
\item\label{theo3.1_2} %[(2)]
$n=5\cdot 2^k - 1$ vertices, between vertices $2^k$ and $3\cdot2^k$ {\upshape (}or, by symmetry, between $2\cdot2^k$ and $4\cdot2^k${\upshape )}.
\end{enumerate}
\end{theorem}
For part~\eqref{theo3.1_1} of this theorem, clearly if there is PGST between two vertices, then there is PGFR. It remains to see that when there is not PGST between symmetric pairs of nodes, then there is not PGFR either. It is clear that any symmetric pair of vertices in a path are strongly cospectral (see~\cite[Lemma 2]{vanBommel2016}), so we need to see if the eigenvalues condition of Theorem~\ref{thm:kronecker} fails when there is not PGST. By the work in~\cite{vanBommel2016} where PGST in paths is characterized, in cases where there is no PGST, this is shown by construction of an integer linear combination of the eigenvalues of the adjacency matrix of a path with $\sum_i\ell_i$ odd (see our remark after the proof of Theorem~\ref{thm:kronecker}). Examining the proof of Theorem 4 of~\cite{vanBommel2016}, in fact, the linear combination constructed has $\sum_i\ell_i = \pm1$. So by Theorem~\ref{thm:kronecker}, \cite{vanBommel2016} has actually proven that there is no PGFR between these vertices.
Thus we only need concern ourselves with part~\eqref{theo3.1_2} of our theorem. The remainder of this section is dedicated to the proof. We will first investigate when two non-symmetric vertices of a path can be fractionally cospectral. For these nodes, we will then investigate the eigenvalue condition of Theorem~\ref{thm:kronecker}.
%%%%%%%%%
\subsection{Fractional cospectrality}\label{sec:cosp}
%%%%%%%%%
The goal of this section is to see when a pair of vertices in a path can be fractionally cospectral. We will primarily be using the walk count characterization of fractional cospectrality from Theorem~\ref{thm:frac_cosp}. Thus, it will be helpful to have some understanding of the combinatorics of walk counts of a path. With this in mind, we give the following lemma.
\begin{lemma}\label{lem:walk}
Let $P_n$ be the path with $n$ vertices labeled $1,\ldots,n$. Let $x 4d$, thus Lemma~\ref{lem:walk} applies to any $j0$, there exists $t_{\epsilon}$ with
\begin{equation*}
U(t_{\epsilon}) \approx
\begin{bmatrix} H & \0\\ \0 & H' \end{bmatrix}.
\end{equation*}
By Equation~\eqref{Eqn:Cycle}, we have
\begin{equation*}
\wt{\phi}_j =
\begin{cases}
\begin{bmatrix}1 &1\end{bmatrix}^T & \text{if $j$ is even,}\\
\begin{bmatrix}1 &-1\end{bmatrix}^T & \text{if $j$ is odd,}
\end{cases}
\end{equation*}
and $\wt{\phi}_j$ being an eigenvector of $H$ implies $\gamma=\alpha$.
In this case, we have
\begin{equation*}
H \wt{\phi}_j= (\alpha+(-1)^j \beta) \wt{\phi}_j \quad \text{for $j=0,\ldots,n-1$.}
\end{equation*}
Since $H$ is a non-diagonal unitary matrix, we have $\beta\neq 0$ and $\alpha \neq \pm \beta$.
Let $\mu$ be the non-zero real number satisfying $\expe^{\ii \mu} = (\alpha+\beta)/(\alpha-\beta)$.
It follows from $U(t_{\epsilon})\phi_j = \expe^{\ii t_{\epsilon} \lambda_j} \phi_j$ that
\begin{equation*}
t_{\epsilon} (\lambda_j - \lambda_{j-1}) \approx
\begin{cases}
\mu \pmod{2\pi} & \text{if $j$ is even,}\\
-\mu \pmod{2\pi} & \text{if $j$ is odd.}\\
\end{cases}
\end{equation*}
Applying Lemma~\ref{lem:Kron} to Equation~\eqref{Eqn:EigenvaluesCn} yields
\begin{equation*}
p\mu \equiv 0 \pmod{2\pi}.
\end{equation*}
Similarly, we have $q\mu\equiv 0\pmod{2\pi}$.
As $p$ and $q$ are coprime, there exist integers $h$ and $k$ such that $hp+kq=1$.
Then $\mu = hp\mu+kq\mu\equiv 0\pmod{2\pi}$, which implies $\beta=0$, a contradiction to $H$ being non-diagonal.
\end{proof}
\begin{lemma}
Let $n=2^hp^s$ for some odd prime $p$, $s\geq 1$ and $h\geq 2$. There is no PGFR in $C_n$.
\end{lemma}
\begin{proof}
Applying Lemma~\ref{lem:cos} with $m=p^s$ and $k=2^{h-1}$, we get
\begin{equation*}
\sum_{j=0}^{p^s-1} (-1)^j \lambda_{2^{h-1}j+a}=0, \quad \text{for $0\leq a <2^{h-1}$.}
\end{equation*}
When $a=0$ and $a=1$, we get
\begin{equation*}
\sum_{j=0}^{p^s-1} (-1)^j \lambda_{2^{h-1}j}=0
\quad \text{and}\quad
\sum_{j=0}^{p^s-1} (-1)^j \lambda_{2^{h-1}j+1}=0.
\end{equation*}
Define
\begin{equation*}
\ell_r =
\begin{cases}
(-1)^j, & \text{if $r=2^{h-1}j$,}\\
(-1)^{j+1}, & \text{if $r=2^{h-1}j+1$,}\\
0 &\text{otherwise.}
\end{cases}
\end{equation*}
Then we have $\sum_{r=0}^{n-1}\ell_r\lambda_r=0$, $\sum_{r=0}^{n-1} \ell_r = 0$ but
\begin{equation*}
\sum_{r\ \mathrm{even}} \ell_r =1.
\end{equation*}
Hence there is no PGFR in $C_n$.
\end{proof}
\begin{theorem}
Pretty good fractional revival occurs between $a$ and $b$ in $C_n$ if and only if
$n=2p^k$, for some prime $p$, for $k\geq 1$,
and $b=a+n/2$.
%\qed
\end{theorem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\paragraph{Acknowledgements} G.L. was supported by NSF/DMS-1800738 and the Simons Foundation Collaboration Grant. O.E was supported by the Herchel Smith Harvard Undergraduate Research Program.
%
%We all acknowledge the support of Chris Godsil's NSERC Accelerator Grant that funded the workshop Algebraic Graph Theory and Quantum Walks, where we all started to work on this project.
\longthanks{We all acknowledge the support of Chris Godsil's NSERC Accelerator Grant that funded the workshop Algebraic Graph Theory and Quantum Walks, where we all started to work on this project.}
%\nocite{*}
\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Chan_445}
\end{document}