format: text

text:
# 1. Introduction

## 1. Introduction

In recent years there has been significant interest in the study of longest increasing subsequences in random permutations. It is beyond the scope of this paper to survey the subject, but the connections are fascinating and relate to random matrix theory, Painleve functions, Riemann surfaces, point processes, Riemann Hilbert problems, and much else. Recent surveys include \[AD\] and \[De\].

By means of the Robinson-Schensted-Knuth (RSK) correspondence, the uniform measure on the symmetric group induces a measure (called the Plancherel measure) on integer partitions of the number $`n`$. We assume that the reader is familiar with these concepts; a very readable treatment is the survey \[AD\]. One of the more interesting aspects of the theory is that to analyze the Plancherel measure, one often analyzes a deformation of the Plancherel measure and then takes a limit in which the deformation approaches Plancherel measure. This approach is used, for instance, in \[J\]; see also the survey \[BO\].

Next let us recall the k-riffle shuffle measure on a deck of $`n`$ cards, defined in \[BDi\] as a generalization of the Gilbert-Shannon-Reeds model of the way real people shuffle cards. For an integer $`k1`$, this shuffle may be described as follows. Given a deck of $`n`$ cards, one cuts it into $`k`$ piles with probability of pile sizes $`j_1,\mathrm{},j_k`$ given by $`\frac{\left(\genfrac{}{}{0pt}{}{n}{j_1,\mathrm{},j_k}\right)}{k^n}`$. Then cards are dropped from the packets with probability proportional to the pile size at a given time. Thus if the current pile sizes are $`A_1,\mathrm{},A_k`$, the next card is dropped from pile $`i`$ with probability $`A_i/(A_1+\mathrm{}+A_k)`$. Let $`d(\pi )`$ be the number of descents of $`\pi `$ (i.e. the number of $`i`$ with $`1in1`$ such that $`\pi (i)>\pi (i+1)`$). There is a simple formula for the chance that a $`k`$-shuffle gives the inverse of a permutation $`\pi `$ in terms of $`d(\pi )`$. Denoting this probability by $`R_{k,n}(\pi )`$, it is proved in \[BDi\] that

$$R_{k,n}(\pi )=\frac{\left(\genfrac{}{}{0pt}{}{n+kd(\pi )1}{n}\right)}{k^n}.$$

One immediate observation is that as $`k\mathrm{}`$, the measure $`R_{k,n}`$ converges to the uniform distribution. In fact, much more is true. The paper \[BDi\] establishes the following equation in the group algebra of the symmetric group, for any integers $`k_1,k_21`$:

$$\left(\underset{\pi S_n}{}R_{k_1,n}(\pi )\pi \right)\left(\underset{\pi S_n}{}R_{k_2,n}(\pi )\pi \right)=\left(\underset{\pi S_n}{}R_{k_1k_2,n}(\pi )\pi \right).$$

Thus the riffle shuffle measure $`R_{k,n}`$ is closed under iteration, in the sense that a $`k_1`$ shuffle followed by a $`k_2`$ shuffle is equal to a $`k_1k_2`$ shuffle. So iterating a $`2`$-shuffle $`k`$ times is equivalent to performing a single $`2^k`$ shuffle, and one can study properties of iterates of riffle shuffles using the explicit formula for $`R_{k,n}`$.

To make this quantitative, one often uses the total variation distance $`P_1P_2`$ between two probability distributions $`P_1`$ and $`P_2`$ on a finite set $`X`$. It is defined as

$$\frac{1}{2}\underset{xX}{}|P_1(x)P_2(x)|.$$

One reason that this is a useful method of quantifying the distance between two distributions is that the total variation distance between probability distributions $`P_1,P_2`$ can also be defined as

$$max_{SX}|P_1(S)P_2(S)|.$$

Thus when the total variation distance is small, any event has nearly the same probability under the measures $`P_1,P_2`$. Aldous \[A\] showed that for large $`n`$, $`\frac{3}{2}log_2(n)`$ 2-riffle shuffles are necessary and suffice to randomize a deck of $`n`$ cards. This was sharpened by Bayer and Diaconis \[BDi\] who showed that (for any $`n`$), if $`k=\frac{3}{2}\mathrm{log}_2n+c`$ and $`U_n`$ denotes the uniform distribution on $`S_n`$, then $`R_{2^k,n}U_n`$ is

$$12\mathrm{\Phi }\left(\frac{2^c}{4\sqrt{3}}\right)+0\left(\frac{1}{n^{1/4}}\right)\text{where}\mathrm{\Phi }(x)=\frac{1}{\sqrt{2\pi }}_{\mathrm{}}^xe^{t^2/2}𝑑t.$$

This marvelous result (sometimes loosely stated as $`\frac{3}{2}log_2(n)`$ iterations of a 2-riffle shuffle are necessary and suffice for randomness) is also quite powerful. As a consequence of the Bayer/Diaconis result, it follows that after $`\frac{3}{2}log_2(n)`$ iterations of a 2-riffle shuffle, the distribution of the longest increasing subsequence is close to that of a random permutation.

The reader might at this point wonder what card shuffling has to do with deformations of the Plancherel measure of the symmetric group. The point is a result of Stanley \[S\] that the the distribution of the longest increasing subsequence (or more generally the RSK shape) under the measure $`R_{k,n}`$ is equal to the distribution of the longest weakly increasing subsequence in a random length $`n`$ word on $`k`$ letters. In fact Johansson’s proof (\[J\]) of the Baik-Deift-Johansson theorem used discrete orthogonal polynomial ensembles to analyze the longest weakly increasing subsequence in random length $`n`$ words on $`k`$ letters, and then let $`k\mathrm{}`$. As observed in \[Fu4\], Johansson’s work implies that iterating a 2-riffle shuffle $`\frac{5}{6}log_2(n)`$ times brings the distribution of the longest increasing subsequence close to that of a random permutation. Note that this is sharper than the $`\frac{3}{2}log_2(n)`$ bound of the previous paragraph. Section 2 of this paper briefly summarizes these developments, giving precise statements and pointers to the literature.

Given the above discussion, it is very natural to study deformations of Plancherel measure given by applying the RSK correspondence to other shuffles which are closed under iteration. The first question is: which shuffles are the most natural? The series of papers \[Fu1\],\[Fu2\],\[Fu3\] used Lie theory to define a number of methods of shuffling which are closed under iteration and mathematically very natural. The paper \[Fu4\] showed that many, but not all, of these shuffles interact nicely with RSK correspondence and with Toeplitz determinants. This paper aims to analyze deformations of Plancherel measure arising from shuffles which on one hand are very natural, but whose interaction with the RSK correspondence is at the present writing unclear (essentially because the interaction of the cyclic descent set of a permutation with the RSK correspondence is unclear).

The first shuffle we analyze can be physically described as cutting the deck at a uniformly chosen random position and then performing a k-riffle shuffle. This shuffle was first studied in the paper \[Fu2\], although throughout that paper we incorrectly called it a shuffle followed by a cut instead of a cut followed by a shuffle; shuffles followed by cuts had been studied in \[BDi\]. In any case, the measure defined in \[Fu2\] is that which picks a permutation $`\pi `$ on n-symbols with probability

$$C_{k,n}(\pi )=\frac{\left(\genfrac{}{}{0pt}{}{n+kcd(\pi )1}{n1}\right)}{nk^{n1}},$$

where $`cd(\pi )`$ is defined as follows. A permutation $`\pi `$ on $`n`$ symbols is said to have a cyclic descent at position $`n`$ if $`\pi (n)>\pi (1)`$. Then $`cd(\pi )`$ is defined as $`d(\pi )`$ if $`\pi `$ has no cyclic descent at $`n`$ and as $`d(\pi )+1`$ if $`\pi `$ has a cyclic descent at $`n`$. Thus $`C_{k,n}(\pi )`$ is the chance of obtaining $`\pi ^1`$ after applying a cut and then a k-riffle shuffle. This probability measure shares many of the truly remarkable properties of the measure $`R_{k,n}`$. For example, the measure $`C_{k,n}`$, like the measure $`R_{k,n}`$, has the property that one can exactly understand its distribution on conjugacy classes, even though $`C_{k,n}`$ is not constant on conjugacy classes. Another property which is more relevant to the current discussion is that

$$\left(\underset{wS_n}{}C_{k_1,n}(w)w\right)\left(\underset{wS_n}{}C_{k_2,n}(w)w\right)=\left(\underset{wS_n}{}C_{k_1k_2,n}(w)w\right).$$

In words, if one iterates the process “cut and then perform a k-riffle shuffle”, one obtains exactly the same result as from first performing a cut and then iterating the k-riffle shuffles. Thus only the initial cut contributes to the randomness. It follows that $`\frac{3}{2}log_2(n)`$ iterations of cut and then $`2`$-riffle shuffle are necessary and suffice to get close to randomness (see \[Fu2\] for details). In particular, the longest increasing subsequence must be random after $`\frac{3}{2}log_2(n)`$ iterations.

In fact since $`C_{k,n}`$ is the convolution of $`R_{k,n}`$ with the probability measure corresponding to cutting the deck at a random position, we have for free that $`C_{k,n}U_nR_{k,n}U_n`$. Indeed, if $`P,Q`$ are any measures whatsoever on the symmetric group, then the chance that $`P`$ followed by $`Q`$ yields a permutation $`\pi `$ is $`_\tau Q(\pi \tau ^1)P(\tau )`$, and it is easy to see that

$$\frac{1}{2}\underset{\pi }{}|\underset{\tau }{}Q(\pi \tau ^1)P(\tau )\frac{1}{n!}|QU_n$$

and

$$\frac{1}{2}\underset{\pi }{}|\underset{\tau }{}Q(\pi \tau ^1)P(\tau )\frac{1}{n!}|PU_n.$$

