text:
# Improving an algorithm to solve Multiple Simultaneous Conjugacy Problems in braid groups

## 1 Introduction

In , Sang Jin Lee and Eonkyung Lee give an algorithm to solve the following problem, that they call Multiple Simultaneous Conjugacy Problem (MSCP), in the braid group $`B_n`$: given the $`r`$-tuples $`(a_1,\mathrm{},a_r)`$ and $`(x^1a_1x,\mathrm{},x^1a_rx)`$ in $`B_n`$, find the conjugator $`x`$.

This problem has been proposed for cryptographical applications: There is a Key Agreement Protocol proposed by Anshell, Anshell and Goldfeld in , improved by the same authors and Fisher in , which is based on the difficulty to solve a MSCP in some groups. Braid groups have been proposed as a good choice. There have been different attacks to this cryptosystem, namely length-based attacks (, ), linear algebraic ones (, ) and others (). But the algorithm we describe in this paper can be thought of as a direct attack to the base problem of the protocol.

We will assume that the reader is familiar with the basic notions in braid theory, which can be found in  or . It is also desirable to know the work in ,  and .

Recall that, given a braid $`aB_n`$, the integer $`inf(a)`$ is the biggest $`k`$ such that $`a=\mathrm{\Delta }^kp`$, where $`\mathrm{\Delta }`$ is the usual Garside element (half twist of all the strands) and $`p`$ is a positive braid (all its crossings are positive).

The algorithm in  works as follows: First they define, for every $`r`$-tuple of braids, $`\alpha =(a_1,\mathrm{},a_r)(B_n)^r`$, the set $`C^{inf}(\alpha )`$ consisting of all $`\beta =(b_1,\mathrm{},b_r)(B_n)^r`$ such that $`inf(b_i)inf(a_i)`$ for all $`i`$ and there exists some $`\omega B_n`$ satisfying $`b_i=\omega ^1a_i\omega `$ for all $`i`$ simultaneously (that is, $`\beta =\omega ^1\alpha \omega `$). Then they prove the following result:

###### Theorem 1.1.

 Let $`\alpha =(a_1,\mathrm{},a_r)`$ and $`\beta =(b_1,\mathrm{},b_r)`$ be an instance of a MSCP in $`B_n`$, and $`x`$ a positive solution. Then one can compute a positive braid $`x_0`$ and a $`r`$-tuple $`\beta ^{}=(b_1^{},\mathrm{},b_r^{})C^{inf}(\alpha )`$ such that $`b_i^{}=x_0b_ix_0^1`$ for all $`i`$, in time proportional to

$$n(\mathrm{log}n)|x|\left(|x|+\underset{i=1}{\overset{r}{}}(|a_i|+|b_i|)\right),$$

where $`||`$ denotes word length in generators. Moreover $`x=x_1x_0`$ for some positive braid $`x_1`$.

Here $`C^{inf}(\alpha )`$ plays the role of the Summit Set defined in  to solve the conjugacy problem in $`B_n`$, in the sense that it satisfies the following result:

###### Theorem 1.2.

 Given $`\beta C^{inf}(\alpha )`$, there exists a chain of elements $`\alpha =\alpha _1,\alpha _2,\mathrm{},\alpha _{k+1}=\beta `$ in $`C^{inf}(\alpha )`$, where successive elements are simultaneously conjugated by a permutation braid. In other words, there exist permutation braids $`s_1,\mathrm{},s_k`$ such that $`s_j^1\alpha _js_j=\alpha _{j+1}`$ for every $`j=1,\mathrm{},k`$.

Therefore, by classical methods (see ), one can use these two results to solve any MSCP in finite time. Nevertheless, this classical approach gives a computational complexity which is exponential with respect to the braid index $`n`$, and involves the cardinality $`N`$ of the set $`C^{inf}(\alpha )`$.

S. J. Lee and E. Lee expect in  that one can apply the methods in  to this algorithm, so that the computational complexity becomes a polynomial in $`(n,r,l,N)`$, where $`l`$ is the maximal word-length of the $`a_i`$’s and $`b_i`$’s. Here we show that this is the case. More precisely, we show:

###### Theorem 1.3.

Let $`\alpha =(a_1,\mathrm{},a_r)(B_n)^r`$ and let $`\beta =(b_1,\mathrm{},b_r)C^{inf}(\alpha )`$. Let $`l`$ be the maximal word length of the $`a_i`$’s and $`b_i`$’s, and let $`N`$ be the number of elements in $`C^{inf}(\alpha )`$. Then one can compute a braid $`xB_n`$ such that $`x^1\alpha x=\beta `$ in time $`O(Nrl^2n^3)`$.

## 2 Minimal simple elements for MSCP

Let us consider the Artin monoid of positive braids, $`B_n^+`$. We can define a prefix order on its elements, $``$, as follows: for $`a,bB_n^+`$, $`ab`$ if and only if there exists $`cB_n^+`$ such that $`ac=b`$. We will say that $`a`$ is a prefix (or a divisor) of $`b`$, or that $`b`$ is divisible by $`a`$. This is a partial order on $`B_n^+`$, with some nice properties: For every $`u,vB_n^+`$ there exists their least common multiple, $`uv`$, and their greatest common divisor, $`uv`$. There also exists an element $`\mathrm{\Delta }`$ (which is represented by a half twist of all the strands) which, together with the above partial order, endows $`B_n^+`$ with a structure of Garside monoid, so $`B_n`$ is a Garside group (cf.  ).

The permutation braids, also called simple elements, are the prefixes (or divisors) of $`\mathrm{\Delta }`$. We denote by $`S`$ the set of simple elements. In $`B_n^+`$ there are $`n!`$ simple elements.

The algorithm used in  to solve a MSCP goes as follows: given $`\alpha ,\beta (B_n)^r`$ conjugated, one computes $`\beta ^{}C^{inf}(\alpha )`$ as in Theorem 1.1. Then one must construct the whole $`C^{inf}(\alpha )`$ using the method by Garside: Conjugate $`\alpha `$ by all simple elements. If new elements in $`C^{inf}(\alpha )`$ are obtained, conjugate each one of them by all simple elements. Continue until no new elements appear. At that point, by Theorem 1.2, we will have computed the whole $`C^{inf}(\alpha )`$ and moreover, we will know a chain going from $`\alpha `$ to any other element in $`C^{inf}(\alpha )`$, as in Theorem 1.2. Hence, the chain associated to $`\beta ^{}`$, together with the element $`x_0`$ in Theorem 1.1 will give us the solution to the MSCP.

One of the main problems of this algorithm is the size of $`S`$. For every element in $`C^{inf}(\alpha )`$ one must compute $`n!`$ conjugations! The idea in  is to consider very small subsets of $`S`$, which can be fastly computed, satisfying some suitable properties that allow the classical algorithm to work with them, instead of the whole $`S`$. The general method to compute these small subsets is the following.

Let $`𝒫`$ be a property for simple elements, and let $`S_𝒫`$ be the set of simple elements satisfying $`𝒫`$. Then $`\mathrm{min}(S_𝒫)`$ is defined as the set of minimal elements (with respect to $``$) in $`S_𝒫`$. We must then define some suitable properties.

Let $`J=(j_1,\mathrm{},j_r)^r`$ and let $`C_J`$ be the set of $`r`$-tuples $`\delta =(d_1,\mathrm{},d_r)(B_n)^r`$ such that $`inf(d_i)j_i`$ for all $`i`$.

###### Definition 2.1.

Let $`J=(j_1,\mathrm{},j_r)^r`$ and let $`\delta =(d_1,\mathrm{},d_r)C_J`$. We say that a simple element $`s`$ satisfies the property $`𝒫(\delta ,J)`$ if $`s^1\delta sC_J`$. In other words, if $`inf(s^1d_is)j_i`$ for all $`i`$.

