---
author:
- 'Chris Godsil, Natalie Mullin, Aidan Roy'
bibliography:
- 'IUM.bib'
title: Uniform Mixing and Association Schemes
---

Introduction
============

Quantum walks are a quantum analogue of a random walk on a graph, and have recently been the subject of much investigation. For recent survey from a mathematician’s viewpoint, see [@godsil12]. A quantum walk can behave quite differently from a classical walk: for example Childs et al. [@childs03] found a graph in which the time to propagate from one node to another was sped up exponentially compared to any classical walk.

We describe the physical motivation for continuous-time quantum walks. Let $X$ be a graph with Laplacian matrix $L$, and let $p(t) = (p_1(t),\ldots,p_n(t))$ be a probability distribution over the vertices $\{1,\ldots,n\}$ of $X$, for each time $t$. Then $p(t)$ is a continuous-time random walk on $X$ if it satisfies the differential equation $$\frac{\mathrm{d}p(t)}{\mathrm{d}t} = -L p(t).$$ This is a continuous version of a discrete-time random walk, in which the Laplacian matrix is the transition matrix for a Markov process on the vertices. The solution to the differential equation is $$p(t) = e^{-Lt}p(0).$$ Since $L$ has rows which sum to $0$, $e^{-Lt}$ has rows which sum to $1$ and is therefore a stochastic process.

In a continuous-time quantum walk, instead of a probability distribution $p(t)$ we use a quantum state ${|\psi(t)\rangle}$ defined on a state space with orthonormal basis $\{{|1\rangle},
\ldots, {|n\rangle} \}$. Instead of a stochastic process, the walk is governed by a unitary evolution. From Schrödinger’s equation for the evolution of a quantum system $$i \frac{\mathrm{d}{|\psi(t)\rangle}}{\mathrm{d}t } = L {|\psi(t)\rangle},$$ we have the solution $${|\psi(t)\rangle} = e^{iLt}{|\psi(0)\rangle}.$$ Since the Laplacian $L$ is Hermitian, $e^{iLt}$ is unitary. Assume our quantum walk begins at some vertex $j$, so ${|\psi(0)\rangle} = {|j\rangle}$. If at some time $t$ we measure the state ${|\psi(t)\rangle}$ in the vertex basis $\{{|1\rangle}, \ldots, {|n\rangle} \}$, then the probability of outcome ${|k\rangle}$ is $${\left|{\langlek|\psi(t)\rangle}\right|}^2 = {\left|{\langlek|}e^{iLt}{|j\rangle}\right|}^2 =  {\left|(e^{iLt})_{kj}\right|}^2.$$ If this probability distribution is uniform over all vertices $k$, and this is true for all initial states ${|j\rangle}$, then the graph is said to have uniform mixing.

In fact we will define the unitary evolution using the adjacency matrix rather than the Laplacian. When $X$ is regular, the resulting states differ only by an overall phase factor, and this does not affect uniform mixing.

In this paper we focus on the question of which graphs have uniform mixing: can a quantum walk beginning at a single vertex result in a state whose probability distribution is uniform over all vertices? If this is possible at some small time $t$, then the behaviour is quite different from a classical walk, which typically approaches the uniform distribution as $t \to \infty$.

Moore and Russell [@moore02] in 2001 gave the first example of uniform mixing, showing that the $n$-cube has uniform mixing at time $t = n\pi/4$. Since then a large body of work has been produced to study this problem. We summarize the conclusions. The following graphs do admit uniform mixing:

(a) The complete graphs $K_2$, $K_3$, and $K_4$.

(b) The Hamming graphs $H(n,q)$, $q \in \{2,3,4\}$ (see [@moore02] [@carlson07]).

(c) The Cartesian product of any two graphs that admit uniform mixing at the same time.

Note that since the Hamming graph $H(n,q)$ is the $n$-th Cartesian power of $K_q$, the results in (b) follow from the results in (a). The Cartesian powers of $K_2$ and $K_4$ admit uniform mixing when $t=\pi/4$, hence the products of powers $K_2^{{\mathbin{\square}}r}\times K_4^{{\mathbin{\square}}s}$) also admit uniform mixing. A number of Cayley graphs for ${{\mathbb Z}}_2^d$ admit uniform mixing, but no classification is yet known. Some work in this direction appears in [@best08].

On the other hand, some graphs are known not to admit uniform mixing:

(a) $K_n$ for $n > 4$.

(b) $H(n,q)$ for $q > 4$.

(c) Cycles $C_n$ for $n = 2^uq$, where $q = 1$ ($u \geq 3$) or $q \cong 3 \mod 4$ [@adamczak07].

(d) The cycle $C_5$ [@carlson07].

(e) Complete multipartite graphs (except $C_4$) [@ahmadi03].

(f) The transpositions Cayley graph $X(S_n,\{\text{transpositions}\})$ [@gerhardt03].

An obvious question raised by these results is which cycles admit uniform mixing. In this work we show that the cycle $C_n$ does not admit uniform mixing if $n$ is even and greater than four, or if $n$ is a prime greater than three. We see that if a bipartite graph on $n$ vertices admits uniform mixing then $n$ must be divisible by four; if in addition the graph is regular then $n$ must be the sum of two integer squares.

The graphs we have that do admit uniform mixing are highly regular, and this leads us to ask which strongly regular graphs admit uniform mixing. We use work of Chan [@chan08] to show that the only strongly regular graphs that admit instantaneous uniform mixing are the Paley graph of order 9 and certain graphs corresponding to regular symmetric Hadamard matrices with constant diagonal.

Since uniform mixing seems to be rare, we consider a relaxed version, called $\epsilon$-uniform mixing, and we demonstrate that this does take place on all cycles of prime length.

Uniform mixing
==============

Let $A$ denote the adjacency matrix of a graph $X$ on $n$ vertices. The transition operator $U(t)$ defined by $$U(t) = e^{itA}.$$ determines a continuous quantum walk. It is straightforward to observe that the transition matrix satisfies the following properties.

(i) [$U(t)^{T} = U(t).$]{}

(ii) [$\overline{U(t)} = U(-t).$]{}

(iii) [$U(t)$ is unitary.]{}

We say the graph $X$ admits *uniform mixing* at time $t$ if and only if $$U(t) \circ U(-t) = \frac{1}{n}J$$ where $J$ is the $n \times n$ all-ones matrix.

We say that $\epsilon$-uniform mixing occurs if, for each $\epsilon > 0$, there is a time $t$ such that $$||U(t) \circ U(-t) - \frac{1}{n} J || < \epsilon.$$

It is useful to note the following lemma, which relates uniform mixing on a graph and its complement at certain times.

Let $X$ denote a regular graph on $n$ vertices, and let $t$ denote an integer multiple of $2 \pi/n$. At time $t$, uniform mixing occurs on $X$ if and only if it occurs on the complement $\overline{X}$.

[*Proof.* ]{}Note that $$\begin{gathered}
    e^{i\bar{A}t} = e^{i(J-I-A)t} = e^{i(J-I)t}e^{-iAt} \\ =        
        \left(e^{i(n-1)t}\left(\frac{1}{n}J\right) +    
        e^{-it}\left(I-\frac{1}{n}J\right)\right)e^{-iAt}.\end{gathered}$$ If $t$ denote an integer multiple of $2 \pi/n$, then the above equation reduces to $$e^{i\bar{A}t} = e^{-it}e^{iAt},$$ which implies that the complement of $X$ has uniform mixing if and only if $X$ does.[  ]{}