But although the measure $`C_{k,n}`$ is closer to the uniform distribution than the measure $`R_{k,n}`$, it does not follow that any statistic is more random under the measure $`C_{k,n}`$ than under the measure $`R_{k,n}`$. For example let $`\pi `$ be a permutation on 3 symbols which has two cyclic descents but only 1 descent (for instance the permutation transposing symbols 1 and 2). Then $`C_{k,3}`$ assigns probability $`\frac{1}{6}\frac{1}{6k}`$ to $`\pi `$, but the measure $`R_{k,3}`$ assigns probability $`\frac{1}{6}\frac{1}{6k^2}`$ to $`\pi `$. Thus if $`S`$ is the event “being equal to the transposition (12)”, $`|C_{k,3}(S)U_3(S)||R_{k,3}(S)U_3(S)|`$. So although it is probably true, we do not know that $`\frac{5}{6}log_2(n)`$ iterations of a cut followed by a $`2`$ riffle shuffle suffice to randomize the longest increasing subsequence.

A main result of this paper is to derive sharp bounds on the total variation distance $`C_{k,n}R_{k,n}`$. A wonderful simplification occurs and the absolute values signs in the definition of total variation distance evaporate and exact generating functions can be used (this does not happen, for example, in the Bayer/Diaconis analysis of $`R_{k,n}U_n`$, where some serious effort is required). We conclude that whereas both a 2-riffle shuffle and a cut followed by a 2-riffle shuffle take $`\frac{3}{2}log_2(n)`$ steps to converge to the uniform distribution, only $`log_2(n)`$ steps are necessary for them to converge to each other. As a corollary, since

$$C_{k,n}U_nC_{k,n}R_{k,n}+R_{k,n}U_n$$

we obtain that for a cut followed by a 2-riffle shuffle, $`log_2(n)`$ steps suffice to bring the distribution of the longest increasing subsequence close to that of a random permutation. This is a significant improvement to the $`\frac{3}{2}log_2(n)`$ bound from two paragraphs ago. And even if it turns out that one can get sharper bounds for the longest increasing subsequence under the measure $`C_{k,n}`$ by other methods, our method is applicable to other statistics as well. For instance since a cut followed by a riffle shuffle makes the position of any particular card perfectly random, we recover a recent result of \[U\] stating that $`log_2(n)`$ steps suffice for a $`2`$-riffle shuffle to randomize any particular card.

The final section of this paper treats another variation of riffle shuffles called type $`A`$ affine k-shuffles \[Fu2\],\[Fu3\]. These are also closed under iteration, and the chance $`A_{k,n}(\pi )`$ of a permutation depends both on the number of cyclic descents and the major index of the permutation. It is proved that $`log_2(n)`$ steps suffice to bring a type $`A`$ affine 2-shuffle and a cut followed by a 2-riffle shuffle close to each other. This implies that $`\frac{3}{2}log_2(n)`$ steps are necessary and suffice for convergence of a type $`A`$ affine 2-shuffles to the uniform distribution, and that the longest increasing subsequence converges is close to that of a random permutation in at most $`log_2(n)`$ steps.

The precise organization of this paper is as follows. Section 2 very briefly reviews connections between riffle shuffles, longest increasing subsequences, and random matrices; some of these will be needed for this paper. Section 3 derives an exact expression for $`C_{k,n}R_{k,n}`$. Then it analyzes the formula and records some corollaries. Section 4 treats the measure $`A_{k,n}`$, proving similar results.

## 2. Shuffling and Subsequences

This section very briefly recalls a few connections between shuffling, increasing subsequences, and random matrices. All of this material is known but perhaps not collected in one place, and we shall need some of it.

Let $`L(\pi )`$ denote the length of the longest increasing subsequence of a permutation chosen uniformly at random from the symmetric group on $`n`$ symbols. The Tracy-Widom distribution $`F(t)`$ is defined as

$$F(t)=exp\left(_t^{\mathrm{}}(xt)u^2(x)𝑑x\right)$$

where $`u(x)`$ is the solution of the Painleve II equation $`u_{xx}=2u^3+xu`$ such that $`u`$ is asymptotic to the negative of the Airy function as $`x\mathrm{}`$. The Baik-Deift-Johansson theorem (\[BDeJ\]), states that

$$lim_n\mathrm{}Prob\left(\frac{L2\sqrt{N}}{N^{1/6}}t\right)=F(t)$$

for all $`tR`$.

Johansson \[J\] later proved this using discrete orthogonal polynomial ensembles. He viewed the Poissonized Plancherel measure (the term Poissonized refers to the fact that the number of symbols $`n`$ is a Poisson random variable) as a limiting case of the Charlier ensemble, and showed that the Charlier ensemble could be exactly analyzed. The Charlier ensemble converges to the Poissonized Plancherel measure because random length $`n`$ words on $`k`$ symbols converge to random permutations on $`n`$ symbols as $`k\mathrm{}`$, and the Charlier ensemble is essentially what arises when applying the RSK to random words. Stanley \[S\] observed that the distribution of the longest weakly increasing subsequence in a random length $`n`$ word on $`k`$ symbols has exactly the same distribution as the longest increasing subsequence in a random permutation after a $`k`$-riffle shuffle. This is simple to see. For example when $`k=2`$, given a word on the symbols $`1,2`$ such as

$$\mathrm{1\; 2\; 1\; 1\; 2\; 1\; 1\; 2\; 1}$$

one obtains a shuffle of the stacks $`1,2,3,4,5,6`$ and $`7,8,9`$ by putting the numbers in the first stack in the positions of the ones (going from left to right), then putting then numbers in the second stack in the position of the twos, and so on. In this example the permutation which emerges is

$$\mathrm{1\; 7\; 2\; 3\; 8\; 4\; 5\; 9\; 6}.$$

Clearly a weakly increasing subsequence in the word corresponds to an increasing subsequence in the permutation associated to the word. Thus the study of longest increasing subsequences in random words (and hence the Charlier ensemble) is really the study of the RSK shape obtained after a permutation distributed as a riffle shuffle.

In fact Johansson \[J\] used orthogonal polynomial ensembles to prove that if $`L(w)`$ denotes the length of the longest weakly increasing subsequence in a random length $`n`$ word on $`k`$ symbols, and if $`n,k\mathrm{}`$ in such a way that $`(log(n))^{1/6}/k0`$, then

$$lim_n\mathrm{}Prob\left(\frac{L(w)\frac{n}{k}2\sqrt{n}}{\left(1+\frac{\sqrt{n}}{k}\right)^{2/3}n^{1/6}}t\right)=F(t)$$

where as above $`F(t)`$ is the Tracy-Widom distribution. The paper \[Fu4\] translated this into card-shuffling language by noting that if $`k=e^cn^{5/6}`$, then

$$lim_n\mathrm{}Prob\left(\frac{L(w)2\sqrt{n}}{n^{1/6}}t\right)=F(te^c).$$

Thus $`\frac{5}{6}log_2(n)`$ 2-riffle shuffles are necessary and suffice to bring the longest increasing subsequence close to that of a random permutation.

We remark that there are connections with random matrices. First, it is known that the Tracy-Widom distribution is the limit distribution for the largest eigenvalue of a random GUE (Gaussian Unitary Ensemble) matrix \[TW1\]. Moreover, the random word problem (or equivalently riffle shuffling) is related both to the ensemble of traceless GUE matrices and to the Laguerre ensemble (see Theorems 3 and 4 of \[TW2\], \[K\] and the references in these papers for details).

## 3. Shuffles with Cuts

Throughout this section, we adhere to the notation in the introduction. Thus $`d(\pi )`$ and $`cd(\pi )`$ denote the number of descents and cyclic descents of a permutation. We also freely use the explicit formulas for $`R_{k,n}`$ and $`C_{k,n}`$ mentioned in the introduction.

Although we will not use it in this paper, we record the following observation.

###### Proposition 3.1.

A k-riffle shuffle followed by a cut and a cut followed by a k-riffle shuffle induce the same measure on conjugacy classes.

###### Proof.

Let $`\zeta `$ denote the cycle $`(12\mathrm{}n1)`$. Let $`s_k`$ be defined as the element of the group algebra of $`S_n`$ equal to $`_{\pi S_n}R_{k,n}(\pi ^1)\pi `$. Then a k-riffle shuffle followed by a cut is given by $`s_k\left(\frac{1}{n}_{j=1}^n\zeta ^j\right)`$ and a cut followed by a k-riffle shuffle is given by $`\left(\frac{1}{n}_{j=1}^n\zeta ^j\right)s_k`$. But it is straightforward to see that if $`g`$ is any element of the group algebra of the symmetric group, then $`g\left(_{j=1}^n\zeta ^j\right)`$ and $`\left(_{j=1}^n\zeta ^j\right)g`$ induce the same measure on conjugacy classes. Indeed, $`g\zeta ^j`$ is conjugate to $`\zeta ^{nj}g`$. ∎

In what follows, we let $`A_{n,d}`$ denote the number of permutations on $`n`$ symbols with $`d1`$ descents. Lemma 3.2 collects known properties of Eulerian numbers; see for example \[FoS\]. Part 3 is called Worpitzky’s identity and is equivalent to the fact that $`R_{k,n}`$ is a probability measure.

###### Lemma 3.2.

Let $`A_{n,d}`$ denote the number of permutations on $`n`$ symbols with $`d1`$ descents.

1. $$A_{n,d}=A_{n,n+1d}.$$
2. $$\underset{\pi S_n}{}\frac{t^{d(\pi )+1}}{(1t)^{n+1}}=\underset{k0}{}k^nt^k.$$
3. $$k^n=\underset{1jn}{}A_{n,j}\left(\genfrac{}{}{0pt}{}{k+nj}{n}\right).$$

###### Lemma 3.3.

For $`n>1`$, the number of permutations on $`n`$ symbols with $`d`$ cyclic descents and $`d1`$ descents is $`dA_{n1,d}`$, and the number of permutations on $`n`$ symbols with $`d`$ cyclic descents and $`d`$ descents is $`(nd)A_{n1},d`$.

###### Proof.

It is proved in \[Fu2\] that for $`n>1`$, the number of permutations on $`n`$ symbols with $`d`$ cyclic descents is equal to $`nA_{n1,d}`$. Now any the set of permutations on n symbols with $`d`$ cyclic descents falls into equivalence classes under the operation of cyclic shifts. For example the permutation $`13524`$ is a member of a set of 5 permutations

$$13524,35241,52413,24135,41352.$$

The number of cyclic descents is constant among this class, but clearly the proportion of members of this class with $`d1`$ descents is $`\frac{d}{n}`$ and the proportion of members of this class with $`d`$ descents is $`\frac{nd}{n}`$. ∎

