text:
# Continuous-time quantum walks on the symmetric group

## 1 Introduction

According to our current understanding of physics, quantum mechanics provides sources of true randomness, and mathematically speaking much of the underlying framework of quantum information and computation may be viewed as an extension of the study of random processes. The focus in quantum information and computation is often placed on finding information processing tasks that can be performed with the help of quantum information (such as factoring integers in polynomial time  or implementing unconditionally secure key distribution ) or on studying the distinctively non-classical aspects of quantum information (such as entanglement; see, for instance, ). However, it seems quite plausible that the study of quantum information and computation will also lead to new methods in the study of classical computation and random processes. Along these lines, Kerenidis and de Wolf  recently used quantum arguments to prove new results on (classical) locally decodable codes.

As a step toward understanding the possible implications of quantum methods for the study of random processes, it is natural to consider the differences between classical and quantum processes. One of the topics that has recently received attention in the quantum computing community that highlights these differences is the the study of quantum computational variants of random walks, or quantum walks . (A recent survey on quantum walks by Kempe  is an ideal starting point for background on quantum walks.) In this paper we consider quantum walks on Cayley graphs of the symmetric group—a topic that has been suggested in at least two previous papers on quantum walks .

Two main variants of quantum walks have been considered: continuous-time quantum walks and discrete-time quantum walks. We restrict our attention to continuous-time quantum walks in this paper. Keeping in line with previous results on quantum walks, we find some significant differences between quantum and classical random walks on Cayley graphs of the symmetric group. In particular, we find that quantum walks on Cayley graphs of the symmetric group do not have uniform limiting distributions for several natural choices for the generators. This answers a question recently suggested by Ahmadi, Belk, Tamon, and Wendler  concerning non-uniform mixing of quantum walks.

One of the principle motivations for studying quantum walks has been that quantum walks may potentially be useful as algorithmic tools. This potential was recently demonstrated by Childs, Cleve, Deotto, Farhi, Gutmann and Spielman , who prove that there exists a black-box problem for which a quantum algorithm based on quantum walks gives an exponential speed-up over any classical randomized algorithm. The key to this algorithm is that a quantum walk is able to permeate a particular graph while any classical random walk (or any classical randomized algorithm, for that matter) cannot. One of the first problems that comes to mind as an obvious challenge for the quantum algorithms community is the graph isomorphism problem, and it is natural to ask whether quantum walks, and in particular quantum walks on Cayley graphs of the symmetric group, can be of any use for an algorithm for this problem. (While this was our primary motivation for studying quantum walks on the symmetric group, we have not found any way to apply our results to this problem.)

## 2 Definitions

### 2.1 Continuous-time quantum walks on graphs

A continuous-time quantum walk on an undirected graph $`\mathrm{\Gamma }=(V,E)`$ can be defined in the following way. First, we let $`A`$ be the $`|V|\times |V|`$ adjacency matrix of $`\mathrm{\Gamma }`$, i.e., $`A`$ is indexed by elements of $`V`$ and is as follows:

$$A[u,v]=\{\begin{array}{cc}1\hfill & \text{if }\{u,v\}E\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

Next, let $`D`$ be the $`|V|\times |V|`$ diagonal matrix for which the diagonal entry corresponding to vertex $`v`$ is $`\mathrm{deg}(v)`$ and let $`L=DA`$. The matrix $`L`$ is positive semidefinite and, under the assumption that $`\mathrm{\Gamma }`$ is connected, 0 is an eigenvalue with multiplicity 1; the uniform vector is a corresponding eigenvector. The quantum walk on $`\mathrm{\Gamma }`$ is then given by the following unitary matrix:

$$U(t)=e^{itL}$$

for $`t`$. If the quantum walk on $`\mathrm{\Gamma }`$ is run for time $`t`$ starting at vertex $`u`$, then the amplitude associated with each vertex $`v`$ is $`U(t)[v,u]`$, and thus measuring at this point (with respect to the standard basis) results in each vertex $`v`$ with probability $`\left|U(t)[v,u]\right|^2`$. If instead of starting at a particular vertex $`u`$ we have some quantum state described by $`\psi :V`$, and we run the quantum walk for time $`t`$, the new quantum state is described by $`U(t)\psi `$, and measuring results in each vertex $`v`$ with probability $`\left|(U(t)\psi )[v]\right|^2`$. Other types of measurements can be considered, but we will focus just on this sort of measurement where the outcome is a vertex of the graph. To our knowledge, continuous-time quantum walks were first considered by Farhi and Gutmann .

Continuous-time quantum walks are analogous to continuous-time random walks on $`\mathrm{\Gamma }`$, where the evolution is described by

$$M(t)=e^{tL}$$

rather than $`U(t)`$ as above. Specifically, if the continuous-time random walk is started at vertex $`u`$ and run for time $`t`$, the probability of being at vertex $`v`$ is given by $`M(t)[v,u]`$. Continuous-time random walks share many properties with their discrete-time variants .

This paper is concerned with quantum walks on Cayley graphs, which are regular graphs. In the case of regular graphs there is no difference between using the matrix $`L`$ and the adjacency matrix for the definition of quantum walks, and we find it is more convenient to use the adjacency matrix for the graphs we are considering. (Of course one cannot replace $`L`$ with the adjacency matrix when discussing the classical case, since this would not give rise to a stochastic process—the equivalence only holds for the quantum case.) The reasoning behind this equivalence is as follows. Because $`D`$ and $`A`$ commute for regular graphs, we see that

$$U(t)=e^{itdI}e^{itA}=e^{itd}e^{itA};$$

the difference is a global phase factor, which has no significance when calculating the probabilities. So, from here after in this paper we will consider the unitary process given by $`U(t)=e^{itA}`$ rather than $`e^{itL}`$.

In the case of classical random walks, there are various properties of random walks that are of interest. One of the most basic properties of a classical random walk is the limiting distribution (or stationary distribution). This distribution is the uniform distribution for random walks on connected, regular graphs, and in fact as a result of the way we have defined continuous-time random walks this distribution is uniform for any connected, undirected graph; this is apparent by considering the spectral decomposition of the matrix $`e^{tL}`$.

As quantum walks are unitary (and therefore invertible) processes, they do not converge to any state, so one must be precise about what is meant by the limiting distribution. Suppose we have a quantum walk on some graph $`\mathrm{\Gamma }`$ and some vertex $`u`$ has been designated as the starting vertex. The probability of measuring the walk at some vertex $`v`$ after time $`t`$ is, as described above, given by

$$P_t[v]=\left|U(t)[v,u]\right|^2.$$

If $`t`$ is chosen uniformly from some range $`[0,T]`$ then the resulting distribution is

$$\overline{P}_T[v]=\frac{1}{T}_0^TP_t[v]dt.$$

In the limit for large $`T`$ these distributions converge to some distribution $`\overline{P}`$, which is the limiting distribution of the quantum walk. This notion of the limiting distribution for a quantum walk is discussed in .

### 2.2 Cayley graphs and representation theory of the symmetric group

In this section we briefly discuss necessary background information on Cayley graphs of the symmetric group and on representation theory of the symmetric group, which is the main tool used in this paper to analyze quantum walks on Cayley graphs.

Let $`G`$ be a finite group and let $`RG`$ be a set of generators for $`G`$ satisfying $`gRg^1R`$ for all $`gG`$. Then the Cayley graph of $`G`$ with respect to $`R`$, which we denote by $`\mathrm{\Gamma }(G,R)`$ in this paper, is an undirected graph defined as follows. The set of vertices of $`\mathrm{\Gamma }(G,R)`$ coincides with $`G`$, and for any $`g,hG`$, $`\{g,h\}`$ is an edge in $`\mathrm{\Gamma }(G,R)`$ if and only if $`gh^1R`$. Equivalently, if $`R=\{h_1,\mathrm{},h_d\}`$ then each vertex $`g`$ is adjacent to vertices $`h_1g,\mathrm{},h_dg`$. Thus, $`\mathrm{\Gamma }(G,R)`$ is a regular graph of degree $`d=|R|`$. We will restrict our attention to generating sets that form conjugacy classes. (The method we use for analyzing quantum walks on Cayley graphs is limited to such generating sets.) Recall that for some group $`G`$, elements $`g`$ and $`h`$ are conjugate if there exists some $`aG`$ such that $`a^1ga=h`$. This is an equivalence relation that partitions $`G`$ into conjugacy classes. A function $`f:G`$ is a class function if it is constant on conjugacy classes of $`G`$.

The conjugacy classes in $`S_n`$ are determined by the cycle structures of elements when they are expressed in the usual cycle notation. Recall that a partition $`\lambda `$ of $`n`$ is a sequence $`(\lambda _1,\mathrm{},\lambda _k)`$ where $`\lambda _1\mathrm{}\lambda _k1`$ and $`\lambda _1+\mathrm{}+\lambda _k=n`$. The notation $`\lambda n`$ indicates that $`\lambda `$ is a partition of $`n`$. There is one conjugacy class for each partition $`\lambda n`$ in $`S_n`$, which consists of those permutations having cycle structure described by $`\lambda `$. We denote by $`C_\lambda `$ the conjugacy class of $`S_n`$ consisting of all permutations having cycle structure described by $`\lambda `$.

A representation of a group $`G`$ is a homomorphism from $`G`$ to $`\mathrm{GL}(d,)`$ for some positive integer $`d`$, where $`\mathrm{GL}(d,)`$ denotes the general linear group of invertible $`d\times d`$ complex matrices. The dimension of such a representation is $`d`$, and we write $`\mathrm{dim}(\rho )`$ to denote the dimension of a given representation $`\rho `$. Two representations $`\rho _1:G\mathrm{GL}(d_1,)`$ and $`\rho _2:G\mathrm{GL}(d_2,)`$ are equivalent if there exists an invertible linear mapping $`A:^{d_1}^{d_2}`$ such that $`A\rho _1(g)=\rho _2(g)A`$ for all $`gG`$, otherwise they are inequivalent. A representation $`\rho `$ of dimension $`d`$ is irreducible if there are no non-trivial invariant subspaces of $`^d`$ under $`\rho `$. That is, if $`W^d`$ is a subspace of $`^d`$ such that $`\rho (g)WW`$ for all $`gG`$, then $`W=^d`$ or $`W=\{0\}`$. A collection of inequivalent, irreducible representations is said to be complete if every irreducible representation is equivalent to one of the representations in this set. It holds that any complete set of irreducible representations can be put into one-to-one correspondence with the conjugacy classes of the group in question.

The character corresponding to a representation $`\rho `$ is a mapping $`\chi _\rho :G`$ obtained by taking the trace of the representation: $`\chi _\rho (g)=\mathrm{tr}(\rho (g))`$. Using the cyclic property of the trace it follows that the characters are constant on the conjugacy classes of a group. If we have a complete set of inequivalent, irreducible representations of a group, then the corresponding characters form an orthogonal basis for the space of all class functions.

The Fourier transform $`\widehat{f}`$ of a complex-valued function $`f`$ on $`G`$ at a representation $`\rho `$ is

$$\widehat{f}(\rho )=\underset{gG}{}f(g)\rho (g).$$

###### Fact 1

Let $`f`$ be a class function on a group $`G`$ and $`\rho `$ be an irreducible representation of $`G`$, then

$$\widehat{f}(\rho )=\frac{1}{\mathrm{dim}(\rho )}\left(\underset{gG}{}f(g)\chi _\rho (g)\right)I$$

For the symmetric group on $`n`$ elements there is a particular way of associating the partitions of $`n`$ (which are in one-to-one correspondence with the conjugacy classes of $`S_n`$) with a complete set of inequivalent, irreducible representations of $`S_n`$. These particular representations are said to be in Young normal form. (Several text books describe the specific method for constructing these representations—see, for instance, James and Kerber . It will not be important for this paper to discuss the actual construction of these representations.) These representations have the special property that all matrix entries in these representations are integers. Once we have these irreducible representations, it is possible to associate with each one an equivalent irreducible representation that has the property that $`\rho (g)`$ is a unitary matrix for every $`gS_n`$. The irreducible, unitary representation associated with a given partition $`\lambda n`$ will be denoted $`\rho _\lambda `$, and the corresponding character will be denoted $`\chi _\lambda `$. The following fact will be a useful fact regarding these representations.

###### Fact 2

Let $`\lambda `$ and $`\mu `$ be partitions of $`n`$ and let $`\rho _\lambda `$ and $`\rho _\mu `$ be the associated unitary representations as described above. Then for all $`1i,j\mathrm{dim}(\rho _\lambda )`$ and $`1k,l\mathrm{dim}(\rho _\mu )`$,

$$\underset{gS_n}{}\rho _\lambda (g)[i,j]\overline{\rho _\mu (g)[k,l]}=\{\begin{array}{cc}\frac{n!}{\mathrm{dim}(\rho _\lambda )}\hfill & \text{if }\lambda =\mu \text{}i=k\text{, and }j=l\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

When $`\lambda ,\nu n`$, we write $`\chi _\lambda (\nu )`$ to denote the character $`\chi _\lambda `$ evaluated at an arbitrary $`gC_\nu `$, and more generally if $`f`$ is a class function we write $`f(\nu )`$ to mean $`f(g)`$ for any $`gC_\nu `$.

###### Fact 3

The sum of the squares of the characters of a conjugacy class over any complete, irreducible set of representations of a group $`G`$ multiplied by the order of the class is the order of $`G`$. Thus, we have for $`\lambda n`$

$$|C_\lambda |\underset{\nu n}{}\chi _\nu (\lambda )^2=n!$$

It will be necessary for us to be able to evaluate the characters associated with the irreducible representations of the symmetric group in certain instances. The Murnaghan-Nakayama rule provides a tool for doing this—information on the Murnaghan-Nakayama rule can be found in .

## 3 Continuous-time quantum walks on $`\mathrm{\Gamma }(S_n,C_\lambda )`$

In this section we analyze the quantum walk on $`\mathrm{\Gamma }(S_n,C_\lambda )`$ for $`\lambda n`$. Our analysis implies that for some natural choices for $`\lambda `$ the quantum walk on $`\mathrm{\Gamma }(S_n,C_\lambda )`$ does not have a uniform limiting distribution with respect to the definition discussed in the previous section. In essence, the quantum walk has a significant “blind spot” consisting of all $`n`$-cycles (i.e., permutations having cycle-structure consisting of a single $`n`$-cycle).

This section is divided into three subsections. First we prove a general result concerning the spectral decomposition of quantum walks on $`S_n`$. We then consider the case where the generating set consists of the set of all transposition, and finally the case where the generating set consists of all $`p`$-cycles for any choice of $`p\{2,\mathrm{},n\}`$.

### 3.1 Spectral decomposition and periodicity

Define $`c_\lambda :S_n`$ to be the unit vector that is uniform on the conjugacy class $`C_\lambda `$ and zero everywhere else:

$$c_\lambda [g]=\{\begin{array}{cc}\frac{1}{\sqrt{|C_\lambda |}}\hfill & \text{if }gC_\lambda \hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}$$

The analysis of quantum walks on $`\mathrm{\Gamma }(S_n,C_\lambda )`$ is greatly simplified by the fact that these walks are constant on conjugacy classes, in the following sense.

###### Proposition 4

Let $`\alpha _t(g)`$ denote the amplitude associated with vertex $`g`$ after evolving the quantum walk on $`\mathrm{\Gamma }(S_n,C_\lambda )`$ for time $`t`$, assuming the walk starts on a conjugacy class, i.e., $`\alpha _t(g)=\left(U(t)c_\lambda \right)[g]`$. Then for all $`t`$, $`\alpha _t`$ is a class function.

The following lemma will be one of the main tools used in our analysis.

###### Theorem 5

Assume $`H[g,h]=f(g^1h)`$ for all $`g,hS_n`$, where $`f`$ a class function on $`S_n`$, and let $`U(t)=e^{itH}`$ for all $`t`$. Then for any partitions $`\lambda ,\mu n`$ we have

$$c_\lambda ^{}U(t)c_\mu =\frac{\sqrt{|C_\lambda |}\sqrt{|C_\mu |}}{n!}\underset{\nu n}{}\mathrm{exp}\left(\frac{it}{\mathrm{dim}(\rho _\nu )}\underset{\gamma n}{}|C_\gamma |f(\gamma )\chi _\nu (\gamma )\right)\chi _\nu (\lambda )\chi _\nu (\mu ).$$

In order to prove this theorem we will use the following lemma, by which a complete orthogonal set of eigenvectors and eigenvalues of $`U(t)`$ can be obtained.

###### Lemma 6

Assume $`H[g,h]=f(g^1h)`$ for all $`g,hS_n`$, where $`f`$ is a class function on $`S_n`$. Define vectors $`\psi _{\nu ,i,j}:S_n`$ for each $`\nu n`$, $`1i,j\mathrm{dim}(\rho _\nu )`$, as follows:

$$\psi _{\nu ,i,j}[g]=\rho _\nu (g)[i,j]$$

for all $`gS_n`$. Then each $`\psi _{\nu ,i,j}`$ is an eigenvector of $`H`$ with associated eigenvalue

$$\frac{1}{\mathrm{dim}(\rho _\nu )}\underset{\gamma n}{}|C_\gamma |f(\gamma )\chi _\nu (\gamma ).$$

Moreover, these eigenvectors are pairwise orthogonal and span the entire space $`^{S_n}`$.

Remark. The fact described in Lemma 6 is not new—for instance, it is discussed in Section 3E of  for general finite groups. A short proof of the lemma follows.

Proof of Lemma 6. For each $`gS_n`$ we have

$$(H\psi _{\nu ,i,j})[g]=\underset{hG}{}H[g,h]\psi _{\nu ,i,j}[h]=\underset{hG}{}f(g^1h)\rho _\nu (h)[i,j]=\underset{hG}{}f(h)\rho _\nu (gh)[i,j].$$

Now, since $`\rho _\nu `$ is a homomorphism, we have $`\rho _\nu (gh)=\rho _\nu (g)\rho _\nu (h)`$, which implies

$$(H\psi _{\nu ,i,j})[g]=\underset{k=1}{\overset{\mathrm{dim}(\rho _\nu )}{}}\rho _\nu (g)[i,k]\left(\underset{hS_n}{}f(h)\rho _\nu (h)\right)[k,j]=\underset{k=1}{\overset{\mathrm{dim}(\rho _\nu )}{}}\rho _\nu (g)[i,k]\widehat{f}(\rho _\nu )[k,j].$$

By Fact 1 we see that

$$(H\psi _{\nu ,i,j})[g]=\frac{1}{\mathrm{dim}(\rho _\nu )}\underset{hS_n}{}f(h)\chi _\nu (h)\rho _\nu (g)[i,j]=\left(\frac{1}{\mathrm{dim}(\rho _\nu )}\underset{\gamma n}{}|C_\gamma |f(\gamma )\chi _\nu (\gamma )\right)\psi _{\nu ,i,j}[g].$$

This establishes that the vectors $`\psi _{\nu ,i,j}`$ are eigenvectors with associated eigenvalues as claimed. The fact that these eigenvectors are pairwise orthogonal follows from Fact 2 and the fact that they span the entire space $`^{S_n}`$ follows from this orthogonality along with Fact 3.

Proof of Theorem 5. By Lemma 6 we may write

$$H=\underset{\nu ,j,k}{}\left(\frac{1}{\mathrm{dim}(\rho _\nu )}\underset{\gamma }{}|C_\gamma |f(\gamma )\chi _\nu (\gamma )\right)\frac{\psi _{\nu ,j,k}\psi _{\nu ,j,k}^{}}{\psi _{\nu ,j,k}^2}$$

and therefore

$$U(t)=\underset{\nu ,j,k}{}\mathrm{exp}\left(\frac{it}{\mathrm{dim}(\rho _\nu )}\underset{\gamma }{}|C_\gamma |f(\gamma )\chi _\nu (\gamma )\right)\frac{\psi _{\nu ,j,k}\psi _{\nu ,j,k}^{}}{\psi _{\nu ,j,k}^2}$$

Let $`X_\lambda :S_n`$ denote the characteristic function of $`C_\lambda `$ for $`\lambda n`$. Then we have that

$$c_\lambda ^{}\psi _{\nu ,j,k}=\frac{1}{\sqrt{|C_\lambda |}}\underset{gS_n}{}X_\lambda (g)\rho _\nu (g)[j,k]=\frac{1}{\sqrt{|C_\lambda |}}\widehat{X_\lambda }(\rho _\nu )[j,k]=\{\begin{array}{cc}\frac{\sqrt{|C_\lambda |}\chi _\nu (\lambda )}{\mathrm{dim}(\rho _\nu )}\hfill & \text{if }j=k\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

by Fact 1. By Fact 2 we have $`\psi _{\nu ,j,k}^2=\frac{n!}{\mathrm{dim}(\rho _\nu )}`$. So,

$`c_\lambda ^{}U(t)c_\mu `$ $`=`$ $`{\displaystyle \frac{1}{n!}}{\displaystyle \underset{\nu }{}}\mathrm{exp}\left({\displaystyle \frac{it}{\mathrm{dim}(\rho _\nu )}}{\displaystyle \underset{\gamma n}{}}|C_\gamma |f(\gamma )\chi _\nu (\gamma )\right)\mathrm{dim}(\rho _\nu ){\displaystyle \underset{1j,k\mathrm{dim}(\rho _\nu )}{}}c_\lambda ^{}\psi _{\nu ,j,k}\psi _{\nu ,j,k}^{}c_\mu `$
$`=`$ $`{\displaystyle \frac{\sqrt{|C_\lambda |}\sqrt{|C_\mu |}}{n!}}{\displaystyle \underset{\nu n}{}}\mathrm{exp}\left({\displaystyle \frac{it}{\mathrm{dim}(\rho _\nu )}}{\displaystyle \underset{\gamma n}{}}|C_\gamma |f(\gamma )\chi _\nu (\gamma )\right)\chi _\nu (\lambda )\chi _\nu (\mu ),`$
which is what we wanted to show.

Theorem 5 implies the following interesting fact.

###### Proposition 7

Any continuous-time quantum walk on the Cayley graph of the symmetric group for which the generators form conjugacy classes is periodic, with period $`2\pi /k`$ for some $`k\{1,2,3,\mathrm{}\}`$.

Proof. Using Fact 1 we see that the quantity $`|C_\gamma |\chi _\nu (\gamma )/\mathrm{dim}(\rho _\nu )`$ is a sum of matrix elements of irreducible representations. This quantity is independent of the particular choice of the basis for the irreducible representations, so we may choose that basis that corresponds to Young’s natural form, in which all of the matrix entries are integer valued, implying that the quantity itself is integer valued. Using Fact 3 and Theorem 5 therefore have that $`U(2\pi )=U(0)=I`$. Thus the period of the walk must divide $`2\pi `$.

We have not discussed mixing times in this paper, but the previous proposition implies that quantum walks on Cayley graphs of $`S_n`$ reach their limiting distribution quickly, and when calculating the limiting distribution it is only necessary to average over times in the range $`[0,2\pi ]`$. Note that in terms of implementation, this does not mean that the walk mixes in constant time; some number of operations that is polynomial in the degree of the graph and in some accuracy parameter is required to implement such a walk, assuming the ability to compute the neighbors of each vertex. See  for further details.

### 3.2 Cayley graphs of $`S_n`$ generated by transpositions

For the Cayley graph of $`S_n`$ generated by the transpositions, Theorem 5 has various implications that we discuss in this section. We will require explicit values for various characters of the symmetric group, which we now mention. Using the Murnaghan-Nakayama rule it can be shown that

$$\chi _\nu \left((n)\right)=\{\begin{array}{cc}(1)^{nk}\hfill & \text{for }\nu =(k,1,\mathrm{},1)\text{}k\{1,\mathrm{},n\}\text{ }\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

and

$$\chi _{(k,1,\mathrm{},1)}\left(\mathrm{id}\right)=\mathrm{dim}(\rho _{(k,1,\mathrm{},1)})=\left(\genfrac{}{}{0pt}{}{n1}{k1}\right).$$

For the characters at the transpositions, it is known  that

$$\chi _\nu (\tau )=\frac{\mathrm{dim}(\rho _\nu )}{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}\underset{j}{}\left(\left(\genfrac{}{}{0pt}{}{\nu _j}{2}\right)\left(\genfrac{}{}{0pt}{}{\nu _j^{}}{2}\right)\right).$$

Here, $`\tau `$ is any transposition, $`\nu ^{}`$ is the partition generated by transposing the Young diagram of $`\nu `$, while $`\nu _j`$ and $`\nu _j^{}`$ are the $`j^{th}`$ components of the partitions $`\nu `$ and $`\nu ^{}`$.

Substituting these values into Theorem 5 gives

$$c_\lambda ^{}U(t)c_\mu =\frac{\sqrt{|C_\lambda |}\sqrt{|C_\mu |}}{n!}\underset{\nu n}{}\mathrm{exp}\left(it\underset{j}{}\left(\left(\genfrac{}{}{0pt}{}{\nu _j}{2}\right)\left(\genfrac{}{}{0pt}{}{\nu _j^{}}{2}\right)\right)\right)\chi _\nu (\lambda )\chi _\nu (\mu )$$

for the quantum walk on $`\mathrm{\Gamma }(S_n,C_{(2,1,\mathrm{},2)})`$, and specifically for the case where $`\mu =(1,\mathrm{},1)`$ and $`\lambda =(n)`$ it follows that

$`c_{(n)}^{}U(t)c_{(1,\mathrm{},1)}`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{nn!}}}{\displaystyle \underset{k=1}{\overset{n}{}}}\mathrm{exp}\left(it\left(\left({\displaystyle \genfrac{}{}{0pt}{}{k}{2}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{nk+1}{2}}\right)\right)\right)(1)^{nk}\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{k1}}\right)`$
$`=`$ $`{\displaystyle \frac{\left(2i\mathrm{sin}(tn/2)\right)^{n1}}{\sqrt{nn!}}}.`$
In particular,

$$\underset{t}{\mathrm{max}}\left|c_{(n)}^{}U(t)c_{(1,\mathrm{},1)}\right|^2=\frac{2^{2n2}}{nn!},$$
(1)
where the maximum occurs for $`t=(2k+1)\pi /n`$, $`k`$.

Eq. 1 has the following interpretation. If we start a quantum walk on $`\mathrm{\Gamma }(S_n,C_{(2,1,\mathrm{},1)})`$ at the identity element and evolve for any amount of time and measure, the probability to measure some $`n`$-cycle is at most $`\frac{2^{2n2}}{nn!}`$ as opposed to probability approaching $`\frac{1}{n}`$ for the classical case. The probability to measure any particular $`n`$-cycle is therefore at most $`\frac{2^{2n2}}{(n!)^2}`$, as opposed to some number approaching $`\frac{1}{n!}`$ classically. The probabilities in the quantum case are smaller by a factor that is exponential in $`n`$.

As discussed in Section 2.1, we will denote by $`P_t`$ the distribution on $`S_n`$ obtained by performing the quantum walk on $`\mathrm{\Gamma }(S_n,C_{(2,1,\mathrm{},1)})`$ for time $`t`$ starting at the identity then measuring. The above analysis gives a lower bound for the total variation distance of $`P_t`$ from the uniform distribution:

$$P_t\mathrm{uniform}\frac{1}{n}\frac{2^{2n2}}{nn!}$$

for all values of $`t`$. This bound follows from considering only the $`n`$-cycles, and we believe the true bound to be much larger. Numerical simulations support this claim, but thus far we only have exact expressions for the $`n`$-cycles.

Given that we have an exact expression for the probability $`P_t[g]`$ for any $`n`$-cycle $`g`$, it is easy to determine the probability associated with any $`n`$-cycle in the limiting distribution. To be precise, let

$$\overline{P}[g]=\frac{1}{2\pi }_0^{2\pi }P_t[g]𝑑t$$

for each $`gS_n`$. Then for any $`gC_{(n)}`$ we have

$$\overline{P}[g]=\frac{1}{2\pi }_0^{2\pi }\frac{\left(2\mathrm{sin}(tn/2)\right)^{2n2}}{(n!)^2}𝑑t=\frac{\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)}{(n!)^2}.$$

Somewhat surprisingly, this average probability associated with reaching a given $`n`$-cycle is not unique to the particular choice of $`C_{(2,1,\mathrm{},1)}`$ as a generating set, as shown in the next subsection.

### 3.3 Other generating sets

We have not been able to obtain tractable expressions for the amplitudes associated with quantum walks for other generating sets besides $`C_{(2,1,\mathrm{},1)}`$. However, we can prove some facts concerning the limiting distributions for such walks in the case that the generating set consists of all $`p`$-cycles for any choice of $`p`$. (In case $`p`$ is odd, we must keep in mind that only the alternating group is being generated.) Again we will focus on the probability of reaching $`n`$-cycles starting from the identity.

Consider the quantum walk on $`\mathrm{\Gamma }(S_n,C_\gamma )`$, where $`\gamma `$ is any partition. According to Theorem 5, the probability associated with a given conjugacy class $`C_\lambda `$ when starting from a uniform superposition on another class $`C_\mu `$ after time $`t`$ is given by

$$|c_\lambda ^{}U(t)c_\mu |^2=\frac{|C_\lambda ||C_\mu |}{(n!)^2}\underset{\nu ,\eta }{}\mathrm{exp}\left(it|C_\gamma |\left(\frac{\chi _\nu (\gamma )}{\mathrm{dim}(\rho _\nu )}\frac{\chi _\eta (\gamma )}{\mathrm{dim}(\rho _\eta )}\right)\right)\chi _\nu (\lambda )\chi _\nu (\mu )\chi _\eta (\lambda )\chi _\eta (\mu ).$$

As before, we let $`\overline{P}`$ denote the limiting distribution of the walk when starting from the identity. Since our walks are periodic with period $`2\pi `$, we therefore have

$`\overline{P}[g]`$ $`=`$ $`{\displaystyle \frac{1}{(n!)^2}}{\displaystyle \frac{1}{2\pi }}{\displaystyle _0^{2\pi }}{\displaystyle \underset{\nu ,\eta }{}}\mathrm{exp}\left(it|C_\gamma |\left({\displaystyle \frac{\chi _\nu (\gamma )}{\mathrm{dim}(\rho _\nu )}}{\displaystyle \frac{\chi _\eta (\gamma )}{\mathrm{dim}(\rho _\eta )}}\right)\right)\chi _\nu (g)\mathrm{dim}(\rho _\nu )\chi _\eta (g)\mathrm{dim}(\rho _\eta )dt`$
$`=`$ $`{\displaystyle \frac{1}{(n!)^2}}{\displaystyle \underset{\nu ,\eta }{\overset{}{}}}\chi _\nu (g)\mathrm{dim}(\rho _\nu )\chi _\eta (g)\mathrm{dim}(\rho _\eta ).`$
Here the asterisk denotes that the sum is over all partitions $`\nu ,\eta `$ subject to the condition

$$\frac{\chi _\nu (\gamma )}{\mathrm{dim}(\rho _\nu )}=\frac{\chi _\eta (\gamma )}{\mathrm{dim}(\rho _\eta )}.$$
(2)
Observe that the choice of generators only affects the average distribution by determining what values other than $`\nu =\eta `$ are included in the sum. More generally, the average probability associated with obtaining some element in $`C_\lambda `$ when starting the walk on the uniform superposition over $`C_\mu `$ is given by

$$\frac{|C_\lambda ||C_\mu |}{(n!)^2}\underset{\nu ,\eta }{\overset{}{}}\chi _\nu (\lambda )\chi _\nu (\mu )\chi _\eta (\lambda )\chi _\eta (\mu ).$$

For the remainder of this section, let $`\gamma n`$ be the partition corresponding to the $`p`$-cycles, i.e., $`\gamma =(p,1,\mathrm{},1)`$, where $`2pn`$. We will consider the limiting distribution for the walk on $`\mathrm{\Gamma }(S_n,C_\gamma )`$. The Murnaghan-Nakayama rule can be used to give the following formula for some of the character values at the $`p`$-cycles for $`1pn1`$:

$$\chi _{(k,1,\mathrm{},1)}((p,1,\mathrm{},1))=\left(\genfrac{}{}{0pt}{}{np1}{kp1}\right)+(1)^{p+1}\left(\genfrac{}{}{0pt}{}{np1}{k1}\right).$$

First, let us assume that $`p`$ is even, so $`C_\gamma `$ generates the entire symmetric group. We will consider first the case $`p\frac{n}{2}`$. To determine the affect of the generators on the walk we need to determine when Eq. 2 holds. In the particular case where we are interested in $`\overline{P}[g]`$ for $`g`$ an arbitrary $`n`$-cycle, we may take advantage of the fact that $`\chi _\nu (g)=0`$ unless $`\nu =(k,1,\mathrm{},1)`$ for some $`k`$. Thus, it will be sufficient to determine for what values of $`k`$ and $`k^{}`$ we have

$$\frac{\chi _{(k,1,\mathrm{},1)}(\gamma )}{\mathrm{dim}(\rho _{(k,1,\mathrm{},1)})}=\frac{\chi _{(k^{},1,\mathrm{},1)}(\gamma )}{\mathrm{dim}(\rho _{(k^{},1,\mathrm{},1)})}.$$
(3)
Define

$$f(k)=\frac{\chi _{(k,1,\mathrm{},1)}(\gamma )}{\mathrm{dim}(\rho _{(k,1,\mathrm{},1)})}.$$

Since $`p`$ is even we have

$$f(k)=\frac{1}{\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)}\left(\left(\genfrac{}{}{0pt}{}{np1}{kp1}\right)\left(\genfrac{}{}{0pt}{}{np1}{k1}\right)\right)=\frac{1}{\left(\genfrac{}{}{0pt}{}{n1}{p}\right)}\left(\left(\genfrac{}{}{0pt}{}{k1}{p}\right)\left(\genfrac{}{}{0pt}{}{nk}{p}\right)\right),$$

and thus

$$f(k+1)f(k)=\frac{1}{\left(\genfrac{}{}{0pt}{}{n1}{p}\right)}\left(\left(\genfrac{}{}{0pt}{}{k1}{p1}\right)+\left(\genfrac{}{}{0pt}{}{nk1}{p1}\right)\right).$$

For $`2p\frac{n}{2}`$ this difference is positive, so $`f(k)`$ is strictly increasing and is therefore 1-to-1. Thus, Eq. 3 is satisfied only when $`k=k^{}`$ and so the average probability of reaching a given $`n`$-cycle is

$$\frac{1}{(n!)^2}\underset{k=1}{\overset{n}{}}\chi _{(k,1,\mathrm{},1)}((n))^2\chi _{(k,1,\mathrm{},1)}(\mathrm{id})^2=\frac{1}{(n!)^2}\underset{k=1}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2=\frac{1}{(n!)^2}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right).$$

The implication is that in this case the probability associated with any $`n`$-cycle in the limiting distribution is identical to the walk where the generating set consists of the transpositions.

For $`\frac{n}{2}<pn1`$, the situation is slightly more complicated. Since $`f(k+1)f(k)`$ is still nonnegative, $`f(k)`$ is increasing, but not strictly:

$$f(k)=f(k^{})k,k^{}\{np+1,\mathrm{},p\}\text{or}k=k^{}.$$

The average probability to reach a given $`n`$-cycle is therefore

$`{\displaystyle \frac{1}{(n!)^2}}{\displaystyle \underset{k=1}{\overset{n}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{k1}}\right)^2+{\displaystyle \frac{1}{(n!)^2}}{\displaystyle \underset{\stackrel{np+1k,k^{}p}{kk^{}}}{}}(1)^{k+k^{}}\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{k1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{k^{}1}}\right)`$
$`=`$ $`{\displaystyle \frac{1}{(n!)^2}}\left({\displaystyle \underset{k=1}{\overset{np}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{k1}}\right)^2+{\displaystyle \underset{k=p+1}{\overset{n}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{k1}}\right)^2\right)+{\displaystyle \frac{1}{(n!)^2}}\left({\displaystyle \underset{np+1kp}{}}(1)^k\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{k1}}\right)\right)^2.`$
If $`n`$ is even we have

$$\underset{np+1kp}{}(1)^k\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)=0$$

and thus the average probability to reach a given $`n`$-cycle can be rewritten as

$$\frac{1}{(n!)^2}\left(\underset{k=1}{\overset{np}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2+\underset{k=p+1}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2\right)=\frac{2}{(n!)^2}\underset{k=1}{\overset{np}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2.$$

This probability is therefore smaller than for the case $`p\frac{n}{2}`$. For $`n`$ odd we have

$$\underset{np+1kp}{}(1)^k\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)=2\left(\genfrac{}{}{0pt}{}{n2}{p1}\right),$$

so the average probability to reach a given $`n`$-cycle is

$$\frac{1}{(n!)^2}\left(2\underset{k=1}{\overset{np}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2+4\left(\genfrac{}{}{0pt}{}{n2}{p1}\right)^2\right).$$

This probability is also smaller than the average probability of reaching an $`n`$-cycle for the case $`pn/2`$ since

$$\underset{k=np+1}{\overset{p}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2(2pn1)\left(\genfrac{}{}{0pt}{}{n1}{p1}\right)^24\left(\genfrac{}{}{0pt}{}{n2}{p1}\right)^2.$$

Finally, for the special case where $`p=n`$ (still assuming $`p`$ is even), we again have the situation that Eq. 3 is satisfied only when $`k=k^{}`$, and thus the average probability to reach an $`n`$-cycle is again $`\frac{1}{(n!)^2}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)`$.

Now we consider the case where $`p`$ is odd. In this case, the quantum walk is taking place on the alternating group. If $`n`$ is even, there is of course therefore zero probability to reach any given $`n`$-cycle, so assume $`n`$ is odd. Letting $`f(k)`$ be as defined before and considering that $`p`$ is odd, we have

$$f(k)=\frac{1}{\left(\genfrac{}{}{0pt}{}{n1}{p}\right)}\left(\left(\genfrac{}{}{0pt}{}{k1}{p}\right)+\left(\genfrac{}{}{0pt}{}{nk}{p}\right)\right),$$

which is symmetric about $`\frac{n+1}{2}`$. By a similar argument to before, it can be shown that in the case $`p\frac{n+1}{2}`$, the function $`f(k)`$ is strictly decreasing for $`1k\frac{n+1}{2}`$ and strictly increasing for $`\frac{n+1}{2}kn`$. Eq. 3 is therefore satisfied if and only if $`k=k^{}`$ or $`k=nk^{}+1`$. This gives an average probability of

$$\frac{2}{(n!)^2}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)\frac{1}{(n!)^2}\left(\genfrac{}{}{0pt}{}{n1}{\frac{n1}{2}}\right)^2$$

to reach a given $`n`$-cycle. This is slightly less than twice the probability of reaching a given $`n`$-cycle for the case $`p`$ even and $`p\frac{n}{2}`$, which is not surprising since the alternating group is half the size of the symmetric group.

Next suppose $`p>\frac{n+1}{2}`$. Then in the range $`1knp+1`$ the function $`f(k)`$ is strictly decreasing, in the range $`np+1kp`$ the function $`f(k)`$ is constant ($`f(k)=0`$ in this range), and in the range $`pkn`$ the function $`f(k)`$ is strictly increasing. This implies that the average probability of reaching each $`n`$-cycle is

$$\frac{1}{(n!)^2}\left(4\underset{k=1}{\overset{np}{}}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2+4\left(\genfrac{}{}{0pt}{}{n2}{p1}\right)^2\right).$$

Lastly, in the case $`p=n`$, we are back to the situation that $`f(k)=f(k^{})`$ if and only if $`k=k^{}`$ or $`k=nk^{}+1`$, giving an average probability of

$$\frac{2}{(n!)^2}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)\frac{1}{(n!)^2}\left(\genfrac{}{}{0pt}{}{n1}{\frac{n1}{2}}\right)^2$$

to reach each $`n`$-cycle.

We summarize the facts we have just discussed in the following table.

| Parity of $`n`$ | Parity of $`p`$ | Range of $`p`$ | Average probability to reach each $`n`$-cycle |
| --- | --- | --- | --- |
| even or odd | even | $`2p\frac{n}{2}`$ | $`\frac{1}{(n!)^2}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)`$ |
| even | even | $`\frac{n}{2}+1pn1`$ | $`\frac{2}{(n!)^2}_{k=1}^{np}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2`$ |
| odd | even | $`\frac{n+1}{2}+1pn1`$ | $`\frac{2}{(n!)^2}_{k=1}^{np}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2+\frac{4}{(n!)^2}\left(\genfrac{}{}{0pt}{}{n2}{p1}\right)^2`$ |
| even | even | $`p=n`$ | $`\frac{1}{(n!)^2}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)`$ |
| even | odd |  | 0 |
| odd | odd | $`2p\frac{n+1}{2}`$ | $`\frac{2}{(n!)^2}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)\frac{1}{(n!)^2}\left(\genfrac{}{}{0pt}{}{n1}{\frac{n1}{2}}\right)^2`$ |
| odd | odd | $`\frac{n+1}{2}+1pn1`$ | $`\frac{4}{(n!)^2}_{k=1}^{np}\left(\genfrac{}{}{0pt}{}{n1}{k1}\right)^2+\frac{4}{(n!)^2}\left(\genfrac{}{}{0pt}{}{n2}{p1}\right)^2`$ |
| odd | odd | $`p=n`$ | $`\frac{2}{(n!)^2}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)\frac{1}{(n!)^2}\left(\genfrac{}{}{0pt}{}{n1}{\frac{n1}{2}}\right)^2`$ |

We have the following lower bounds on the total variation distance of the limiting distribution from the uniform distribution. As for the case of the case of the quantum walk generated by the transpositions, this bound follows just from considering the $`n`$-cycles, and we believe the true distance from uniform to be much larger.

* Let $`p\{2,\mathrm{},n\}`$ be even, let $`\gamma =(p,1,\mathrm{},1)n`$ and let $`\overline{P}`$ denote the limiting distribution of the quantum walk on $`\mathrm{\Gamma }(S_n,C_\gamma )`$. Then

$$\overline{P}\mathrm{uniform}(S_n)\frac{1}{n}\frac{1}{nn!}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right).$$
* Let $`n`$ be odd, let $`p\{2,\mathrm{},n\}`$ be odd, let $`\gamma =(p,1,\mathrm{},1)n`$ and let $`\overline{P}`$ denote the limiting distribution of the quantum walk on $`\mathrm{\Gamma }(S_n,C_\gamma )`$. Then

$$\overline{P}\mathrm{uniform}(A_n)\frac{2}{n}\frac{2}{nn!}\left(\genfrac{}{}{0pt}{}{2n2}{n1}\right)+\frac{1}{nn!}\left(\genfrac{}{}{0pt}{}{n1}{\frac{n1}{2}}\right)^2.$$

## 4 Conclusion

In this paper we have studied some of the properties of continuous-time quantum walks on Cayley graphs of the symmetric group. Many questions concerning these walks remain unanswered. One obvious question that we have not attempted to address in this paper is whether quantum walks on the symmetric group can be applied in the context of quantum algorithms. In terms of specific properties of these walks, we have focused on the limiting distribution—is the limiting distribution bounded away from uniform by a constant? Many other properties of these walks may be of interest as well. For instance, the effect of decoherence on these walks is an interesting topic to consider.


format: text

text:
# A model-independent analysis of the dependence of the anomalous 𝐽/𝜓 suppression on the number of participant nucleons

## References


text:
# Improvement of dielectric loss tangent of doped Ba0.5Sr0.5TiO3 thin films for tunable microwave devices

## I INTRODUCTION

It is a challenging task for microwave communication researchers to develop tunable microwave devices. One of the approaches is to use a ferroelectric thin film as a buffer layer, while the dielectric constant $`\epsilon _r`$ of the ferroelectric thin film can be tuned by applying an electric field and hence the working frequency of the microwave devices can be tuned accordingly1 ; 2 ; 3 ; 4 . The forerunner candidate of a hybrid multi-layer thin film system involves Ba1-xSrxTiO3 (BST) where $`x`$ is the concentration of the constituent which can be tuned as well. An additional advantage of BST is the Curie temperature (TC) of BST dependence on $`x`$. Therefore, the working temperature of the tunable microwave devices can be tuned as well5 ; 6 ; 7 ; 8 . Unfortunately, the dielectric loss $`tan\delta `$ of the BST is normally high, which is around 0.03 for $`x=0.5`$ in the present study on pulsed laser deposited thin film. The reported values of $`tan\delta `$ for BST from different research groups are varied. In general, the values of $`tan\delta `$ are too high for BST to be useful to be of practical use in microwave tunable devices. It is a general belief that $`tan\delta `$ values have to be lower than 0.01 for BST thin films to be useful in the microwave devices9 ; 10 ; 11 . In the present study, we chose to address the problem of dielectric loss by doping the BST with low loss oxide12 ; 13 ; 14 . The Al2O3 is chosen for its low microwave dielectric loss as a dopant. The dielectric properties of doped ferroelectric film is measured by a home-made microstrip dual resonator near 7.7 GHz. The result was then checked by measured the $`\epsilon _r`$ of LaAlO3 single crystal substrate.

## II EXPERIMENTAL

BST target with diameter 2.5 cm was prepared using BaTiO3, SrTiO3 powders with ratio 1:1, via the conventional ceramic processing. The BaTiO3 and SrTiO3 powders were mixed and calcined at 950 oC for 1 hour before they were compacted and sintered at 1350 oC for 4 hours. The Al2O3 doped BST thin films were deposited on (100) LaAlO3 single crystal substrates with size of 10 $`\times `$ 5 $`\times `$ 0.5 mm3, by PLD with a KrF excimer laser at repetition rate of 5 Hz, and the average pulse energy was 250 mJ. BST target with Al2O3 plates on its surface was employed in the film deposition. The Al2O3 doped BST films deposition as carried out at substrate temperature of 650 oC and an oxygen pressure of 0.2 mbar for 45 minutes. The post-deposition annealing was done in the PLD chamber at the same temperature but with a higher oxygen pressure of 1.0 atm. The optimum distance between substrate and target was 4.5 cm for this temperature and pressure. The content of Al2O3 in the deposited Al2O3 doped BST films are controlled by coverage area of Al2O3 over the BST target. BST film without doping was also deposited for comparison. The films produced from the targets with 10 percents, 20 percents, 30 percents and 40 percents Al2O3 coverage of the BST target were abbreviated to BSTA1, BSTA2, BSTA3 and BSTA4. The Al2O3 content in the films were characterized by Rutherford Backscattering Analysis (RBS), and the relative concentration of Al2O3 in BSTA1: BSTA2: BSTA3: BSTA4 were found to be 1 : 4 : 6 : 9 .
Structural phase composition and crystallization of the Al2O3 doped BST thin films were determined by X-ray diffraction (XRD), using a Philips PW 1729 type X-ray diffractometer. Surface morphology was examined by scanning electron microscopy (SEM), using a JEOL JSM-6340F type field emission scanning electron microscope. The dielectric properties of Al2O3 doped BST films in terms of $`\epsilon _r`$ and $`tan\delta `$ were measured by a home-made non-destructive microstrip dual-resonator method at room temperature and microwave frequency 7.7 GHz15 ; 16 . The microstrip dual-resonator patterned on a TMM10i microwave substrate, consists of two planar half-wavelength resonators coupled through a gap of 36$`\mu m`$. The film under test was placed on top of the microstrip circuit, covering the gap between two microstrip resonators. The $`\epsilon _r`$ and $`tan\delta `$ of the films were derived from the resonant frequencies $`f`$1, $`f`$2 and the corresponding quality factor $`Q`$1, $`Q`$2, of the microstrip dual-resonator. In the study of the electric field dependence of the Al2O3 doped BST thin films, a maximum dc voltage of 2.1 kV was applied through two electrode pads on the microstrip circuit board across a gap of about 2.6 mm, corresponding to a maximum electric field of 8.1 kV/cm.

## III RESULTS and DISCUSSION

Fig. 1 shows the XRD patterns of the deposited thin films. It is found that all the films have a single phase perovskite structure. The intensity peak was broadened with increasing Al2O3 dopant, which means that the grain size of the Al2O3 doped BST films decreased as a result of increased Al2O3 content. The Al2O3 was not detected by XRD due to the relatively small amount of Al2O3 compared with BST. However, for the BSTA4 film, two unidentified peaks were observed at 2$`\theta `$ $``$ 39.39o and 2$`\theta `$ $``$ 43.01o (marked $`\mathrm{}`$ as in Fig. 1). These peaks are attributed to a second phase caused by the excessive Al2O3 content. The second phase might be undesirable for the film to be applied in microwave devices. This would put a limit on the amount of dopant.
Fig. 2 displays the surface morphology of the Al2O3 doped BST thin films by SEM. The films exhibited a dense microstructure, which was greatly modified by Al2O3 doping. It is found that the surface roughness increases with the increase of Al2O3 content, and it is consistent with the XRD data. Furthermore, the thicknesses of the thin films were estimated as 500 nm in average from a cross-sectional SEM image.
The $`\epsilon _r`$ of the Al2O3 doped BST films as a function of applied electric field are shown in Fig. 3. The pure BST films have $`\epsilon _r`$ =1622 that is higher than doped films, BSTA1($`\epsilon _r`$ =1387), BSTA2($`\epsilon _r`$ =1311), BSTA3($`\epsilon _r`$ =950) and BSTA4($`\epsilon _r`$ =870). The$`\epsilon _r`$ of Al2O3 doped BST films decrease with increasing Al2O3 content. The high $`\epsilon _r`$ values are due to the fact that all thin films are epitaxially c-axis oriented, which are indicated by (100) and (200) peaks in XRD patterns. The highly c-axis oriented films provide a strong polarization direction compared to randomly oriented samples, and tends to form a concentrated polarization which results in higher $`\epsilon _r`$ . Fig. 4 depict the plot for $`tan\delta `$ of Al2O3 doped BST films as a function of the applied electric field. The $`tan\delta `$ decreased as 0.030, 0.021, 0.015, 0.012 and 0.011, corresponding to the samples BST, BSTA1, BSTA2, BSTA3 and BSTA4, respectively.
It is known that tunable microwave device applications, require a high dielectric constant and low dielectric loss. The dielectric tunability was calculated by the formula,

$`tunability`$ $`=`$ $`{\displaystyle \frac{\epsilon _{r0}\epsilon _{rb}}{\epsilon _{r0}}},`$ (1)
where $`\epsilon _{r0}`$ and $`\epsilon _{rb}`$ represent the dielectric constant value at zero applied electric field and the maximum applied electric field, respectively. The dielectric properties of Al2O3 doped BST films were listed in Table 1. Identical to dielectric constant and loss tangent, the dielectric tunability also reduce as a consequence of Al2O3 doping. We found that the dielectric tunability was reduced from 22.0 percents (BST thin film) to 15.9 percents (BSTA4). In tunable microwave devices application, figure of merit $`\kappa `$ is usually used to compare the quality of ferroelectric films, which is defined as,

$`\kappa `$ $`=`$ $`{\displaystyle \frac{tunability}{tan\delta }}.`$ (2)
One can noticed that $`\kappa `$ \- factors is proportional to Al2O3 content, as given in Table 1 in which $`\kappa `$ =7.33 (BST) and $`\kappa `$ =14.5 (BSTA4).

## IV SUMMARY

In conclusion, we demonstrated that highly c-axis oriented Al2O3 doped BST films could be deposited on (100) LaAlO3 single-crystal substrate, by PLD technique. It is found that$`\epsilon _r`$ , $`tan\delta `$ and dielectric tunability of the Al2O3 doped BST thin films have decreased due to increasing Al2O3 content. As a result of this, $`\kappa `$ \- factor were improved significantly. The Al2O3 substitution into BST films is observed to significantly modify the microstructure of the films. Our results showed the dielectric properties of BST ferroelectric thin films can be readily modified to fit the requirements of microwave device applications with Al2O3 doping.

One of the Authors (K. B. Chong) would like to thank National University of Singapore for the financial assistances.


text:
# Chapter 1 Very High Energy Observations Of PSR B1823-13

## Chapter 1 Very High Energy Observations Of PSR B1823-13

### Abstract

To date three plerionic systems have been detected as emitters of very energetic photons. As part of an ongoing study of pulsar systems at the Whipple observatory, observations of the plerion PSR B1823-13 are being conducted. Observations were made with the Whipple 10 m gamma-ray telescope utilizing the high resolution, 490 pixel camera.

### 1. Introduction

Four sources of detected very high energy (VHE) gamma radiation are associated with systems containing pulsars. Three of these sources (Crab Nebula , Vela pulsar , and PSR B1706-44 ) represent a class of objects known as plerions. A plerion is a compact nebula resulting from a relativistic particle wind emanating from a pulsar interacting with the pulsar’s environment.

PSR B1823-13 is a young, spin-powered pulsar with characteristics similar to both Vela and PSR B1706-44. Observations in the X-ray band  have revealed that PSR B1823-13 is powering a compact synchrotron nebula (plerion) with a physical size similar to that seen in the other plerionic sources (Crab, Vela, and PSR B1706-44). PSR B1823-13 is 7th in a rank ordered list of $`\dot{E}`$/d2.

In addition to the X-ray detection of this young isolated neutron star, the position of PSR B1823-13 is near the EGRET unidentified source, 3EG 1823-1314 . This EGRET source is also one of the stronger detections in the Lamb 1 GeV catalog . The above factors make PSR B1823-13 a prime candidate for observations in the VHE band.

### 2. Observations and Analysis

The observations of PSR B1823-13 presented here were made with the Whipple 10 m gamma-ray telescope located on Mt. Hopkins in southern Arizona . These data were collected during the spring of 2000. During this time, the telescope utilized a high resolution camera consisting of an array of 490 photomultiplier tubes mounted at the focal plane of the reflector. A detailed description of the telescope and its characteristics can be found in .

Images of extensive air showers initiated by high-energy photons and cosmic rays are made by recording the Čerenkov radiation emitted as the shower propagates through the atmosphere. By making use of distinctive differences in the angular distribution of light and the orientation of the shower images, it is possible to differentiate a gamma ray initiated event from a very large hadronic background.

#### 2.1. Unpulsed Analysis

The observations reported here were collected in the ON/OFF observation mode. In ON/OFF mode, the candidate source position is observed for 28 minutes (ON run) followed by a 28 minute reference observation (OFF run) taken at the same azimuth and elevation as the ON run. The OFF region is used to estimate the background counts in the ON region.

During the 2000 observing season, 430 minutes of ON source data (16 on/off pairs) were acquired. A moment analysis routine  utilizing the parameter cuts was applied to the data yielding a 3.4 $`\sigma `$ excess (0.7 g/min) in an ALPHA analysis. Figure 1 displays the ALPHA distribution and the ON minus OFF counts as a function of ALPHA angle. A flux upper limit of 2.6x10-11cm-2s-1 at a peak energy of 1 TeV was derived at a coinfidence level of 99.9%. A 2-Dimensional analysis  was also applied to the data yielding a 3.1 sigma excess near the position of PSR B1823-13 as seen in Figure 2.

#### 2.2. Periodic Analysis

The arrival times of Čerenkov events were recorded by a GPS clock and a 10 MHz oscillator calibrated by a GPS second mark to achieve an absolute time resolution of 0.1 $`\mu `$s. All arrival times were then transformed to the solar system barycenter using the JPL DE200 planetary ephemerides . The phase of each event passing the parameter cuts was calculated using the appropriate ephemeris for the epoch of the data. To test for the presence of a periodic signal, $`\chi ^2`$ and $`Z_m^2`$ tests were performed. The analysis of event arrival times showed no evidence of modulation at the pulsar period.

In order to calculate an upper limit for pulsed emission, a method utilizing the $`Z_2^2`$ statistic, which assumes a sinusoidal pulse profile, was used. The pulsed fraction at a peak energy of 1 TeV is found to be less than 6% of the background at a confidence level of 99.9%.

### 3. Discussion

Results from the observations of PSR B1823-13 show an excess in the ALPHA distribution consistent with a weak source. Figure 3 shows the cumulative significance obtained from the analysis. The gradual increase in significance may be due to a weak, persistent gamma-ray source. Further observations are currently being conducted. The results of these new observations will be presented at the conference.

### 4. Acknowledgments

We acknowledge the technical assistance of E. Roache and J. Melnick. We would also like to thank A. Lyne and Z. Arzoumanian for providing radio ephemerides for this report. This research is supported by grants from the U. S. Department of Energy, by Enterprise Ireland, and by PPARC in the UK.

### 5. References

1. Catanese M. et al. 1998, ApJ 501, 616

2. Cawley M.F., Fegan D.J., Harris K., Kwok P.W., Hillas A.M. 1990, Experimental Astronomy 1, 173

3. Finley J.P., Srinivasan R., Park S. 1996, ApJ 466, 938

4. Finley J.P. et al. 2001, in Proc. 27th ICRC (Hamburg, Germany), OG 2.5

5. Hartman R.C., et al. 1999, ApJS 123, 79

6. Kifune T. et al. 1995, ApJ 438, L91

7. Lamb R.C., Macomb D.J. 1997, ApJ 488, 872

8. Lessard R.W., Buckley J.H., Connaughton V., Le Bohec, S. 2001, APh 15, 1

9. Reynolds P.T. et al. 1993, ApJ 404, 206

10. Standish E.M. Jr. 1982, AAP, 114, 297

11. Weekes T.C. et al. 1989, ApJ 342, 379

12. Yoshikoshi T. et al. 1997, ApJ 487, L65


text:
# Velocity and Velocity-Difference Distributions in Burgers Turbulence

## Abstract

We consider the one-dimensional Burgers equation randomly stirred at large scales by a Gaussian short-time correlated force. Using the method of dissipative anomalies, we obtain velocity and velocity-difference probability density functions, and confirm the results with high-resolution numerical simulations.

1. Introduction. The one-dimensional Burgers equation with a random external force,

$`u_t+uu_x=\nu u_{xx}+f(x,t),`$ (1)
is a simple model of turbulence, where $`u(x,t)`$ is a one-dimensional velocity field, and $`\nu `$ is small viscosity. The external force is assumed to be Gaussian, with zero mean and white-in-time covariance,

$`f(x,t)f(x^{},t^{})=\kappa (xx^{})\delta (tt^{}),`$ (2)
where $`\kappa (y)`$ should be specified. We will assume that it is an analytic function at $`y0`$ with the characteristic scale $`L`$; non-analytic forms of $`\kappa `$ have been considered as well yakhot . This model has attracted considerable attention since it is believed to be exactly solvable yakhot ; polyakov ; boldyrev ; gurarie ; bouchaud ; balkovsky ; weinan ; weinan1 ; gotoh ; gotoh1 ; kraichnan1 ; bec ; frisch ; gurarie1 .

Let us introduce the characteristic function of the $`N`$-point velocity distribution, $`Z_N(\lambda _1,x_1;\mathrm{};\lambda _N,x_N;t)=\mathrm{exp}(\lambda _1u(x_1,t)+\mathrm{}+\lambda _Nu(x_N,t))`$. As was shown in polyakov , it obeys the master equation that one derives by differentiating this function with respect to $`t`$, and by using Eq. (1),

$`{\displaystyle \frac{Z_2}{t}}=\lambda _i{\displaystyle \frac{}{\lambda _i}}{\displaystyle \frac{1}{\lambda _i}}{\displaystyle \frac{Z_2}{x_i}}+{\displaystyle \frac{1}{2}}\lambda _i\lambda _j\kappa (x_ix_j)Z_2+D,`$ (3)
where the summation over repeated indices is assumed.

The last term in Eq. (3) denotes the contribution of the dissipative terms. Although the method of our paper is valid for the general case of $`N`$-point characteristic function, we will concentrate on the case $`N=2`$, where the solution is easy to find. In this case, $`D=\nu \left(\lambda _1u_{x_1x_1}+\lambda _2u_{x_2x_2}\right)\mathrm{exp}(\lambda _1u(x_1,t)+\lambda _2u(x_2,t))`$. This term does not vanish in the limit of infinitely large Reynolds number, $`\nu 0`$; rather, it has a finite value, because the velocity field develops singularities, shocks, where large velocity gradients are balanced by the small viscosity. It has been proposed in polyakov  that the origin of this term is analogous to the origin of anomalies in quantum field theories, and it has been suggested that this term can be expressed linearly through the $`Z`$ function. Namely, the following ansatz should be true inside any $`N2`$ point correlation function

$`A\underset{\nu 0}{lim}\nu \lambda u_{xx}e^{\lambda u(x)}=\left[{\displaystyle \frac{a}{2}}+{\displaystyle \frac{b1}{\lambda }}{\displaystyle \frac{}{x}}\right]e^{\lambda u(x)}.`$ (4)
The right hand side of (4) contains the simplest linear in $`e^{\lambda u}`$ terms that are consistent with translation, scale, and Galilean invariance polyakov ; boldyrev . The higher-derivative terms are not allowed since they would change the structure of Eq. (3) and may lead to additional, non-physical, solutions. The parameters $`a`$ and $`b`$, which we will call ‘anomalies,’ should be found from the requirement that the stationary solution of Eq. (3) correspond to a positive, finite, and normalizable PDF, similar to the eigenvalue problem in quantum mechanics. The other condition is non-positivity of the dissipation, $`D0`$. These two conditions restrict the values of the anomalies considerably. It has been shown in boldyrev  that the admissible solution exists for a one-parameter family $`\{b,a(b)\}`$, where $`3/4b1`$ and the corresponding interval for the $`a`$ anomaly is $`0a0.45`$.

The corresponding scale-invariant solution for the velocity difference PDF, $`w(\mathrm{\Delta }u/y)`$, where $`\mathrm{\Delta }u=u(x_1)u(x_2)u_{rms}`$ and $`y=x_1x_2L`$ can be found from (3). It has a peculiar structure that was first qualitatively established in numerical simulations yakhot  and was confirmed by a variety of analytical methods polyakov ; boldyrev ; gurarie ; bouchaud ; balkovsky ; weinan . It decays hyper-exponentially fast for the large positive argument, $`w(z)\mathrm{exp}(z^3/3)`$, and has an algebraic tail for the large negative argument, $`w(z)|z|^{2b1}`$ \[see section 2\]. This behavior is understood since due to the nonlinear term in Eq. (1), positive gradients decrease in the course of time, while negative gradients become stronger. Therefore, large negative velocity gradients are more probable than large positive ones.

According to the allowed values of the anomaly $`b`$ in model (4), the distribution density should decay slower than $`|z|^3`$ for $`z\mathrm{}`$. However, the geometric consideration of pre-shock events producing large negative velocity gradients, proposed in weinan ; weinan1 , suggested the asymptotic $`|z|^{7/2}`$. Lagrangian simulations of only the left tail of the PDF agreed with the latter result bec ; frisch ; gurarie1 .

So far, no analytical derivation of the full velocity-difference PDF decaying as $`|z|^{7/2}`$ was available. The direct numerical simulations of Eq. (1), carried out in gotoh ; gotoh1 , have not convincingly reproduced such a PDF either. The form of the PDF has therefore remained a subject of controversy.

In this Letter we propose that the PDF is not unique. In an infinite system, where the Galilean invariance holds, the anomaly has the form (4). In the finite-size systems, investigated in bec ; frisch ; gurarie1 , the global Galilean invariance is broken and the weak Galilean principle should be applied. In this case the form of the anomaly is different from (4), and the solution with the asymptotics $`|z|^{7/2}`$ may be allowed. We derive the corresponding velocity and velocity-difference PDFs. Next, we conduct extensive numerical simulations of Eq. (1), using a high-resolution shock capturing scheme. The results agree well with our analytical prediction. Section 2 presents the theory, section 3 – numerical simulations.

2. Velocity and velocity-difference PDF’s. The resolution of the controversy mentioned above is based on the fact that the form (4) of the anomaly is dictated by the strong form of the Galilean principle (see below) while the arguments of weinan ; weinan1  as well as numerical results bec ; frisch ; gurarie1  are correct only when the weak G-principle applies. The strong Galilean principle is the requirement that in the infinite system, taking velocity to zero at infinity does not break the Galilean symmetry in the middle. This requirement is analogous to the absence of the spontaneous symmetry breaking in magnetic systems. For the systems considered in weinan ; weinan1 ; bec ; frisch ; gurarie1  this strong G-principle obviously does not hold. The reason is that the size of the systems is of the same order as the correlation length of the force. Therefore, the velocities in the middle of the system are correlated to those at the boundary. The same argument works for the periodic case, in which the Galilean symmetry is broken by the condition $`u_0=u𝑑x=0`$.

So, the results in polyakov  and weinan ; weinan1 ; bec ; frisch ; gurarie1  refer to the different dynamical systems and that explains the discrepancy. The natural question is whether we can apply the methods of polyakov  for the case in which the strong G-symmetry is broken. This is important because the method of dissipative anomalies is the only known non-perturbative way to solve Burgers turbulence. In this case we still have the weak G-symmetry, which says that all correlation functions are G-symmetric, provided that we average them over $`u_0`$. This is of course always true, but how to impose this condition?

Let us notice that the correlation functions calculated at the fixed $`u_0`$ have the property

$`e^{{\scriptscriptstyle \lambda _ju(x_j,t)}}_{u_0}=e^{u_0{\scriptscriptstyle \lambda _j}}e^{{\scriptscriptstyle \lambda _ju(x_j,t)}}_0.`$ (5)
Hence, if we integrate over $`u_0`$ the correlations must have the form:

$`e^{{\scriptscriptstyle \lambda _ju(x_j,t)}}=2\pi \delta \left({\displaystyle \lambda _j}\right)e^{{\scriptscriptstyle \lambda _ju(x_j,t)}}_0.`$ (6)
The master equation (3) must allow this ansatz, namely the proportionality to the $`\delta \left(\lambda _j\right)`$ must be consistent with the equation. This is obviously so with the anomaly (4), but this also allows a more general form of the anomaly. Let us look at the expression

$`\stackrel{~}{A}=A+c\lambda {\displaystyle \frac{}{\lambda }}e^{\lambda u},`$ (7)
it adds the term $`\stackrel{~}{D}=c\lambda _jZ/\lambda _j`$ to the right hand side of Eq. (3). When $`Z=\delta \left(\lambda _j\right)Z_0`$, we have $`\stackrel{~}{D}=c\left(\lambda _jZ_0/\lambda _jZ_0\right)\delta \left(\lambda _j\right)`$, where we used the identity $`x\delta ^{}(x)=\delta (x)`$. It is important to notice that any other function of $`\lambda `$ or higher power of $`/\lambda `$ would break the ansatz. Anomalies of the form (7) have been considered in relation to incompressible turbulence by V. Yakhot \[private communication\].

The restrictions on the coefficients $`a`$, $`b`$, and $`c`$ can be obtained from the equation for the velocity-difference PDF. To write this equation, substitute the dissipative term (7) into Eq. (3). In the Galilean-invariant limit, the statistics of velocity differences are separated from those of the mean velocity field. Let us change the variables, $`\lambda _1=\mathrm{\Lambda }+\mu `$, $`\lambda _2=\mathrm{\Lambda }\mu `$, $`x_1=X+y/2`$, $`x_2=Xy/2`$, and assume that $`\mathrm{\Lambda }\mu `$, and $`yL`$. The latter condition allows us to expand $`\kappa (y)\kappa _0\kappa _2y^2/2`$. In this limit, the master equation (3) becomes

$`{\displaystyle \frac{^2Z_2}{\mu y}}{\displaystyle \frac{2b}{\mu }}{\displaystyle \frac{Z_2}{y}}2\mathrm{\Lambda }^2\kappa _0Z_2{\displaystyle \frac{\kappa _2\mu ^2y^2}{2}}Z_2`$
$`=c\mu {\displaystyle \frac{Z_2}{\mu }}+c\mathrm{\Lambda }{\displaystyle \frac{Z_2}{\mathrm{\Lambda }}}+aZ_2,`$ (8)
where we consider the stationary case, $`_tZ_2=0`$. In the finite-size system with $`u_0=0`$, we assume the weak G-symmetry and look for the solution in the form $`Z_2=Z_+(\mathrm{\Lambda })Z_{}(\mu ,y)`$. \[The strong G-symmetry would imply $`Z_+(\mathrm{\Lambda })\delta (\mathrm{\Lambda })`$ and the solution might be different.\] Substituting this into Eq. (8) we get the following set of equations for the characteristic functions $`Z_+`$ and $`Z_{}`$:

$`2\mathrm{\Lambda }^2\kappa _0Z_+=c\mathrm{\Lambda }{\displaystyle \frac{Z_+}{\mathrm{\Lambda }}},`$ (9)
$`{\displaystyle \frac{^2Z_{}}{\mu y}}{\displaystyle \frac{2b}{\mu }}{\displaystyle \frac{Z_{}}{y}}{\displaystyle \frac{\kappa _2\mu ^2y^2}{2}}Z_{}=c\mu {\displaystyle \frac{Z_{}}{\mu }}+aZ_{}.`$ (10)
The solution of Eq. (9) corresponds to a positive and normalizable PDF only when $`c<0`$, and the solution is a Gaussian. Its Laplace transform then gives the velocity probability density function

$`P(U)=\sqrt{{\displaystyle \frac{c}{\pi \kappa _0}}}\mathrm{exp}\left({\displaystyle \frac{cU^2}{\kappa _0}}\right),`$ (11)
where $`U=[u(x_1)+u(x_2)]/2`$. Since the point separation is much smaller than the force correlation length, $`P(U)`$ becomes the one-point probability density function of the velocity field. Strictly speaking, expression (11) is phenomenological, it is expected to match the velocity PDF only in the region $`UU_{rms}`$; for larger $`U`$ the velocity PDF may be not universal. We compare this result with the simulations in section 3.

Equation (10) is more complicated, but it can be simplified if we are looking for the solution in the scale-invariant form, $`Z_{}(\mu ,y)=\mathrm{\Phi }(x)`$, where $`x=\mu y`$,

$`x\mathrm{\Phi }^{\prime \prime }+(12b)\mathrm{\Phi }^{}{\displaystyle \frac{\kappa _2}{2}}x^2\mathrm{\Phi }=a\mathrm{\Phi }+cx{\displaystyle \frac{}{x}}\mathrm{\Phi }.`$ (12)
To rewrite this equation in the velocity space, let us Laplace transform the $`\mathrm{\Phi }`$ function,

$`\mathrm{\Phi }(x)={\displaystyle \underset{\mathrm{}}{\overset{+\mathrm{}}{}}}w(\stackrel{~}{z})\mathrm{exp}(x\stackrel{~}{z})𝑑\stackrel{~}{z},`$ (13)
The function $`w(\stackrel{~}{z})`$ is then related to the velocity-difference probability density function, $`W(\mathrm{\Delta }u,y)`$, as $`W(\mathrm{\Delta }u,y)=w(\mathrm{\Delta }u/y)/y`$. Equation for $`w`$ is readily obtained by substituting (13) into (12). Introducing the dimensionless variable $`z=\stackrel{~}{z}(\kappa _2/2)^{1/3}`$, we thus get

$`w^{\prime \prime }+z^2w^{}+(1+2b)zw=\stackrel{~}{a}w+\stackrel{~}{c}(zw)^{},`$ (14)
where the derivatives are with respect to $`z`$, and $`\stackrel{~}{a}=a(\kappa _2/2)^{1/3}`$ and $`\stackrel{~}{c}=c(\kappa _2/2)^{1/3}`$. Asymptotics of the solution at $`|z|\mathrm{}`$ can be found from Eq. (14),

$`w`$ $``$ $`z^{(2b1)}\mathrm{exp}(z^3/3+\stackrel{~}{c}z^2/2),z+\mathrm{},`$ (15)
$`w`$ $``$ $`|z|^{(2b+1)},z\mathrm{},`$ (16)
they have the form that we already discussed in the introduction.

Ideally, we should be able to derive all the anomalies $`a`$, $`b`$, and $`c`$ from our theory. At present we are not able to do this, so in the next section we turn to numerical simulations.

In general, the anomalies $`a`$, $`b`$ and $`c`$ should satisfy the requirement that Eq. (14) have positive and normalizable solution, and that the dissipation is non-positive, $`\stackrel{~}{a}w+2(b1)zw\stackrel{~}{c}(zw)^{}0`$ boldyrev . This eigenvalue problem thus has two-parameter family of solutions.

Note that the geometric approach of weinan ; weinan1 ; kraichnan1 ; bec ; frisch ; gurarie1 , proposed the asymptotic for negative velocity differences, $`w|z|^{7/2}`$. This condition is satisfied by $`b=5/4`$. This value was not allowed by the condition of non-positivity of the dissipation in the theory based on (4), but with the new expression for the anomaly (7) this value is admissible. For $`b=5/4`$, Eq, (14) can be solved numerically, leading to the approximate window of acceptable values, $`0.37\stackrel{~}{c}0.025`$, which turns out to be consistent with (11). We now find the values of the anomalies from numerical simulations of Eq. (1).

3. Numerical results. We perform numerical simulations of Eq. (1) in a periodic interval of length $`L=1`$ containing $`10^6`$ grid points. The used numerical scheme is the standard shock capturing, total variation diminishing (TVD) scheme with non-linear, limited solution reconstruction leveque . For non-linear, scalar equations the scheme is provably TV-stable, monotonicity preserving and second-order accurate in the $`L_p,p<\mathrm{}`$, norm. To resolve discontinuous solutions the scheme uses nonlinear numerical viscosity that appears only inside the shocks. This dissipation mechanism ensures that the shocks are restricted to 2-3 grid points.

The external force is generated as

$`f(x)={\displaystyle \underset{k=1}{\overset{m}{}}}A(k)\left[\xi _k\mathrm{sin}(2\pi kx)+\eta _k\mathrm{cos}(2\pi kx)\right],`$ (17)
where $`\xi _k`$ and $`\eta _k`$ are independent Gaussian random variables with mean $`0`$ and covariance $`1`$. The amplitude of the force is $`A(k)=k\left[\mathrm{exp}(k^2/n^2)/\tau \right]^{1/2}`$, where $`\tau `$ is the force renewal time; in our simulations we had $`\tau =10^5`$, while the integration time step was $`t_0=10^7`$. We used $`m=10`$, and performed a series of runs for $`n=5,10`$. In this paper we mainly present the results averaged over 5 independent runs with $`n=5`$, and with the integration time $`t=2`$ each.

We found that the one-point PDF can be best matched by the solution of Eq. (11), with the choice $`\stackrel{~}{c}=0.3`$. Formula (11) gives

$`P(U)=\sqrt{{\displaystyle \frac{0.3\kappa _2^{1/3}}{2^{1/3}\pi \kappa _0}}}\mathrm{exp}\left({\displaystyle \frac{0.3\kappa _2^{1/3}}{2^{1/3}\kappa _0}}U^2\right),`$ (18)
and Fig. (1) shows its good agreement with the simulations for both $`n=5`$ and $`n=10`$. As expected, the best agreement is seen in the top parts of the curves; the tails of the PDF seem to be non-universal.

Once the $`c`$ anomaly is given, we find the anomaly $`b`$ by matching the numerically obtained velocity-difference PDF with the solution of Eq. (14), see Fig. (2, 3). The best match to the whole PDF is given by $`b1.19`$ which is slightly less than the value $`b=5/4`$, predicted in weinan ; weinan1 ; kraichnan1 ; bec ; frisch ; gurarie1 , and leads to the left-tail exponent $`3.38`$. The solution of Eq. (14) with the value $`b=5/4`$ is less consistent with our simulations. Although the reason for this discrepancy is quite intriguing and is not clear to us, our numerical resolution is not high enough to distinguish between the two asymptotics, $`3.5`$ and $`3.38`$. Therefore, more extensive numerical work is required to understand this difference.

Once the anomalies $`c`$ and $`b`$ are found, the $`a`$ anomaly is obtained from the eigenvalue problem (14), which gives $`\stackrel{~}{a}0.65`$.

4 Conclusions. We have found that our analytical model (14) with parameters $`\stackrel{~}{a}0.65`$, $`b1.19`$, and $`\stackrel{~}{c}0.3`$ provides an excellent fit to the numerically obtained velocity and velocity-difference PDF’s of Burgers turbulence. As the important numerical check, one can directly find the form of the anomalies by numerically constructing conditional probabilities of shock amplitudes for given velocity gradients on the left and on the right of the shock weinan1 . We plan to address this question in the future with more extensive simulations.

We also believe that the method of dissipative anomalies can be generalized for turbulence with pressure and can be applicable in more than 1 dimension. We currently conduct the corresponding simulations, the results will be reported elswere. Practically, the Burgers model is expected to work for strongly compressible flows, i.e., in astrophysical application, such as supersonic turbulence in cold molecular clouds Weizsacker ; Brunt .

We thank Victor Yakhot for important discussions. The work of SB and TL was supported by the NSF Center for magnetic self-organization in laboratory and astrophysical plasmas at the University of Chicago. The research of AP was supported in part by the NSF grants PHY-9802484 and PHY-0243680.