In Section \[srg\_section\], we see that the previous lemma applies to all cases of strongly regular graphs that admit uniform mixing.

Recall that an $n \times n$ matrix $H$ is a complex Hadamard matrix if and only if

(i) [$H H^{*} = nI.$]{}

(ii) [$H \circ {{\mkern2mu\overline{\mkern-2muH}}} = J.$]{}

With this terminology we see that uniform mixing occurs on $X$ at time $t$ if and only if $\sqrt{n} U(t)$ is a complex Hadamard matrix.

For the known examples of uniform mixing, the corresponding entries of $\sqrt{n}U(t)$ are roots of unity. Such matrices are called *Butson-type*. They live in a more general family of complex Hadamard matrices whose entries are all algebraic numbers. In general, we see that if $U_X(t)$ has all algebraic entries, then the ratio of any two eigenvalues of $X$ must be transcendental. First we recall a useful formulation of the Gelfond-Schneider Theorem. This formulation is due to Michel Waldschmidt [@burger04].

\[gelfond\_schneider\] If $x$ and $y$ are two nonzero complex numbers with $x$ irrational, then at least one of the numbers $x$, $e^{y}$, or $e^{xy}$ is transcendental.[  ]{}

The above theorem is crucial in the proof of the following result.

\[no\_algebraic\] Let $X$ denote a graph. If at time $t$ all entries of the transition matrix $U(t)$ are algebraic, then the ratio of any two eigenvalues of $X$ must be rational.

Let $A$ denote the adjacency matrix of $X$, and let $\{\theta_0, \dots, \theta_d\}$ denote the eigenvalues of $A$. We consider a fixed pair of eigenvalues $\theta_r$ and $\theta_s$. Since $A$ is an integer matrix, the characteristic polynomial of $A$ is a monic polynomial with integer coefficients. Therefore each eigenvalue of $A$ is an algebraic integer. Furthermore, since $A$ is symmetric, we decompose $A$ as $$A = \sum_{k = 0}^{d} \theta_k E_k,$$ where each $E_k$ is orthogonal projection onto the $k$-th eigenspace. This directly implies that $$\label{scaled_transition}
    U(t) = \sum_{k=0}^{d} e^{\theta_k it} E_k.$$ From this we see that the eigenvalues of $U(t)$ are $\{e^{it \theta_0}, \dots, e^{it
\theta_d}\}$. If all entries of $U(t)$ are algebraic, then the eigenvalues of $U(t)$ must be algebraic. If we further suppose that $\theta_r / \theta_s$ is irrational, then Theorem \[gelfond\_schneider\] implies that one of $$\{ \theta_r / \theta_s, e^{it \theta_s}, e^{i t \theta_s (\theta_r/\theta_s)} \}$$ must be transcendental, which is a contradiction. Therefore $\theta_r / \theta_s$ must be rational for every pair of distinct eigenvalues $\theta_r$ and $\theta_s$ of $X$.[  ]{}

\[no\_algebraic\_reg\] If $X$ is regular and at time $t$ all entries of the transition matrix $U(t)$ are algebraic, then $X$ must have integral eigenvalues.

[*Proof.* ]{}First recall that all of the eigenvalues of $X$ are roots of a monic polynomial with integral coefficients. Therefore the eigenvalues of $X$ are algebraic integers. If we assume that $X$ is regular, then the largest eigenvalue $\theta_0$ is equal to the valency (see [@godsil01]). Using Theorem \[no\_algebraic\], we see that the nontrivial eigenvalues of $X$ must be rational. The only rational algebraic integers are the integers, and so we see that the eigenvalues of $X$ must be integral.[  ]{}

The following observation is useful in our following work.

If $U(t)$ is the complex scalar multiple of a matrix with all entries algebraic, then all entries of $U(t)$ are algebraic.

[*Proof.* ]{}Suppose $U(t) = cH$ for some scalar $c$ in ${{\mathbb C}}$ and some $H$ in ${{\mathbb C}}^{n \times n}$ such that each entry of $H$ is algebraic. By a well-known result from linear algebra, we know that for the complex matrix $itA$ we have $$\det(e^{itA}) = e^{\operatorname{tr}(itA)} = 1.$$ If we assume that $U(t) = cH$, then this implies that $$c^n \det(H) = 1.$$ Since $H$ has algebraic entries, it follows that $\det(H)$ is algebraic. This implies that $c$ is algebraic, which further implies that all of the entries of U(t) are algebraic.[  ]{}