Theorem 3.4 gives three expressions for the total variation distance between the measures $`R_{k,n}`$ and $`C_{k,n}`$. It is rather remarkable that such a simple formula (i.e. one not involving absolute values) exists. We remark that for the purpose of an upper bound, only the first equality in Theorem 3.4 is used. The third equality is useful for lower bounds and involves $`B_n`$, the nth Bernoulli number. They are defined by the generating function $`_{n0}\frac{B_nz^n}{n!}=\frac{z}{e^z1}`$, so that $`B_0=1,B_1=\frac{1}{2},B_2=\frac{1}{6},B_3=0,B_4=\frac{1}{30}`$ and $`B_i=0`$ if $`i3`$ is odd. Also $`(n)_t`$ denotes $`n(n1)\mathrm{}(nt+1)`$.

###### Theorem 3.4.

$`R_{k,n}C_{k,n}`$ $`=`$ $`{\displaystyle \frac{1}{k^nn}}{\displaystyle \underset{j=1}{\overset{n1}{}}}j(nj)A_{n1,j}\left({\displaystyle \genfrac{}{}{0pt}{}{n+kj1}{n1}}\right)`$
$`=`$ $`{\displaystyle \frac{1}{k^n}}\left(k^n{\displaystyle \frac{k^{n+1}}{n}}+(n+1){\displaystyle \underset{s=1}{\overset{k1}{}}}s^nk(n1){\displaystyle \underset{s=1}{\overset{k1}{}}}s^{n1}\right)`$
$`=`$ $`\left({\displaystyle \underset{t=1}{\overset{n2}{}}}{\displaystyle \frac{B_{t+1}}{k^t}}\left({\displaystyle \frac{(n)_t}{t!}}+{\displaystyle \frac{(n1)_t}{(t+1)!}}\right)\right)+{\displaystyle \frac{(n+1)B_n}{k^{n1}}}.`$
###### Proof.

To compute $`R_{k,n}C_{k,n}`$, note that for any permutation $`\pi `$, either $`cd(\pi )=d(\pi )+1`$ or $`cd(\pi )=d(\pi )`$. If $`cd(\pi )=d(\pi )+1`$, then by the explicit formulas for $`R_{k,n}`$ and $`C_{k,n}`$ in the introduction, it follows that

$`|R_{k,n}(\pi )C_{k,n}(\pi )|`$ $`=`$ $`|{\displaystyle \frac{1}{k^n}}\left({\displaystyle \genfrac{}{}{0pt}{}{n+kd1}{n}}\right){\displaystyle \frac{1}{nk^{n1}}}\left({\displaystyle \genfrac{}{}{0pt}{}{n+kd2}{n1}}\right)|`$
$`=`$ $`|{\displaystyle \frac{(nd1)(n+kd2)!}{k^nn!(kd1)!}}|`$
$`=`$ $`{\displaystyle \frac{(nd1)(n+kd2)!}{k^nn!(kd1)!}}.`$
Similarly if $`cd(\pi )=d(\pi )`$, it follows that

$`|R_{k,n}(\pi )C_{k,n}(\pi )|`$ $`=`$ $`|{\displaystyle \frac{1}{k^n}}\left({\displaystyle \genfrac{}{}{0pt}{}{n+kd1}{n}}\right){\displaystyle \frac{1}{nk^{n1}}}\left({\displaystyle \genfrac{}{}{0pt}{}{n+kd1}{n1}}\right)|`$
$`=`$ $`|{\displaystyle \frac{d(n+kd1)!}{k^nn!(kd)!}}|`$
$`=`$ $`{\displaystyle \frac{d(n+kd1)!}{k^nn!(kd)!}}.`$
Letting $`j`$ index the number of cyclic descents, we conclude from Lemma 3.3 that

$`R_{k,n}C_{k,n}`$
$`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{j=1}{\overset{n1}{}}}jA_{n1,j}{\displaystyle \frac{(nj)(n+kj1)!}{k^nn!(kj)!}}`$
$`+(nj)A_{n1,j}{\displaystyle \frac{j(n+kj1)!}{k^nn!(kj)!}}`$
$`=`$ $`{\displaystyle \frac{1}{k^nn}}{\displaystyle \underset{j=1}{\overset{n1}{}}}j(nj)A_{n1,j}\left({\displaystyle \genfrac{}{}{0pt}{}{n+kj1}{n1}}\right).`$
This proves the first equality of the theorem.

For the second equality of the theorem, consider the expression for $`R_{k,n}C_{k,n}`$ given in the first equality of the theorem. We use the first part as follows. We break it into two terms as

$$\frac{1}{k^n}\underset{j=1}{\overset{n1}{}}jA_{n1,j}\left(\genfrac{}{}{0pt}{}{n+kj1}{n1}\right)\frac{1}{nk^n}\underset{j=1}{\overset{n1}{}}j^2A_{n1,j}\left(\genfrac{}{}{0pt}{}{n+kj1}{n1}\right).$$

To analyze the first term, we begin with part 3 of Lemma 3.2 (Worpitzky’s identity):

$$\underset{j=1}{\overset{n1}{}}\frac{t^jA_{n1,j}}{(1t)^n}=\underset{k=0}{\overset{\mathrm{}}{}}k^{n1}t^k.$$

Thus

$$\underset{j=1}{\overset{n1}{}}t^jA_{n1,j}=(1t)^n\underset{k=0}{\overset{\mathrm{}}{}}k^{n1}t^k.$$

Differentiate both sides with respect to $`t`$. One obtains the equality

$$\underset{j=1}{\overset{n1}{}}jt^{j1}A_{n1,j}=n(1t)^{n1}\underset{k=0}{\overset{\mathrm{}}{}}k^{n1}t^k+(1t)^n\underset{k=0}{\overset{\mathrm{}}{}}k^nt^{k1}.$$

Dividing both sides by $`(1t)^n`$ gives

$$\underset{j=1}{\overset{n1}{}}\frac{jt^{j1}A_{n1,j}}{(1t)^n}=\frac{n}{1t}\underset{k=0}{\overset{\mathrm{}}{}}k^{n1}t^k+\underset{k=0}{\overset{\mathrm{}}{}}k^nt^{k1}.$$

Taking the coefficient of $`t^{k1}`$ on both sides now gives the equation

$$\underset{j=1}{\overset{n1}{}}jA_{n1,j}\left(\genfrac{}{}{0pt}{}{n+kj1}{n1}\right)=k^nn\underset{s=0}{\overset{k1}{}}s^{n1}.$$

Next consider the term

$$\frac{1}{nk^n}\underset{j=1}{\overset{n1}{}}j^2A_{n1,j}\left(\genfrac{}{}{0pt}{}{n+kj1}{n1}\right).$$

Recall from the previous paragraph that

$$\underset{j=1}{\overset{n1}{}}\frac{jt^{j1}A_{n1,j}}{n}=(1t)^{n1}\underset{k=0}{\overset{\mathrm{}}{}}k^{n1}t^k+\frac{(1t)^n}{n}\underset{k=0}{\overset{\mathrm{}}{}}k^nt^{k1}.$$

Multiplying both sides by $`t`$ and differentiating yields the equation

$`{\displaystyle \underset{j=1}{\overset{n1}{}}}{\displaystyle \frac{j^2t^{j1}A_{n1,j}}{n}}`$
$`=`$ $`(1t)^{n1}{\displaystyle \underset{k0}{}}(k+1)k^{n1}t^k+(n1)(1t)^{n2}{\displaystyle \underset{k0}{}}k^{n1}t^{k+1}`$
$`(1t)^{n1}{\displaystyle \underset{k0}{}}k^nt^k+{\displaystyle \frac{(1t)^n}{n}}{\displaystyle \underset{k0}{}}k^{n+1}t^{k1}.`$
Dividing both sides by $`(1t)^n`$ and then taking the coefficient of $`t^{k1}`$ one obtains that

$`{\displaystyle \frac{1}{nk^n}}{\displaystyle \underset{j=1}{\overset{n1}{}}}j^2A_{n1,j}\left({\displaystyle \genfrac{}{}{0pt}{}{n+kj1}{n1}}\right)`$
$`=`$ $`{\displaystyle \frac{k^{n+1}}{n}}(n+1){\displaystyle \underset{s=1}{\overset{k2}{}}}s^n2(k1)^n{\displaystyle \underset{s=1}{\overset{k1}{}}}s^{n1}`$
$`+(n1)(k1){\displaystyle \underset{s=1}{\overset{k2}{}}}s^{n1}.`$
This simplifies to the expression in the second part of the theorem.

The third expression follows from the second expression by the expansion of partial power sums in \[GR\]:

$$\underset{r=0}{\overset{a1}{}}r^n=\frac{a^n}{n+1}\left(a+\underset{t=0}{\overset{n1}{}}\frac{B_{t+1}(n+1)_{t+1}}{(t+1)!a^t}\right).$$

Theorem 3.6 will give upper and lower bounds on the total variation distance between $`R_{k,n}`$ and $`C_{k,n}`$, and implies that $`log_2(n)+c`$ iterations of a cut followed by a 2-riffle shuffle are necessary and sufficient for randomness. For the lower bound we will use the following elementary lemma about Bernoulli numbers.

###### Lemma 3.5.

For $`t1`$ an integer, the function $`\frac{(1)^{t1}B_{2t}}{(2t1)!}`$ is a positive, decreasing function of $`t`$.

###### Proof.

It is well known that $`\frac{B_{2t}}{(2t)!}=\frac{(1)^{t1}2\zeta (2t)}{(2\pi )^{2t}}`$ where $`\zeta `$ is the Riemann zeta function. The result now follows from the fact that the Riemann zeta function is decreasing in $`t`$ together with the inequality $`(2\pi )^2\frac{t+1}{t}`$ for $`t1`$. ∎

###### Theorem 3.6.

1. $$R_{k,n}C_{k,n}.25\frac{n}{k}.$$

In particular, for $`k\frac{ne^{c_0}}{4}`$, the total variation distance is at most $`e^{c_0}`$.
2. $$R_{k,n}C_{k,n}.24\frac{n1}{k}+\frac{(n+1)B_n}{k^{n1}}$$

for $`kn`$. The term $`\frac{(n+1)B_n}{k^{n1}}`$ goes to $`0`$ as $`n\mathrm{}`$ (again for $`kn`$).