Now consider the subsets $`S_{\delta ,J}=\mathrm{min}(S_{𝒫(\delta ,J)})S`$, where $`\delta C_J`$. These are the small subsets of $`S`$ we were talking about. We can use them to solve a MSCP by means of the following result:

###### Proposition 2.2.

Given $`\alpha =(a_1,\mathrm{},a_r)(B_n)^r`$, let $`J=(inf(a_1),\mathrm{},inf(a_r))^r`$. For every $`\beta C^{inf}(\alpha )`$, there exists a chain $`\alpha =\alpha _1,\alpha _2,\mathrm{},\alpha _{k+1}=\beta `$ in $`C^{inf}(\alpha )`$, where for $`j=1,\mathrm{},k`$, $`\alpha _j`$ is conjugated to $`\alpha _{j+1}`$ by a simple element $`s_jS_{\alpha _j,J}`$. That is, $`s_j^1\alpha _js_j=\alpha _{j+1}`$ and $`s_j`$ is minimal among the simple elements conjugating $`\alpha _j`$ to an element in $`C_J`$.

###### Proof.

This result is analogous to Proposition 4.10 in . It suffices to take the chain given in Theorem 1.2 and decompose every simple element into minimal ones. We notice that we obtain a chain of elements in $`C_J`$, but since all these elements are conjugated to $`\alpha `$, they all belong to $`C^{inf}(\alpha )`$. ∎

## 3 Size of $`𝐒_{\delta ,𝐉}`$

In this section we will show that the cardinal of $`S_{\delta ,J}`$, for every $`J^r`$ and every $`\delta C_J`$, is always smaller that $`n`$. Hence, if we know how to compute it fastly, we will improve considerably the speed of the algorithm by Lee and Lee (recall that $`\mathrm{\#}(S)=n!`$). We will need the following results:

###### Proposition 3.1.

 If a property $`𝒫`$ is closed under gcd (i.e., if $`s_1,s_2S_𝒫`$ implies $`s_1s_2S_𝒫`$) then $`\mathrm{\#}(\mathrm{min}(S_𝒫))n1`$.

###### Proposition 3.2.

For every $`J^r`$ and every $`\delta C_J`$, the property $`𝒫(\delta ,J)`$ is closed under gcd.

###### Proof.

Suppose that $`s_1,s_2S_{𝒫(\delta ,J)}`$, that is, for every $`i=1,\mathrm{},r`$, $`inf(s_1^1d_is_1)j_i`$ and $`inf(s_2^1d_is_2)j_i`$. Since $`\delta C_J`$ one has $`d_i=\mathrm{\Delta }^{j_i}p_i`$ for some positive braid $`p_i`$. Then

$$s_1^1d_is_1=s_1^1\mathrm{\Delta }^{j_i}p_is_1=\mathrm{\Delta }^{j_i}\tau ^{j_i}(s_1^1)p_is_1,$$

where $`\tau `$ is the inner automorphism of $`B_n`$ which consists on conjugation by $`\mathrm{\Delta }`$. Hence, $`inf(s_1^1d_is_1)j_i`$ means that $`\tau ^{j_i}(s_1^1)p_is_1`$ is positive, or in other words: $`\tau ^{j_i}(s_1)p_is_1`$. In the same way one has $`\tau ^{j_i}(s_2)p_is_2`$ for all $`i`$. We must therefore show that, for $`i=1,\mathrm{},r`$, one has $`\tau ^{j_i}(s)p_is`$, where $`s=s_1s_2`$.

Since $`\tau `$ is a homomorphism that preserves the prefix order, then $`\tau ^{j_i}(s_1)\tau ^{j_i}(s_2)=\tau ^{j_i}(s_1s_2)=\tau ^{j_i}(s)`$. This implies $`\tau ^{j_i}(s)p_is_1`$ and $`\tau ^{j_i}(s)p_is_2`$, hence $`\tau ^{j_i}(s)(p_is_1)(p_is_2)=p_i(s_1s_2)=p_is`$, as we wanted to show. ∎

###### Corollary 3.3.

For every $`J^r`$ and every $`\delta C_J`$, the set $`S_{\beta ,J}=\mathrm{min}(S_{𝒫(\beta ,J)})`$ has at most $`n1`$ elements.

## 4 How to compute $`𝐒_{\delta ,𝐉}`$

We will finally present an algorithm that computes $`S_{\delta ,J}`$, given $`J^r`$ and $`\delta C_J`$. This algorithm will have complexity $`O(rl^2n^3)`$. Hence, in the algorithm by Lee and Lee, we no longer need to conjugate every $`\delta C^{inf}(\alpha )`$ by all simple elements (n! conjugations); we can compute $`S_{\delta ,J}`$ and then we do no more than $`n1`$ conjugations.

We first need to be more precise about the work in . We saw in Proposition 3.1 that $`\mathrm{min}(S_𝒫)`$ has at most $`n1`$ elements; but be can actually say more: for every generator $`\sigma _i`$, there is exactly one element $`r_i\mathrm{min}(S_𝒫)`$ such that $`\sigma _ir_i`$. It can happen, however, that $`r_i=r_j`$ for some $`ij`$. Anyway, in order to compute $`\mathrm{min}(S_𝒫)`$ (in our particular case $`S_{\delta ,J}`$), we just need to compute $`r_i`$ for $`i=1,\mathrm{},n1`$.

It is also given in  a method to compute the least common multiple $`sp`$ of a simple element $`s`$ and a positive braid $`p`$. More precisely, the algorithm given in  computes a simple element $`s^{}`$ such that $`ps^{}=sp`$. This takes time $`O(l^2n\mathrm{log}n)`$, where $`l`$ is the word length of $`p`$, and $`n`$ is the number of strands. Notice that, in terms of theoretical complexity, this algorithm is equivalent to the computation a normal form (cf. ). Furthermore, it is also shown in  that if $`p`$ is given in left normal form, then the complexity becomes $`O(ln\mathrm{log}n)`$.

So let us suppose that we are given $`J=(j_1,\mathrm{},j_r)^r`$ and $`\delta =(d_1,\mathrm{},d_r)C_J`$, and we want to compute $`S_{\delta ,J}`$. As we said before, we just need to compute $`r_i`$ for every $`i=1,\mathrm{},n1`$, where, in this case, $`r_i`$ is the minimal simple element which is divisible by $`\sigma _i`$ and conjugates $`\delta `$ to an element in $`C_J`$. We propose the following algorithm:

Algorithm to compute $`𝐫_𝐢`$.

1. Let $`D\{1,\mathrm{},r\}`$ consisting of those $`t`$ such that $`inf(d_t)=j_t`$.
2. For every $`tD`$, compute $`p_t`$ such that $`d_t=\mathrm{\Delta }^{j_t}p_t`$.
3. Let $`s=\sigma _i`$.
4. If $`\tau ^{j_t}(s)p_ts`$ for every $`tD`$, then return $`s`$. Stop.
5. Take $`mD`$ such that $`\tau ^{j_m}(s)p_ms`$.
6. Compute $`s^{}`$ such that $`(p_ms)s^{}=\tau ^{j_m}(s)p_ms`$.
7. Let $`s=ss^{}`$ and go to step 4.

###### Proposition 4.1.

Given $`J=(j_1,\mathrm{},j_r)^r`$, $`\delta =(d_1,\mathrm{},d_r)C_J`$ and $`i\{1,\mathrm{},n1\}`$, the above algorithm computes $`r_i`$, the minimal simple element which is divisible by $`\sigma _i`$ and conjugates $`\delta `$ to an element in $`C_J`$.

###### Proof.

The algorithm starts by considering just those $`d_t`$ whose infimum is exactly $`j_t`$. This is due to the following fact: If we can write $`d_t=\mathrm{\Delta }^kp_t`$ where $`k>j_t`$ and $`p_t`$ is a positive braid, then for every simple element $`s`$ we will have:

$$s^1d_ts=s^1\mathrm{\Delta }^kp_ts=\mathrm{\Delta }^k\tau ^k(s^1)p_ts=\mathrm{\Delta }^{k1}(\mathrm{\Delta }\tau ^k(s^1))p_ts.$$

But $`\tau ^k(s)`$ is a simple element, so $`\mathrm{\Delta }\tau ^k(s^1)`$ is a positive braid, hence the infimum of $`s^1d_ts`$ is at least $`k1j_t`$. Therefore, we just need to care about those $`d_t`$ where $`tD`$.

For every $`tD`$ one has $`d_t=\mathrm{\Delta }^{j_t}p_t`$, where $`p_t`$ is a positive braid. These elements $`p_t`$ are computed in Step 2 just by computing the left normal form of $`d_t`$.

We want to find $`r_i`$, and we know that $`\sigma _ir_i`$. In the algorithm, the simple element $`s`$ will be the possible value of $`r_i`$. At every iteration of the loop in steps 4-7, we start with a simple element $`s`$ such that $`\sigma _isr_i`$, and we check if $`s=r_i`$. If it is not, we multiply $`s`$ by some suitable simple element $`s^{}`$, and we start again. We must show that this makes sense.

At Step 3 we set $`s=\sigma _i`$, so we are sure that $`\sigma _isr_i`$. Then we start the loop. In order to decide if $`s=r_i`$, we must check if $`inf(s^1d_ts)j_t`$ for all $`tD`$. But, in the same way as above, one has $`s^1d_ts=\mathrm{\Delta }^{j_t}\tau ^{j_t}(s^1)p_ts`$, so $`inf(s^1d_ts)j_t`$ if and only if $`\tau ^{j_t}(s^1)p_ts`$ is a positive braid, or in other words, if $`\tau ^{j_t}(s)p_ts`$. This is what is checked at Step 4.

If Step 4 determined that $`sr_t`$, we must have found some $`mD`$ such that $`\tau ^{j_m}(s)p_ms`$. Step 5 just takes one of these values.

Now it comes the main step: We know that $`sr_i`$, so $`r_i=s\widehat{s}`$ for some simple element $`\widehat{s}`$. Moreover, $`inf(r_i^1d_mr_i)j_t`$ so one has $`\tau ^{j_m}(r_i)p_mr_i`$. Hence, $`\tau ^{j_m}(s)\tau ^{j_m}(s)\tau ^{j_m}(\widehat{s})=\tau ^{j_m}(r_i)p_mr_i`$ while on the other hand $`p_msp_ms\widehat{s}=p_mr_i`$. Therefore, the least common multiple $`\tau ^{j_m}(s)p_ms`$ must also divide $`p_mr_i`$. Step 6 computes this lcm. Actually, it computes $`s^{}`$ such that $`\tau ^{j_m}(s)p_ms=(p_ms)s^{}`$. But since this divides $`p_mr_i`$, we finally obtain that $`ss^{}r_i`$.

We must remark two facts: First, $`ss^{}`$ is always a simple element, since it divides the simple element $`r_i`$. Second, $`s^{}`$ cannot be trivial, since otherwise we would have $`\tau ^{j_m}(s)p_ms=p_ms`$, implying $`\tau ^{j_m}(s)p_ms`$, which gives a contradiction with the choice of $`m`$. Therefore, $`ss^{}`$ is strictly greater than $`s`$, but still a divisor of $`r_i`$, so in Step 7 we set $`s=ss^{}`$, and start the loop again. This cannot run forever since the word length of $`s`$ is increased at every iteration, so the maximal number of iterations is $`\frac{n(n1)}{2}`$ (the word length of $`\mathrm{\Delta }`$).

Therefore, at a certain iteration, we will obtain $`s=r_i`$, and the algorithm stops at Step 4 giving the correct output. ∎

## 5 Theoretical complexity

The algorithm we presented in this paper is exactly as the one in  except for the computations of $`S_{\delta ,J}`$, for every $`\delta C^{inf}(\alpha )`$. The main step is the computation of $`r_i`$ given by the algorithm in the previous section. So we start by studying the complexity of this computation:

###### Proposition 5.1.

Given $`J=(j_1,\mathrm{},j_r)^r`$, $`\delta =(d_1,\mathrm{},d_r)C_J`$ and $`i\{1,\mathrm{},n1\}`$, one can compute $`r_i`$ (the minimal simple element which is divisible by $`\sigma _i`$ and conjugates $`\delta `$ to an element in $`C_J`$) in time $`O(rl^2n^2)`$ where $`l`$ is the maximal word-length of the $`d_i`$’s.

###### Proof.

We need to study the complexity of the algorithm in the previous section. First, Step 1 can be performed by computing the left normal form of every $`d_t`$. Every normal form takes time $`O(l^2n\mathrm{log}n)`$, so Step one can be done in time $`O(rl^2n\mathrm{log}n)`$.

The requirements of Step 2 can be achieved while doing Step 1: if some $`d_t`$ has infimum $`j_t`$, we keep the value of $`p_t`$. Hence Step 2 is negligible, as well as Step 3.

Now we start a loop in Steps 4-7, which has at most $`\frac{n(n1)}{2}`$ iterations, as we saw above. The only non-negligible steps are Steps 4 and 6. In Step 4, for every $`tD`$ we must compute $`\tau ^{j_t}(s)`$, which can be done in linear time on the word size of $`s`$ (at most $`\frac{n(n1)}{2}`$), and then we must compute the left normal form of $`p_ts`$ taking time $`O(ln\mathrm{log}n)`$ (notice that $`p_t`$ is already in left normal form). After performing these computations, to check if $`\tau ^{j_t}(s)p_ts`$ is $`O(n\mathrm{log}n)`$ (cf ). Hence Step 4 takes time $`O(rln^2)`$. On the other hand, Step 6 can be done in time $`O(ln\mathrm{log}n)`$ by . Therefore, each iteration of the loop takes time $`O(rln^2)`$.

Now we could say that, since there are at most $`\frac{n(n1)}{2}`$ iterations, all of them can be computed in time $`O(rln^4)`$. But we can do better than that: The different values of $`s`$ in the successive iterations form an ascending chain of simple elements. Hence, the total number of computations performed in all the iterations is the same as if it were just one iteration, with the maximum value of $`s`$ (see ). Therefore, the whole loop can be done in time $`O(rln^2)`$, and the whole algorithm takes time $`O(rl^2n^2)`$. ∎

We can now apply this result to measure our contribution to the algorithm in :

Proof of Theorem 1.3. One just need to apply the classical algorithm by Garside, together with the results given in Proposition 2.2 and Corollary 3.3. To be more precise, let $`J=(inf(a_1),\mathrm{},inf(a_r))^r`$. For every element $`\delta C^{inf}(\alpha )`$ (there are $`N`$ elements) one must compute $`S_{\delta ,J}`$. This takes time $`O(rl^2n^2)`$ for every element, by the above result. Since there are at most $`n1`$ elements, it takes time $`O(rl^2n^3)`$. Then one must conjugate $`\delta `$ by all the elements in $`S_{\delta ,J}`$ (at most $`n1`$), so we do at most $`n1`$ conjugations by simple elements, each one taking time $`O(ln\mathrm{log}n)`$ since $`\delta `$ is already in left normal form.

The algorithm stops when we find $`\beta `$. So, in the worst case, the complexity of the whole computation is $`O(Nrl^2n^3)`$, as we wanted to show.

## 6 Final remarks

In this paper we have improved the algorithm in  to solve a MSCP. More precisely, we have improved a particular case of a MSCP, when the conjugate elements $`\alpha `$ and $`\beta `$ are such that $`\beta C^{inf}(\alpha )`$.

It is shown in  how to transform the general situation into this particular case (see Theorem 1.1), but the complexity of this step depends on the size of the solution! Therefore, using this method we do not have an upper bound for the complexity of the general case, in terms of the input data. Nevertheless, if our interest is to attack the cryptosystem in , where the secret key is the solution to the MSCP, then the complexity given in Theorem 1.1, to transform the general case into this particular case, yields a very efficient running time.