Complex Hadamards and SRGs {#srg_section}
==========================

Let $X$ be a strongly regular graph with parameters $(n,k,{\lambda},\mu)$ and let $A$ be its adjacency matrix, with spectral decomposition $$A = kE_k + \theta E_\theta + \tau E_\tau,$$ where $k > \lambda \geq \tau$.

The following result of Chan [@chan08] is instrumental in our classification of strongly regular graphs that admit uniform mixing.

\[thm:chan\] Let $A$ be the adjacency matrix of a primitive strongly regular graph $X$ with eigenvalues $k$, ${\theta}$, $\tau$, and $W = I + xA +y\bar{A}$. If $W$ is a complex Hadamard matrix, then $X$ or $\bar{X}$ has one of the following parameter sets $(n,k,{\lambda},\mu)$:

-   $(4{\theta}^2,2{\theta}^2- {\theta}, {\theta}^2-{\theta},{\theta}^2-{\theta})$

-   $(4{\theta}^2,2{\theta}^2+ {\theta}, {\theta}^2+{\theta},{\theta}^2+{\theta})$

-   $(4{\theta}^2-1,2{\theta}^2, {\theta}^2,{\theta}^2)$

-   $(4{\theta}^2+4{\theta}+1,2{\theta}^2+2{\theta}, {\theta}^2+{\theta}-1,{\theta}^2+{\theta})$

-   $(4{\theta}^2+4{\theta}+2,2{\theta}^2+ {\theta}, {\theta}^2-1,{\theta}^2)$

Moreover, Chan determines the possible values of $x$ and $y$ that can occur in each of these cases.

Uniform mixing on SRGs
======================

If we suppose a strongly regular graph $X$ admits uniform mixing, then there are numbers $c$, $x$ and $y$ with $|c| = |x| = |y| = 1$ such that $$c\sqrt{n}U(t) = I + xA + y\bar{A},$$ and $c \sqrt{n} U(t)$ is a complex Hadamard matrix. Applying Chan’s results in the previous section, we obtain the following classification of primitive strongly regular graphs that admit uniform mixing. Our main result in this section follows.

\[srg\_theorem\] A primitive strongly regular graph $X$ with adjacency matrix $A$ has uniform mixing if and only if one of the following holds

-   $J-2A$ is a regular symmetric Hadamard matrix of order $4\theta^2$ with constant diagonal and positive row sum and $\theta$ is even.

-   $J- 2A-2I$ is a regular symmetric Hadamard matrix of order $4\theta^2$ with constant diagonal and positive row sum and $\theta$ is odd.

-   The Paley graph of order 9, which has parameters $(9,4,1,2)$.

To prove this theorem, we consider each possible case of \[thm:chan\] separately. First we lay some groundwork that applies to all cases. Recall that we have $$e^{iAt} = e^{ikt}E_k + e^{i{\theta}t} E_{\theta}+ e^{i\tau t} E_\tau,$$ and so we can expand both sides of this equation in terms of the spectral decomposition. Comparing the expressions for $E_k$, $E_{\theta}$ and $E_\tau$ on both sides, we get the following system of equations: $$\begin{aligned}
ce^{ikt} \sqrt{n} & = 1 + xk + y(v-k-1) \label{eqn:flatsrg1} \\
ce^{i{\theta}t} \sqrt{n} & = 1 + x{\theta}+ y(-{\theta}-1) \label{eqn:flatsrg2} \\
ce^{i\tau t} \sqrt{n} & = 1 + x\tau + y(-\tau-1)\label{eqn:flatsrg3}.\end{aligned}$$ These equations are the *characterizing equations*. The graph $X$ admits uniform mixing if and only if a solution to the characterizing equations exists in $t$, $x$, $y$ and $c$ with $|x| = |y| = |c| = 1$.

Chan shows (Lemma 2.2) that if $X$ has at least $5$ vertices, then ${\theta}+ \tau \in \{0,1,2\}$. Moreover, for each value of ${\theta}+\tau$, Chan finds parameter sets $(n,k,{\lambda},\mu)$ in Theorem \[thm:chan\] that can occur and also determines the values of $x$ and $y$ that can occur in the characterizing equations.

In each case, we must also consider if the complement has uniform mixing $ce^{i\bar{A}t} = I + xA + y\bar{A}$. The eigenvalues of the complement are $$\{v-k-1,-{\theta}-1,-\tau-1\}.$$ The characterizing equations for the complement of $X$, written in terms of the parameters of $X$, are: $$\begin{aligned}
ce^{i(n-k-1)t} \sqrt{n} & = 1 + xk + y(n-k-1) \label{eqn:flatsrgc1} \\
ce^{i(-{\theta}-1) t} \sqrt{n} & = 1 + x{\theta}+ y(-{\theta}-1) \label{eqn:flatsrgc2} \\
ce^{i(-\tau-1) t} \sqrt{n} & = 1 + x\tau + y(-\tau-1)\label{eqn:flatsrgc3} .\end{aligned}$$

Regular symmetric Hadamard matrices
-----------------------------------

We first consider uniform mixing on strongly regular graphs with parameters given in (i) or (ii) of Theorem \[thm:chan\]. If a graph $X$ with adjacency matrix $A$ has these parameters or the complementary parameters, then $J-2A$ or $J-2A-2I$, respectively, is a regular symmetric Hadamard matrix [@brouwer84].

Suppose $X$ is a primitive strongly regular graph such that $X$ or $\overline{X}$ has parameters given in (i) or (ii) of Theorem \[thm:chan\]. Then $X$ admits uniform mixing if and only if one of the following holds:

1.  The parameters of $X$ or $\overline{X}$ are given in (i) and $\theta$ is even.

2.  The parameters of $X$ or $\overline{X}$ are given in (ii) and $\theta$ is odd.

[*Proof.* ]{}First suppose that $X$ is a graph with parameters $(4{\theta}^2,2{\theta}^2- {\theta}, {\theta}^2-{\theta},{\theta}^2-{\theta})$. Chan shows that $x = -1$ and $y = 1$. The characterizing equations above reduce to $$\begin{aligned}
ce^{i{\theta}(2{\theta}-1)t}  & = 1  \\
ce^{i{\theta}t} & = -1 \\
ce^{-i{\theta}t}  & = 1.\end{aligned}$$ Thus $c=e^{i{\theta}t} = \pm i$, so ${\theta}t = \pi(m+1/2)$ for some integer $m$, and $t = \pi(m+1/2)/{\theta}$ and $kt = (2{\theta}-1)\pi(m+1/2)$. When ${\theta}$ is even, any $m$ is a valid solution and uniform mixing occurs. These are the Latin square graphs $L_{\theta}(2{\theta})$. When ${\theta}$ is odd, no solutions occur.

For the complement, the characterizing equations for $\overline{G}$ reduce to $$\begin{aligned}
ce^{i(2{\theta}^2+{\theta}-1)t} & = 1  \\
ce^{i({\theta}-1) t} & = 1  \\
ce^{i(-{\theta}-1)t} & = -1\end{aligned}$$ for some ${\left|c\right|} = 1$. Thus $c = e^{-i({\theta}-1) t}$ and the first and third equations are $e^{it2{\theta}^2t} = 1$ and $e^{-i2{\theta}t} = -1$. Thus $e^{i{\theta}t} = \pm i$, so ${\theta}t = \pi(m+1/2)$ for some $m$, and $t = \pi(m+1/2)/{\theta}$. When ${\theta}$ is even, any $m$ is a valid solution and uniform mixing occurs. When ${\theta}$ is odd, no solutions occur.

If $X$ or $\overline{X}$ has parameters $(4{\theta}^2,2{\theta}^2+ {\theta}, {\theta}^2+{\theta},{\theta}^2+{\theta})$, then a similar results holds: there are no solutions for ${\theta}$ even, and for ${\theta}$ odd $t = \pi(m+1/2)/{\theta}$ is a solution for every $m$. These are the negative Latin square graphs $NL_{\theta}(2{\theta})$. The same applies to the complement: uniform mixing occurs when ${\theta}$ is even, and no solutions occur when ${\theta}$ is odd.[  ]{}

There are infinite families of strongly regular graphs with these parameters [@haemers08].

Symplectic-type graphs
----------------------

We turn the graphs in part (iii) of Theorem \[thm:chan\]. These are the strongly regular graphs with parameters $(4{\theta}^2-1,2{\theta}^2, {\theta}^2,{\theta}^2)$; their eigenvalues satisfy ${\theta}+ \tau = 0$. Chan shows in this case that $(x,y)$ is one of $$\left\{\left(-1, \frac{2{\theta}^2-3 \pm i\sqrt{4{\theta}^2-5}}{2({\theta}^2-1)}\right),
        \left(\frac{-2{\theta}^2+1 \pm i\sqrt{4{\theta}^2-1}}{2{\theta}^2},1\right)\right\}.$$

[**Case**]{} $(x,y) = (\tfrac{-2{\theta}^2+1 \pm i\sqrt{4{\theta}^2-1}}{2{\theta}^2},1)$: The characterizing equations reduce to $$\begin{aligned}
ce^{i2{\theta}^2t} \sqrt{n} & = \pm i\sqrt{n} \label{eqn:flatsrg1.1} \\
ce^{i{\theta}t} \sqrt{n} & = {\theta}(x-1) \label{eqn:flatsrg1.2}  \\
ce^{-i{\theta}t} \sqrt{n} & = -{\theta}(x-1) \label{eqn:flatsrg1.3} .\end{aligned}$$ Equations and imply that $e^{2i{\theta}t} = -1$ and so $e^{i{\theta}t} = \pm i$ and $e^{i2{\theta}^2t} = (-1)^{\theta}$. Then Equation implies that $c = \pm i$. But then the LHS of equation is real while the RHS is not, a contradiction. So there are no solutions.

The characterizing equations for the complement of $X$ are: $$\begin{aligned}
ce^{i(2{\theta}^2-2)t} \sqrt{n} & = \pm i\sqrt{n} \label{eqn:flatsrgc1.1} \\
ce^{i(-{\theta}-1)t} \sqrt{n} & = {\theta}(x-1) \label{eqn:flatsrgc1.2}  \\
ce^{i({\theta}-1)t} \sqrt{n} & = -{\theta}(x-1) \label{eqn:flatsrgc1.3} .\end{aligned}$$ Equations and imply that $e^{i2{\theta}t} = -1$ and so $e^{i2{\theta}^2t} = (-1)^{\theta}$. Then equation implies that $c = \pm i e^{i2t}$. Since $e^{it}$ is a $4{\theta}$-th root of unity, so is $ce^{i(-{\theta}-1)t} = e^{it(1-{\theta})}$. On the other hand, from equation , $$e^{it(1-{\theta})} = \tfrac{{\theta}}{\sqrt{n}}(x-1) = \tfrac{-\sqrt{n} \pm i}{2{\theta}},$$ which has algebraic degree exactly four since $n$ is not a perfect square. This implies that $e^{it(1-{\theta})}$ is a primitive $m$-th root of unity for some $m$ such that $\phi(m) = 4$, namely $m \in \{5,8,10,12\}$. (Here $\phi$ is the Euler totient function.) But then it is not difficult to check that none of these primitive $m$-th roots of unity have imaginary part $\pm1/2{\theta}$, for any ${\theta}> 1$. Thus there are no solutions.

#### 

[[**Case**]{} $(x,y) = (-1, \tfrac{2{\theta}^2-3 \pm i\sqrt{4{\theta}^2-5}}{2({\theta}^2-1)})$:]{} The characterizing equations reduce to $$\begin{aligned}
ce^{i2{\theta}^2t} \sqrt{n} & = -2 \pm i\sqrt{4{\theta}^2-5}  \label{eqn:flatsrg2.1} \\
ce^{i{\theta}t} \sqrt{n} & = 1 - {\theta}+ y(-{\theta}-1) \label{eqn:flatsrg2.2} \\
ce^{-i{\theta}t} \sqrt{n} & = 1 + {\theta}+ y({\theta}-1) \label{eqn:flatsrg2.3}.\end{aligned}$$ Simplifying plus we have $\sqrt{n} c{\mathrm{Re}}(e^{i{\theta}t}) = 1 - y$. Taking the absolute value, we get ${\mathrm{Re}}(e^{i{\theta}t})^2 = 1/n({\theta}^2-1)$. Similarly, from minus we get ${\mathrm{Im}}(e^{i{\theta}t})^2 = {\theta}^2(4{\theta}^2 - 5)/n({\theta}^2-1)$. Thus we can solve: $$\begin{aligned}
e^{i{\theta}t} & = \frac{1}{\sqrt{n({\theta}^2-1)}}[\pm 1 \pm {\theta}i\sqrt{4{\theta}^2-5}] \label{eqn:eitht}, \\
c & = \frac{1}{2\sqrt{{\theta}^2-1}}[\pm 1 \pm i\sqrt{4{\theta}^2-5}] \label{eqn:c}.\end{aligned}$$ We then check that there are no solutions to the characterizing equations for any choice of integer ${\theta}$. For small ${\theta}$ we can check explicitly. When ${\theta}$ is large, we examine $\arg(ce^{i2{\theta}^2 t})$ in two different ways: once from combining and and once from . We use asymptotics with error bounds to show the values are not equal. We need one preliminary observation: when ${\theta}$ is large, $e^{i {\theta}t}$ is close to $\pm i$ and so the argument of $e^{i{\theta}t}$ is approximately $\pm (\pi/2 - {\mathrm{Re}}(e^{i{\theta}t}))$.

\[lem:argbound\] For any $x$ on the unit circle, $\arg(x) = \pm (\pi/2 - {\mathrm{Re}}(x)) + {\epsilon}$, where ${\left|{\epsilon}\right|} \leq {\mathrm{Re}}(x)^2$.

[*Proof.* ]{}Assume ${\mathrm{Im}}(x) > 0$ and ${\mathrm{Re}}(x) < 0$: the other cases are similar. The part of $\arg(x)$ past $\pi/2$ is the portion of the unit circle arc in the upper left quadrant, which is contained in a rectangle with horizontal width ${\mathrm{Re}}(x)$ and vertical height $1 - \sqrt{1-{\mathrm{Re}}(x)^2}$. Since $\sqrt{z} \geq z$ for any $z \in [0,1]$, we have $$\begin{aligned}
 \arg(x) - \pi/2 & \leq -{\mathrm{Re}}(x) + 1 - \sqrt{1-{\mathrm{Re}}(x)^2} \\
& \leq -{\mathrm{Re}}(x) + 1 - (1-{\mathrm{Re}}(x)^2) \\
& = -{\mathrm{Re}}(x) + {\mathrm{Re}}(x)^2.\end{aligned}$$ On the the other hand $\arg(x) - \pi/2 \geq -{\mathrm{Re}}(x)$.[  ]{}

Now consider the arguments of $e^{i{\theta}t}$ and $c$ from equations and : $$\begin{aligned}
{\theta}t = \arg(e^{i {\theta}t}) &= \pm \tfrac{\pi}{2} \pm \tfrac{1}{2{\theta}^2} + O(\tfrac{1}{{\theta}^4}), \\ \vspace{4pt}
\arg(c) &= \pm\tfrac{\pi}{2} \pm \tfrac{1}{2{\theta}} + O(\tfrac{1}{{\theta}^2}), \\ \vspace{4pt}
\arg(ce^{i2{\theta}^2 t}) &= \arg(c) + 2{\theta}({\theta}t) \\ \vspace{4pt}
& = \pm \tfrac{\pi}{2}  \pm \tfrac{1}{2{\theta}}[2 \pm 1] +O(\tfrac{1}{{\theta}^2}). \vspace{4pt}\end{aligned}$$ On the other hand from we have ${\mathrm{Re}}(ce^{i2{\theta}^2 t}) = -2/\sqrt{n} \approx  -\tfrac{1}{{\theta}}$, and so $$\arg(ce^{i2{\theta}^2 t}) = \pm \tfrac{\pi}{2}  - \tfrac{1}{{\theta}} +O(\tfrac{1}{{\theta}^2}),$$ a contradiction. Using Lemma \[lem:argbound\] this asymptotic argument can be made exact. Details are left to the reader.

The characterizing equations of the complement reduce to $$\begin{aligned}
ce^{i(2{\theta}^2-2)t} \sqrt{n} & = -2 \pm i\sqrt{4{\theta}^2-5} \label{eqn:flatsrg2.1c} \\
ce^{i(-{\theta}-1) t} \sqrt{n} & = 1 - {\theta}+ y(-{\theta}-1) \label{eqn:flatsrg2.2c} \\
ce^{i({\theta}-1) t} \sqrt{n} & = 1 + {\theta}+ y({\theta}-1) \label{eqn:flatsrg2.3c}.\end{aligned}$$ Adding/subtracting the last two equations gives $\sqrt{n}ce^{-it}{\mathrm{Re}}(e^{i{\theta}t}) = 1-y$ and $\sqrt{n}ce^{-it}{\mathrm{Im}}(e^{i{\theta}t}) = {\theta}(1+y)$. Again we can solve: $$\begin{aligned}
e^{i{\theta}t} & = \frac{1}{\sqrt{n({\theta}^2-1)}}[\pm 1 \pm {\theta}i\sqrt{4{\theta}^2-5}] \\
ce^{-it} & = \frac{1}{2\sqrt{{\theta}^2-1}}[\pm 1 \pm i\sqrt{4{\theta}^2-5}].\end{aligned}$$ Again we use an asymptotic description of the argument which can be made precise with Lemma \[lem:argbound\]. We get: $$\begin{aligned}
{\theta}t = \arg(e^{i {\theta}t}) &= \pm \tfrac{\pi}{2} \pm \tfrac{1}{2{\theta}^2} + O(\tfrac{1}{{\theta}^4}), \\
t &= \pm  \tfrac{\pi}{2{\theta}} \pm \tfrac{1}{2{\theta}^3} + O(\tfrac{1}{{\theta}^5}),\\
\arg(c) & = t  \pm  \tfrac{\pi}{2} \pm \tfrac{1}{2{\theta}} + O(\tfrac{1}{{\theta}^2}), \\ 
\arg(ce^{i(2{\theta}^2-2)t}) &= \arg(c) + (2{\theta}^2-2)t \\
& = \pm  \tfrac{\pi}{2} + \tfrac{1}{{\theta}}[\pm \tfrac{1}{2} \pm 1 \pm \pi/2] + O(\tfrac{1}{{\theta}^2}).\end{aligned}$$ Meanwhile from equation , $$\arg(ce^{i(2{\theta}^2-2)t}) = \pm  \tfrac{\pi}{2} - \tfrac{1}{{\theta}} + O(\tfrac{1}{{\theta}^2}).$$ Since the two expressions are not equal, no solution exists. Thus there is no uniform mixing in the symplectic-type graphs or their complements.

Regular conference matrix type graphs
-------------------------------------

We treat the fourth family of graphs from Chan’s theorem. These have parameters $(n,k,{\lambda},\mu) = (4{\theta}^2+4{\theta}+2,2{\theta}^2+ {\theta}, {\theta}^2-1,{\theta}^2)$ and ${\theta}+ \tau = -1$.

Chan found $x = \pm i$ or $x = \tfrac{-1 \pm i\sqrt{(4{\theta}^2({\theta}+1)^2-1}}{2{\theta}({\theta}+1)}$ and in either case, the $y = \bar{x}$. The characteristic equations reduce to: $$\begin{aligned}
ce^{ikt} \sqrt{n} & = 1 + xk + y(n-k-1) \label{eqn:flatsrg4.1} \\
ce^{i{\theta}t} \sqrt{n} & = 1 + x{\theta}+ \bar{x}(-{\theta}-1) \label{eqn:flatsrg4.2} \\
ce^{i(-{\theta}-1) t} \sqrt{n} & = 1 + x(-{\theta}-1) + \bar{x}{\theta}\label{eqn:flatsrg4.3} .\end{aligned}$$ From plus we have $$\sqrt{n}c(e^{i{\theta}t} + e^{i(-{\theta}-1)t}) = 2 - 2{\mathrm{Re}}(x),$$ so $ce^{i{\theta}t} + ce^{i(-{\theta}-1)t}$ is real. Thus either $ce^{i{\theta}t} = -ce^{i (-{\theta}-1)t}$ or $ce^{i{\theta}t} = \overline{ce^{i (-{\theta}-1)t}}$. But in the first case $x = y = 1$, which is not a solution. We conclude that or $ce^{i{\theta}t} = \overline{ce^{i (-{\theta}-1)t}}= \bar{c}e^{i({\theta}+1)t}$ and therefore $c = e^{it/2}$. The same analysis shows that $c = e^{it/2}$ for the complement of $G$ as well.

#### 

[[**Case**]{} $x = i$, $y = -i$:]{} The characteristic equations reduce to: $$\begin{aligned}
\sqrt{n}e^{it(k+1/2)} &= 1 -i(2{\theta}+1) \\
\sqrt{n}e^{it({\theta}+1/2)} &= 1 +i(2{\theta}+1) \label{eqn:algdeg4} \end{aligned}$$ It follows that $e^{it(k+{\theta}+1)} = 1$, so $e^{it}$ is a $(k+{\theta}+1) = (2{\theta}^2+2{\theta}+1)$-th root of unity and $e^{it({\theta}+1/2)}$ is a $(4{\theta}^2+4{\theta}+2)$-th root of unity. But by , noting that $\sqrt{n}$ is not an integer, $e^{it({\theta}+1/2)}$ has algebraic degree exactly $4$. Since none of the primitive $m$-th roots of unity of algebraic degree $4$ have real part $1/\sqrt{n}$ for any ${\theta}$, there are no solutions.

For the complement of $X$, the characteristic equations reduce to $$\begin{aligned}
\sqrt{n}e^{it((n-k-1)+1/2)} &= 1 -i(2{\theta}+1) \\
\sqrt{n}e^{it({\theta}+1/2)} &= 1 -i(2{\theta}+1) \label{eqn:algdeg4.2} \end{aligned}$$ So $e^{it(n-k-1-{\theta})} = 1$ and $e^{it}$ is a $n-k-1-{\theta}= (2{\theta}^2+2{\theta}+1)$-th root of unity. Again there are no solutions.

#### 

[[**Case**]{} $x = \tfrac{-1 \pm i\sqrt{(4{\theta}^2({\theta}+1)^2-1}}{2{\theta}({\theta}+1)}$:]{} This case is similar. The characteristic equations reduce to: $$\begin{aligned}
\sqrt{n}e^{it(k+1/2)} &= \frac{-2{\theta}^2-2{\theta}-1 \pm i(2{\theta}+1)\sqrt{4{\theta}^2({\theta}+1)^2-1}}{2{\theta}({\theta}+1)} \\
\sqrt{n}e^{it({\theta}+1/2)} &= \frac{2{\theta}^2+2{\theta}+1 \mp i(2{\theta}+1)\sqrt{4{\theta}^2({\theta}+1)^2-1}}{2{\theta}({\theta}+1)} \end{aligned}$$ Thus $-e^{it({\theta}+1/2)} = e^{it(k+1/2)}$ and so $e^{it(k-{\theta})} = -1$ and $e^{it}$ is a $2(k-{\theta}) = 4{\theta}^2$-th root of unity while $e^{it(k+1/2)}$ is an $8{\theta}^2$-th root of unity. Since none of the primitive $m$-th roots of unity of algebraic degree $4$ have real part $\tfrac{2{\theta}^2+2{\theta}+1}{\sqrt{n}(2{\theta}({\theta}+1)}$ for any ${\theta}$, there are no solutions.

For the complement of $X$, the characteristic equations are: $$\begin{aligned}
\sqrt{n}e^{it((n-k-1)+1/2)} &= \frac{-2{\theta}^2-2{\theta}-1 \pm i(2{\theta}+1)\sqrt{4{\theta}^2({\theta}+1)^2-1}}{2{\theta}({\theta}+1)} \\
\sqrt{n}e^{it({\theta}+1/2)} &= \frac{2{\theta}^2+2{\theta}+1 \pm i(2{\theta}+1)\sqrt{4{\theta}^2({\theta}+1)^2-1}}{2{\theta}({\theta}+1)} \end{aligned}$$ Then $e^{it(n-k+{\theta})} = 1$, so $e^{it}$ is a $(n-k+{\theta}) = (2{\theta}^2+4{\theta}+2)$-th root of unity. Again no solutions exist.

Conference graphs
-----------------

The final family of graphs that arise in Chan’s theorem are known as conference graphs. A conference graph has parameters $((2{\theta}+1)^2,2{\theta}^2+2{\theta}, {\theta}^2+{\theta}-1,{\theta}^2+{\theta})$ with ${\theta}+ \tau = -1$. Chan shows that $y = \bar{x}$. As in the previous case, the characteristic equations reduce to , , and with $c = e^{it/2}$. Then equations minus reduce to ${\mathrm{Im}}(x) = {\mathrm{Im}}(e^{it({\theta}+1/2)})$ and therefore $x =
e^{it({\theta}+1/2)}$ or $x = -e^{-it({\theta}+1/2)}$. There are two possible values of $(x,y)$, namely $$x \in \left\{\frac{-1 \pm \sqrt{(2{\theta}+1)(2{\theta}-1)}i}{2{\theta}},  
        \frac{1 \pm \sqrt{(2{\theta}+1)(2{\theta}+3)}i}{2({\theta}+1)}\right\}, \; y = \bar{x}.$$

[[**Case**]{} $x = \tfrac{-1 \pm \sqrt{(2{\theta}+1)(2{\theta}-1)}i}{2{\theta}}$:]{} In this case reduces to $ce^{ikt} = -1$. Thus $t = \frac{\pi(2m+1)}{k+1/2} =
\tfrac{2\pi(2m+1)}{n}$, for some integer $m$.

Suppose ${\theta}$ is an integer. Now $x = e^{it({\theta}+1/2)} = e^{i\pi(2m+1)/(2{\theta}+1)}$ or $-e^{-it({\theta}+1/2)} = -e^{-i\pi(2m+1)/(2{\theta}+1)}$, so $x$ is a $2(2{\theta}+1)$-th root of unity. But we claim that $x$ is a $2(2{\theta}+1)$-th root of unity only when ${\theta}= 1$. To see this, note that ${\left|{\mathrm{Re}}(x)\right|} = 1/2{\theta}$, while any $2(2{\theta}+1)$-th root of unity has a real part of larger absolute value. (The root smallest real part in absolute value is ${\omega}=
e^{i\pi({\theta}+1)/(2{\theta}+1)}$, which has ${\left|{\mathrm{Re}}({\omega})\right|} = \sin(\tfrac{\pi}{2(2{\theta}+1)}) > 1/2{\theta}$ for ${\theta}> 1$.) In the case ${\theta}= 1$, we get the $3 \times 3$ Latin square graph, for which uniform mixing does occur.

If ${\theta}$ is not an integer, then ${\theta}= (\sqrt{n}-1)/2$ for integer $n$, so ${\theta}$ and consequently $x$ are both algebraic. We use the Gelfand-Schneider theorem, as fomulated in Theorem \[gelfond\_schneider\]: since $\theta+1/2$ is irrational and $e^{it}$ is an $n$-th root of unity (and so algebraic) it follows that $e^{it({\theta}+1/2)}$ is transcendental, a contradiction. So there are no solutions if ${\theta}$ is not an integer.

[[**Case**]{} $x = \tfrac{1 \pm \sqrt{(2{\theta}+1)(2{\theta}+3)}i}{2({\theta}+1)}$:]{} This case is similar: we find $ce^{ikt} = 1$. Thus $t = \frac{\pi(2m+1)}{k+1/2} = \tfrac{2\pi(2m+1)}{n}$, for some integer $m$. So $t({\theta}+1/2) = (2\pi m)/(2{\theta}+1)$, and $x = e^{it({\theta}+1/2)}$ or $-e^{-it({\theta}+1/2)}$ is a $(2{\theta}+1)$-th root of unity. Since ${\left|{\mathrm{Re}}(x)\right|}$ is too small, this never occurs. Thus the only conference graph having uniform mixing is the $3 \times 3$ Latin square.

The combination of the work above proves Theorem \[srg\_theorem\].

Bipartite graphs {#bipartite_graphs}
================

Next we consider bipartite graphs. Assume $X$ is bipartite on $n$ vertices with adjacency matrix $A$ such that $$A =\begin{pmatrix} 0&B\\ B^T&0 \end{pmatrix}$$ Then $$A^{2k} = {\begin{pmatrix} (BB^T)^k&0\\ 0&(B^TB)^k \end{pmatrix}},$$ $$\qquad A^{2k+1} = {\begin{pmatrix} 0&(BB^T)^kB\\ (B^TB)^kB^T&0 \end{pmatrix}},$$ and $$U(t) = e^{itA} = {\begin{pmatrix} \cos(tBB^T)& i\sin(tBB^T)B\\ i\sin(B^TB)B^T& \cos(tB^TB) \end{pmatrix}}.$$ To simplify notation we write $$U(t) = {\begin{pmatrix} C_1(t)& iK(t)\\ iK^T(t)&C_2(t) \end{pmatrix}}.$$ What we are seeing in this expression for $U(t)$ is a reflection of the fact that any normal matrix can be written as a sum $C+iK$, where $C$ and $K$ are commuting Hermitian matrices; this is relevant because $U(t)$ is normal. ($2N = (N+N^*) +i(-iN+iN^*)$)

We immediately rederive Kay’s result [@Kay11] concerning the phase factors for perfect state transfer in bipartite graphs.

If $X$ is a bipartite graph on $n > 2$ vertices that admits uniform mixing, then $n$ is divisible by four.

[*Proof.* ]{}Now suppose $U(\tau)$ is flat. Using the notation above, we see that all entries of $C_1(\tau)$, $C_2(\tau)$ and $K(\tau)$ are equal to $\pm1/\sqrt{n}$. Since $U(\tau)$ is unitary, $$I=U(\tau)U(\tau)^* ={\begin{pmatrix} C_1^2 +KK^T& i(C_1K-KC_2)\\ i(K^TC_1-C_2K^T)& K^TK+C_2^2 \end{pmatrix}}$$ and thus all entries of $\sqrt{n}U(\tau)$ are fourth roots of unity. If $D$ is diagonal of order $n\times n$ and $D_{u,u}$ is 1 or $i$ according as $u$ is in the first or second colour class of $X$, then $$H = \sqrt{n} DU(\tau)D$$ is a real Hadamard matrix. In particular, we have $$H = \sqrt{n}{\begin{pmatrix} C_1& -K\\ -K^T&-C_2 \end{pmatrix}}$$ It is well known that if $n$ is a real Hadamard matrices of order $n$ such that $n > 2$, then $n$ is divisible by four.[  ]{}

Adamczak et al. [@adamczak07] show that if uniform mixing occurs on $C_{2m}$, then $m$ must be a sum of two squares. We generalize this result to all bipartite graphs.

If $X$ is a regular, bipartite graph with $n$ vertices, then $n$ is the sum of two integer squares.

[*Proof.* ]{}Suppose $X$ is regular (and bipartite). Then $$\sqrt{n}U(\tau){\textbf{1}}=(a+ib){\textbf{1}}$$ for some integers $a$ and $b$ and then $$n{\textbf{1}}= \sqrt{n}{{\mkern2mu\overline{\mkern-2muU(\tau)}}}\, \sqrt{n}U(\tau){\textbf{1}}= (a-ib)(a+ib){\textbf{1}}$$ and this shows that $n$ is the sum of two integer squares.[  ]{}

Cycles
======

It was conjectured by Ahmadi et al. [@ahmadi03] that no cycle $C_n$, except for $C_3$ and $C_4$, admits uniform mixing. Adamczak et al. [@adamczak07] show that $C_n$ does not admit uniform mixing if $n = 2^u$ for $u \geq 3$ or if $n = 2^{u}m$ where $m$ is not the sum of two integer squares and $u \geq 1$. Carlson et al. [@carlson07] show that uniform mixing does not occur on $C_5$. (This result also follows from the earlier result in this paper that uniform mixing does not occur on conference graphs.)

Using Theorem \[no\_algebraic\], we show that uniform mixing cannot occur on any even cycle. Likewise, we see that uniform mixing cannot occur on $C_p$ where $p$ is a prime such that $p \geq 5$. For both of these results, we use the irrationality of the eigenvalues of the underlying graph.

Recall that the eigenvalues of a general cycle $C_n$ have the form $$\theta_r = \zeta^r + \zeta^{-r},$$ where $\zeta = e^{2 \pi i /n}$. If $n$ is even, then $\theta_0 = 2$ and $\theta_{n/2} = -2$ are both simple eigenvalues of $C_n$, and the remaining eigenvalues each have multiplicity 2. On the other hand, if $n$ is odd, then $\theta_0 = 2$ is the only simple eigenvalue, and the nontrivial eigenvalues each have multiplicity two.

\[irrational\_lemma\] If $n =5$ or $n \geq 7$, then $C_n$ has an irrational eigenvalue.

[*Proof.* ]{}Using the notation above, we note that $\theta_1 = 2 \cos(2 \pi i / n)$. Since $n$ is a positive integer, the eigenvalue $\theta_1 = 2 \cos(2 \pi i / n)$ is rational if and only if $n \in \{1,3,4,6\}$ (see [@olmsted45].) If we assume $n = 5$ and $n \geq 7$, then $\theta_1$ is an irrational eigenvalue of $C_n$.[  ]{}

Using our work on bipartite graphs and Theorem \[no\_algebraic\], we eliminate the possibility of uniform mixing occurring on all even cycles other than $C_4$. This extends the work of Adamczak et al. [@adamczak07].

The cycle $C_4$ is the unique even cycle that admits uniform mixing.

[*Proof.* ]{}Let $U(t)$ denote the transition matrix of $C_{2m}$. If $m = 2$, it is straightforward to observe that $U(t)$ is flat at time $t = \pi/4 + r \pi/2$ for any $r \in {{\mathbb Z}}$. Suppose for a contradiction that $m > 2$ and $U(t)$ is flat at some time $t$. From the discussion in Section \[bipartite\_graphs\], it follows that $m$ must be even, and so $m > 3$. Furthermore, all of the entries of $U(t)$ are $\pm 1/\sqrt{n}$ or $\pm 1\sqrt{n}$, and hence they are all algebraic. Thus by Corollary \[no\_algebraic\_reg\], the eigenvalues of $C_{2m}$ must be integers, which contradicts Lemma \[irrational\_lemma\].[  ]{}

Next we turn our attention to cycles of odd prime order. It is known that $C_3$ admits uniform mixing at times $t = 2 \pi/9 + 2 \pi$ and $t = 4 \pi /9 + 2 \pi r$ for all $r \in {{\mathbb Z}}$. On the other hand, it is known that $C_5$ does not admit uniform mixing [@carlson07]. (This is also a consequence of our earlier results about conference graphs.) We extend these results to show that $C_p$ does not admit uniform mixing for any prime $p$ such that $p \geq 5$.

To obtain this result, we consider the general framework of cyclic $p$-roots. The essential point is that there is a one-to-one correspondence between cyclic $p$-roots of order $n$ and complex circulant matrices $H$ of order $n$ such that $H$ has constant diagonal $1$ and $$\label{typeII}
    H H^{(-)} = nI.$$ Note that the set of circulant complex Hadamard matrices with diagonal $1$ are a subset of such matrices. The key motivation for switching to this more general setting is that cyclic $p$-roots form an algebraic variety. This follows from the observation that the constraints corresponding to (\[typeII\]) are polynomial constraints with rational coefficients.

The following important observation is due to Haagerup [@haagerup08].

There are a finite number of cyclic $p$-roots.[  ]{}

An algebraic consequence of this result is that any cyclic $p$-root must have algebraic coordinates. Combining this with Theorem \[no\_algebraic\], we obtain the following new result.

The cycle $C_3$ is the unique cycle of odd prime order that admits uniform mixing.

[*Proof.* ]{}We compute a Groebner basis for the affine variety in ${{\mathbb C}}^n$ corresponding to the set of cyclic $p$-roots. The affine variety is a finite set, and so for each $j$ in $1 \leq j \leq n$ there is some $m_j \geq 0$ such that $x_j^{m_j}$ is the leading term of a element in the Groebner basis [@cox97]. This implies that each coordinate of a cyclic $p$-root is an algebraic number. Every complex Hadamard matrix is the scalar multiple of a matrix whose entries correspond to cyclic $p$-roots, and so every cyclic complex Hadamard matrix is the scalar multiple of matrix with all algebraic entries. By Lemma \[irrational\_lemma\], we know that $C_p$ has an irrational eigenvalue for all prime $p$ such that $p \geq 5$. From Corollary \[no\_algebraic\_reg\], we conclude that $U(t)$ is never flat.[  ]{}

$\epsilon$-uniform mixing on $C_{p}$
====================================

In this section we show that $\epsilon$-uniform mixing occurs on cycles of prime length. In particular, we show in these cases that $U(t)$ gets arbitrarily close to the scalar multiple of a complex Hadamard matrix.

Let $p$ denote an odd prime, and let $\omega$ denote a primitive $p$-th root of unity. Define $F_p$ to be the Fourier-type matrix such that $$[F_p]_{j,k} = \omega^{(j-k)^2} \; \; \; \; 0 \leq i,j \leq n-1.$$ It is well-known that $\sqrt{p} F_p$ is a complex Hadamard.

Since cyclic association schemes are formally self-dual, it follows that the dual of $F_p$ is also a complex Hadamard matrix. Note that the dual matrix is defined to be $$\label{dual_fouriertype}
    \widehat{F_p} = \sqrt{n} \sum_{r=0}^d \omega^{r^2} E_r.$$

Our goal is to show that the scaled transition matrix of $C_p$ gets arbitrarily close to $\widehat{F_p}$. First we recall some well-known algebraic facts about the eigenvalues of $C_p$. Let $\phi$ denote the Euler phi function, and let $\theta_1, \dots, \theta_d$ denote the nontrivial eigenvalues of $C_p$, where $d = (p-1)/2$.

The extension field ${{\mathbb Q}}(\theta_1, \dots, \theta_d)$ is isomorphic to ${{\mathbb Q}}(\theta_1)$, and $$[{{\mathbb Q}}(\theta_1) : {{\mathbb Q}}] = (p-1)/2.$$

[*Proof.* ]{}Recall that the cyclotomic field ${{\mathbb Q}}(\zeta)$ is an algebraic extension of ${{\mathbb Q}}$, and $$[{{\mathbb Q}}(\zeta): {{\mathbb Q}}]  = \phi(p) = p-1.$$ Since $\zeta$ is the root of a quadratic polynomial over ${{\mathbb Q}}(\theta_1)$, the result follows.[  ]{}

\[prime\_independence\] The set $\{1, \theta_1, \theta_2, \dots, \theta_{(p-3)/2}\}$ is linearly independent over the rationals.

[*Proof.* ]{}This follows from the observation that for all $1 \leq t \leq d-1$, the eigenvalue $\theta_t$ is an integer polynomial in $\theta_1$ of degree at most $t$. However, the minimal polynomial of $\theta_1$ over ${{\mathbb Q}}$ has degree $(p-1)/2$.[  ]{}

Now we consider the transition matrix $U(t)$ of $C_p$. Recall that by scaling the transition matrix, we see that $$\label{scaled_transition2}
    e^{-2it} U(t) = E_0 + e^{(\theta_1 - 2)it}E_1 + \dots + e^{(\theta_d -2)it} E_d.$$ We wish to find $t$ such that $e^{-2it} \sqrt{p} U(t) \approx \widehat{F_p}$. To show that such a $t$ exists, we use a theorem due to Kronecker. (See [@bump04].) Recall that a *generator* of a compact torus $T$ is an element $t$ such that the smallest closed subgroup of $T$ containing $t$ is $T$ itself.

\[kronecker\] Let $(t_1,\dots,t_r)$ denote an element of ${{\mathbb R}}^r$, and let $t$ be the image of this point in $T = ({{\mathbb R}}/{{\mathbb Z}})^r$. Then $t$ is a generator of $T$ if and only if $1,t_1,\dots,t_r$ are linearly independent over ${{\mathbb Q}}$.[  ]{}

Using Kronecker’s Theorem, we are able to show that first $d-1$ nontrivial coordinates of (\[scaled\_transition2\]) get arbitrarily close to the first $d-1$ coordinates of $\widehat{F_p}$. By restricting our consideration to times $t$ that are integer multiples of $2 \pi / p$, we see that the $d$-th coordinates will be simultaneously approximated. This leads us to our desired result.

If $p$ is an odd prime, then $\epsilon$-uniform mixing occurs on $C_p$.

[*Proof.* ]{}Recall that $\omega = e^{2 \pi i /p}$, and therefore the coordinates of $\widehat{F_p}$ are $$\omega^{r^2} = e^{(2 r^2 \pi i)/p}.$$ Referring back to the coordinates in (\[dual\_fouriertype\]) and (\[scaled\_transition2\]), we see that $e^{-2it} \sqrt{p} U(t) \approx \widehat{F_p}$ if and only if $$\frac{1}{p} r^2 \approx \frac{(\theta_r - 2)t}{2 \pi}$$ for $1 \leq r \leq d$ when those exponents are considered elements in ${{\mathbb R}}/ {{\mathbb Z}}$. We restrict to times $t$ such that $t = (2 \pi /p) \alpha$ for some $\alpha$ in ${{\mathbb Z}}$. We have $e^{-2it} \sqrt{p} U(t) \approx \widehat{F_p}$ at these restricted times if and only if $$\label{pcyc_exponents}
    \frac{1}{p} r^2 \approx \frac{\alpha}{p}(\theta_r - 2),$$ where again we consider the exponents in ${{\mathbb R}}/ {{\mathbb Z}}$. Recall that for a cyclic association scheme we have $$\theta_d = -1 - \theta_1 - \theta_2 \dots - \theta_{d-1}.$$ Thus if (\[pcyc\_exponents\]) holds for $1 \leq r \leq d-1$, in the additive group ${{\mathbb R}}/ {{\mathbb Z}}$, we have that $$\begin{aligned}
    \frac{\alpha}{p}(\theta_d -2) &= -\frac{\alpha}{p} 
        - (p-3)\frac{\alpha}{p} - \sum_{r=1}^{d-1}(\theta_r-2) \frac{\alpha}{p} 
        - \frac{2 \alpha}{p} \\
        &= -\alpha - \frac{1}{p} \sum_{r=1}^{d-1} r^2 \\
        &= - \frac{1}{p} \sum_{r=1}^{d-1} r^2.\end{aligned}$$ Recall that $$\begin{aligned}
    \sum_{r=1}^{d-1} r^2 + d^2 &= \frac{d(d+1)(2d+1)}{6} \\
        &= \frac{p(p-1)(p+1)}{24}\end{aligned}$$

Since $p$ is an odd prime strictly larger than $3$, we see that\
$(p-1)(p+1)/24$ must be an integer. Therefore in ${{\mathbb R}}/ {{\mathbb Z}}$ we have $$- \frac{1}{p} \sum_{r=1}^{d-1} r^2 = \frac{1}{p}d^2.$$ Thus if Equation \[pcyc\_exponents\] holds for $1 \leq r \leq d-1$ in ${{\mathbb R}}/ {{\mathbb Z}}$, we have $$\frac{\alpha}{p}(\theta_d -2) \approx \frac{1}{p} d^2.$$ It suffices to show that there exists $t$ such that Equation \[pcyc\_exponents\] holds for $1 \leq r \leq d-1$ in ${{\mathbb R}}/ {{\mathbb Z}}$. From Theorem \[prime\_independence\], we know that $1, \theta_1, \dots, \theta_{d-1}$ are linearly independent over ${{\mathbb Q}}$, and consequently the following set is linearly independent over the rationals. $$\left\{1, \frac{1}{p}(\theta_{1} -2), \dots, \frac{1}{p}(\theta_{d-1} -2)\right\}.$$ By Kronecker’s Theorem, we see that $$D = \left\{ \left(\frac{1}{p}(\theta_{1} -2)\alpha, 
        \dots, \frac{1}{p}(\theta_{d-1} -2)\alpha \right) : \alpha \in {{\mathbb Z}}\right\}$$ is dense in $({{\mathbb R}}/{{\mathbb Z}})^r$. Therefore we can get arbitrarily close to our desired first $d$ coefficients of $\widehat{F_p}$.[  ]{}

Future work
===========

We conjecture that uniform mixing does not occur on the cycle $C_{p^2}$ for any prime $p > 3$. With this in mind, it would be desirable to relate the mixing properties of $C_{pm}$ to mixing properties of $C_m$ for any prime $p$ and integer $m$. The combination of two such results could lead to a complete classification of cycles with admit uniform mixing. Also it would be interesting to find additional examples of graphs in association schemes that admit uniform mixing.

We would like to know whether a graph that admits uniform mixing is necessarily regular. Naturally we would also like to know if the cycle $C_n$ admits uniform mixing when $n$ is odd and greater than three.