###### Proof.

For this upper bound, we use the first equality of Theorem 3.4. Together with the fact that $`j(nj)\frac{n^2}{4}`$ for $`1jn1`$, it follows that

$$R_{k,n}C_{k,n}\frac{n}{4k^n}\underset{j=1}{\overset{n1}{}}A_{n1,j}\left(\genfrac{}{}{0pt}{}{n+kj1}{n1}\right).$$

By part 3 of Lemma 3.2, this is $`\frac{n}{4k}`$.

For the lower bound, we use the third equality of Theorem 3.4, and suppose throughout that $`kn`$. Then by Lemma 3.5

$$\underset{t=1}{\overset{n2}{}}\frac{B_{t+1}(n)_t}{t!k^t}$$

is (after disregarding the terms corresponding to even $`t`$ which all vanish) an alternating sum whose terms decrease in magnitude, so is at least $`\frac{n}{k}(B_2+\frac{B_4}{3!}).16\frac{n}{k}`$. Similarly one sees that

$$\underset{t=1}{\overset{n2}{}}\frac{B_{t+1}(n1)_t}{(t+1)!k^t}\frac{n1}{k}(\frac{B_2}{2}+\frac{B_4}{4!}).08\frac{n1}{k}.$$

The assertion about the term involving $`B_n`$ follows from the well known asymptotics (\[Od\]) $`B_{2t}(1)^t4\sqrt{\pi n}\left(\frac{n}{\pi e}\right)^{2n}`$, so that for $`kn`$ this term is extremely small. ∎

Next we record three corollaries of Theorem 3.6. Corollary 3.7 relates to the distribution of the longest increasing subsequence.

###### Corollary 3.7.

$`log_2(n)+c`$ iterations of a cut followed by a 2-riffle shuffle are sufficient to bring the distribution of the longest increasing subsequence close to that of a random permutation.

###### Proof.

This is immediate from Theorem 3.6 and the fact (see the discussion in Section 2 of this paper), that $`\frac{5}{6}log_2(n)`$ iterations of a 2-riffle shuffle are sufficient to bring the distribution of the longest increasing subsequence close to that of a random permutation. ∎

Corollary 3.8 pertains to the numbers of descents.

###### Corollary 3.8.

$`\frac{3}{2}log_2(n)+c`$ iterations of a cut followed by a 2-riffle shuffle are necessary and sufficient to randomize the number of descents of a permutation.

###### Proof.

It is known \[BDi\] that $`\frac{3}{2}log_2(n)+c`$ iterations of a 2-riffle shuffle are necessary and sufficient to random the number of descents of a permutation. The result now follows from Theorem 3.6. ∎

Corollaries 3.7 and 3.8 applied Theorem 3.6 to deduce information about the measure $`C_{k,n}`$ using information about the measure $`R_{k,n}`$. Corollary 3.9 gives an example where Theorem 3.6 is used to deduce information about the measure $`R_{k,n}`$ from information about the measure $`C_{k,n}`$. In fact the result of Corollary 3.9 is known \[U\], by an entirely different method of proof.

###### Corollary 3.9.

$`log_2(n)+c`$ iterations of a 2-riffle shuffle are sufficient to randomize the position of any single card.

###### Proof.

Under the measure $`C_{k,n}`$, the position of any card is perfectly random. The result follows from Theorem 3.6. ∎

## 4. Affine Shuffles

This section considers a measure $`A_{k,n}`$ on the symmetric group known as the affine k-shuffle measure. It was introduced in \[Fu2\] and studied further in \[Fu3\]. As above, let $`cd(\pi )`$ be the number of cyclic descents of $`\pi `$. Let $`maj(\pi )`$ be the major index of $`\pi `$ (i.e. the sum of the values $`i`$ with $`1in1`$ such that $`\pi (i)>\pi (i+1)`$). Let $`C_r(m)`$ denote the Ramanujan sum $`_{\genfrac{}{}{0pt}{}{1lr}{gcd(l,r)=1}}e^{2\pi ilm/r}`$. Then the measure $`A_{k,n}`$ assigns mass

$$\begin{array}{cc}\frac{1}{nk^{n1}}_{r|n,kcd(\pi )}\left(\genfrac{}{}{0pt}{}{\frac{n+kcd(\pi )r}{r}}{\frac{nr}{r}}\right)C_r(maj(\pi ))\hfill & \text{if }kcd(\pi )>0\hfill \\ \frac{1}{k^{n1}}\hfill & \text{if }k=cd(\pi ),n|maj(\pi )\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}$$

Note that the $`r=1`$ term in this formula is the measure $`C_{k,n}`$, suggesting that $`A_{k,n}`$ and $`C_{k,n}`$ should be quite close.

When $`k=2`$ and the deck size $`2n`$ is even, the inverse of an affine shuffle has a physical description: choose an even number $`2j`$ between $`1`$ and $`2n`$ with the probability of getting $`2j`$ equal to $`\frac{\left(\genfrac{}{}{0pt}{}{2n}{2j}\right)}{2^{2n1}}`$. From the stack of $`2n`$ cards, form a second pile of size $`2j`$ by removing the top $`j`$ cards of the stack and putting the bottom $`j`$ cards of the first stack on top of them; then riffle the two stacks (of size $`2n2j`$ and $`2j`$) together as in ordinary riffle shuffles. One of the main results of this section is that as for ordinary riffle shuffles, $`\frac{3}{2}log_2(n)+c`$ iterations of an affine 2-shuffle are necessary and sufficient for randomness.

The probability measure $`A_{k,n}`$ has many remarkable properties. First, it satisfies the equation

$$\left(\underset{\pi S_n}{}A_{k_1,n}(\pi )\pi \right)\left(\underset{\pi S_n}{}A_{k_2,n}(\pi )\pi \right)=\left(\underset{\pi S_n}{}A_{k_1k_2,n}(\pi )\pi \right).$$

Second, one can understand in a very precise way the distribution of this measure on conjugacy classes, even though the measure $`A_{k,n}`$ is not constant on conjugacy classes. See \[Fu2\],\[Fu3\] for details.

Theorem 4.1 gives an upper bound on the total variation distance $`A_{k,n}C_{k,n}`$, which is sufficient for our purposes.

###### Theorem 4.1.

$`A_{k,n}C_{k,n}<n\left(\frac{2n}{ek}\right)^{n/2}`$ for $`kn`$.

###### Proof.

Since $`kn`$ and $`cd(\pi )n1`$, clearly $`kcd(\pi )>0`$ for all $`\pi `$. From the explicit formulas for $`A_{k,n}`$ and $`C_{k,n}`$ mentioned in this paper, it follows that

$$A_{k,n}C_{k,n}=\frac{1}{2nk^{n1}}\underset{\pi }{}|\underset{\genfrac{}{}{0pt}{}{r|n,kcd(\pi )}{r>1}}{}\left(\genfrac{}{}{0pt}{}{\frac{n+kcd(\pi )}{r}1}{\frac{n}{r}1}\right)C_r(maj(\pi ))|.$$

Using the fact that there are $`n!`$ permutation on $`n`$ symbols and the bound $`|C_r|\varphi (r)`$ where $`\varphi `$ is Euler’s $`\varphi `$ function of elementary number theory, this is at most

$$\frac{n!}{2nk^{n1}}\underset{\genfrac{}{}{0pt}{}{r|n}{r>1}}{}\left(\genfrac{}{}{0pt}{}{\frac{n+k}{r}}{\frac{n}{r}1}\right)\varphi (r).$$

Since $`kn`$,

$$\left(\genfrac{}{}{0pt}{}{\frac{n+k}{r}}{\frac{n}{r}1}\right)\frac{(\frac{n+k}{r})^{\frac{n}{r}1}}{(\frac{n}{r}1)!}\frac{(\frac{2k}{r})^{\frac{n}{r}1}}{(\frac{n}{r}1)!}=\frac{n}{2k}\frac{(\frac{2k}{r})^{\frac{n}{r}}}{(\frac{n}{r})!}.$$

Since $`r2`$ and $`kn`$, this is less than $`\frac{nk^{n/2}}{2k(n/2)!}`$. Thus

$$A_{k,n}C_{k,n}\frac{n!}{4k^{n/2}(\frac{n}{2})!}\underset{r|n,r>1}{}\varphi (r).$$

Using the fact that $`_{r|n}\varphi (r)=n`$, together with the Stirling formula bounds proved in \[Fe\]

$$n!<(2\pi )^{1/2}n^{n+1/2}e^{n+1/(12n)}$$

$$(n/2)!>(2\pi )^{1/2}(n/2)^{n/2+1/2}e^{n/2+1/(6n+1)},$$

it follows that

$$A_{k,n}C_{k,n}n\left(\frac{2n}{ek}\right)^{n/2}.$$

Corollary 4.2 is immediate from Theorem 4.1 and the corresponding results for the measure $`C_{k,n}`$ in Section 3.

###### Corollary 4.2.

1. $`\frac{3}{2}log_2(n)+c`$ affine 2 shuffles are necessary and suffice for randomness.
2. $`log_2(n)+c`$ iterations of an affine 2 shuffle suffice to bring the longest increasing subsequence close to that of a random permutation.
3. $`\frac{3}{2}log_2(n)+c`$ iterations of an affine 2 shuffle are necessary and sufficient to randomize the number of descents of a permutation.
4. $`log_2(n)+c`$ iterations of an affine 2 shuffle are sufficient to randomize the position of any single card.

## 5. Acknowledgements

The author was support by NSA Grant MDA904-03-1-0049. We thank Ira Gessel for discussions.


text:
# Representation theorem for obsevables on a quantum logic

## 1 Introduction

The idea that quantum probabilities are nothing other than conditional probabilities was intesively discussed from various points of views, see, e.g., . Recently this approach to quantum probability was generalized in the so called contextual framework . In the latter approach we consider conditioning with respect to various contexts, complexes of experimental physical conditions and not conditioning of one event, $`a,`$ with respect to other event, $`b,`$ under the same context (state) as it was done in investigations on conditional probabilities (compare with Kolmogorov , , Renyi , Cox , or quantum logic generalizations , see also ).

In the present paper we still use the traditional event-conditioning (under the fixed conditional state). However, we essentially generalize the notion of a conditional state (here we continue investigations ).