Nevertheless, if one dislikes to measure the complexity in terms of the length of the solution, one can do the following: given two conjugate elements $`\alpha =(a_1,\mathrm{},a_r)`$ and $`\beta =(b_1,\mathrm{},b_r)`$ in $`(B_n)^r`$, let $`J=(j_1,\mathrm{},j_r)^r`$ where $`j_i=\mathrm{min}(inf(a_i),inf(b_i))`$. Then one has $`\alpha ,\beta C_J`$. Now define $`C^{inf}(\alpha ,\beta )`$ as the set of $`\delta C_J`$ conjugate to $`\alpha `$ (thus to $`\beta `$). Then all the above results can be applied to $`C^{inf}(\alpha ,\beta )`$, so we do not need to pass through Theorem 1.1. That is, we have:

###### Theorem 6.1.

Let $`\alpha =(a_1,\mathrm{},a_r)`$ and $`\beta =(b_1,\mathrm{},b_r)`$ in $`(B_n)^r`$. Let $`l`$ be the maximal word length of the $`a_i`$’s and $`b_i`$’s, and let $`M`$ be the number of elements in $`C^{inf}(\alpha ,\beta )`$. Then one can compute a braid $`xB_n`$ such that $`x^1\alpha x=\beta `$ in time $`O(Mrl^2n^3)`$.

Anyway, we do not think that this is the better way to proceed, since $`C^{inf}(\alpha ,\beta )`$ will be, in general, much bigger than $`C^{inf}(\alpha )`$, so one should try first to raise the infimum of the entries of $`\alpha `$ and $`\beta `$, before starting to construct the whole $`C^{inf}(\alpha ,\beta )`$.

On the other hand, the complexity given in Theorems 1.3 and 6.1 may lead to confusion, since one may think that we solved the MSCP in polynomial time. This is not true, since the factors $`N`$ and $`M`$ (the size of $`C^{inf}(\alpha )`$ and $`C^{inf}(\alpha ,\beta )`$) may not be a polynomial in $`(n,r,l)`$ (there is no known bounds for $`N`$ or $`M`$ in terms of $`(n,l,r)`$). All we can say by now is that $`N`$ and $`M`$ get smaller as $`r`$ grows, so it seems that MSCP’s are simpler than usual conjugacy problems in braid groups (see the discussion in  about the size of $`N`$).

Finally, the algorithm in this paper works not only for braid groups, but for a larger class of groups, called Garside groups (see ,  and ), that share with braid groups the existence of simple elements and their basic properties. It can also be applied to other Garside structures in braid groups, as the one obtained from the presentation by Birman, Ko and Lee in .

Juan González-Meneses:
Dep. Matemática Aplicada I, ETS Arquitectura, Univ. de Sevilla, Av. Reina Mercedes 2, 41012-Sevilla (SPAIN).
E-mail: meneses@us.es


format: text

text:
# Fundamental limitation on qubit operations due to the Bloch-Siegert Oscillation

## Abstract

We show that if the Rabi frequency is comparable to the Bohr frequency so that the rotating wave approximation is inappropriate, an extra oscillation is present with the Rabi oscillation. We discuss how the sensitivity of the degree of excitation to the phase of the field may pose severe constraints on precise rotations of quantum bits involving low-frequency transitions. We present a scheme for observing this effect in an atomic beam.

It is well known that the amplitude of an atomic state is necessarily complex. The electric or magnetic field generated by an oscillator, on the other hand, is real, composed of the sum of two complex components. In describing semiclassically the atom-field interaction involving such a field, one often side-steps this difference by making the so-called rotating wave approximation (RWA), under which only one of the two complex components is kept, and the counter-rotating part is ignored. We discuss how the sensitivity of the degree of excitation to the phase of the field poses severe constraints on precise rotations of quantum bits involving low-frequency transitions. We also present a scheme for observing this effect in an atomic beam.

We consider an ideal two-level system where a ground state $`|0`$ is coupled to an excited state $`|1`$, and the $`01`$ transitions are magnetic dipolar, with a transition frequency $`\omega `$, and the magnetic field is of the form $`B=B_0\mathrm{cos}(\omega t+\varphi )`$. We now summarize briefly the two-level dynamics without the RWA. In the dipole approximation, the Hamiltonian can be written as:

$$\widehat{H}=ϵ(\sigma _0\sigma _z)/2+g(t)\sigma _x$$
(1)
where $`g(t)=g_0[\mathrm{exp}(i\omega t+i\varphi )+c.c.]/2`$, $`\sigma _i`$ are Pauli matrices, and $`ϵ=\omega `$ corresponds to resonant excitation. The state vector is written as:

$$|\xi (t)=\left(\begin{array}{c}C_0(t)\\ C_1(t)\end{array}\right).$$
(2)
We perform a rotating wave transformation by operating on $`|\xi (t)`$ with the unitary operator $`\widehat{Q}`$, where: $`\widehat{Q}=(\sigma _0+\sigma _z)/2+\mathrm{exp}(i\omega t+i\varphi )(\sigma _0\sigma _z)/2`$. The Schrödinger equation then takes the form (setting $`\mathrm{}=1`$): $`\dot{|\stackrel{~}{\xi }}=i\stackrel{~}{H(t)}|\stackrel{~}{\xi }(t)`$ where the effective Hamiltonian is given by:

$$\stackrel{~}{H}=\alpha (t)\sigma _++\alpha ^{}(t)\sigma _{},$$
(3)
with $`\alpha (t)=(g_0/2)\left[\mathrm{exp}(i2\omega ti2\varphi )+1\right]`$, and in the rotating frame the state vector is:

$$|\stackrel{~}{\xi }(t)\widehat{Q}|\xi (t)=\left(\begin{array}{c}\stackrel{~}{C}_0(t)\\ \stackrel{~}{C}_1(t)\end{array}\right).$$
(4)
Now, by making the rotating wave approximation (RWA), corresponding to dropping the fast oscillating term in $`\alpha (t)`$ one ignores effects (such as the Bloch-Siegert shift ) of the order of $`(g_0/\omega )`$, which can easily be observed in experiment if $`g_0`$ is large . Otherwise, by choosing $`g_0`$ to be small enough, one can make the RWA for any value of $`\omega `$. We explore here both regimes, and we find the general results without the RWA.

From Eqs.3 and 4, we get two coupled differential equations:

$`\dot{\stackrel{~}{C}}_0(t)`$ $`=`$ $`i(g_0/2)\left[1+\mathrm{exp}(i2\omega ti2\varphi )\right]\stackrel{~}{C}_1(t)`$ (5)
$`\dot{\stackrel{~}{C}}_1(t)`$ $`=`$ $`i(g_0/2)\left[1+\mathrm{exp}(+i2\omega t+i2\varphi )\right]\stackrel{~}{C}_0(t).`$ (6)
Let $`|C_0(0)|^2=1`$ be the initial condition, and we proceed to find approximate analytical solutions of Eqs.5 and 6. Due to the periodic nature of the effective Hamiltonian, the general solution to Eqs.5 and 6 can be written in the form:

$$|\stackrel{~}{\xi }(t)=\underset{n=\mathrm{}}{\overset{\mathrm{}}{}}\left(\begin{array}{c}a_n\\ b_n\end{array}\right)\mathrm{exp}(n(i2\omega ti2\varphi )).$$
(7)
Inserting Eq.7 in Eqs.5 and 6 we get for all $`n`$ :