We will study a conditional state on a quantum logic using Renyi’s approach (or Bayesian principle). This approach helps us to define independence of events and differently from the situation in the classical theory of probability, if an event $`a`$ is independent of an event $`b`$, then the event $`b`$ can be dependent on the event $`a`$ (problem of causality) (, ). We will show that we can define a $`s`$-map (function for simultaneous measurements on a quantum logic). It can be shown that if we have the conditional state we can define the $`s`$-map and conversely. By using the $`s`$-map we can introduce joint distribution also for noncompatible observables on a quantum logic. Moreover, if $`x`$ is an obsevable on $`L`$ and $`B`$ is Boolean sub-algebra of $`L`$, we can construct an observable $`z=Exp(x|B)`$, which is a version of conditional expectation of $`x`$ but it need not to be necessarily compatible with $`x`$.

1. A conditional state on a quantum logic

In this part we introduce the notions as a quantum logic, a state, a conditional state and their basic properties.

###### Definition 1. 1

Let $`L`$ be a nonempty set endowed with a partial ordering $``$. Let there exists the greatest element ($`1`$) and the smallest element ($`0`$). Let there be defined the operations supremum $`()`$, infimum $``$ (the lattice operations ) and a map $`:LL`$ with the following properties:

* For any $`\{a_n\}_{n𝒜}L`$, where $`𝒜𝒩`$ are finite

$$\underset{n𝒜}{}a_n,\underset{n𝒜}{}a_nL.$$
* For any $`aL`$ $`(a^{})^{}=a`$.
* If $`aL`$, then $`aa^{}=1`$.
* If $`a,bL`$ such that $`ab`$, then $`b^{}a^{}`$.
* If $`a,bL`$ such that $`ab`$ then $`b=a(a^{}b)`$ (orthomodular law).

Then $`(L,0,1,,,)`$ is called the quantum logic (briefly q.l.).

Let $`L`$ be q.l.. Then elements $`a,bL`$ will be called:

* orthogonal ($`ab`$) iff $`ab^{}`$;
* compatible ($`ab`$) iff there exist mutually orthogonal elements $`a_1,b_1,cL`$ such that

$$a=a_1c\text{ and }b=b_1c.$$

If $`a_iL`$ for any $`i=1,2,3,\mathrm{}`$ and $`bL`$ is such, that $`ba_i`$ for all $`i`$, then $`b_{i=1}^na_i`$ and

$$b(\underset{i=1}{\overset{\mathrm{}}{}}a_i)=\underset{i=1}{\overset{\mathrm{}}{}}(a_ib)$$

(,,).

A subset $`L_0L`$ is a sub-logic of $`L`$  if for any $`aL_0`$ we have $`a^{}L_0`$ and for any $`a,bL_0`$ $`abL_0`$.

###### Definition 1. 2

A map $`m:L[0,\mathrm{})`$ such that

* $`m(0)=0`$ and $`m(1)=1`$.
* If $`ab`$ then $`m(ab)=m(a)+m(b)`$

is called a state on $`L`$. If we have orthomodular $`\sigma `$-lattice and $`m`$ is $`\sigma `$-additive function, then $`m`$ will be called a $`\sigma `$-state.

###### Definition 1. 3

 Let $`L`$ be a quantum logic. A subset $`L_cL\{0\}`$ is called a conditional system (CS) in $`L`$ ($`\sigma `$-CS in $`L`$ )if the following conditions hold:

* If $`a,bL_c`$, then $`abL_c`$. (If $`a_nL_c`$, for $`n=1,2,\mathrm{}`$, then $`_na_nL_c`$.)
* If $`a,bL_c`$ and $`a<b`$, then $`a^{}bL_c`$.

Let $`AL`$. Then $`L_c(A)`$ is the smallest CS ($`\sigma `$-CS ), which contains the set $`A`$.

###### Definition 1. 4

 Let $`L`$ be a quantum logic and $`L_c`$ be an $`\sigma `$-CS in $`L`$. Let $`f:L\times L_c[0,1]`$. If the function $`f`$ fulfill the following conditions:

* for each $`aL_0`$ $`f(.,a)`$ is a state on $`L`$;
* for each $`aL_0`$ $`f(a,a)=1`$;
* if $`\{a_n\}_{n𝒜}L_0`$, where $`𝒜𝒩`$ and $`a_n`$ are mutually orthogonal, then for each $`bL`$

$$f(b,\underset{n𝒜}{}a_n)=\underset{n𝒜}{}f(a_n,\underset{n𝒜}{}a_n)f(b,a_n);$$

then it is called conditional state.

###### Proposition 1. 1

 Let $`L`$ be a q.l.. Let $`\{a_i\}_{i=1}^nL`$, $`nN`$ where $`a_ia_j`$ for $`ij`$. If for any $`i`$ there exists a state $`\alpha _i`$, such that $`\alpha _i(a_i)=1`$, then there exists $`\sigma `$-CS such that for any $`𝐤=(k_1,k_2,\mathrm{},k_n)`$, where $`k_i[0;1]`$ for $`i\{1,2,\mathrm{},n\}`$ with the property $`_{i=1}^nk_i=1`$, there exists a conditional state

$$f_𝐤:L\times L_c[0;1],$$

such that

1. for any $`i`$ and each $`dL`$ $`f_𝐤(d,a_i)=\alpha _i(d);`$
2. for each $`a_i`$

$$f_𝐤(a_i,\underset{i=1}{\overset{n}{}}a_i)=k_i;$$

###### Definition 1. 5

 Let $`L`$ be a quantum logic and $`f`$ be a conditional state. Let $`bL`$, $`a,cL_c`$ such that $`f(c,a)=1`$. Then $`b`$ is independent of $`a`$ with respect to the state $`f(.,c)`$ ($`b_{f(.,c)}a`$) if $`f(b,c)=f(b,a)`$.

The classical definition of independency of a probability space $`(\mathrm{\Omega },,𝒫)`$ is a special case of this definition, because

$`P(A|B)=P(A|\mathrm{\Omega })`$ if and only if $`P(AB|\mathrm{\Omega })=P(A|\mathrm{\Omega })P(B|\mathrm{\Omega })`$.

If $`L_c`$ be CS and $`f:L\times L_c[0,1]`$ is a conditional state, then ( )

* Let $`a^{},a,cL_c`$, $`bL`$ and $`f(c,a)=f(c,a^{})=1`$. Then $`b_{f(.,c)}a`$ if and only if $`b_{f(.,c)}a^{}`$.
* Let $`a,cL_c`$, $`bL`$ and $`f(c,a)=1`$. Then $`b_{f(.,c)}a`$ if and only if $`b^{}_{f(.,c)}a`$.
* Let $`a,c,bL_c`$, $`ba`$ and $`f(c,a)=f(c,b)=1`$. Then $`b_{f(.,c)}a`$ if and only if $`a_{f(.,c)}b`$.

2. Observables and s-map

Let $`L`$ be a quantum logics. Let us denote $`L^2=L\times L`$.

###### Definition 2. 1

Let $`L`$ be a quantum logic. The map $`p:L^2[0,1]`$ will be called s-map if the following conditions hold:

* $`p(1,1)=1`$;
* if there exists $`iN`$ $`ab`$, then $`p(a,b)=0`$;
* if $`ab`$, then for any $`cL`$,

$$p(ab,c)=p(a,c)+p(b,c)$$

$$p(c,ab)=p(c,a)+p(c,b)$$

.

###### Proposition 2. 1

Let $`L`$ be a q.l. and let $`p`$ be a s-map. Let $`a,b,cL`$, then

* if $`ab`$ , then $`p(a,b)=p(ab,ab)=p(b,a)`$;
* if $`ab`$, then $`p(a,b)=p(a,a)`$;
* if $`ab`$, then $`p(a,c)p(b,c)`$;
* $`p(a,b)p(b,b)`$;
* if $`\nu (b)=p(b,b)`$, then $`\nu `$ is a state on $`L`$.

###### Proposition 2. 2

Let $`L`$ be a q.l., let there be a s-map $`p`$. Then there exists a conditional state $`f_p`$, such that

$$p(a,b)=f_p(a,b)f_p(a,1).$$

Let $`L`$ be a q.l. and let $`L_c=L\{0\}`$. If $`f:L\times L_c[0,1]`$ is a conditional state, then there exists a s-map $`p_f:L\times L[0,1]`$.

###### Proposition 2. 3

Let $`L`$ be a quantum logic.

* If $`f`$ is a conditional state, then $`b_{f(.,1)}a`$ iff $`p_f(b,a)=p_f(a,a)p_f(b,b)`$, where $`p_f`$ is the s-map generated by $`f`$.
* Let $`p`$ be a s-map. Then $`b_{f_p(.,1)}a`$ iff $`p(b,a)=p(a,a)p(b,b)`$, where $`f_p`$ is the conditional state generated by the s-map $`p`$.

Let $`()`$ be $`\sigma `$-algebra of Borel sets. A $`\sigma `$-homomorphism $`x:()`$ is called an observable on $`L`$. If $`x`$ is an observable, then $`R(x):=\{x(E);E()\}`$ is called range of the observable $`x`$. It is clear that $`R(x)`$ is Boolean $`\sigma `$-algebra . A spectrum of an observable $`x`$ is defined by the following way: $`\sigma (x)=\{E();`$ $`x(E)=1\}.`$ If $`g`$ is a real function, then $`gx`$ is such observable on $`L`$ that:

* $`R(gx)R(x)`$;
* $`\sigma (gx)=\{g(t);t\sigma (x)\}`$;
* for any $`E()`$

$`gx(E)=x(\{t\sigma (x);g(t)E\})`$.

We say that $`x`$ and $`y`$ are compatible ($`xy`$) if there exist a Boolean sub-$`\sigma `$-algebra $`L`$ such that $`R(x)R(y)`$. In other words $`xy`$ if for any $`E,F()`$ $`x(E)y(F)`$.

We call an observable $`x`$ a discrete if $`\sigma (x)`$ is a countable set. It means, that $`\sigma (x)=\{t_i\}_{i𝒜}`$, where $`𝒜`$$`\{1,2,\mathrm{}\}`$. Let us denote $`𝒪`$ the set of all discrete observables on $`L`$.

###### Definition 2. 2