$`\dot{a}_n`$ $`=`$ $`i2n\omega a_n+ig_0(b_n+b_{n1})/2,`$ (8)
$`\dot{b}_n`$ $`=`$ $`i2n\omega b_n+ig_0(a_n+a_{n+1})/2.`$ (9)
Here, the coupling between $`a_0`$ and $`b_0`$ is the conventional one when the RWA is made. The couplings to the nearest neighbors, $`a_{\pm 1}`$ and $`b_{\pm 1}`$, are detuned by an amount $`2\omega `$, and so on. To the lowest order in $`(g_0/\omega )`$, we can ignore terms with $`|n|>1`$, thus yielding a truncated set of six equations for $`\dot{a}_0,\dot{b}_0,\dot{a}_{\pm 1},\dot{b}_{\pm 1}`$. Now consider $`g_0`$ to have a time-dependence of the form $`g_0(t)=g_{0M}\left[1\mathrm{exp}(t/\tau _{sw})\right]`$, where the switching time constant $`\tau _{sw}`$ is large compared to other characteristic time scales such as $`1/\omega `$ and $`1/g_{0M}`$. Then, these equations can be solved by the method of adiabatic elimination, which is valid to first order in $`\eta (g_0/4\omega )`$. (Note $`\eta (t)=\eta _0\left[1\mathrm{exp}(t/\tau _{sw})\right]`$, where $`\eta _0(g_0M/4\omega ))`$. To solve the set of equations above, we consider first $`a_1`$ and $`b_1`$. Define $`\mu _\pm (a_1\pm b_1)`$, then one can write $`\dot{\mu }_\pm =i(2\omega +g_0/2)\mu _\pm \pm ig_0a_0/2`$. Adiabatic following then yields (again, to lowest order in $`\eta `$ ): $`a_10`$ and $`b_1\eta a_0`$. Likewise, we can show that $`a_1\eta b_0`$ and $`b_10`$. The only non-vanishing (to lowest order in $`\eta `$ with $`|C_0(t=0)|^2=1`$) terms in the solution of Eqs.5 and 6 are:

$`C_0(t)`$ $`=`$ $`\mathrm{cos}(g_0^{}(t)t/2)i\eta e^{i(2\omega t+2\varphi )}\mathrm{sin}(g_0^{}(t)t/2),`$ (10)
$`C_1(t)`$ $`=`$ $`ie^{i(\omega t+\varphi )}[\mathrm{sin}(g_0^{}(t)t/2)i\eta e^{+i(2\omega t+2\varphi )}\mathrm{cos}(g_0^{}(t)t/2)],`$ (11)
where $`g_0^{}(t)=1/t_0^tg_0(t)𝑑t=g_0\left[1(t/\tau _{sw})^1\mathrm{exp}(t/\tau _{sw})\right].`$

To lowest order in $`\eta `$, this solution is normalized at all times. Note that if one wants to carry this excitation on an ensemble of atoms using a $`\pi /2`$ pulse and measure the population of the state $`|1`$ after the excitation terminates (at $`t=\tau `$ when $`g^{}(\tau )\tau /2=\pi /2`$ ), the output signal will be:

$$|C_1(g_0^{}(\tau ),\varphi )|^2=\frac{1}{2}\left[1+2\eta \mathrm{sin}(2\omega \tau +2\varphi )\right],$$
(12)
which contains information of both the amplitude and the phase of the driving field $`B`$. This clearly indicates that the Rabi transition probability depends on the total phase $`\varphi _\tau =\omega \tau +\varphi `$ of the driving field.

A physical realization of this result can be best appreciated by considering an experimental arrangement of the type illustrated in Fig.1(left). And plot of the Rabi oscillations is shown in Fig.1(right). Under the RWA, the curve of Fig.1(a)(right) represents the conventional Rabi oscillation. However, we notice here some additional oscillation, which is magnified and shown separately in Fig.1(b)(right), produced by subtracting the conventional Rabi oscillation ($`\mathrm{sin}^2(g(t)/2)`$) from Fig.1(a)(right). That is, Fig.1(b)(right) corresponds to what we call the Bloch-Siegert Oscillation (BSO), given by $`\eta \mathrm{sin}(g_0^{}(\tau )\tau )\mathrm{sin}(2\varphi _\tau )`$. These analytical results agree very closely to the results which are obtained via direct numerical integration of Eqs.5 and 6. Note that the BSO is at twice the frequency of the driving field, and its amplitude is enveloped by a function that vanishes when all the atoms are in a single state. This osillation will be stonger when the ratio of the resonance frequency to the Rabi frequency is large . One should keep track of the phase of the excitation field at the location of the qubit  for low energy qubit systems  with fast driving.

In conclusion, we have shown that when a two-level atomic system is driven by a strong periodic field, the Rabi oscillation is accompanied by another oscillation at twice the transition frequency. This extra oscillation can limit the qubit operations in Rabi flopping without a proper matching of the parameters. However, it has been shown that, this phase has potential application in teleportation. By making use of distant entanglement, this mechanism may enable teleportation of the phase of a field that is encoded in the atomic state amplitude, and has potential applications to remote frequency locking .

We wish to acknowledge support from DARPA grant No. F30602-01-2-0546 under the QUIST program, ARO grant No. DAAD19-001-0177 under the MURI program, and NRO grant No. NRO-000-00-C-0158.


text:
# Vacuum Photon Splitting in Lorentz-Violating Quantum Electrodynamics

## Abstract

Radiative corrections arising from Lorentz violation in the fermion sector induce a nonzero amplitude for vacuum photon splitting. At one loop, the on-shell amplitude acquires both CPT-even and CPT-odd contributions forbidden in conventional electrodynamics.

In quantum electrodynamics (QED), a photon traveling in the vacuum has a zero amplitude for decay into multiple on-shell photons at any order in perturbation theory. This classic no-splitting result is a byproduct of Schwinger’s work on the proper-time method and the Euler-Heisenberg effective action in QED .

Schwinger’s result relies heavily on gauge invariance and also implicitly on Lorentz and CPT symmetry. However, Lorentz and CPT symmetry may be broken by effects from the Planck scale . Any effects are expected to be heavily suppressed by at least one power of the Planck mass, which implies most processes in QED and the Standard Model acquire only small Lorentz-violating corrections. Nonetheless, some processes normally excluded may now occur. It is natural to ask how Schwinger’s result forbidding on-shell vacuum photon splitting generalizes to the Lorentz-violating case.

The purpose of this work is to discuss the amplitude for vacuum photon splitting in the context of the general Lorentz- and CPT-violating QED extension , which includes all possible Lorentz-violating terms involving electron and photon fields. At leading order in certain coefficients for Lorentz violation, we find a nonzero on-shell one-loop amplitude for photon triple splitting.

We work within the renormalizable sector of the general QED extension for a single Dirac field $`\psi `$ of mass $`m`$, for which the lagrangian $``$ is

$``$ $`=`$ $`\frac{1}{2}i\overline{\psi }\mathrm{\Gamma }^\nu \stackrel{}{D_\nu }\psi \overline{\psi }M\psi \frac{1}{4}F^{\mu \nu }F_{\mu \nu }`$ (2)
$`\frac{1}{4}(k_F)_{\kappa \lambda \mu \nu }F^{\kappa \lambda }F^{\mu \nu }+\frac{1}{2}(k_{AF})^\kappa ϵ_{\kappa \lambda \mu \nu }A^\lambda F^{\mu \nu },`$
where $`D_\mu `$ is the usual covariant derivative and

$`\mathrm{\Gamma }^\nu `$ $``$ $`\gamma ^\nu +c^{\mu \nu }\gamma _\mu +d^{\mu \nu }\gamma _5\gamma _\mu +e^\nu +if^\nu \gamma _5+\frac{1}{2}g^{\lambda \mu \nu }\sigma _{\lambda \mu },`$ (3)
$`M`$ $``$ $`m+a_\mu \gamma ^\mu +b_\mu \gamma _5\gamma ^\mu +\frac{1}{2}H_{\mu \nu }\sigma ^{\mu \nu }.`$ (4)
The Lorentz violation is controlled by the real coefficients $`a_\mu `$, $`b_\mu `$, $`c_{\mu \nu }`$, $`d_{\mu \nu }`$, $`e_\mu `$, $`f_\mu `$, $`g_{\lambda \mu \nu }`$, $`H_{\mu \nu }`$ in the fermion sector and $`(k_{AF})_\mu `$, $`(k_F)_{\kappa \lambda \mu \nu }`$ in the photon sector. Inspection of Eq. (2) shows the amplitude for vacuum photon splitting is zero at tree level. The task at hand is thus to investigate possible finite radiative corrections to photon splitting at one loop and at leading order in the coefficients for Lorentz violation. In fact, for our purposes it suffices to restrict attention to a conventional photon sector with negligible $`(k_{AF})_\mu `$, $`(k_F)_{\kappa \lambda \mu \nu }`$. The four coefficients $`(k_{AF})_\mu `$ have been strongly constrained using measurements of cosmological birefringence . Ten of the 19 independent coefficients in $`(k_F)_{\kappa \lambda \mu \nu }`$ have also been strongly constrained using spectropolarimetry of cosmological sources, while the other nine can be absorbed into the fermion sector by a field redefinition without loss of generality .

With a conventional photon sector, photon splitting in the vacuum is strongly restricted by kinematics. If the incident on-shell photon has energy $`E_1`$ and 3-momentum $`\stackrel{}{p}_1`$, and the $`n`$ photons produced in the decay have energies $`E_j`$ and 3-momenta $`\stackrel{}{p}_j`$, $`j=2,3,\mathrm{},n+1`$, then conservation of 3-momentum implies $`_j|\stackrel{}{p}_j||\stackrel{}{p}_1|`$. Since each on-shell photon has 4-momentum $`p^\mu =(E,\stackrel{}{p})`$ satisfying $`p^2=0`$ and hence $`E=|\stackrel{}{p}|`$, this inequality is compatible with conservation of energy only if all the $`\stackrel{}{p}_j`$ are aligned. The incident photon and the decay products must therefore be collinear. It then follows that the 4-momenta of all photons are mutually orthogonal, $`p_j^\mu p_{k\mu }=0`$, and that they are all proportional to some momentum $`p_0^\mu `$ satisfying $`p_0^2=0`$ on shell. Moreover, the transversality of each physical photon implies that its polarization 4-vector $`\epsilon ^\mu `$ obeys $`p_\mu \epsilon ^\mu =0`$. Together with the requirement of collinearity, this implies $`\epsilon _j^\mu p_{k\mu }=0`$ and that there are at most two linearly independent physical polarization vectors in any process.

In addition to these kinematical constraints, the amplitude for photon splitting must satisfy criteria imposed by symmetry transformations and field redefinitions. First, since the theory (2) is invariant under observer Lorentz transformations, the amplitude must be an observer Lorentz scalar and so any Lorentz indices it contains must be contracted. Second, the properties of the Lorentz-violating operators in Eq. (2) under charge conjugation C imply a generalization of Furry’s theorem, which eliminates both divergent and finite contributions arising from certain coefficients . It follows that only $`a_\mu `$, $`d_{\mu \nu }`$, $`e_\mu `$, $`f_\mu `$, $`H_{\mu \nu }`$ can contribute to splitting into an even number of photons, while only $`b_\mu `$, $`c_{\mu \nu }`$, $`g_{\lambda \mu \nu }`$ can contribute to odd splitting. Third, the behavior of Eq. (2) under parity inversion P ensures that any contribution to the amplitude linear in $`b_\mu `$, $`d_{\mu \nu }`$, $`f_\mu `$ must come with one factor of the antisymmetric tensor $`ϵ_{\mu \nu \rho \sigma }`$. Fourth, gauge invariance demands that the amplitude be invariant when an external photon polarization vector is shifted by an amount proportional to its momentum. The expression for the amplitude must therefore vanish if any one polarization vector is replaced by the corresponding external momentum. Finally, in the single-fermion theory (2), some coefficients for Lorentz violation can be removed at linear order by suitable field redefinitions  and cannot contribute at leading order to physical processes. So we can ignore potential contributions from $`a_\mu `$, $`e_\mu `$, $`f_\mu `$, from the antisymmetric parts of $`c_{\mu \nu }`$, $`d_{\mu \nu }`$, and from all but the mixed-symmetry part of $`g_{\lambda \mu \nu }`$.

The combination of all the above constraints severely restricts the possibilities for photon splitting. For splitting into two photons, we find the only possibility for a nonzero amplitude involves the combination $`\epsilon _j^\mu H_{\mu \nu }p_k^\nu \epsilon _l^\alpha \epsilon _{m\alpha }`$. For splitting into three photons, the possibilities for a nonzero amplitude include the two combinations $`ϵ_{\mu \nu \rho \sigma }b^\mu p^\nu \epsilon _j^\rho \epsilon _k^\sigma \epsilon _l^\alpha \epsilon _{m\alpha }`$ and $`c_{\mu \nu }p^\mu p^\nu \epsilon _j^\alpha \epsilon _{k\alpha }\epsilon _l^\beta \epsilon _{m\beta }`$. Similar strong constraints can be deduced on the amplitudes for splitting into any number of photons.

To determine whether any of these amplitudes are nonzero, we proceed by direct calculation. For splitting into two photons, the calculation reveals that the overall amplitude vanishes. Photon double splitting is therefore absent, despite the presence of general Lorentz-violating terms in the fermion sector. However, the calculation of photon triple splitting reveals a nonzero amplitude, as we demonstrate next .

Consider first the P- and CPT-even contribution to photon triple splitting, which is linear in $`c_{\mu \nu }`$. This arises from a propagator insertion involving $`c_{\mu \nu }`$ in the usual one-loop four-point diagram, as shown in Fig. 1a. Note that a vertex insertion of $`c_{\mu \nu }`$, shown in Fig. 1b, cannot give a gauge-invariant contribution to on-shell photon triple splitting because $`c_{\mu \nu }`$ always appears contracted with a polarization vector. Denoting the external momenta as $`p_j`$, $`j=1,2,3,4`$, and the loop momentum as $`k`$, and adopting the shorthand notation $`k_1=k+p_1`$, $`k_{12}=k+p_1+p_2`$, etc., the contribution $`G`$ from a single graph of the form in Fig. 1a is

$`G^{\mu _1\mu _2\mu _3\mu _4}`$ $`=`$ $`{\displaystyle \frac{d^4k}{(2\pi )^4}\left[\frac{\mathrm{Tr}[(k/+m)c^{\mu \nu }\gamma _\mu k_\nu (k/+m)\gamma ^{\mu _1}(k/_1+m)\gamma ^{\mu _2}(k/_{12}+m)\gamma ^{\mu _3}(k/_{123}+m)\gamma ^{\mu _4}]}{(k^2m^2)^2(k_1^2m^2)(k_{12}^2m^2)(k_{123}^2m^2)}\right]}.`$ (5)
The denominators can be combined in the usual way using Feynman parameters, so that $`G=A+B`$ with

$`A`$ $`=`$ $`4!{\displaystyle _0^1}𝑑x_1{\displaystyle _0^{1x_1}}𝑑x_2{\displaystyle _0^{1x_{12}}}𝑑x_3{\displaystyle _0^{1x_{123}}}𝑑x_4{\displaystyle \frac{d^4k}{(2\pi )^4}2k_\mu c^{\mu \nu }k_\nu \left[\frac{\mathrm{Tr}[(k/+m)\gamma ^{\mu _1}(k/_1+m)\gamma ^{\mu _2}(k/_{12}+m)\gamma ^{\mu _3}(k/_{123}+m)\gamma ^{\mu _4}]}{(k^2m^2+2kq)^5}\right]},`$ (6)
$`B`$ $`=`$ $`3!{\displaystyle _0^1}𝑑x_1{\displaystyle _0^{1x_1}}𝑑x_2{\displaystyle _0^{1x_{12}}}𝑑x_3{\displaystyle \frac{d^4k}{(2\pi )^4}\left[\frac{\mathrm{Tr}[(c^{\mu \nu }\gamma _\mu k_\nu )\gamma ^{\mu _1}(k/_1+m)\gamma ^{\mu _2}(k/_{12}+m)\gamma ^{\mu _3}(k/_{123}+m)\gamma ^{\mu _4}]}{(k^2m^2+2kq)^4}\right]},`$ (7)
where $`x_{12}=x_1+x_2`$, $`x_{123}=x_1+x_2+x_3`$, $`q=x_1p_1+x_2p_{12}+x_3p_{123}`$ with $`q^2=0`$, and the indices on $`A`$, $`B`$ are suppressed for brevity. The trace of an odd number of $`\gamma `$-matrices vanishes, so the traces can be expanded as polynomials in $`m^2`$:

$`A`$ $`=`$ $`4!{\displaystyle _0^1}𝑑x_1{\displaystyle _0^{1x_1}}𝑑x_2{\displaystyle _0^{1x_{12}}}𝑑x_3{\displaystyle _0^{1x_{123}}}𝑑x_4(A_1+m^2A_2+m^4A_3),B=3!{\displaystyle _0^1}𝑑x_1{\displaystyle _0^{1x_1}}𝑑x_2{\displaystyle _0^{1x_{12}}}𝑑x_3(B_1+m^2B_2),`$ (8)
where

$`A_1`$ $`=`$ $`{\displaystyle \frac{d^4k}{(2\pi )^4}2k_\mu c^{\mu \nu }k_\nu \left[\frac{\mathrm{Tr}[k/\gamma ^{\mu _1}k/_1\gamma ^{\mu _2}k/_{12}\gamma ^{\mu _3}k/_{123}\gamma ^{\mu _4}]}{(k^2m^2+2kq)^5}\right]},`$ (9)
$`A_2`$ $`=`$ $`{\displaystyle }{\displaystyle \frac{d^4k}{(2\pi )^4}}2k_\mu c^{\mu \nu }k_\nu [{\displaystyle \frac{\mathrm{Tr}[k/\gamma ^{\mu _1}k/_1\gamma ^{\mu _2}\gamma ^{\mu _3}\gamma ^{\mu _4}]+\mathrm{Tr}[k/\gamma ^{\mu _1}\gamma ^{\mu _2}k/_{12}\gamma ^{\mu _3}\gamma ^{\mu _4}]+\mathrm{Tr}[k/\gamma ^{\mu _1}\gamma ^{\mu _2}\gamma ^{\mu _3}k/_{123}\gamma ^{\mu _4}]}{(k^2m^2+2kq)^5}}`$ (11)
$`+{\displaystyle \frac{\mathrm{Tr}[\gamma ^{\mu _1}k/_1\gamma ^{\mu _2}k/_{12}\gamma ^{\mu _3}\gamma ^{\mu _4}]+\mathrm{Tr}[\gamma ^{\mu _1}k/_1\gamma ^{\mu _2}\gamma ^{\mu _3}k/_{123}\gamma ^{\mu _4}]+\mathrm{Tr}[\gamma ^{\mu _1}\gamma ^{\mu _2}k/_{12}\gamma ^{\mu _3}k/_{123}\gamma ^{\mu _4}]}{(k^2m^2+2kq)^5}}],`$
$`A_3`$ $`=`$ $`{\displaystyle \frac{d^4k}{(2\pi )^4}2k_\mu c^{\mu \nu }k_\nu \left[\frac{\mathrm{Tr}[\gamma ^{\mu _1}\gamma ^{\mu _2}\gamma ^{\mu _3}\gamma ^{\mu _4}]}{(k^2m^2+2kq)^5}\right]},`$ (12)
and

$`B_1`$ $`=`$ $`{\displaystyle \frac{d^4k}{(2\pi )^4}\left[\frac{\mathrm{Tr}[\gamma ^\mu c_{\mu \nu }k^\nu \gamma ^{\mu _1}k/_1\gamma ^{\mu _2}k/_{12}\gamma ^{\mu _3}k/_{123}\gamma ^{\mu _4}]}{(k^2m^2+2kq)^4}\right]},`$ (13)
$`B_2`$ $`=`$ $`{\displaystyle \frac{d^4k}{(2\pi )^4}\left[\frac{\mathrm{Tr}[\gamma ^\mu c_{\mu \nu }k^\nu \gamma ^{\mu _1}k/_1\gamma ^{\mu _2}\gamma ^{\mu _3}\gamma ^{\mu _4}]+\mathrm{Tr}[\gamma ^\mu c_{\mu \nu }k^\nu \gamma ^{\mu _1}\gamma ^{\mu _2}k/_{12}\gamma ^{\mu _3}\gamma ^{\mu _4}]+\mathrm{Tr}[\gamma ^\mu c_{\mu \nu }k^\nu \gamma ^{\mu _1}\gamma ^{\mu _2}\gamma ^{\mu _3}k/_{123}\gamma ^{\mu _4}]}{(k^2m^2+2kq)^4}\right]}.`$ (14)
The traces in these expressions can be reduced using

$`2\mathrm{T}\mathrm{r}[\gamma _1\gamma _2\mathrm{}\gamma _n]`$ $`=`$ $`\eta _{12}\mathrm{Tr}[\gamma _3\gamma _4\mathrm{}\gamma _n]\eta _{13}\mathrm{Tr}[\gamma _2\gamma _4\mathrm{}\gamma _n]+\eta _{14}\mathrm{Tr}[\gamma _2\gamma _3\mathrm{}\gamma _n]\mathrm{}+\eta _{1n}\mathrm{Tr}[\gamma _2\gamma _3\mathrm{}\gamma _{n1}].`$ (15)
The full contribution to this vertex from all the relevant graphs, including all permutations over external momenta, must be finite . However, the expression $`G`$ for a single contributing graph diverges, and the divergences must be isolated by regulation. The integrals can be performed in $`d=42ϵ`$ dimensions, using the result

$`{\displaystyle \frac{d^dk}{(2\pi )^4}\frac{k_{\mu _1}\mathrm{}k_{\mu _n}}{(k^2m^2+2kq)^\alpha }}`$ $`=`$ $`(1)^n{\displaystyle \frac{i\pi ^{d/2}(m^2)^{(d2\alpha )/2}}{\mathrm{\Gamma }(\alpha )}}[\mathrm{\Gamma }(\alpha d/2)q_{\mu _1}\mathrm{}q_{\mu _n}`$ (18)
$`+(m^2/2)\mathrm{\Gamma }(\alpha 1d/2)(q_{\mu _1}\mathrm{}q_{\mu _{(n2)}}\eta _{\mu _{(n1)}\mu _n}+\mathrm{permutations})`$
$`+\mathrm{}+(m^2/2)^{n/2}\mathrm{\Gamma }(\alpha (n+d)/2)\eta _{\mu _1\mu _2}\mathrm{}\eta _{\mu _{(n1)}\mu _n}].`$
Since the external momenta are parallel, they can all be written in terms of a single vector $`p_0^\mu `$ satisfying $`p_0^2=0`$ and $`p_0^\mu ϵ_\mu =0`$. We can therefore write $`q^\mu =qp_0^\mu `$, etc., so that in what follows a quantity such as $`q^2`$ no longer denotes a square of the corresponding four-vector but instead denotes the square of a scalar coefficient. Various terms such as $`q/\gamma ^\mu q/`$ can then be shown to vanish upon contraction with $`ϵ_\mu `$, and after some algebra we find that only terms quadratic in $`p_0^\mu `$ survive. These terms are finite, so the limit $`d4`$ can be taken. The result is:

$`A_1+m^2A_2+m^4A_3`$ $`=`$ $`{\displaystyle \frac{ic_{\mu \nu }p_0^\mu p_0^\nu }{192\pi ^2m^2}}[\eta ^{\mu _1\mu _2}\eta ^{\mu _3\mu _4}(80q^2q(44p_1+32p_2+12p_3)+4p_1p_{123})`$ (21)
$`+\eta ^{\mu _1\mu _3}\eta ^{\mu _2\mu _4}(112q^2+q(60p_1+40p_2+20p_3)4p_1p_{123})`$
$`+\eta ^{\mu _1\mu _4}\eta ^{\mu _2\mu _3}(80q^2q(52p_1+32p_2+20p_3)+4p_1p_{123})],`$
$`B_1+m^2B_2`$ $`=`$ $`{\displaystyle \frac{ic_{\mu \nu }p_0^\mu p_0^\nu }{24\pi ^2m^2}}[\eta ^{\mu _1\mu _2}\eta ^{\mu _3\mu _4}(5q^2q(6p_1+3p_2+3p_3)+p_1p_{123})`$ (24)
$`+\eta ^{\mu _1\mu _3}\eta ^{\mu _2\mu _4}(5q^2+q(6p_1+3p_2+3p_3)p_1p_{123})`$
$`+\eta ^{\mu _1\mu _4}\eta ^{\mu _2\mu _3}(3q^2q(4p_1+p_2+3p_3)+p_1p_{123})].`$
Inserting these expressions into Eq. (8), we can explicitly integrate over the Feynman parameters since these appear at most quadratically in the integrands. The result for $`G=A+B`$ is:

$`G^{\mu _1\mu _2\mu _3\mu _4}`$ $`=`$ $`{\displaystyle \frac{ic_{\mu \nu }p_0^\mu p_0^\nu }{1440\pi ^2m^2}}[\eta ^{\mu _1\mu _2}\eta ^{\mu _3\mu _4}(102p_1^2+24p_2^2+37p_3^2+89p_1p_2+115p_1p_3+81p_2p_3)`$ (27)
$`\eta ^{\mu _1\mu _3}\eta ^{\mu _2\mu _4}(126p_1^2+48p_2^2+41p_3^2+133p_1p_2+119p_1p_3+93p_2p_3)`$
$`+\eta ^{\mu _1\mu _4}\eta ^{\mu _2\mu _3}(48p_1^2+37p_3^2+11p_1p_2+85p_1p_3+63p_2p_3)].`$
The full amplitude for the photon triple splitting at this order is obtained by summing the contributions from 24 graphs. These consist of four diagrams of the form in Fig. 1a with $`c_{\mu \nu }`$ insertions on the different fermion propagators, with three distinct topological channels for each diagram, and two orientations of the fermion loop for each channel. All these contributions can be derived from the result (27) for $`G`$ by suitable index permutations. Defining $`P`$ as $`P(f(\mu _1,\mu _2,\mu _3,\mu _4,p_1,p_2,p_3,p_4))f(\mu _4,\mu _1,\mu _2,\mu _3,p_4,p_1,p_2,p_3)`$, then the sum of the four $`c_{\mu \nu }`$ insertions is given by $`R=G+P(G)+P(P(G))+P(P(P(G)))`$ for one channel. To obtain different topological channels, we interchange first $`\mu _1`$ and $`\mu _2`$ and subsequently $`\mu _1`$ and $`\mu _4`$ without changing the momentum indices. Hence, the full contribution to the photon triple splitting amplitude $`T_c`$ is $`T_c=2(R+C_{12}(R)+C_{14}(R))`$, where $`C_{12}(f(\mu _1,\mu _2,\mu _3,\mu _4))=f(\mu _2,\mu _1,\mu _3,\mu _4)`$, $`C_{14}(f(\mu _1,\mu _2,\mu _3,\mu _4))=f(\mu _4,\mu _2,\mu _3,\mu _1)`$. Explicitly, we find

$`T_c^{\mu _1\mu _2\mu _3\mu _4}`$ $`=`$ $`{\displaystyle \frac{ic_{\mu \nu }p_0^\mu p_0^\nu }{60\pi ^2m^2}}[\eta ^{\mu _1\mu _2}\eta ^{\mu _3\mu _4}(9p_1^28p_2^2p_3^2+2p_1p_2+16p_1p_318p_2p_3)`$ (30)
$`+\eta ^{\mu _1\mu _3}\eta ^{\mu _2\mu _4}(4p_1^28p_2^2+4p_3^28p_1p_2+16p_1p_38p_2p_3)`$
$`+\eta ^{\mu _1\mu _4}\eta ^{\mu _2\mu _3}(p_1^28p_2^2+9p_3^218p_1p_2+16p_1p_3+2p_2p_3)],`$
where we have used $`p_1+p_2+p_3+p_4=0`$. Thus, a nonzero coefficient $`c_{\mu \nu }`$ yields a finite CPT-even contribution $`T_c`$ to the amplitude for photon triple splitting, even in the collinear limit.

By a similar set of calculations we obtain a finite CPT-odd contribution $`T_b`$ to the amplitude for photon triple splitting from a nonzero coefficient $`b_\mu `$, again in the collinear limit:

$`T_b^{\mu _1\mu _2\mu _3\mu _4}`$ $`=`$ $`{\displaystyle \frac{b_\mu p_{0\nu }}{6\pi ^2m^2}}\left[(9p_1+3p_3)\eta ^{\mu _1\mu _2}ϵ^{\mu _3\mu _4\mu \nu }(5p_1+4p_2+3p_3)\eta ^{\mu _1\mu _3}ϵ^{\mu _2\mu _4\mu \nu }(3p_1+p_3)\eta ^{\mu _2\mu _3}ϵ^{\mu _1\mu _4\mu \nu }\right].`$ (31)
Note that these results also imply nonzero contributions in the off-shell, non-collinear case. However, the existence of nonzero amplitudes in the collinear limit suffices to show that Schwinger’s no-splitting result is vitiated in the presence of Lorentz violation .

The nonzero amplitudes (30), (31) must arise from gauge-invariant terms in the effective action $`S_{\mathrm{eff}}`$ for the Lorentz-violating QED extension (2). The form of $`S_{\mathrm{eff}}`$ is not known explicitly, and it would be of interest to obtain it. The amplitudes (30), (31) are determined in the collinear limit and therefore cannot be used to deduce uniquely the terms in $`S_{\mathrm{eff}}`$ from which they arise. However, $`S_{\mathrm{eff}}`$ could include expressions such as $`c_{\mu \nu }F^{\mu \kappa }F_\kappa ^\nu ^2F^{\alpha \beta }F_{\alpha \beta }`$, which for transverse photons in the collinear limit generates terms of the structure necessary to reproduce the result (30). Note that the appearance of the inverse box operator is to be expected in the effective action of a massless field .

We close with brief remarks about an issue that is of some interest but lies beyond our present scope: the determination of a physical rate for on-shell photon triple splitting. For a massive particle, the decay rate is defined in the rest frame with a kinematic factor inversely proportional to the mass, so cannot trivially be extended to the massless case. Since the theory (2) is observer Lorentz covariant, it may be possible to define a physically consistent decay rate in terms of the particle energy in the observer frame . There is also a separate kinematical issue to consider because collinear momenta occupy a set of measure zero in the phase space. However, a physical analogy is provided by the collinear parametric down conversion of photons in optically active crystals, for which photon multiple splitting has been experimentally observed . The Lorentz violation induces an analogous effective optical activity of the vacuum . Equations (30) and (31) imply any nonzero decay rate would be quadratically suppressed in the small coefficients $`c_{\mu \nu }`$ and $`b_\mu `$ . Nonetheless, Lorentz-violating photon degradation over cosmic distances might lead to observable effects on the redshift , conceivably even affecting open issues such as the origin of the cosmological constant.

We thank R. Jackiw for discussions. This work is supported in part by the United States Department of Energy under grant DE-FG02-91ER40661.