Let $`L`$ be a $`\sigma `$-quantum logic and $`p:L\times L[0;1]`$ be a s-map. Let $`x,y`$ be some observables on $`L`$. Then a map $`p_{x,y}:()\times ()`$ $`[0,1]`$, such that

$$p_{x,y}(E,F)=p(x(E),y(F)),$$

is called a joint distribution for the observables $`x`$ and $`y`$ for the $`s`$-map $`p`$..

If $`x`$ is an observable on $`L`$ and $`m`$ is a state on $`L`$, then $`m_x(E)=m(x(E))`$, $`E()`$ is a probability distribution for $`x`$ and

$$m(x)=_R\lambda m_x(d\lambda )$$

is called the expectation of $`x`$ in the state $`m`$, if the integral on the right side exists. From this follows that for $`x𝒪`$

$$m(x)=\underset{t\sigma (x)}{}tm(x(\{t\}))$$

and for any real function $`g`$ we have

$$m(gx):=\underset{t\sigma (x)}{}g(t)m(x(\{t\})).$$

###### Definition 2. 3

Let $`L`$ be a $`\sigma `$-quantum logic and $`p:L\times L[0;1]`$ be a s-map. Let $`x,y𝒪`$. Then

$$p(x,y)=\underset{x_i\sigma (x)}{}\underset{y_j\sigma (y)}{}x_iy_jp(x(\{x_i\}),y(\{y_j\})),$$

is called the first joint moment for the observables $`x,y`$.

From the previous definition follows that

$$p(x,x)=\underset{x_i\sigma (x)}{}x_i^2p(x(\{x_i\}),x(\{x_i\}))=\underset{x_i\sigma (x)}{}x_i^2\nu (x(\{x_i\})):=\nu (gx),$$

where $`g(t)=t^2`$.

Anallogicaly to the classical theory of probability we can define notions for example as covariance ($`c(.,.)`$), variance ($`var(.)`$) and correlation coeficient ($`r(.,.)`$) by the following way:

$$c(x,y):=p(x,y)\nu (x)\nu (y),$$

$$var(x):=c(x,x),$$

$$r(x,y)=\frac{c(x,y)}{\sqrt{var(x).var(y)}}.$$

In spite of the classical theory of probability in this case $`c(x,y)`$ is not equal to $`c(y,x)`$ in generali.

###### Proposition 2. 4

Let $`L`$ be a quantum logic, $`p`$ be a s-map on $`L`$ and $`𝒪`$ be a set of all discrete observables on $`L`$. For each $`x,y𝒪`$ there exist $`(\mathrm{\Omega }_i,`$$`𝒮`$$`{}_{i}{}^{},P_i)`$ ($`i=1,2`$) probability spaces and random variables $`\xi _i,\eta _i`$ ($`i=1,2`$), which are $`𝒮`$i-measurable such that:

* $`c(x,y)=cov(\xi _1,\eta _1)`$, $`c(y,x)=cov(\eta _2,\xi _2)`$;
* $`E_i(\xi _i)=\nu (x)`$ and $`E_i(\eta _i)=\nu (y)`$, $`i=1,2`$;
* $`(c(x,y))^2c(x,x)c(y,y)`$.

Proof. If $`x,y𝒪`$, then $`\sigma (x)=\{x_k\}_{k𝒜}`$, $`\sigma (y)=\{y_j\}_{j𝒟}`$, where $`𝒜`$,$`𝒟`$ $`N`$. Let us denote $`\mathrm{\Omega }_1=\{(x_k,y_j);k𝒜`$ , $`j𝒟`$$`\}`$, $`\mathrm{\Omega }_2=\{(y_j,x_k);k𝒜`$ , $`j𝒟`$$`\}`$ and $`𝒮`$$`{}_{i}{}^{}=2^{\mathrm{\Omega }_i}`$, $`i=1,2`$. Then $`(\mathrm{\Omega }_i,𝒮`$$`{}_{i}{}^{})`$ is the measurable space.

If $`p`$ is a s-map, then from the properties of $`p`$ follows, that $`P_1=p_{x,y}`$ is the probability measure on $`(\mathrm{\Omega }_1,𝒮`$$`{}_{1}{}^{})`$ and $`P_2=p_{y,x}`$ is the probability measure on the measurable space $`(\mathrm{\Omega }_2,𝒮`$$`{}_{2}{}^{})`$. From this

$$E_i(\xi _i)=\underset{k}{}x_kP_i(\xi _1=x_k)=\nu (x).$$

Anallogicaly we get

$$E_i(\eta _i)=\nu (y).$$

(b) Let us denote

$$\xi _1((x_k,y_j))=x_k,\eta _1((x_k,y_j))=y_j,$$

$$\xi _2((y_j,x_k))=x_k,\eta _2((y_j,x_k))=y_j.$$

It is clear, that

$$P_1(\{\omega \mathrm{\Omega }_1;\xi _1(\omega )=x_k\})=P_1\{(x_k,y_j);j𝒟\}$$

From this follows, that

$$P_1(\{\omega \mathrm{\Omega }_1;\xi _1(\omega )=x_k\})=p(x(\{x_k\}),y(\sigma (y)))=p(x(\{x_k\},1)=\nu (x(\{x_k\})).$$

Anallogicaly from this follows, that

$$P_i(\xi _i=x_k)=\nu (x(\{x_k\})$$

and

$$P_i(\eta _i=y_j)=\nu (y(\{y_j\}))$$

(a) From the theory of probability follows, that

$$var(\xi _1,\eta _1)=\underset{k}{}\underset{j}{}(x_k\nu (x))(y_j\nu (y))P_1(\xi _1=x_k,\eta _1=y_j))$$

Let us denote $`a_k=x(\{x_k\})`$ and $`b_j=y(\{y_j\})`$. Then

$$cov(\xi _1,\eta _1)=\underset{k}{}(x_k\nu (x))(y_j\nu (y))p(a_k,b_j)$$

and

$$cov(\xi _2,\eta _2)=\underset{k}{}(x_k\nu (x))(y_j\nu (y))p(b_j,a_k).$$

Because

$$\underset{k,j}{}p(a_k,b_j)=\underset{k,j}{}p(b_j,a_k)=1,$$

$$\underset{k}{}p(a_k,b_j)=\underset{k}{}p(b_j,a_k)=\nu (b_j)$$

and

$$\underset{j}{}p(a_k,b_j)=\underset{j}{}p(b_j,a_k)=\nu (a_k)$$

we have

$$\underset{k}{}(x_k\nu (x))(y_j\nu (y))p(b_j,a_k)=p(x,y)\nu (x)\nu (y)=c(x,y).$$

Anallogically

$$var(\xi _2,\eta _2)=p(y,x)\nu (x)\nu (y)=c(y,x).$$

(c) Because $`(cov(\xi _i,\eta _i))^2cov(\xi _i,\xi _i)cov(\eta _i,\eta _i)`$ and $`cov(\xi _i,\xi _i)=c(x,x)`$, $`cov(\eta _i,\eta _i)=c(y,y)`$ we have

$$(c(x,y))^2c(x,x)c(y,y),$$

$$(c(y,x))^2c(x,x)c(y,y).$$

(Q.E.D.)

###### Proposition 2. 5

Let $`L`$ be a quantum logic and $`𝒪`$ be the set of all discrete observables on $`L`$. Let $`x,y𝒪`$. Then

* $`c(x,y)=p(g_xx,g_yy)`$, where $`g_z`$ is a real function such that $`g_z(t)=t\nu (z)`$, for $`z𝒪`$, ;
* $`r(x,y)[1,1]`$;
* if $`xy`$, then $`c(x,y)=c(y,x)`$ and $`r(x,y)=r(y,x)`$.

Proof. Let $`x,y𝒪`$. Then $`\sigma (x)=\{x_i\}_{i𝒜}`$ and $`\sigma (y)=\{y_j\}_j`$, where $`𝒜,`$ are countabte sets of indexes.

(i) From the definition $`g_xx,g_yy`$ we have

$$\begin{array}{cccc}p(g_xx,g_yy)& =_{x_i\sigma (x)}_{y_j\sigma (y)}g_x(x_i)g_y(y_j)p(x(x_i),y(y_j))\hfill & & \\ & =_{x_i\sigma (x)}_{y_j\sigma (y)}(x_i\nu (x))(y_j\nu (y))p(x(x_i),y(y_j))\hfill & & \\ & =_{x_i\sigma (x)}_{y_j\sigma (y)}x_iy_jp(x(x_i),y(y_j))\hfill & & \\ & _{x_i\sigma (x)}_{y_j\sigma (y)}\nu (x)\nu (y)p(x(x_i),y(y_j))\hfill & & \\ & =p(x,y)\nu (x)\nu (y)=c(x,y).\hfill & & \end{array}$$

(ii) From the previous proposition we know that there exist two probability spaces $`(\mathrm{\Omega }_k,_k,P_k)`$ and random variables $`\xi _k,\eta _k`$, $`k=1,2`$ such that $`c(x,y)=cov(\xi _1,\eta _1)`$ and $`c(x,y)=cov(\xi _2,\eta _2)`$. Moreover $`c(x,x)=cov(\xi _k,\xi _k)=var(\xi _k)`$. Anallogicaly $`c(y,y)=cov(\eta _k,\eta _k)=var(\eta _k)`$. Then

$$r(x,y)=\frac{c(x,y)}{\sqrt{c(x,x)c(y,y)}}=\frac{cov(\xi _1,\eta _1)}{\sqrt{var(\xi _1)var(\eta _1)}}=\rho (\xi _1,\eta _1)=\rho _1$$

and

$$r(y,x)=\frac{c(y,x)}{\sqrt{c(x,x)c(y,y)}}=\frac{cov(\xi _2,\eta _2)}{\sqrt{var(\xi _2)var(\eta _2)}}=\rho (\xi _2,\eta _2)=\rho _2.$$

becuase $`\rho _k`$ is correlation coeficient on the probability space $`(\mathrm{\Omega }_k,_k,P_k)`$, then $`\rho _k[1,1]`$ for for $`k=1,2`$. From this follows that $`r(x,y),r(y,x)[1,1]`$. Also this fact follows immidiately from the Proposition 2.4 (c).

(iii) Let $`xy`$. Then for each $`x_i\sigma (x)`$ and each for $`y_j\sigma (y)`$ we have

$$p(x(x_i),y(y_j))=p(y(y_j),x(x_i))$$

and so

$$\begin{array}{cccc}p(x,y)& =_{x_i\sigma (x)}_{y_j\sigma (y)}x_iy_jp(x(x_i),y(y_j))\hfill & & \\ & =_{x_i\sigma (x)}_{y_j\sigma (y)}x_iy_jp(y(y_j),x(x_i))\hfill & & \\ & =p(y,x).\hfill & & \end{array}$$

From this follows that

$$c(x,y)=c(y,x).$$

(Q.E.D.)

###### Example 2. 1

. Let $`L=\{a,a^{},b,b^{},0,1\}`$. Let $`cd=1`$ if $`cd`$ and $`c,dL\{0\}`$. Let $`cd=0`$ if $`cd`$ and $`c,dL\{1\}`$. Let $`(d^{})^{}=d`$ for $`dL`$ and $`1^{}=0`$. It is clear that $`L`$ is a quantum logic and $`B_d=\{d,d^{},0,1\}`$, $`d\{a,b\}`$ is Booelan algebra. Let $`f(s,t)`$ is defined by the following way:

| $`s/t`$ | $`a`$ | $`a^{}`$ | $`b`$ | $`b^{}`$ | $`1`$ |
| --- | --- | --- | --- | --- | --- |
| $`a`$ | $`1`$ | $`0`$ | $`0.4`$ | $`0.4`$ | $`0.4`$ |
| $`a^{}`$ | $`0`$ | $`1`$ | $`0.6`$ | $`0.6`$ | $`0.6`$ |
| $`b`$ | $`0.2`$ | $`11/30`$ | $`1`$ | $`0`$ | $`0.3`$ |
| $`b^{}`$ | $`0.8`$ | $`19/30`$ | $`0`$ | $`1`$ | $`0.7`$ |

From $`f`$ this we can compute $`p_f(s,t)`$ . Then we get:

| $`s/t`$ | $`a`$ | $`a^{}`$ | $`b`$ | $`b^{}`$ |
| --- | --- | --- | --- | --- |
| $`a`$ | $`0.4`$ | $`0`$ | $`0.12`$ | $`0.28`$ |
| $`a^{}`$ | $`0`$ | $`0.6`$ | $`0.18`$ | $`0.42`$ |
| $`b`$ | $`0.08`$ | $`0.22`$ | $`0.3`$ | $`0`$ |
| $`b^{}`$ | $`0.32`$ | $`0.38`$ | $`0`$ | $`0.7`$ |

We can see that $`p_f(a,b)=p_f(a,a)p_f(b,b)`$, but $`p_f(b,a)p_f(b,b)p_f(a,a)`$. In the following we will write $`p_f=p`$. Let $`x,y`$ be observales on $`L`$ such that $`R(x)=\{a,a^{},0,1\}=B_a`$, and $`R(y)=\{b,b^{},0,1\}=B_b`$. It is easy to see, that $`x`$ is not compatible with $`y`$. Let, for example,

$$x(1)=ax(1)=a^{}$$

$$y(0)=by(5)=b^{}.$$

In the following tables we have the joint distributions $`p_{x,y}`$ and $`p_{y,x}`$.

| $`p_{x,y}`$ | $`0`$ | $`5`$ |
| --- | --- | --- |
| $`1`$ | $`0.12`$ | $`0.28`$ |
| $`1`$ | $`0.18`$ | $`0.42`$ |

$`p_{y,x}`$ $`1`$ $`1`$  $`0`$ $`0.08`$ $`0.22`$  $`5`$ $`0.32`$ $`0.38`$
Now we can compute the following characteristics:

$$\nu (x)=1\times 0.4+0.2\times 0.6=0.2,$$

$$\nu (y)=0\times 0.3+5\times 0.7=3.5,$$

$$p(x,y)=5\times 0.28+5\times 0.42=0.7,$$

$$p(y,x)=5\times 0.32+5\times 0.38=0.3,$$

$$c(x,y)=p(x,y)\nu (x)\nu (y)=0.70.2\times 3.5=0,$$

$$c(y,x)=p(y,x)\nu (x)\nu (y)=0.30.2\times 3.5=0.4,$$

$$c(x,x)=0.96c(y,y)=5.25,$$

$$r(x,y)=0r(y,x)0.178.$$

In the end we can write these results to ”the covariance matrix”:

$$\left(\begin{array}{cc}c(x,x)& c(x,y)\\ c(y,x)& c(y,y)\end{array}\right)=\left(\begin{array}{cc}0.96& 0\\ 0.178& 5.25\end{array}\right)$$

We see that ”the covariance matrix” need not to be symmetry. In the classical theory of probability, where we suppose that all random variables are compatible, have to be symmetry.

###### Example 2. 2

. Let $`L`$ the same quantum logic as in the Example 2.1. Let $`p(s,t)`$ is defined by the following way:

| $`s/t`$ | $`a`$ | $`a^{}`$ | $`b`$ | $`b^{}`$ |
| --- | --- | --- | --- | --- |
| $`a`$ | $`0.4`$ | $`0`$ | $`0.08`$ | $`0.38`$ |
| $`a^{}`$ | $`0`$ | $`0.6`$ | $`0.22`$ | $`0.32`$ |
| $`b`$ | $`0.08`$ | $`0.22`$ | $`0.3`$ | $`0`$ |
| $`b^{}`$ | $`0.32`$ | $`0.38`$ | $`0`$ | $`0.7`$ |

Let $`x,y`$ be observables on $`L`$ such that $`R(x)=\{a,a^{},0,1\}`$, and $`R(y)=\{b,b^{},0,1\}`$. It is easy to see, that $`x`$ is not compatible with $`y`$. Let, for example,

$$x(1)=ax(1)=a^{}$$

$$y(0)=by(5)=b^{}.$$

In this case $`p_{x,y}=p_{y,x}`$.

| $`p_{x,y}`$ | $`0`$ | $`5`$ |
| --- | --- | --- |
| $`1`$ | $`0.08`$ | $`0.38`$ |
| $`1`$ | $`0.22`$ | $`0.32`$ |

Now we get

$$\nu (x)=0.2,\nu (y)=3.5,$$

$$p(x,y)=p(y,x)=0.3,c(x,y)=c(y,x)=0.4,$$

$$c(x,x)=0.96,c(y,y)=5.25,$$

$$r(x,y)=r(y,x)0.178.$$

In the end we can write these results to the covariance matrix:

$$\left(\begin{array}{cc}c(x,x)& c(x,y)\\ c(y,x)& c(y,y)\end{array}\right)=\left(\begin{array}{cc}0.96& 0.178\\ 0.178& 5.25\end{array}\right)$$

We see that the covariance matrix is symmetry as in the classical theory of probability, but $`x,y`$ are not compatible.

In the end we can say that we cannot prove that two observables are compatible by using statistics but we can prove that they are not compatible.


text:
# Is the Giant Radio Galaxy M 87 a TeV Gamma-Ray Emitter?

## 1 Introduction

Active Galactic Nuclei (AGN) are believed to contain as a central “engine” a supermassive black hole which causes the development of large scale jets. Extragalactic TeV $`\gamma `$-ray emission has been observed so far from AGN only of the BL Lac type, i. e. objects ejecting matter in a jet oriented very close to the observer’s line of sight. In BL Lacs, TeV photons are commonly believed to originate in the relativistic jets, most popularly due to inverse Compton scattering. The well studied objects Mkn 421 (redshift $`z=`$ 0.030) and Mkn 501 ($`z=`$ 0.034) belong to this type of TeV $`\gamma `$-ray emitters. Recently, the BL Lac type objects 1ES 1959+650 ($`z=`$ 0.047) (Nishiyama et al. (1999); Aharonian et al. 2003b ) and the much more distant H 1426+428 ($`z`$ = 0.129) (Horan et al. (2002); Aharonian et al. 2002a ) have also been established as TeV $`\gamma `$-ray emitters. However, other types of AGN, e. g. giant radio galaxies, also show relativistic mass outflows, though, in contrast to BL Lac type objects, under large viewing angles. Amongst these the nearby radio galaxy M 87 has been speculated to be a powerful accelerator of cosmic rays (including the highest energy particles observed in the universe, see e. g. Ginzburg & Syrovatskii (1964); Biermann et al. (2000)). M 87 has been targeted with the HEGRA Cherenkov telescopes as one of the prime candidates for TeV $`\gamma `$-ray emission from this class of objects.

The elliptical galaxy M 87 (right ascension $`\alpha _{\text{J2000.0}}`$ : $`12^{\text{hr}}30^\text{m}`$49.4$`^\text{s}`$, declination $`\delta _{\text{J2000.0}}`$ : $`+12^{}23^{}28^{\prime \prime }`$, redshift $`z=0.00436`$) has an optical extension of $`8.3^{}\times 6.6^{}`$ (Ma et al. (1998)) with a large radio halo of $`16^{}\times 12^{}`$ (Cameron (1971)). M 87 contains a supermassive black hole with a mass $`M_{\text{BH}}2\text{}3\times 10^9\text{M}_{}`$ (Harms et al. (1994)). The power of the non-thermal jet is estimated to be as high as a few $`10^{44}\text{erg\hspace{0.17em}s}^1`$ (Owen et al. 2000a ). The angle of the M 87 jet axis to the line of sight was determined to be $`30^{}`$$`35^{}`$ (Bicknell & Begelman (1996)). M 87 is located in the central region of the Virgo cluster of galaxies, which itself is another interesting site for particle acceleration (e. g. Völk et al. (1996)).

The VERITAS collaboration has targeted M 87 with the Whipple 10 m Cherenkov telescope in the years 2000 and 2001 for a total time of 14 h. Positive excesses have been observed at low significances of 1.6 $`\sigma `$ (2000) and 0.9 $`\sigma `$ (2001) leading to a 3 $`\sigma `$ upper limit of $`N_\gamma (E>250\text{GeV})<2.2\times 10^{11}`$ phot. cm-2s-1 (Lebohec et al. (2001)).

The HEGRA collaboration has extensively observed M 87 in 1998 and 1999 with the stereoscopic system of 5 imaging atmospheric Cherenkov telescopes (IACT system, Daum et al. (1997)). About half of the total observation time (44.1 h out of 83.4 h) has been used in an earlier analysis (Götting et al. (2001)). No evidence for TeV emission was found in this dataset and a 3 $`\sigma `$ upper limit on the TeV $`\gamma `$-ray flux from M 87 was determined to be $`N_\gamma (E>720\text{GeV})<1.45\times 10^{12}`$ phot. cm-2s-1.

In this Letter the results of the whole data set of the extensive HEGRA M 87 observations during the years 1998 and 1999 are reported, now also applying a more sensitive analysis method. Astrophysical conclusions concerning the nature of the observed excess are briefly discussed.

## 2 Observations and results of analysis

M 87 was observed in the years 1998 and 1999 with the HEGRA IACT system for a total of 83.4 h. There were no further observations of M 87 with the HEGRA telescopes in the subsequent years. The major part of the M 87 data was taken with a 4-telescope setup. Table 1 specifies the observation times and mean zenith angles of the individual HEGRA observation periods. The mean zenith angle of 21.6 can be converted into a mean energy threshold (defined as the peak detection rate for $`\gamma `$-showers) of 730 GeV for a Crab-like spectrum (Konopelko et al. (1999)).

Only data of good quality were considered for the analysis, the most critical condition being the IACT system’s cosmic ray background trigger rate not deviating more than 30 % from the rate expected for the current zenith angle. A total of about 5 % of the data was rejected due to this selection.

All observations of M 87 were carried out in the so-called wobble mode targeting the object’s position (“ON”) as given in Section 1 shifted by $`\pm `$0.5 in declination with respect to the center of the field of view. This observation mode allows for simultaneous estimation of the background (“OFF”) rate induced by charged cosmic rays (Aharonian et al. (1997)). The analysis uses an extended OFF-region reducing the statistical error on the number of background events. A ring segment is chosen with 260 opening angle at the same radial distance to the center of the field of view as for the ON-source position (see also Aharonian et al. (2002b)). The width of the ring is set to the diameter of the ON-source area in order to provide the same angular acceptance for ON- resp. OFF-source events. This ring segment background model is similar to the usage of a set of control regions (Aharonian et al. (2001)), but provides a smaller ratio of ON- to OFF-source solid angle areas ($`\alpha =\mathrm{\Omega }_{\text{ON}}/\mathrm{\Omega }_{\text{OFF}}`$) and thus reduces the statistical error on the number of estimated background events. For a consistency check (and for a search for $`\gamma `$-ray sources in the field of view, see below) the so-called template background model has also been used (Rowell (2003), see also Aharonian et al. (2002c)).

For the image analysis, the mirror reflectivities and photocathode efficiencies – which degrade slowly with time – along with the factors converting from digitized photomultiplier signals to photoelectrons have been determined on a monthly basis. The shower reconstruction and the event selection cuts have already been described in previous publications (e. g. Aharonian et al. (1999)). The stereo air shower direction reconstruction algorithm #3 (Hofmann et al. (1999)) and a “tight shape cut” (parameter mscw $`<1.1`$) (Konopelko et al. (1999)) for an effective $`\gamma `$-hadron separation have been applied leading to a sensitivity gain as compared to the earlier analysis of the HEGRA M 87 observations. The optimum angular cut was derived using $`\gamma `$-ray events from the Crab nebula on the basis of a nearly contemporaneous data set at similar zenith angles. Table 2 summarizes the event selection cuts, the resulting event numbers and significances for the data set as derived using the ring segment and template background models.

Figure 1 shows the event distribution both for the ON-source and the OFF-source regions as a function of the squared angular distance of the reconstructed shower direction to the source position after applying all event selection cuts. The statistical significance of the observed excess from the direction of M 87 (at the reference coordinates given in Section 1) is 4.1 $`\sigma `$, calculated using formula (17) from Li & Ma (1983). On the basis of the limited event statistics the excess is compatible with a point-like source for the HEGRA IACT system at the position of M 87, although extended emission cannot be excluded. After background subtraction the mscw values show a Gaussian distribution around the value of 1.0 as expected for a $`\gamma `$-ray population (see Konopelko et al. (1999)). This test supports the hypothesis that the measured excess is a result of M 87 being a true TeV $`\gamma `$-ray source. Applying different statistical tests in order to search for burstlike behaviour of M 87 no evidence for flux variations in the TeV energy range has been found.

The event distribution in the field of view was used to determine the center of gravity position (CoG) of the TeV $`\gamma `$-ray excess at $`\alpha _{\text{J2000.0}}=12^{\text{hr}}30^\text{m}54.4^\text{s}\pm 6.9_{\text{stat}}^\text{s}\pm 1.7_{\text{syst}}^\text{s}`$, $`\delta _{\text{J2000.0}}=12^{}24^{}17^{\prime \prime }\pm 1.7_{\text{stat}}^{}\pm 0.4_{\text{syst}}^{}`$ as shown in Figure 2. The accuracy of the CoG determination is limited by a systematic pointing error of about 25 ′′ (Pühlhofer et al. (1997)). Within the large errors, the CoG is consistent with the M 87 position, although a small shift of the source position cannot be ruled out. Therefore, it is not possible to localize a candidate TeV $`\gamma `$-ray production site to particlular inner radio structures of M 87.

In order to search for TeV $`\gamma `$-ray sources in the relatively large field of view of the HEGRA IACT system (and for a consistency check with the ring segment background model), the template background model was used for a further analysis of the M 87 data. A $`2^{}\times 2^{}`$ skymap of excess events determined for this sky region is shown in Figure 3. The excess from the direction of M 87 is clearly visible in the representation using overlapping circular bins, showing that the only significant excess in the field of view is related to M 87. The significance using the template model is $`3.9\sigma `$ as given in Table 2. The two background models applied in this analysis use widely different approaches, supporting the assumption that the M 87 excess does not stem from a background fluctuation.

The observed excess can be converted into an integral flux of ($`3.3\pm 0.8)`$ % of the Crab nebula flux (only the statistical error is given because of the low statistics). A conversion into absolute flux units using the well measured photon flux and spectrum of the Crab nebula around 1 TeV (e. g. Aharonian et al. (2000)) results in a $`\gamma `$-ray flux of

$$N_\gamma (E>730\text{GeV})=(0.96\pm 0.23)\times 10^{12}\text{phot.\hspace{0.17em}cm}^2\text{s}^1\text{.}$$
(1)
A spectral analysis of the data of the M 87 data has been performed using the analysis technique described in Aharonian et al. (2003a). The data can be well described with a power law $`\text{d}N/\text{d}EE^\alpha `$ with $`\alpha =2.9\pm 0.8_{\text{stat}}\pm 0.08_{\text{syst}}`$. The large statistical error results from the low event statistics.

## 3 Summary and Conclusions

The radio galaxy M 87 has been observed with the HEGRA IACT system for a total of 83.4 h. For the first time a significant excess of 4.1 $`\sigma `$ has been detected at energies above a mean energy threshold of 730 GeV from a member of this class of objects using the imaging atmospheric Cherenkov technique. Note that nearly 30 years ago the radio galaxy Centaurus A was reported to be a TeV source observed with a non-imaging instrument (Grindlay et al. (1975)).

Due to the limited number of excess events detected by the HEGRA telescopes, an analysis of the spectral shape results in a very large statistical error, thus making it difficult to draw a conclusion about the origin of the TeV $`\gamma `$-radiation. Assuming a power-law shape with a photon spectral index of 2.9 the integral photon flux at the level of ($`3.3\pm 0.8)`$ % of the Crab nebula flux converts into an energy flux of

$$F_\gamma (E>730\text{GeV})=(2.4\pm 0.6)\times 10^{12}\text{erg\hspace{0.17em}cm}^2\text{s}^1\text{.}$$
(2)
Given the distance to M 87 of about 16 Mpc, this corresponds to a $`\gamma `$-ray luminosity above 730 GeV of about $`10^{41}\text{erg\hspace{0.17em}s}^1`$ under the assumption of isotropic emission.

Several different possibilites for the origin of GeV/TeV $`\gamma `$-radiation are conceivable. M 87 with its pc scale jet has recently been modeled within the Synchrotron Self Compton scenario as a BL Lac object seen at a large angle to its jet axis (Bai & Lee (2001)). It has also been modeled using the so-called Synchrotron Proton Blazar model (Protheroe et al. (2002)). In both models, the observed flux can be accommodated.

The large scale (kpc) jets with several knots detected at radio to X-ray frequencies and believed to have synchrotron origin due to electrons with energies up to 100 TeV is also a possible $`\gamma `$-ray production site in M 87. Consequently, inverse Compton $`\gamma `$-rays in the 1 – 10 TeV energy range can be expected within reasonable model parameters.

Moreover, $`\gamma `$-rays could be produced in the interstellar medium of M 87, i. e. at larger distance scales from the center of this active galaxy. Both inverse Compton and hadronic interactions could generate a TeV $`\gamma `$-ray luminosity in the observed range of approx. $`10^{41}\text{erg\hspace{0.17em}s}^1`$. If this interpretation is valid, one would expect a slightly extended source (2 – 3).

It should be noted that M 87 is also considered as a possible source of TeV $`\gamma `$-rays from the hypothetical neutralino annihilation process (Baltz et al. (2000)).

A weak signal at the centi-Crab level is at the sensitivity threshold for the HEGRA IACT system for observation times of the order of 100 h. Therefore, a deep investigation and possible confirmation with a spectral analysis of the M 87 excess should be subject of the next generation Cherenkov telescope projects like H$``$E$``$S$``$S, MAGIC and VERITAS, which provide increased sensitivity together with a lower energy threshold. Due to the proximity to M 87 (16 Mpc) and to the increased accuracy of these observations (a fraction of an arc minute), these measurements may allow the location of the $`\gamma `$-ray production site in M 87 to be more accurately determined thus greatly advancing our understanding of its TeV $`\gamma `$-radiation.

###### Acknowledgements.

The support of the German Federal Ministry for Research and Technology BMBF and of the Spanish Research Council CICYT is gratefully acknowledged. G. Rowell acknowledges receipt of a von Humboldt fellowship. We thank the Instituto de Astrofísica de Canarias (IAC) for the use of the HEGRA site at the Observatorio del Roque de los Muchachos (ORM) and for supplying excellent working conditions on La Palma.