text:
# How close are 𝑝th powers in the Nottingham group?

## Abstract

Let $`F`$ be a field of characteristic $`p>0`$ and let $`f,g`$ be elements of the Nottingham group $`𝒩(F)`$ such that $`f`$ has depth $`k`$ and $`gf^1`$ has depth $`nk`$. We find the best possible lower bound for the depth of $`g^pf^p`$.

Let $`R`$ be a commutative ring with 1 which has characteristic $`p>0`$, and let $`𝒩=𝒩(R)`$ denote the Nottingham group over $`R`$. Thus $`𝒩`$ is the set of all formal power series $`f(x)R[[x]]`$ with leading term $`x`$, and the product of $`f,g𝒩`$ is defined to be $`(fg)(x)=f(g(x))`$. For each $`k1`$ define a normal subgroup $`𝒩_k\mathrm{}𝒩`$ by setting

$$𝒩_k=\{f𝒩:f(x)x(\text{mod }x^{k+1})\}.$$
(1)
The depth of $`f𝒩`$ is defined to be $`D(f)=sup\{k:f𝒩_k\}`$.

Let $`nk1`$ and let $`k_0`$ be the least nonnegative residue of $`k`$ modulo $`p`$. We define a nonnegative integer $`e(k,n)`$ as follows:

$$e(k,n)=\{\begin{array}{cc}0\hfill & \text{ if }pk\text{ and }n=k\text{,}\hfill \\ 1\hfill & \text{ if }pk\text{}pn\text{, and }n>k\text{,}\hfill \\ 0\hfill & \text{ if }pk\text{ and }pn\text{,}\hfill \\ i\hfill & \text{ if }pk\text{ and }n2ki(\text{mod }p)\text{ for some }0ik_0\text{,}\hfill \\ k_0\hfill & \text{ if }pk\text{ and }n2ki(\text{mod }p)\text{ for all }0ik_0\text{.}\hfill \end{array}$$
(2)
Our main result is the following:

###### Theorem 1

(a) Let $`f`$ and $`g`$ be elements of $`𝒩(R)`$ such that $`D(f)k`$ and $`D(gf^1)n`$. Then

$$D(g^pf^p)n+(p1)k+e(k,n).$$
(3)
(b) There exist $`f,g𝒩(R)`$ such that $`D(f)=k`$, $`D(gf^1)=n`$, and

$$D(g^pf^p)=n+(p1)k+e(k,n).$$
(4)
The following corollary generalizes Theorem 1(a) to higher powers of $`p`$. It would be interesting to know whether the bound given here is the best possible.

###### Corollary 2

Let $`f,g𝒩(R)`$ be such that $`D(f)k`$ and $`D(gf^1)n`$. Then for all $`m1`$ we have

$$D(g^{p^m}f^{p^m})n+(p^m1)k+\frac{p^mp}{p1}k_0+e(k,n).$$
(5)
Proof: By repeated application of Lemma 5 below we get

$$D(f^{p^i})p^ik+\frac{p^i1}{p1}k_0$$
(6)
for all $`i1`$. It follows from (2) that

$$n+(p1)k+e(k,n)\{\begin{array}{cc}n(modp)\hfill & \text{if }e(k,n)=k_0\text{,}\hfill \\ k(modp)\hfill & \text{if }0e(k,n)<k_0\text{,}\hfill \\ 1(modp)\hfill & \text{if }pk\text{}pn\text{, and }n>k\text{.}\hfill \end{array}$$
(7)
Using (3), (6), and (7) we can iteratively compute lower bounds for $`D(g^{p^i}f^{p^i})`$. For $`i1`$ we get $`D(g^{p^i}f^{p^i})d_i`$, where $`d_1=n+(p1)k+e(k,n)`$ and

$$d_{i+1}=d_i+(p1)\left(p^ik+\frac{p^i1}{p1}k_0\right)+k_0.$$
(8)
By summing the terms we get

$$d_m=n+(p^m1)k+\frac{p^mp}{p1}k_0+e(k,n),$$
(9)
as required. $`\mathrm{}`$

Let $`S`$ be a commutative ring with 1 which has characteristic $`p`$ and let $`\sigma :RS`$ be a unitary ring homomorphism. Then $`\sigma `$ induces a group homomorphism $`𝒩(R)𝒩(S)`$ which we denote by $`ff^\sigma `$. We clearly have $`D(f^\sigma )D(f)`$. Let $`=𝔽_p[r_k,r_{k+1},\mathrm{},s_n,s_{n+1},\mathrm{}]`$, where $`𝔽_p=/p`$ is the field with $`p`$ elements and $`r_i,s_j`$ are variables. Also set

$`𝐟(x)`$ $`=x+r_kx^{k+1}+r_{k+1}x^{k+2}+\mathrm{}`$ (10)
$`𝐮_1(x)`$ $`=x+s_nx^{n+1}+s_{n+1}x^{n+2}+\mathrm{}`$ (11)
and $`𝐠=𝐮_1𝐟`$. Then $`𝐟`$ is a generic element of $`𝒩()`$ of depth $`k`$, and $`𝐮_1`$ is a generic element of $`𝒩()`$ of depth $`n`$.

Let $`f,g𝒩(R)`$ satisfy $`D(f)k`$ and $`D(gf^1)n`$. Then we have

$`f(x)`$ $`=x+a_kx^{k+1}+a_{k+1}x^{k+2}+\mathrm{}`$ (12)
$`gf^1(x)`$ $`=x+b_nx^{n+1}+b_{n+1}x^{n+2}+\mathrm{}`$ (13)
with $`a_i,b_jR`$. Let $`\sigma :R`$ be the unique homomorphism such that $`\sigma (r_i)=a_i`$ for $`ik`$ and $`\sigma (s_j)=b_j`$ for $`jn`$. Then $`𝐟^\sigma =f`$, $`(\mathrm{𝐠𝐟}^1)^\sigma =gf^1`$, and hence $`𝐠^\sigma =g`$. Therefore to prove Theorem 1(a) it suffices to show

$$D(𝐠^p𝐟^p)n+(p1)k+e(k,n).$$
(14)
Since $`𝔽_p`$ is a subring of every ring of characteristic $`p`$, it suffices to prove Theorem 1(b) in the case $`R=𝔽_p`$. We define a specialization to be a homomorphism $`\sigma :𝔽_p`$. Associated to a specialization $`\sigma `$ we have elements $`𝐟^\sigma `$, $`𝐠^\sigma `$, $`𝐮_1^\sigma `$ of $`𝒩(𝔽_p)`$.

Remark 3 Theorem 1 can be expressed entirely in terms of the generic power series $`𝐟(x)`$. Theorem 1(a) is equivalent to the statement that for all $`in+(p1)k+e(k,n)`$ the coefficient of $`x^i`$ in $`𝐟^p(x)`$ does not depend on any $`r_j`$ with $`jn`$. Theorem 1(b) is equivalent to the statement that there exist specializations $`\sigma ,\tau `$ such that $`\sigma (r_j)=\tau (r_j)`$ for $`kj<n`$, $`\sigma (r_n)\tau (r_n)`$, and $`D((𝐟^\tau )^p(𝐟^\sigma )^p)=n+(p1)k+e(k,n)`$. $`\mathrm{}`$

The following lemma is useful in the proof of Theorem 1(b):

###### Lemma 4

Suppose there are $`n^{}>nk`$ such that Theorem 1(a) holds for $`(k,n)`$, Theorem 1(b) holds for $`(k,n^{})`$, and

$$n+(p1)k+e(k,n)=n^{}+(p1)k+e(k,n^{}).$$
(15)
Then Theorem 1(b) holds for $`(k,n)`$.

Proof: Since Theorem 1(b) holds for $`(k,n^{})`$ there are $`f,g𝒩(R)`$ such that $`D(f)=k`$, $`D(gf^1)=n^{}`$, and $`D(g^pf^p)=n+(p1)k+e(k,n)`$. Choose $`h𝒩(R)`$ such that $`D(hf^1)=n`$. Then we have

$$D(h^pf^p)D(𝐠^p𝐟^p)n+(p1)k+e(k,n).$$
(16)
If $`D(h^pf^p)=n+(p1)k+e(k,n)`$ then $`f`$, $`h`$ satisfy the conditions of Theorem 1(b). If $`D(h^pf^p)>n+(p1)k+e(k,n)`$ then $`D(h^pg^p)=n+(p1)k+e(k,n)`$, $`D(g)=k`$, and $`D(hg^1)=n`$. Therefore $`g`$, $`h`$ satisfy the conditions of Theorem 1(b). $`\mathrm{}`$

The proof of Theorem 1 proceeds by cases, depending mainly on the relative sizes of $`k`$ and $`n`$. We start with the cases where $`n`$ is small. We first require a lemma.

###### Lemma 5

$`D(𝐟^p)=pk+k_0`$.

Proof: If $`p3`$ then the result follows from \[1, Th. 6\], while if $`p=2`$ and $`k`$ is even then it follows from \[1, Lemma 1\]. If $`p=2`$ and $`k`$ is odd then by an explicit calculation we get $`𝐟^2(x)=x+(r_1r_2+r_1^3)x^4+O(x^5)`$ if $`k=1`$, and $`𝐟^2(x)=x+r_kr_{k+1}x^{2k+2}+O(x^{2k+3})`$ if $`k3`$, which implies the result. $`\mathrm{}`$

###### Case 1

Theorem 1 holds if $`knk+k_0`$.

Proof: For $`n`$ in this range we have $`e(k,n)=k+k_0n`$. By Lemma 5 we have

$$D(𝐟^p)=D(𝐠^p)=pk+k_0=n+(p1)k+e(k,n).$$
(17)
It follows that $`D(𝐠^p𝐟^p)n+(p1)k+e(k,n)`$, which proves Theorem 1(a). To prove Theorem 1(b) we first consider the case $`n=k+k_0`$. Set $`f(x)=x+x^{k+1}`$, $`u(x)=x+x^{k+k_0+1}`$, and $`g=uf`$, so that $`D(gf^1)=D(u)=k+k_0`$. If $`pk`$ then $`k_0=0`$ and $`u=f`$, so by \[1, Lemma 1\] we have $`D(g^pf^p)=D(f^p)=pk`$. If $`p3`$ and $`pk`$ then by the third paragraph in the proof of \[1, Th. 6\] we have $`D(g^pf^p)=pk+k_0`$. If $`p=2`$ and $`n`$ is odd then by the explicit computations in the proof of Lemma 5 we get $`D(g^2f^2)=2k+1=pk+k_0`$. Thus Theorem 1(b) holds when $`n=k+k_0`$. It follows from Lemma 4 that Theorem 1(b) also holds for $`kn<k+k_0`$. $`\mathrm{}`$

We next consider the cases where $`n(p1)k+p`$. We will need the following basic result, which is proved in \[1, Prop. 1\].

###### Lemma 6

Let $`R`$ be an integral domain of characteristic $`p`$, let $`f,g𝒩(R)`$, and let $`[f,g]=f^1g^1fg`$ denote the commutator of $`f`$ with $`g`$. Then $`D([f,g])D(f)+D(g)`$, with equality if and only if $`D(f)D(g)(modp)`$.

Recall that $`𝐮_1=\mathrm{𝐠𝐟}^1𝒩()`$, and define $`𝐮_2,\mathrm{},𝐮_p`$ inductively by setting $`𝐮_{i+1}=[𝐮_i,𝐟]`$. By Lemma 6 we have $`D(𝐮_{i+1})D(𝐮_i)+D(𝐟)`$; since $`D(𝐮_1)=n`$ this implies $`D(𝐮_i)n+(i1)k`$ for $`1ip`$. It follows that $`D([𝐮_i,𝐮_j])2n+k`$ for $`1i,jp`$. Let $`𝒩=𝒩()`$, let $`\overline{𝒩}=𝒩/𝒩_{n+(p1)k+p}`$, and let $`\overline{𝐟}`$, $`\overline{𝐠}`$, $`\overline{𝐮}_i`$ denote the images of $`𝐟`$, $`𝐠`$, $`𝐮_i`$ in $`\overline{𝒩}`$. Since $`n(p1)k+p`$ we have $`2n+kn+(p1)k+p`$. Therefore $`\overline{𝐮}_i`$ commutes with $`\overline{𝐮}_j`$ for all $`1i,jp`$. Using the formula $`𝐮_i𝐟=\mathrm{𝐟𝐮}_i𝐮_{i+1}`$ we get

$$\overline{𝐠}^p=\overline{𝐟}^p\overline{𝐮}_1^{C(p,1)}\overline{𝐮}_2^{C(p,2)}\mathrm{}\overline{𝐮}_p^{C(p,p)},$$
(18)
where $`C(p,i)=p!/i!(pi)!`$ is the binomial coefficient. It follows from Lemma 5 that

$$D(𝐮_i^p)pnn+(p1)k+p.$$
(19)
Since $`pC(p,i)`$ for $`1ip1`$, this implies $`\overline{𝐮}_i^{C(p,i)}=1`$, and hence $`\overline{𝐠}^p=\overline{𝐟}^p\overline{𝐮}_p`$. To prove Theorem 1 for $`n(p1)k+p`$ it suffices to show that $`D(𝐮_p)n+(p1)k+e(k,n)`$, and that there is a specialization $`\sigma :𝔽_p`$ such that $`D(𝐮_p^\sigma )=n+(p1)k+e(k,n)`$.

###### Case 2

Theorem 1 holds if $`n(p1)k+p`$ and $`pk`$.

Proof: If $`pn`$ then an inductive argument based on Lemma 6 shows that $`D(𝐮_p)=n+(p1)k`$. If $`pn`$ then it follows from Lemma 6 that $`D(𝐮_2)n+k+1`$, and hence that $`D(𝐮_p)n+(p1)k+1`$. This proves Theorem 1(a). If $`pn`$ let $`\sigma `$ be a specialization such that $`D(𝐟^\sigma )=k`$ and $`D(𝐮_1^\sigma )=n`$. Then by Lemma 6 we have $`D(𝐮_p)=n+(p1)k`$, which proves Theorem 1(b) in this case. If $`pn`$ let $`\sigma `$ be a specialization such that $`D(𝐟^\sigma )=k`$ and $`D(𝐮_1^\sigma )=n+1`$. Using Lemma 6 we get

$`D(𝐮_p^\sigma )`$ $`=n+(p1)k+1`$ (20)
$`=n+(p1)k+e(k,n)`$ (21)
$`=(n+1)+(p1)k+e(k,n+1).`$ (22)
Theorem 1(b) now follows from Lemma 4. $`\mathrm{}`$

Since $`𝐮_1`$ and $`𝐟`$ are generic one might expect that $`D(𝐮_{i+1})=D(𝐮_i)+D(𝐟)+1`$ when $`D(𝐮_i)D(𝐟)(modp)`$. In fact this is not always the case: There are instances where $`D(𝐮_{i+1})>D(𝐮_i)+D(𝐟)+1`$. To compute $`D(𝐮_p)`$ when $`pk`$, we introduce a doubly-indexed sequence $`(c_{ij})`$ which is closely related to the coefficients of $`𝐮_h(x)`$. We retain the variables $`r_k,r_{k+1},r_{k+2},\mathrm{}`$ and introduce a new variable $`K`$. For $`i,j0`$ we define $`c_{ij}[K,r_k,r_{k+1},\mathrm{}]`$ using the difference equation

$$c_{ij}=\underset{t=0}{\overset{j}{}}\left((i2)K+n+2tj\right)r_{k+jt}c_{i1,t}$$
(23)
for $`i1`$, $`j0`$, and the initial conditions

$$c_{0j}=\{\begin{array}{cc}1\hfill & \text{if }j=0,\hfill \\ 0\hfill & \text{if }j1.\hfill \end{array}$$
(24)
Let $`S=(K)[r_k^1,r_k,r_{k+1},r_{k+2},\mathrm{}]`$, and for $`a`$, $`i0`$ define

$$P_a(i)=\underset{h=1}{\overset{i}{}}((h2)K+n+a)[K].$$
(25)
###### Lemma 7

There are $`\varphi _{jab}S`$ such that for all $`i,j0`$ we have

$$c_{ij}=r_k^i\underset{a=0}{\overset{j}{}}\underset{b=0}{\overset{j}{}}\varphi _{jab}P_a(i+b).$$
(26)
Proof: We use induction on $`j`$. It follows from (23) and (24) that $`c_{i0}=r_k^iP_0(i)`$. Thus by setting $`\varphi _{000}=1`$ we get the lemma in the case $`j=0`$. Let $`j1`$ and assume that the lemma holds for all $`c_{it}`$ with $`i0`$ and $`0t<j`$. Then for $`i1`$ and $`0t<j`$ we have

$$c_{i1,t}=r_k^{i1}\underset{a=0}{\overset{t}{}}\underset{b=0}{\overset{t}{}}\varphi _{tab}P_a(i1+b),$$
(27)
with $`\varphi _{tab}S`$. Since

$$\begin{array}{c}((i2)K+n+2tj)P_a(i1+b)=\hfill \\ \hfill P_a(i+b)+(bK+2tja)P_a(i1+b),\end{array}$$
(28)
by substituting (27) into the difference equation (23) we get

$$c_{ij}=\left((i2)K+n+j\right)r_kc_{i1,j}+r_k^{i1}\underset{t=0}{\overset{j1}{}}\underset{a=0}{\overset{t}{}}\underset{b=0}{\overset{t+1}{}}\psi _{tab}P_a(i1+b),$$
(29)
where

$$\psi _{tab}=\{\begin{array}{cc}(2tja)r_{k+jt}\varphi _{ta0}\hfill & \text{if }b=0,\hfill \\ (bK+2tja)r_{k+jt}\varphi _{tab}+r_{k+jt}\varphi _{t,a,b1}\hfill & \text{if }1bt,\hfill \\ r_{k+jt}\varphi _{tat}\hfill & \text{if }b=t+1\text{.}\hfill \end{array}$$
(30)
The general solution to (29) as a difference equation in $`i`$ is

$$c_{ij}=\alpha r_k^iP_j(i)+r_k^{i1}\underset{t=0}{\overset{j1}{}}\underset{a=0}{\overset{t}{}}\underset{b=0}{\overset{t+1}{}}\frac{\psi _{tab}}{bK+aj}P_a(i+b),$$
(31)
with $`\alpha `$ arbitrary. For $`0a<j`$, $`0bj`$ set

$$\varphi _{jab}=r_k^1\underset{t=c}{\overset{j1}{}}\frac{\psi _{tab}}{bK+aj},$$
(32)
where $`c=\mathrm{max}\{a,b1\}`$. Then for $`0a<bj`$ we have

$$\varphi _{jab}=\frac{\varphi _{b1,a,b1}}{bK+aj}r_{k+jb+1}r_k^1+\underset{t=b}{\overset{j1}{}}\frac{(bK+2tja)\varphi _{tab}+\varphi _{t,a,b1}}{bK+aj}r_{k+jt}r_k^1,$$
(33)
for $`1ba<j`$ we have

$$\varphi _{jab}=\underset{t=a}{\overset{j1}{}}\frac{(bK+2tja)\varphi _{tab}+\varphi _{t,a,b1}}{bK+aj}r_{k+jt}r_k^1,$$
(34)
and for $`0a<j`$, $`b=0`$ we have

$$\varphi _{ja0}=\underset{t=0}{\overset{j1}{}}\frac{(2tja)\varphi _{ta0}}{aj}r_{k+jt}r_k^1.$$
(35)
It follows that (31) can be rewritten as

$$c_{ij}=\varphi _{jj0}r_k^iP_j(i)+r_k^i\underset{a=0}{\overset{j1}{}}\underset{b=0}{\overset{j}{}}\varphi _{jab}P_a(i+b),$$
(36)
where the value of $`\varphi _{jj0}=\alpha `$ is determined by the initial conditions (24) to be

$$\varphi _{jj0}=\underset{a=0}{\overset{j1}{}}\underset{b=0}{\overset{j}{}}\varphi _{jab}P_a(b).$$
(37)
Finally, set $`\varphi _{jjb}=0`$ for $`1bj`$. Then $`c_{ij}`$ is given by (26). Since $`\varphi _{tab}S`$ for $`0t<j`$, it follows from (33), (34), and (35) that $`\varphi _{jab}S`$ for $`0a<j`$ and $`0bj`$. Hence by (37) we have $`\varphi _{jj0}S`$ as well. Thus all the coefficients $`\varphi _{jab}`$ in (26) lie in $`S`$, so the lemma holds for $`j`$. $`\mathrm{}`$

In the proof of Lemma 7 we define $`\varphi _{jab}`$ for all $`(j,a,b)`$ such that $`0a,bj`$. Set $`\varphi _{jab}=0`$ for all other integer values of $`j,a,b`$. Then by (33), (34), and (35) we have

$$\underset{t=a}{\overset{j}{}}(bK+j+a2t)r_{k+jt}\varphi _{tab}=\underset{t=a}{\overset{j1}{}}r_{k+jt}\varphi _{t,a,b1}$$
(38)
for $`ja0`$, $`b0`$. Shifting $`j`$ and $`t`$ by $`a`$ gives

$$\underset{t=0}{\overset{j}{}}(bK+j2t)r_{k+jt}\varphi _{t+a,a,b}=\underset{t=0}{\overset{j1}{}}r_{k+jt}\varphi _{t+a,a,b1}$$
(39)
for $`j,a,b`$ nonnegative.

From (33) and (34) we would expect the denominator of $`\varphi _{jab}`$ to contain the factor $`bK+aj`$. Surprisingly, this factor is not present unless $`baj`$. For $`l,m0`$ define a subring of $`S`$,

$$S_{lm}=[\frac{1}{l!},K,\frac{1}{K1},\frac{1}{K2},\mathrm{},\frac{1}{Km},r_k^1,r_k,r_{k+1},r_{k+2},\mathrm{}].$$
(40)
If $`ll^{}`$ and $`mm^{}`$ then clearly $`S_{lm}S_{l^{}m^{}}`$. For each $`(j,a,b)`$ we will find $`(l,m)`$ such that $`\varphi _{jab}S_{lm}`$. To accomplish this we fix $`a`$ and find the generating function for $`(\varphi _{jab})`$.

###### Proposition 8

Let $`a0`$. The ordinary generating function for $`(\varphi _{jab})_{j,b0}`$ is

$$F_a(x,y)=\underset{j=0}{\overset{\mathrm{}}{}}\underset{b=0}{\overset{\mathrm{}}{}}\varphi _{jab}x^jy^b=\varphi _{aa0}r_k^1x^a\alpha (x)e^{\omega (x)y},$$
(41)
where $`\alpha (x)=r_k+r_{k+1}x+r_{k+2}x^2+\mathrm{}`$, $`{\displaystyle \frac{r_k}{\alpha (x)}}=1+q_1x+q_2x^2+\mathrm{}`$, and

$`\omega (x)`$ $`={\displaystyle \underset{t=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{q_t}{tK}}x^t.`$ (42)
Proof: When $`a=0`$ the difference equation (39) is equivalent to the partial differential equation

$$\left(Ky\frac{}{y}+x\frac{}{x}\right)\left(F_0(x,y)\alpha (x)\right)2x\alpha (x)\frac{}{x}F_0(x,y)=yF_0(x,y)\left(\alpha (x)r_k\right).$$
(43)
In addition, since $`\varphi _{000}=1`$ and $`\varphi _{00b}=0`$ for $`b1`$, we have the boundary condition $`F_0(0,y)=1`$. The solution to this boundary value problem is easily determined by the method of characteristics to be the function given in (41), with $`a=0`$. Alternatively, one can use the formula

$$x\omega ^{}(x)K\omega (x)=\frac{r_k}{\alpha (x)}1$$
(44)
to check directly that this function is the unique solution. For $`a1`$, the sequence $`(\varphi _{j+a,a,b})_{j,b0}`$ satisfies the same linear difference equation (39) as $`(\varphi _{j0b})_{j,b0}`$, and we have $`\varphi _{aab}=0`$ for $`b1`$. Therefore the generating function for $`(\varphi _{j+a,a,b})_{j,b0}`$ is $`\varphi _{aa0}F_0(x,y)`$. Since $`\varphi _{jab}=0`$ for $`j<a`$, this implies that the generating function for $`(\varphi _{jab})_{j,b0}`$ is $`F_a(x,y)=\varphi _{aa0}x^aF_0(x,y)`$$`\mathrm{}`$

###### Corollary 9

Let $`j,a,b`$ be nonnegative. If $`a+b>j`$ then $`\varphi _{jab}=0`$. If $`a+bj`$ then $`\varphi _{jab}S_{lm}`$, where $`l=\mathrm{max}\{a,b\}`$, $`m=a`$ if $`b=0`$, and $`m=\mathrm{max}\{a,j+1ab\}`$ if $`b1`$.

Proof: We first consider the case $`a=0`$. By Proposition 8 we see that $`\varphi _{j0b}`$ is the coefficient of $`x^j`$ in

$$r_k^1\alpha (x)\frac{1}{b!}\omega (x)^b=\frac{r_k^1x^b}{b!}(r_k+r_{k+1}x+\mathrm{})\left(\underset{t=1}{\overset{\mathrm{}}{}}\frac{q_t}{tK}x^{t1}\right)^b.$$
(45)
It follows easily from this observation that $`\varphi _{j00}`$ lies in $`S_{00}`$, $`\varphi _{j0b}`$ lies in $`S_{b,j+1b}`$ for $`1bj`$, and $`\varphi _{j0b}=0`$ for $`b>j`$. We next use induction to show that $`\varphi _{jj0}S_{jj}`$ for $`j0`$. Since $`\varphi _{000}=1`$, the case $`j=0`$ is clear. Let $`j1`$ and suppose $`\varphi _{aa0}S_{aa}`$ for all $`0a<j`$. By Proposition 8 we have $`\varphi _{jab}=\varphi _{aa0}\varphi _{ja,0,b}`$, so (37) can be rewritten as

$$\varphi _{jj0}=\underset{a=0}{\overset{j1}{}}\underset{b=0}{\overset{j}{}}\varphi _{aa0}\varphi _{ja,0,b}P_a(b).$$
(46)
By the inductive assumption we have $`\varphi _{aa0}S_{aa}`$, and it follows from the first case that $`\varphi _{ja,0,b}S_{jj}`$ for $`0aj1`$, $`0bj`$. Therefore all the terms of (46) are in $`S_{jj}`$, so we get $`\varphi _{jj0}S_{jj}`$. The general case of the corollary now follows from the formula $`\varphi _{jab}=\varphi _{aa0}\varphi _{ja,0,b}`$. $`\mathrm{}`$

###### Corollary 10

View $`\varphi _{jab}`$ as a rational function of $`K`$. Then for each $`j1`$, $`\varphi _{j01}`$ has a simple pole at $`K=j`$ with residue $`q_j`$.

Proof: Using (45) we get

$$\varphi _{j01}=\frac{r_k^1r_{k+j1}q_1}{1K}+\frac{r_k^1r_{k+j2}q_2}{2K}+\mathrm{}+\frac{r_k^1r_kq_j}{jK}.$$
(47)
The corollary now follows from the fact that $`q_j0`$. $`\mathrm{}`$

We now use Corollaries 9 and 10 to prove Theorem 1 in the cases where $`pk`$ and $`n(p1)k+p`$. Set $`e=e(k,n)`$ and let $`A_h\mathrm{M}_{(e+1)\times (e+1)}()`$ be the upper triangular matrix whose $`(i,j)`$ entry for $`0ije(k,n)`$ is

$$a_{hij}=((h2)k+n+2ij)r_{k+ji}.$$
(48)
Then we have

$$A_h=\left[\begin{array}{ccccc}n_hr_k& (n_h1)r_{k+1}& (n_h2)r_{k+2}& \mathrm{}& (n_he)r_{k+e}\\ 0& (n_h+1)r_k& n_hr_{k+1}& \mathrm{}& (n_he+2)r_{k+e1}\\ 0& 0& (n_h+2)r_k& \mathrm{}& (n_he+4)r_{k+e2}\\ \mathrm{}& \mathrm{}& \mathrm{}& & \mathrm{}\\ 0& 0& 0& \mathrm{}& (n_h+e)r_k\end{array}\right],$$
(49)
where $`n_h=(h2)k+n`$. For $`1hp`$ let $`\stackrel{}{v}_h^{e+1}`$ be the row vector whose entries are the coefficients of $`x^{(h1)k+n+1},x^{(h1)k+n+2},\mathrm{},x^{(h1)k+n+e+1}`$ in $`𝐮_h(x)`$.

###### Lemma 11

If $`e(k,n)<k`$ then $`\stackrel{}{v}_{h+1}=\stackrel{}{v}_hA_h`$.

Proof: Write $`𝐟(x)=x+x^{k+1}\alpha (x)`$ and $`𝐮_h(x)=x+x^{(h1)k+n+1}\beta (x)`$. Then we have the following expansions modulo $`x^{(h+1)k+n+1}`$:

$$\begin{array}{c}𝐮_h(𝐟(x))x+x^{k+1}\alpha (x)+x^{(h1)k+n+1}\beta (x)+\hfill \\ \hfill ((h1)k+n+1)x^{hk+n+1}\alpha (x)\beta (x)+x^{hk+n+2}\alpha (x)\beta ^{}(x)\end{array}$$
(50)
$$\begin{array}{c}𝐟(𝐮_h(x))x+x^{k+1}\alpha (x)+x^{(h1)k+n+1}\beta (x)+\hfill \\ \hfill (k+1)x^{hk+n+1}\alpha (x)\beta (x)+x^{hk+n+2}\alpha ^{}(x)\beta (x)\end{array}$$
(51)
$$\begin{array}{c}[𝐮_h,𝐟](x)x+((h2)k+n)x^{hk+n+1}\alpha (x)\beta (x)+\hfill \\ \hfill x^{hk+n+2}(\alpha (x)\beta ^{}(x)\alpha ^{}(x)\beta (x)).\end{array}$$
(52)
We have $`\alpha (x)=r_k+r_{k+1}x+r_{k+2}x^2+\mathrm{}`$, and we can write $`\beta (x)=t_0+t_1x+t_2x^2+\mathrm{}`$ with $`t_i`$. Since $`e(k,n)k1`$, it follows from (52) that for $`0je(k,n)`$ the coefficient of $`x^{hk+n+j+1}`$ in $`𝐮_{h+1}(x)=[𝐮_h,𝐟](x)`$ is

$$\underset{i=0}{\overset{j}{}}((h2)k+n+2ij)r_{k+ji}t_i.$$
(53)
Comparing this expression with (49) gives the lemma. $`\mathrm{}`$

###### Case 3

Theorem 1 holds if $`n(p1)k+p`$, $`pk`$, and $`e(k,n)<k`$.

Proof: For $`h1`$ define a matrix $`\mathrm{\Pi }_h\mathrm{M}_{(e+1)\times (e+1)}()`$ by setting $`\mathrm{\Pi }_h=A_1A_2\mathrm{}A_h`$. It follows from Lemma 11 that $`\stackrel{}{v}_p=\stackrel{}{v}_1\mathrm{\Pi }_{p1}`$, where $`\stackrel{}{v}_1=(s_n,s_{n+1},\mathrm{},s_{n+e})`$ has entries which are independent variables in $``$ which don’t occur in $`\mathrm{\Pi }_{p1}`$. Thus to prove Theorem 1 in this case it suffices to show that the first $`e(k,n)`$ columns of $`\mathrm{\Pi }_{p1}`$ are all zero, and that there is a specialization $`\sigma :𝔽_p`$ which maps the last column of $`\mathrm{\Pi }_{p1}`$ to a nonzero element of $`𝔽_p^{e+1}`$. We indicate the dependence of $`A_h`$ on $`n`$ by writing $`A_h=A_h(n)`$ and $`a_{hij}=a_{hij}(n)`$. We also let $`\pi _{hij}=\pi _{hij}(n)`$ denote the $`(i,j)`$ entry of $`\mathrm{\Pi }_h`$. If $`0ije(k,n)`$ then $`e(k,n+i)e(k,n)i`$, so $`a_{h,0,ji}(n+i)`$ is defined. By (48) we have $`a_{hij}(n)=a_{h,0,ji}(n+i)`$ for $`0ije`$, and an inductive argument shows then that $`\pi _{hij}(n)=\pi _{h,0,ji}(n+i)`$. If $`j<e(k,n)`$ then $`ji<e(k,n+i)`$. Therefore it will suffice to prove the following statements for all $`n(p1)k+p`$:

$`\pi _{p1,0,j}(n)`$ $`=0\text{ for all }0j<e(k,n)\text{,}`$ (54)
$`\sigma (\pi _{p1,i,e}(n))`$ $`0\text{ for some }0ie(k,n)\text{ and some specialization }\sigma \text{.}`$ (55)
There is a natural map $`\rho :[K,r_k,r_{k+1},\mathrm{}]`$ which takes $`K`$ to the image of $`k`$ in $``$. We denote this map by $`x\overline{x}`$. Since $`\mathrm{\Pi }_h=\mathrm{\Pi }_{h1}A_h`$, the sequence $`(\pi _{h0j})`$ satisfies the difference equation

$$\pi _{h0j}=\underset{t=0}{\overset{j}{}}\left((h2)k+n+2tj\right)r_{k+jt}\pi _{h1,0,t}$$
(56)
for $`h1`$, and the initial conditions

$$\pi _{00j}=\{\begin{array}{cc}1\hfill & \text{if }j=0,\hfill \\ 0\hfill & \text{if }j1.\hfill \end{array}$$
(57)
Comparing (56) and (57) with (23) and (24), we see that $`\pi _{h0j}=\overline{c}_{hj}`$ for all $`h,j`$ such that $`h0`$ and $`0je(k,n)`$. For $`a`$, $`h0`$ let $`\overline{P}_a(h)=_{i=1}^h((i2)k+n+a)`$ denote the image of $`P_a(h)`$ in $``$. Since $`pk`$ we have $`\overline{P}_a(p1+b)=0`$ for $`b1`$, and $`\overline{P}_a(p1)0`$ if and only if $`n2ka(modp)`$. Suppose $`0j<e(k,n)`$. Then by Corollary 9 we have $`\varphi _{jab}S_{p1,k_01}`$ for all $`a,b0`$. Since $`k_0<p`$ the reduction map $`\rho `$ extends to a map $`\stackrel{~}{\rho }:S_{p1,k_01}[r_k^1]`$. Applying $`\stackrel{~}{\rho }`$ to (26) we get

$$\pi _{p1,0,j}=r_k^{p1}\underset{a=0}{\overset{j}{}}\underset{b=0}{\overset{j}{}}\overline{\varphi }_{jab}\overline{P}_a(p1+b).$$
(58)
The terms $`\overline{P}_a(p1+b)`$ in the sum are all zero, except those with $`b=0`$ and $`n2ka(modp)`$. In this case we would have $`a=e(k,n)`$, which contradicts the assumption $`j<e(k,n)`$. Thus $`\pi _{p1,0,j}=0`$ for $`0j<e(k,n)`$, which proves (54).

To prove (55), we first observe that if $`n2ki(modp)`$ for some $`0ik_0`$ then $`e(k,n)=i`$ and $`\pi _{p1,e,e}=\overline{P}_e(p1)r_k^{p1}0`$. Hence $`\sigma (\pi _{p1,e,e})=\overline{P}_e(p1)0`$ for any $`\sigma :𝔽_p`$ such that $`\sigma (r_k)=1`$. If $`n2ki(modp)`$ for all $`0ik_0`$ then $`e(k,n)=k_0`$. By Lemma 7 we have

$$c_{p1,k_0}=r_k^{p1}\underset{a=0}{\overset{k_0}{}}\underset{b=0}{\overset{k_0}{}}\varphi _{k_0ab}P_a(p1+b).$$
(59)
We will show that all but two of the terms in (59) have image zero under $`\stackrel{~}{\rho }`$. Let $`0a,bk_0`$ be such that $`(a,b)(0,1)`$ and $`(a,b)(k_0,0)`$. Then $`\overline{P}_a(p1+b)=0`$, and by Corollary 9 we have $`\varphi _{k_0ab}S_{p1,k_01}`$. Therefore $`\overline{\varphi }_{k_0ab}=\stackrel{~}{\rho }(\varphi _{k_0ab})`$ is defined and $`\overline{\varphi }_{k_0ab}\overline{P}_a(p1+b)=0`$.

It remains to consider the terms $`\varphi _{k_001}P_0(p)`$ and $`\varphi _{k_0k_00}P_{k_0}(p1)`$ in (59). It follows from (37) and the previous paragraph that $`\varphi _{k_0k_00}=\varphi _{k_001}P_0(1)+\gamma `$ for some $`\gamma S_{p1,k_01}`$. Therefore we have

$$\varphi _{k_001}P_0(p)+\varphi _{k_0k_00}P_{k_0}(p1)=\varphi _{k_001}(P_0(p)P_0(1)P_{k_0}(p1))+\gamma P_{k_0}(p1).$$
(60)
We wish to expand (60) in powers of $`Kk_0`$. Let $`Q=_{i=1}^p((i2)k_0+n)`$. Then we have the following expansions modulo $`(Kk_0)^2`$:

$`P_0(p)`$ $`Q+Q\left({\displaystyle \frac{1}{k_0+n}}+{\displaystyle \underset{h=0}{\overset{p2}{}}}{\displaystyle \frac{h}{hk_0+n}}\right)(Kk_0)`$ (61)
$`P_0(1)P_{k_0}(p1)`$ $`Q+Q\left({\displaystyle \frac{1}{k_0+n}}+{\displaystyle \underset{h=0}{\overset{p2}{}}}{\displaystyle \frac{h1}{hk_0+n}}\right)(Kk_0)`$ (62)
$`P_0(p)P_0(1)P_{k_0}(p1)`$ $`\left({\displaystyle \underset{h=0}{\overset{p2}{}}}{\displaystyle \frac{Q}{hk_0+n}}\right)(Kk_0).`$ (63)
Since $`pk_0`$ and $`nk_0(modp)`$, there is a unique $`0h_0p2`$ such that $`ph_0k_0+n`$. Then $`Q^{}=Q/(h_0k_0+n)`$ is the unique term of the sum in (63) which is not divisible by $`p`$. Since $`\overline{P}_{k_0}(p1)=0`$, it follows from Corollary 10 that the image of (60) in $``$ is $`\overline{Q}^{}\overline{q}_{k_0}`$. Therefore by (59) we get $`\pi _{p1,0,k_0}=\overline{c}_{p1,k_0}=\overline{Q}^{}r_k^{p1}\overline{q}_{k_0}`$, with $`\overline{Q}^{}𝔽_p^\times `$. Let $`\sigma :𝔽_p`$ be a specialization such that $`\sigma (r_i)=0`$ for $`k<i<k+k_0`$. Then $`\sigma (r_k^{p1}\overline{q}_{k_0})=\sigma (r_k^{p2}r_{k+k_0})`$, so by choosing $`\sigma `$ so that $`\sigma (r_k)=\sigma (r_{k+k_0})=1`$ we get $`\sigma (\pi _{p1,0,k_0})=\overline{Q}^{}0`$. This proves (55). $`\mathrm{}`$

###### Case 4

Theorem 1 holds if $`n(p1)k+p`$, $`pk`$, and $`e(k,n)k`$.

Proof: If $`e(k,n)k`$ then $`e(k,n)=k=k_0`$. To compute the necessary coefficients of $`𝐮_h(x)`$ we need to consider the expansions (50)–(52) modulo $`x^{(h+1)k+n+2}`$. In this higher-order expansion (50) and (52) acquire the additional term

$$\left(\genfrac{}{}{0pt}{}{(h1)k+n+1}{2}\right)x^{(h+1)k+n+1}\alpha (x)^2\beta (x).$$
(64)
To account for this extra term the matrix $`A_h`$ must be replaced by the upper triangular matrix $`A_h^{}\mathrm{M}_{(k+1)\times (k+1)}()`$ whose $`(i,j)`$ entry for $`0i,jk`$ is

$$a_{hij}^{}=\{\begin{array}{cc}a_{h0k}+\left(\genfrac{}{}{0pt}{}{(h1)k+n+1}{2}\right)r_k^2\hfill & \text{if }(i,j)=(0,k),\hfill \\ a_{hij}\hfill & \text{otherwise.}\hfill \end{array}$$
(65)
Consequently, $`\mathrm{\Pi }_h`$ is replaced by $`\mathrm{\Pi }_h^{}=A_1^{}A_2^{}\mathrm{}A_h^{}`$. An easy computation shows that there is $`m𝔽_p`$ such that

$$\pi _{p1,i,j}^{}=\{\begin{array}{cc}\pi _{p1,0,k}+mr_k^p\hfill & \text{if }(i,j)=(0,k),\hfill \\ \pi _{p1,i,j}\hfill & \text{otherwise.}\hfill \end{array}$$
(66)
Thus the first $`k`$ columns of $`\mathrm{\Pi }_{p1}^{}`$ are the same as those of $`\mathrm{\Pi }_{p1}`$. It follows by the reasoning in Case 3 that the first $`k`$ columns of $`\mathrm{\Pi }_{p1}^{}`$ are zero, and hence that Theorem 1(a) holds in this case. If $`n2ki(modp)`$ for some $`0ik`$ then $`\pi _{p1,k,k}^{}=\pi _{p1,k,k}`$, so there is a specialization $`\sigma `$ such that $`\sigma (\pi _{p1,k,k}^{})=\sigma (\pi _{p1,k,k})0`$ as in Case 3. If $`n2ki(modp)`$ for all $`0ik`$ then $`\pi _{p1,0,k}^{}=\overline{Q}^{}r_k^{p1}\overline{q}_k+mr_k^p`$. Let $`\sigma `$ be a specialization such that $`\sigma (r_i)=0`$ for $`k<i<2k`$. As in Case 3 we have $`\sigma (r_k^{p1}\overline{q}_{k_0})=\sigma (r_k^{p2}r_{2k})`$, and hence $`\sigma (\pi _{p1,0,k}^{})=\overline{Q}^{}\sigma (r_k^{p2}r_{2k})+m\sigma (r_k^p)`$. By choosing $`\sigma `$ so that $`\sigma (r_k)=1`$ and $`\sigma (r_{2k})`$ is either 0 or 1 we get $`\sigma (\pi _{p1,k,k}^{})0`$. Therefore Theorem 1(b) holds in this case. $`\mathrm{}`$

In Case 1 we proved Theorem 1 for $`nk+k_0`$, and in Cases 2, 3, 4 we proved Theorem 1 for $`n(p1)k+p`$. It remains to prove Theorem 1 for intermediate values of $`n`$. Recall that $`𝐟(x)=x+r_kx^{k+1}+r_{k+1}x^{k+2}+\mathrm{}𝒩()`$. The map $`T_𝐟:𝒩()𝒩()`$ defined by $`T_𝐟(h(x))=h(𝐟(x))`$ induces a linear transformation on coefficient vectors $`(1,a_1,a_2,\mathrm{})`$ of elements of $`𝒩()`$ (see ). This linear transformation can be represented by right multiplication by an infinite matrix of the form $`I+M`$, where $`I`$ is the identity and $`M`$ is an upper triangular matrix whose diagonal entries are all 0. The rows and columns of $`I`$ and $`M`$ are indexed by positive integers, and for $`1i<j`$ the $`(i,j)`$ entry of $`M`$ is

$$m_{ij}=\underset{l_1+\mathrm{}+l_i=ji}{}r_{l_1}r_{l_2}\mathrm{}r_{l_i},$$
(67)
where by convention we set $`r_0=1`$ and $`r_l=0`$ for $`1l<k`$. In particular, we have $`m_{ij}=0`$ for $`ji<k`$. The formula (67) may be rewritten as

$$m_{ij}=\left(\genfrac{}{}{0pt}{}{i}{n_0,n_k,n_{k+1}\mathrm{},n_{ji}}\right)r_k^{n_k}r_{k+1}^{n_{k+1}}\mathrm{}r_{ji}^{n_{ji}},$$
(68)
where the sum is taken over nonnegative integers $`n_0,n_k,n_{k+1},\mathrm{},n_{ji}`$ such that

$`n_0+n_k+n_{k+1}+\mathrm{}+n_{ji}`$ $`=i`$ (69)
$`kn_k+(k+1)n_{k+1}+\mathrm{}+(ji)n_{ji}`$ $`=ji.`$ (70)
For $`h2`$ the $`(i,j)`$ entry of $`M^h`$ can be expressed in terms of the $`m_{ij}`$:

$$m_{ij}^{(h)}=\underset{i<b_1<\mathrm{}<b_{h1}<j}{}m_{ib_1}m_{b_1b_2}\mathrm{}m_{b_{h1}j}.$$
(71)
This formula allows us to compute the entries of the matrix $`(I+M)^p=I+M^p`$ which represents $`𝐟^p`$. We are particularly interested in $`m_{1j}^{(p)}`$, which for $`j2`$ is the coefficient of $`x^j`$ in $`𝐟^p(x)`$.

###### Lemma 12

Let $`d,i`$ be positive integers such that $`d<pk`$ and $`i(d+1k)/k`$. Then $`m_{i,i+d}=m_{i+p,i+p+d}`$.

Proof: Note that if $`n_k,n_{k+1},\mathrm{},n_d`$ are nonnegative integers such that

$$kn_k+(k+1)n_{k+1}+\mathrm{}+dn_d=d$$
(72)
then we have $`n_k+n_{k+1}+\mathrm{}+n_dd/k`$. Since $`i(d+1k)/k`$ this implies

$$i(n_k+n_{k+1}+\mathrm{}+n_d)\frac{d+1k}{k}\frac{d}{k}>1.$$
(73)
It follows that $`n_0=i(n_k+n_{k+1}+\mathrm{}+n_d)`$ is nonnegative. Hence by (68) we have

$$m_{i,i+d}=\left(\genfrac{}{}{0pt}{}{i}{n_0,n_k,n_{k+1},\mathrm{},n_d}\right)r_k^{n_k}r_{k+1}^{n_{k+1}}\mathrm{}r_d^{n_d},$$
(74)
where the sum is taken over nonnegative $`n_k,n_{k+1},\mathrm{},n_d`$ satisfying (72). For $`kjd`$ we have $`jn_jd<pkpj`$, and hence $`n_j<p`$. Therefore in characteristic $`p`$ the multinomial coefficient

$`\left({\displaystyle \genfrac{}{}{0pt}{}{i}{n_0,n_k,n_{k+1},\mathrm{},n_d}}\right)`$ $`={\displaystyle \frac{i!}{n_0!n_k!n_{k+1}!\mathrm{}n_d!}}`$ (75)
$`={\displaystyle \frac{i(i1)\mathrm{}(i(n_k+n_{k+1}+\mathrm{}+n_d1))}{n_k!n_{k+1}!\mathrm{}n_d!}}`$ (76)
is unchanged if we replace $`i`$ by $`i+p`$ and $`n_0`$ by $`n_0+p`$. It follows that (74) is also unchanged if we replace $`i`$ by $`i+p`$. $`\mathrm{}`$

###### Lemma 13

Let $`0t<n`$ and $`i2`$. Then there is a polynomial $`A`$ with coefficients in $`𝔽_p`$ such that

$$m_{i,i+n+t}=A(r_k,r_{k+1},\mathrm{},r_{n1})+ir_{n+t}+i\underset{w=0}{\overset{tk}{}}r_{n+w}m_{i1,i1+tw}.$$
(77)
Proof: We can write

$`m_{i,i+n+t}`$ $`={\displaystyle \underset{l_1+\mathrm{}+l_i=n+t}{}}r_{l_1}r_{l_2}\mathrm{}r_{l_i}`$ (78)
$`=A(r_k,r_{k+1},\mathrm{},r_{n1})+B(r_k,r_{k+1},\mathrm{},r_{n+t}),`$ (79)
where $`A`$ is the sum of the terms which depend only on $`r_k,r_{k+1},\mathrm{},r_{n1}`$, and $`B`$ is the sum of the remaining terms. Let $`r_{l_1}r_{l_2}\mathrm{}r_{l_i}`$ be a term of $`B`$. Then $`l_jn`$ for some $`j`$, so we have $`l_j=n+w`$ with $`0wt`$. Furthermore, since $`t<n`$, we have $`l_h<n`$ for all $`hj`$. Since there are $`i`$ possible values for $`j`$ we get

$$B(r_k,r_{k+1},\mathrm{},r_{n+t})=ir_{n+t}+i\underset{w=0}{\overset{t1}{}}r_{n+w}m_{i1,i1+tw}.$$
(80)
Since $`m_{i1,i1+tw}=0`$ for $`w>tk`$, the lemma follows. $`\mathrm{}`$

###### Proposition 14

Let $`s0`$ satisfy $`n>k+s`$ and $`pk>k+s`$. Then the coefficient of $`x^{1+s+n+(p1)k}`$ in $`𝐟^p(x)`$ can be written uniquely in the form

$$m_{1,1+s+n+(p1)k}^{(p)}=C_{ns}+E_{ns}^{(0)}r_n+E_{ns}^{(1)}r_{n+1}+\mathrm{}+E_{ns}^{(s)}r_{n+s},$$
(81)
with $`C_{ns}𝔽_p[r_k,r_{k+1},\mathrm{},r_{n1}]`$ and $`E_{ns}^{(w)}𝔽_p[r_k,r_{k+1},\mathrm{},r_{k+sw}]`$ for $`0ws`$. Furthermore, we have $`E_{n+p,s}^{(w)}=E_{ns}^{(w)}`$.

Proof: Set $`b_0=1`$ and $`b_p=1+s+n+(p1)k`$. By (71) we have

$$m_{1,1+s+n+(p1)k}^{(p)}=\underset{b_0<b_1<\mathrm{}<b_p}{}m_{b_0b_1}m_{b_1b_2}\mathrm{}m_{b_{p1}b_p}.$$
(82)
To prove the first statement it suffices to show that each term in the sum (82) can be expressed in the form of (81), i. e.,

$$m_{b_0b_1}m_{b_1b_2}\mathrm{}m_{b_{p1}b_p}=c+e^{(0)}r_n+e^{(1)}r_{n+1}+\mathrm{}+e^{(s)}r_{n+s},$$
(83)
with $`c𝔽_p[r_k,r_{k+1},\mathrm{},r_{n1}]`$ and $`e^{(w)}𝔽_p[r_k,r_{k+1},\mathrm{},r_{k+sw}]`$. If $`m_{b_0b_1}m_{b_1b_2}\mathrm{}m_{b_{p1}b_p}`$ lies in $`𝔽_p[r_k,r_{k+1},\mathrm{},r_{n1}]`$ then this is clear. If $`m_{b_0b_1}m_{b_1b_2}\mathrm{}m_{b_{p1}b_p}`$ depends on $`r_h`$ for some $`hn`$ then $`b_ib_{i1}k`$ for all $`1ip`$ and $`b_jb_{j1}=n+t`$ for some $`1jp`$ and $`t0`$. For $`ij`$ we have $`b_ib_{i1}k+st`$. Therefore $`ts`$ and $`m_{b_{i1}b_i}𝔽_p[r_k,r_{k+1},\mathrm{},r_{k+st}]`$. If $`j=1`$ then $`b_{j1}=b_0=1`$, and hence $`m_{b_0b_1}=m_{1,1+n+t}=r_{n+t}`$. In this case $`m_{b_0b_1}m_{b_1b_2}\mathrm{}m_{b_{p1}b_p}`$ can be written in the form (83) with $`c=0`$, $`e^{(t)}=m_{b_1b_2}\mathrm{}m_{b_{p1}b_p}`$, and $`e^{(w)}=0`$ for all $`wt`$. If $`j2`$ then $`b_{j1}2`$, and hence $`m_{b_{j1}b_j}`$ is given by Lemma 13. Therefore $`m_{b_0b_1}m_{b_1b_2}\mathrm{}m_{b_{p1}b_p}`$ can be written in the form (83), with $`e^{(w)}=0`$ for all $`wt`$ with $`w>tk`$. It follows that $`m_{1,1+s+n+(p1)k}^{(p)}`$ can be written in the form (81). The fact that $`C_{ns}`$ and $`E_{ns}^{(w)}`$ are uniquely determined follows from the assumption $`n>k+s`$.

To prove the last statement we observe that there is a one-to-one correspondence between the terms of (82) which don’t lie in $`𝔽_p[r_k,r_{k+1},\mathrm{},r_{n1}]`$ and the terms of the corresponding expansion of $`m_{1,1+s+n+p+(p1)k}^{(p)}`$ which don’t lie in $`𝔽_p[r_k,r_{k+1},\mathrm{},r_{n+p1}]`$. This correspondence is given by

$$m_{b_0b_1}\mathrm{}m_{b_{j1}b_j}\mathrm{}m_{b_{p1}b_p}m_{b_0b_1}\mathrm{}m_{b_{j1},b_j+p}\mathrm{}m_{b_{p1}+p,b_p+p},$$
(84)
where $`j`$ is determined by the condition $`b_jb_{j1}n`$. Set $`b_jb_{j1}=n+t`$ as above. It follows from Lemma 13 that for $`0wtk`$ the coefficient of $`r_{n+w}`$ in $`m_{b_{j1}b_j}`$ and the coefficient of $`r_{n+p+w}`$ in $`m_{b_{j1},b_j+p}`$ are both equal to $`b_{j1}m_{b_{j1}1,b_{j1}1+tw}`$, and that the coefficient of $`r_{n+t}`$ in $`m_{b_{j1}b_j}`$ and the coefficient of $`r_{n+p+t}`$ in $`m_{b_{j1},b_j+p}`$ are both equal to $`b_{j1}`$. In addition, since $`pk>k+s`$, Lemma 12 implies that $`m_{b_{i1}b_i}=m_{b_{i1}+p,b_i+p}`$ for $`i>j`$. It follows that $`E_{n+p,s}^{(w)}=E_{ns}^{(w)}`$ for $`0ws`$$`\mathrm{}`$

###### Case 5

Theorem 1 holds if $`k+k_0<n<(p1)k+p`$.

Proof: Choose $`n^{}`$ such that $`n^{}n(modp)`$ and $`n^{}(p1)k+p`$, and set $`e=e(k,n)=e(k,n^{})`$. It follows from Theorem 1(a) in Cases 2, 3, 4 and Remark 2 that $`E_{n^{}s}^{(w)}=0`$ for all $`s,w`$ such that $`0ws<e`$. It follows from Proposition 14 that $`E_{ns}^{(w)}=0`$ for $`0ws<e`$. Therefore by Remark 2 we see that Theorem 1(a) holds for $`n`$. It follows from Theorem 1(b) in Cases 2, 3, 4 that there is a specialization $`\sigma `$ such that $`\sigma (E_{n^{}e}^{(w)})0`$ for some $`0we`$. Using Proposition 14 we get $`\sigma (E_{ne}^{(w)})=\sigma (E_{n^{}e}^{(w)})0`$. Let $`\tau :𝔽_p`$ be a specialization such that $`\tau (r_i)=\sigma (r_i)`$ for $`in+w`$, and $`\tau (r_{n+w})\sigma (r_{n+w})`$. Since $`\tau (E_{ne}^{(w)})=\sigma (E_{ne}^{(w)})0`$, it follows from Proposition 14 that

$$D((𝐟^\tau )^p(𝐟^\sigma )^p)=n+(p1)k+e(k,n).$$
(85)
Therefore Theorem 1(b) holds for $`n`$. $`\mathrm{}`$

By combining Cases 1 through 5 we conclude that Theorem 1 holds for all $`nk1`$.

Acknowledgment: I would like to thank Professor Charles Leedham-Green for asking whether Theorem 1(b) is true.


format: text

text:
# Phase synchronization and topological defects in inhomogeneous media

## Abstract

The influence of topological defects on phase synchronization and phase coherence in two-dimensional arrays of locally-coupled, nonidentical, chaotic oscillators is investigated. The motion of topological defects leads to a breakdown of phase synchronization in the vicinities of the defects; however, the system is much more phase coherent as long as the coupling between the oscillators is strong enough to prohibit the continuous dynamical creation and annihilation of defects. The generic occurrence of topological defects in two and higher dimensions implies that the concept of phase synchronization has to be modified for these systems.

The rich collective behavior, including mutual entrainment and self-synchronization, seen in systems of coupled oscillators has been a stimulus for the long-standing interest in these systems (see, for example, Refs. Pikovsky et al. (2001); Strogatz (2000); Kuramoto (1984) and references therein). Recently, attention has turned to the study of coupled *chaotic* oscillators and, in particular, to the phenomenon of phase synchronization. Provided that the phase can be defined Pikovsky et al. (1997); Josić and Mar (2001), two coupled nonidentical chaotic oscillators are said to be phase synchronized if their frequencies are locked Rosenblum et al. (1996); Pikovsky et al. (2001). This appears to be a general phenomenon and it has been observed in such diverse systems as electrically coupled neurons Elson et al. (1998); Makarenko and Llinás (1998), biomedical systems Schäfer et al. (1998), chemical systems Kiss et al. (2002), and spatially extended ecological systems Blasius et al. (1999), to name only a few. Moreover, the potential role of phase synchronization in brain functions has been recognized Tass et al. (1998); Fitzgerald (1999).

Much of the theoretical analyses of phase synchronization have been carried out on systems consisting of two locally coupled oscillators Rosenblum et al. (1996) or many globally coupled oscillators Pikovsky et al. (1996). Large one-dimensional chains of locally coupled chaotic oscillators have been investigated very recently Liu et al. (2001); Zhang et al. (2001); Valladares et al. (2002). Here, we address the question whether phase synchronization can persist in higher spatial dimensions where topological defects can play a central role. We show that the existence of topological defects can lead to a breakdown of global phase synchronization in two-dimensional arrays of nonidentical chaotic oscillators. While most of the medium may remain phase synchronized, oscillators close to moving topological defects have a different frequency. Despite this fact, the phase coherence of the system is higher than in systems without topological defects. The transition to phase synchronization via phase clustering observed in one-dimensional systems Zheng et al. (1998); Liu et al. (2001) is not found in our simulations on two-dimensional systems; instead, a transition involving point defects occurs.

Point topological defects in two-dimensional *homogeneous* oscillatory media are associated with the appearance of spiral waves Kapral and Showalter (1996); Walgraef (1997); Mikhailov (1994). The phase field $`\varphi (𝐫,t)`$ of a medium with a spiral wave contains a point topological phase defect in the spiral core such that

$$\frac{1}{2\pi }\varphi (𝐫,t)𝑑𝐥=\pm n_t,$$
(1)
where $`n_t`$ is the topological charge of the defect Mernin (1979). A topological defect corresponds to a point in the medium where the local amplitude is zero and the phase is not defined. For periodic boundary conditions, the net topological charge of the medium is zero. For identical chaotic oscillators textchaos , spatially coherent spiral dynamics can still exist implying a phase locking of the oscillations Goryachev et al. (2000).

To illustrate the phase synchronization properties in two-dimensional networks of nonidentical chaotic oscillators, we consider an $`L\times L`$ array of locally coupled Rössler oscillators with periodic boundary conditions Rössler (1976),

$$\frac{𝐱(𝐫,t)}{t}=𝐑(𝐱(𝐫,t))+K\underset{\widehat{𝐫}N(𝐫)}{}\left(𝐱(\widehat{𝐫},t)𝐱(𝐫,t)\right),$$
(2)
where $`R_1=\omega (𝐫)x_2x_3`$, $`R_2=\omega (𝐫)x_1+0.2x_2`$, $`R_3=x_1x_35.9x_3+0.2`$. The sites of the lattice are labelled by $`𝐫`$, $`K`$ is the coupling constant and $`N(𝐫)`$ is the set of the four next nearest neighbors of site $`𝐫`$. The phase angles of the oscillators are given by $`\varphi (𝐫,t)=\mathrm{arctan}\frac{x_2(𝐫,t)}{x_1(𝐫,t)}`$. To obtain the results presented below, we take $`L=64`$ and choose the $`\omega (𝐫)`$’s randomly from a uniform distribution on the interval $`[0.95,1.05]`$, ensuring that the system is in the chaotic regime.

First, we consider $`K=K_00.1`$. For different initial conditions leading to stable patterns, basically two scenarios can be observed. For homogeneous initial conditions or initial conditions with small inhomogeneities, no topological defects are created and the system evolves to a target pattern similar to the one in Fig. 1 (left panel). In the case of larger inhomogeneities in the initial conditions, a number of topological defects with $`n_t=\pm 1`$ is created initially. Some pairs of topological defects with opposite charge are quickly annihilated until only a small number is left generating a spiral pattern similar to that in Fig. 1 (middle panel). The topological defects are not necessarily stationary and for very long times it is possible that all defects could disappear through further annihilation events; however, the motion of the surviving topological defects is very slow compared to the initial annihilation processes and no further annihilation events were observed on our long simulation time scale ($`10^4`$ \- $`10^5`$ spiral revolutions). These two scenarios persist provided $`K`$ is not too small.

When there are no topological defects, the system is phase synchronized. The occurrence of phase synchronization for coupled Rössler oscillators is usually attributed to the high degree of phase coherence of the attractor of a *single* Rössler oscillator Pikovsky et al. (2001) although this might not be a sufficient condition Josić and Mar (2001). Phase coherence means that $`(_{\mathrm{}}^{\mathrm{}}𝑑\tau \eta (t)\eta (t+\tau )_t)^{1/2}\omega _0`$, where $`d\stackrel{~}{\varphi }/dt=\omega _0+\eta (t)`$, $`\stackrel{~}{\varphi }`$ is the unbounded phase and $`\mathrm{}_t`$ signifies an average over $`t`$. If $`\eta `$ is $`\delta `$-correlated Gaussian noise this condition reduces to $`\sigma \omega _0`$ and corresponds to a very narrow peak of width $`\sigma ^2`$ at $`\omega _0`$ in the power spectrum of $`x_1(t)`$. However, generally temporal correlations in $`\eta `$ exist. These correlations determine the speed of convergence of the time average $`\overline{\omega }(T)=T^1(\stackrel{~}{\varphi }(T)\stackrel{~}{\varphi }(0))`$ towards $`\omega _0`$. For the system of coupled Rössler oscillators considered here, the speed of convergence — as measured by the standard deviation of the ensemble distribution of $`\overline{\omega }(T)`$ — scales as $`1/T`$ as shown in Fig. 2. This is in contrast to what one would expect if the $`\eta `$ variables were independent where one obtains $`1/\sqrt{T}`$ scaling since $`\overline{\omega }(T)\omega _0=1/T_0^T𝑑t\eta (t)`$ and the standard deviation of $`_0^T𝑑t\eta (t)`$ scales with $`\sqrt{T}`$. The observed variation with $`T`$ is much faster, implying an extremely high degree of phase coherence, even in the coupled system. The origin of this effect resides in the shape of the local attractors. They are two-banded with distinct frequencies $`\omega _1`$ and $`\omega _2`$ such that $`\omega _0=(\omega _1+\omega _2)/2`$. Moreover, each deviation from $`\omega _1`$ is followed by a deviation from $`\omega _2`$ of similar amplitude but with opposite sign, and vice versa. Hence, the deviations of $`\overline{\omega }(T)`$ from $`\omega _0`$ should be dominated by the switching between the bands for not too large values of $`T`$. Thus, the maximal deviation from $`\omega _0`$ is given by the term $`(\omega _1\omega _2)/(2T)`$, reproducing the observed scaling. The two-banded structure can also be found in the ensemble distribution of $`\overline{\omega }(T)`$. There, two distinct peaks can be seen for certain $`T`$ values consistent with the fluctuations around the $`1/T`$ scaling in Fig. 2.

If topological defects are present global phase synchronization is no longer guaranteed. Since a topological defect corresponds to a point in the system where a phase variable cannot be defined, this implies that the concept of phase synchronization can only be applied to parts of the system which exclude topological defects. For *discrete* lattices of oscillators considered here, this does not pose any problems because the defect is located almost surely *between* lattice sites. Thus, the presence of topological defects does not exclude global phase synchronization *a priori*. We indeed observe phase synchronization for quasi-stationary topological defects which explains the occurrence of phase synchronization in the presence of topological defects described in Ref. Zhou and Kurths (2002). However, the motion of topological defects destroys phase synchronization locally. As shown in Fig. 3, the motion of a topological defect leads to a distortion of nearby local orbits. This in turn influences their local frequencies such that the system is no longer phase synchronized as can be deduced from the corresponding $`\omega _0`$ distribution in Fig. 4 text . In particular, the “outliners” in this distribution are located in the vicinity of the topological defect(s).

For homogeneous oscillatory media it is well known that the time scales for the motions of topological defects depend on the system parameters, ranging from very slow motion to rapid dynamics Aranson and Kramer (2002). Inhomogeneity provides another mechanism for defect motion and, in the present case of a network of non-identical Rössler oscillators, this is the dominant mechanism. For a network of identical Rössler oscillators, the topological defects are quasi-stationary on the time scales considered here; thus, the observed breakup of global phase synchronization for this system is due to the quenched disorder in the network.

Although global phase synchronization is lost in the presence of moving topological defects, the fluctuations of the instantaneous period in the medium are greatly reduced. While the phase coherence criterion, $`(_{\mathrm{}}^{\mathrm{}}𝑑\tau \eta (t)\eta (t+\tau )_t)^{1/2}\omega _0`$, is satisfied to a high degree of accuracy as in the case without topological defects, the average amplitude of the fluctuations in the instantaneous periods $`T(𝐫,n)=2\pi /\omega (𝐫,n)`$ as measured by $`SS(𝐫)_𝐫_\omega `$ with

$$S(𝐫)=\frac{T(𝐫,n)_n}{\sqrt{(T(𝐫,n)T(𝐫,n)_n)^2_n}},$$
(3)
are significantly different. Here, $`T(𝐫,n)`$ is the time needed for the $`n`$th rotation at site $`𝐫`$ and $`\mathrm{}_\omega `$ is the average over all realizations of $`\omega (𝐫)`$. Figure 5 (left panel) shows that the value of $`S`$ is much larger above a certain coupling $`K_c`$ when (more) topological defects are present in the system, corresponding to a higher degree of coherence. An analysis of $`S(𝐫)`$ shows that high values exist, especially in the vicinity of quasi-stationary topological defects (see right panel of Fig. 5). This is due to the influence of topological defects on the shapes of the local orbits: they are close to periodic limit cycles. This is in accord with observations in Goryachev and Kapral (1996) for identical oscillators although the “effective” spatial period doubling cascade found there is absent in the present case.

The system maintains memory of its initial condition above $`K_c0.043`$ leading to the different values of $`S`$. For single $`\omega (𝐫)`$ realizations, different scenarios, with either no defects or with defects present, can be observed for $`K_0>K>K_c`$ text2 . For $`K`$ below $`K_c`$, however, a qualitatively new behavior occurs. Topological defects are now generated and annihilated continuously by the dynamics which is responsible for the loss of memory of the initial condition. The number of topological defects fluctuates around a mean value which increases with decreasing $`K`$. This is expected because $`K`$ should control the characteristic length scale in the system. Moreover, the topological defects move on average much faster than above $`K_c`$, similar to defect mediated turbulence Coullet et al. (1989). The creation and annihilation of topological defects as well as the fast motion lead to strong distortion of the local orbits affected by the moving defects . This makes it impossible to define a proper phase variable for most of the oscillators in the network. Consequently, the concept of phase synchronization can no longer be applied.

In Refs. Zheng et al. (1998); Liu et al. (2001), the transition to phase synchronization via the route of phase clustering and merging of clusters was investigated for chains of oscillators. Liu, et al. Liu et al. (2001) concluded that phase clustering should be more prevalent than full phase synchronization, especially in networks of coupled neurons. However, the two-dimensional system considered here shows a different behavior for increasing $`K`$ starting from a value below $`K_c`$. We observe a transition from a state where topological defects are generated continuously by the dynamics to a partial phase synchronized state with moving topological defects, similar to the case with surviving point defects. This partial phase synchronized state is characterized by a large number of phase synchronized oscillators and a small number of oscillators close to the point defects with mutually different frequencies. Thus, only one cluster with more than one oscillator exists in contrast to the chain geometry. The existence of topological defects in two dimensions and higher dimensions suggests that the transition described here should be prevalent for general networks of chaotic oscillators.

We have shown that the occurrence of topological defects in two-dimensional arrays of nonidentical chaotic oscillators has a two-fold effect: moving topological defects lead to a breakup of global phase synchronization, while all topological defects — especially quasi-stationary ones — increase the phase coherence of the system significantly. Since moving and quasi-stationary topological defects are present in many circumstances, the apparently contradictory scenario of increased phase coherence but loss of global phase synchronization occurs.

###### Acknowledgements.

This work was supported in part by a grant from the Natural Sciences and Engineering Research Council of Canada. We thank G. Rousseau for providing the numerical integrator.


text:
# Searching for Hydrogen in Type Ib Supernovae, and for Helium and Hydrogen in Type Ic

## 1. Introduction

Type Ia supernovae are thought to be nuclear–powered disruptions of accreting or merging white dwarfs. Most if not all other supernovae (SNe) are thought to involve expulsion of the envelopes of massive stars following the gravitational collapse of their highly evolved cores. Of these, Type II SNe have conspicuous features due to hydrogen in their optical spectra. Type Ib SNe lack conspicuous hydrogen features but have conspicuous He I features during their photospheric phase. In the spectra of Type Ic SNe, neither hydrogen nor He I features are conspicuous. For reviews of SN classification see Filippenko (1997) and Turatto (2002).

The optical spectrum of a typical SN II evolves from a nearly featureless continuum when the temperature is high to one that contains mainly hydrogen features and then gradually develops features of lower excitation due to Ca II, Fe II, O I, Na I, and Ti II, plus Ba II and Sr II if the temperature gets sufficiently low. Apart from the defining differences involving the hydrogen and He I features, the spectra of SNe Ib and SNe Ic evolve in much the same way.

Among the questions that those who make explosion models of SNe Ib and SNe Ic would like spectroscopists to answer include two very basic ones. Do SNe Ib eject any hydrogen? And do SNe Ic eject any helium — and perhaps even some hydrogen? I will be able to provide only partial and tentative answers to these questions — but I should at least be able to explain why they are so hard to answer.

## 2. Direct Analysis of Supernova Spectra

First we must say something about the analysis of SN spectra. One nice thing is that the simple explosion velocity law — velocity proportional to radius — ordinarily is an excellent approximation. One big problem is that ejection velocities usually are high, so spectral features are blended and the amount of information that can be obtained by analyzing the spectra with a ruler is limited. Consequently, much use is made of synthetic spectra. The use of synthetic spectra for SNe has been reviewed by Branch, Baron, & Jeffery (2002). Detailed and physically self–consistent NLTE synthetic spectra can and have been carried out with very complex codes, notably the PHOENIX code, but so far nearly all such work has been for SNe Ia and SNe II. At the other extreme, of simplicity, the fast parameterized SYNOW code is useful for establishing line identifications and placing constraints on the velocity intervals in which the line–contributing ions are detected. We refer to this process as “direct analysis” to distinguish it from detailed spectrum synthesis with more complicated codes. The synthetic spectra shown in this article have been generated with SYNOW.

SYNOW assumes spherical symmetry, velocity proportional to radius, and a sharp photosphere that emits a blackbody continuum. Line formation, treated in the Sobolev approximation, occurs only by resonance scattering of photons from the photosphere. The effects of multiple scattering (line blending) on the line source functions and the emergent spectrum are treated exactly, within the context of the model and the Sobolev approximation. In the synthetic spectra shown in this article, line optical depths are taken to decrease as $`v^8`$. For each ion whose lines are introduced, the optical depth of a “reference line” at the photosphere is a fitting parameter, and the optical depths of the other lines of the ion are determined by assuming LTE level populations at some excitation temperature $`T_{exc}`$, which for the synthetic spectra of this article is 7000 K. Oscillator strengths are Kurucz (1993). Line formation ordinarily takes place immediately above the photosphere, i.e., the lower boundary of the line–forming layer has the velocity at the photosphere, $`v_{phot}`$. But sometimes it is appropriate to “detach” the lines of an ion by allowing line formation only above some detachment velocity that exceeds $`v_{phot}`$.

An undetached resonance–scattering line has a P Cygni profile consisting of a rounded emission component that peaks at the rest wavelength, and an absorption component whose minimum is blueshifted by the amount that corresponds to $`v_{phot}`$ (or more if the line is strong). A detached resonance–scattering line also has a P Cygni profile but the emission component has a flat top, and the absorption minimum is blueshifted by the amount that corresponds to the detachment velocity. The absorption component of a detached line is deeper than that of an undetached line that has the same maximum Sobolev optical depth (Jeffery & Branch 1990; Branch et al. 2002).

## 3. SNe IIb

Before discussing SNe Ib we must mention SNe IIb — events in which hydrogen features are conspicuous at early times but later become weak or undetectable. The first well observed example was SN 1993J in M81 (Matheson et al. 2000 and numerous references therein). Conspicuous hydrogen features were present at early times, but conspicuous He I features began to appear around 25 days after explosion; later the hydrogen features became weak. The minimum velocity of the hydrogen–containing layer was about 9000 km s-1. Most estimates of the mass of this layer have been in the range 0.1 to 0.6 M; the hydrogen mass was lower because much of the mass of this layer probably was in the form of helium. In SN 1996cb, the second well observed SN IIb (Qiu et al. 1999), He I features appeared earlier, before maximum light, but a deep H$`\alpha `$ absorption persisted throughout the photospheric phase. The minimum velocity and mass of the hydrogen–containing layer were about 10,000 km s-1 and perhaps $`0.1`$ M (Deng, Qiu,& Hu, 2002).

## 4. Hydrogen in SNe Ib?

Until recently not much work had been done on searching for hydrogen in SNe Ib. Branch (1972) considered H$`\alpha `$, as well as the strongest optical line of Ne I, $`\lambda `$6402, as possible identifications of a deep absorption in SN 1954A. Wheeler et al. (1994) tentatively attributed a weak absorption in SNe 1983N and 1984L to H$`\alpha `$, as did Deng et al. (2000) in SN 1999dn. An opportunity to study this issue more systematically was presented by Matheson et al. (2001, hereafter M01) who published spectra of a number of SNe Ib (and SNe Ic) that were observed at the Lick Observatory during the 1990s.

Recently the SYNOW code has been used to study the spectra of 11 SNe Ib selected on the basis of having deep optical He I absorptions (Branch et al. 2002, hereafter B02). As had been emphasized by M01, from whom much of the data of the B02 sample were taken, in most respects the spectra of these events were quite homogeneous. The velocity at the photosphere, as inferred from Fe II features near 5000 Å, decreased smoothly from about 11,000 km s-1 at the time of maximum light to about 5000 km s-1 50 days later, with little scatter. In postmaximum spectra the He I absorptions generally were detached, with the detachment velocity ending up at about 7000 km s-1.

Two events in the B02 sample, SNe 1999di and 2000H, differed from the others by containing deep, persistent absorptions near 6300 Å that resembled the deep H$`\alpha `$ absorption in the Type IIb SN 1996cb. It is safe to identify the 6300 Å absorptions in these two SNe Ib as H$`\alpha `$, detached at 12,000 or 13,000 km s-1, because there is no plausible alternative identification that would not entail unwanted features in the spectrum, and because weak absorptions consistent with H$`\beta `$ could be seen. SN 1954A, for which of course only photographic spectra are available, appears to have been similar. I will refer to these events as “deep–H$`\alpha `$” SNe Ib. They are classified as Type Ib because when they were first observed the presence of hydrogen features was not obvious, even though their H$`\alpha `$ absorptions were deep. The explanation, illustrated in Figure 24 of B02, is that because the hydrogen lines were detached, the H$`\alpha `$ emission components that we are accustomed to seeing in SNe II were flat and therefore inconspicuous, and the deep H$`\alpha `$ absorptions were produced with sufficiently small H$`\alpha `$ optical depths that the other Balmer lines were too weak to be conspicuous. (The Sobolev optical depth of H$`\beta `$ is lower than that of H$`\alpha `$ by a factor of 7.) If these events had been observed earlier their hydrogen features might have been stronger, undetached, and conspicuous, as in the earliest spectra of SN 1996cb, in which case these events would have been classified as SNe IIb.

Among the eight other events of the B02 sample, four (SNe 1983N, 1984L, 1996N, and 1999dn) were first observed earlier than 10 days after maximum light and they also had absorptions near 6300 Å, but less deep than in the deep–H$`\alpha `$ events. I will refer to these as typical SNe Ib. In Figure 1 a spectrum of SN 1984L is compared with a synthetic spectrum. B02 attributed the 6300 Å absorption in typical SNe Ib to H$`\alpha `$, detached at 18,000 km s-1 in the earliest available spectrum and at 12,000 or 13,000 km s-1 when it was last observed. The identification was tentative, however, because H$`\beta `$ could not be seen, and there are other possible line identifications for the 6300 Å absorption. The strongest optical line of C II, $`\lambda `$6580, would need to be detached only 800 km s-1 more than H$`\alpha `$, but highly detached C II lines would be surprising in SNe Ib. The strongest optical line of Si II, $`\lambda `$6355, would need to be blueshifted 9500 km s-1 less than H$`\alpha `$, which is a problem because it would require the Si II feature to form in deeper layers than the Fe II features. A more plausible alternative to H$`\alpha `$ is Ne I $`\lambda `$6402, which would need to be blueshifted 7400 km s-1 less than H$`\alpha `$; this would put it right at the same velocity as the Fe II lines. The Ne I lines would need to be nonthermally excited, as are the He I lines of SNe Ib. When Fe II features become strong they also can produce a feature that could be mistaken for highly blueshifted H$`\alpha `$ (see below), but in these four SNe Ib the Fe II features were not strong enough around the time of maximum. The best choices for the 6300 Å absorption in typical SNe Ib seem to be detached H$`\alpha `$ or undetached Ne I $`\lambda `$6402.

Only very recently has it become clear that some events have optical He I absorptions that are definite but not as deep as in typical SNe Ib. I will refer to these as “shallow–helium” SNe Ib. One of these, SN 1991D (Benetti et al. 2002), deviates from typical SNe Ib in other respects too. It was exceptionally luminous for a SN Ib; 10 days after maximum light the velocity at the photosphere inferred from the Fe II features was only 5000 km s-1 as opposed to 8000 km s-1 for typical SNe Ib; and at the same epoch the He I lines were not detached from the 5000 km s-1 photosphere whereas in typical SNe Ib they are detached at about 10,000 km s-1. SN 1991D contained a weak 6300 Å absorption that can be accounted for by H$`\alpha `$ detached at 12,000 km s-1, but in SYNOW synthetic spectra not only did Ne I $`\lambda `$6402 provide a nice fit to this feature, other Ne I lines did more good than harm (Figure 3 of Benetti et al.). Ne I $`\lambda `$6402 appears to be a serious alternative to H$`\alpha `$ in SN 1991D.

Hamuy et al. (2002) have presented spectra of another shallow–helium SN Ib, SN 1999ex. In this case the Fe II velocity evolution does conform to that of typical SNe Ib. The depth of the 6300 Å absorption of SN 1999ex was in between those of typical and deep–H$`\alpha `$ SNe Ib. Hamuy et al. labelled the 6300 Å absorption as Si II but this identification encounters the problem mentioned above. In Figure 2 a spectrum of SN 1999ex is compared with a synthetic spectrum in which the 6300 Å absorption is produced by H$`\alpha `$, detached at 15,000 km s-1. Undetached Ne I $`\lambda `$6402 also can fit the 6300 Å absorption fairly well but because it needs to be rather strong the other Ne I lines cause problems. H$`\alpha `$ appears to be the most likely identification in SN 1999ex.

## 5. Helium in SNe Ic?

In the past, two lines of evidence have been offered for the presence of He I features in SNe Ic, but both are difficult to confirm. First, in SN 1994I, the best observed SN Ic (other than hypernovae), Filippenko et al. (1995) observed a strong absorption near 1 $`\mu `$m that was attributed to He I $`\lambda `$10830. However, when we (Millard et al. 1999) carried out a SYNOW analysis of SN 1994I, we were unable to account for the bulk of the 1 $`\mu `$m absorption with $`\lambda `$10830 without also producing optical He I features that were too strong. We concluded that the 1 $`\mu `$m absorption may have been produced at least in part by C I $`\lambda `$10695 and/or blends of Si I lines. Baron et al. (1999) carried out detailed spectrum calculations with the PHOENIX code and also had problems accounting for the 1 $`\mu `$m feature in terms of $`\lambda `$10830 alone.

The observations of the Type Ib SN 1999ex by Hamuy et al. (2002) clarify this issue. Hamuy et al. obtained good infrared spectra of SN 1999ex, and as expected from the presence of definite optical He I features, the infrared spectra contained P Cygni profiles due to He I $`\lambda `$10830 and $`\lambda `$20581. (In LTE the Sobolev optical depth of $`\lambda `$10830 exceeds that of He I 5876 by a factor of 7 at 10,000 K and 4.5 at 15,000 K.) However, even though SN 1999ex had definite optical He I lines, its $`\lambda `$10830 feature was weaker than the 1 $`\mu `$m feature in SN 1994I, which had less distinct, if any, optical He I features. It is interesting that in SN 1999ex, unlike in SN 1994I, a SYNOW synthetic spectrum that fits the $`\lambda `$10830 feature also fits the optical He I features reasonably well. This supports the suspicion that the 1 $`\mu `$m absorption in SN 1994I was not mainly due to He I $`\lambda `$10830 — and if it wasn’t mainly due to He I then it doesn’t provide convincing evidence for the presence of helium at all.

The second line of evidence for He I features in SNe Ic has been the identification of weak absorptions in optical spectra with high–velocity He I lines, detached at about 17,000 km s-1 (Clocchiatti et al. 1996). However, M01 reexamined the evidence and were unable to confirm these identifications. One problem was that the absorption attributed to detached He I $`\lambda `$6678 usually is substantially more blueshifted than those attributed to $`\lambda `$5876 and $`\lambda `$7065. M01 also mentioned that the typical Type Ib SN 1999dn, whose deep He I absorptions were at low velocity, contained a weak absorption like the one that Clocchiatti et al. attributed to high–velocity $`\lambda `$5876 in SNe Ic. In fact, that feature often appears in spectra of core–collapse SNe, including the Type II SN 1987A (Jeffery & Branch 1990), when the temperature is low enough for lines of singly ionized iron–peak elements to be strong. It is produced by a group of Sc II lines from $`\lambda `$5641 to $`\lambda `$5684.

Being unpersuaded by the first two lines of evidence for He I in SNe Ic, we consider a third. After failing to confirm high–velocity He I absorptions in SNe Ic, M01 mentioned that in the Type Ic SN 1990B, if He I absorptions were present at all, they were at low velocity. Clocchiatti et al. (2001) also considered the possibility of low–velocity He I in SN 1990B. In Figure 3 a spectrum of SN 1990B is compared with a synthetic spectrum that contains undetached He I lines. Note that because Fe II features are quite strong, they account nicely for the 6300 Å absorption. He I $`\lambda `$5876 accounts for an observed absorption, but of course that observed feature could be Na I instead. More important is that the observed absorption near 6800 Å is accounted for by undetached He I $`\lambda `$7065, and I’m not aware of any good alternative for undetached $`\lambda `$7065; neither a line of similar wavelength nor a line of longer wavelength that could be detached and mistaken for undetached $`\lambda `$7065. An obvious problem is that there is no counterpart in the observed spectrum for the synthetic absorption produced by $`\lambda `$6678, but this is not necessarily fatal for He I. First, M01 showed that in SNe Ib $`\lambda `$6678 gradually weakens relative to $`\lambda `$5876 and $`\lambda `$7065; this is to be expected on the grounds of NLTE calculations (Lucy 1991; Swartz et al. 1993) because $`\lambda `$6678 is a singlet transition while $`\lambda `$5876 and $`\lambda `$7065 are triplets, and the singlet resonance transition to the ground state becomes less opaque as the ejecta density decreases through expansion. It follows that the use of LTE excitation in SYNOW can overestimate the strength of $`\lambda `$6678 relative to $`\lambda `$5876 and $`\lambda `$7065. Second, in SN 1990B the $`\lambda `$6678 absorption would be partially filled in by the H II–region H$`\alpha `$ emission seen in the spectrum, and possibly also by H$`\alpha `$ emission from SN 1990B itself (see §6).

Another reason to take low–velocity He I in SNe Ic seriously is that the early spectra of SN 1994I contained an absorption feature that we (Millard et al. 1999) attributed to Na I $`\lambda `$5892. But at these early times the color temperature was high — $``$17,000 K in the spectrum obtained four days before maximum brightness. The presence of Na I absorption at such a high temperature is doubtful. In SN 1987A, for example, Na I began to appear only when the color temperature fell to about 6000 K (Jeffery & Branch 1990). In the early spectra of SN 1994I even the Ca II absorptions were not yet very strong. The observed feature may have been produced by undetached He I $`\lambda `$5876 rather than Na I.

During the course of an ongoing comparative study of spectra of SNe Ic, similar to that of B02 for SNe Ib, it has become clear that absorptions that can be attributed to undetached He I $`\lambda `$5876 and $`\lambda `$7065 are common in the early spectra of SNe Ic, and sometimes a weak absorption consistent with $`\lambda `$6678 also is present.

## 6. Hydrogen in SNe Ic?

In the past, two lines of evidence for the presence of H$`\alpha `$ in SNe Ic also have been presented, but again confirmation is difficult. Filippenko, Porter, & Sargent (1990) and Jeffery et al. (1991) tentatively attributed a weak absorption near 6360 Å in SN 1987M to H$`\alpha `$, but as emphasized by Wheeler et al. (1994) the required blueshift of H$`\alpha `$ was suspiciously low compared to those of other lines in the same spectrum. In any case, the absorption in question is unusual, perhaps even unique so far; it is not the same as the broader feature that is commonly referred to as the 6300 Å absorption, which ordinarily appears at a wavelength roughly consistent with undetached Ne I $`\lambda `$6402 (whether Ne I is the right identification or not). The 6360 Å absorption in SN 1987M is farther to the red.

More intriguing is that Filippenko (1988, 1992) pointed out that SNe Ic have a broad emission peak near the wavelength of H$`\alpha `$. We must be careful about attributing this feature to H$`\alpha `$ emission when the Fe II features are strong — but it appeared even in the pre–maximum spectra of SN 1994I, when the Fe II features were not yet strong. It is indeed tempting to attribute this feature to H$`\alpha `$. The H$`\alpha `$ would need to be in net emission (as it often is in SNe II), and to produce the rounded emission peak the H$`\alpha `$ would need to be undetached.

## 7. Discussion

So — do SNe Ib eject hydrogen? Yes, the deep–H$`\alpha `$ events certainly do; they appear to be closely related to SNe IIb. In fact, the differences between SNe IIb and the deep–H$`\alpha `$ SNe Ib can be so small that the classification of some events probably depends on how early the first spectrum is obtained. \[In the nomenclature of Clocchiatti & Wheeler (1997) the deep–H$`\alpha `$ events could be included among the “transition supernovae”, SNe IIt.\]

Whether typical SNe Ib eject hydrogen is much more difficult to decide. Given the strong similarities between the deep–H$`\alpha `$ and typical SNe Ib (B02), the most natural assumption would seem to be that the 6300 Å absorption in typical SNe Ib also is produced by H$`\alpha `$. This is supported by the probable presence of intermediate–strength 6300 Å absorption in the shallow–helium SN 1999ex. On the other hand, nonthermally excited Ne I lines are not implausible, and because Ne I $`\lambda `$6402 would not need to be detached it would require one fewer free parameter (the detachment velocity of H$`\alpha `$). The 6300 Å absorption tends to drift redward with time like the other features; this may seem to favor undetached Ne I, but it is not decisive since the detached He I lines in SNe Ib also drift to the red. (B02 offer an explanation.) How are we to decide about the H$`\alpha `$ identification? The most direct confirmation would be to detect Paschen–alpha (P$`\alpha \lambda `$18751), but in LTE its Sobolev optical depth is lower than that of H$`\alpha `$ by a factor of 34 at 5000 K and 3.4 at 10,000 K, so this may not work. A larger sample of high quality optical spectra of typical SNe Ib will allow the following test to be applied: if the 6300 Å feature always is consistent with undetached Ne I, then it probably is Ne I, because it would be hard to believe that hydrogen always is detached by the same amount with respect to the velocity at the photosphere. The current data are inconclusive on this point.

Do SNe Ic eject helium? As we have seen, the 1 $`\mu `$m feature in SN 1994I does not provide convincing evidence for He I $`\lambda `$10830, and the presence of weak optical absorptions with highly detached He I lines is unlikely. However, it may be that the optical spectra contain undetached He I lines. How are we to decide? Since He I $`\lambda `$10830 can be confused with lines of other ions, the most direct test might be to look for $`\lambda `$20581, which in LTE has about the same Sobolev optical depth as $`\lambda `$10830 above 10,000 K. (But be careful — $`\lambda `$20581 is a singlet transition.) Infrared spectra also could be used to sort out the contributions of C I and Si I to the 1 $`\mu `$m feature because both ions have other strong lines that should be detectable (Figure 12 of Millard et al. 1999).

Do SNe Ic eject hydrogen? Identifying the weak 6360 Å absorption in SN 1987M with H$`\alpha `$ may be questionable, but the possibility of emission near the rest wavelength of H$`\alpha `$ looks interesting. The hydrogen would need to be undetached. This, together with the possibility that SNe Ic contain undetached He I lines, means that if SNe Ic do eject helium and hydrogen then these elements extend to lower ejection velocities than in SNe Ib. The appearance of the hydrogen and He I features in SNe Ib and SNe Ic may be affected by the radial distributions of the helium and hydrogen in addition to the total ejected masses of helium and hydrogen. We should consider the possibility that the composition structures of SNe Ic are more mixed up than those of SNe Ib.

This discussion of line identifications has been based on calculations carried out with the simple SYNOW code. Detailed NLTE calculations for a grid of explosion models for SNe Ib and SNe Ic are needed, especially to test the possibilities of nonthermally excited Ne I lines in SNe Ib (and SNe Ic), and of rounded H$`\alpha `$ emission in SNe Ic. It also is needed in order to estimate, or place upper limits on, the masses of helium and hydrogen in SNe Ib and SNe Ic.

Clocchiatti et al. (1997) have emphasized that light–curve shapes imply significant differences in the ejected masses of supernovae of the same spectral type. This, together with our uncertainty about the composition structures of the ejected matter, and our still scanty knowledge of the relative occurrence frequencies of the various kinds of SNe Ib and SNe Ic, means that there is much work to be done before we will be able to match the various kinds of SNe Ib and SNe Ic with their stellars progenitors in a detailed way.

### Acknowledgments.

I am grateful to Tom Matheson and Mario Hamuy for providing spectra; to them, Eddie Baron, Jinsong Deng, Chris Gerardy, and David Jeffery for comments on the manuscript; and to members of the University of Oklahoma supernova group for many discussions. This work has been supported by NSF grant AST–9986965.

## References

Baron, E., Branch, D., Hauschildt, P. H., Filippenko, A. V., Kirshner, R. P. 1999, ApJ 527, 739

Benetti, S. et al. 2002, MNRAS in press; astro-ph/0205453

Branch, D. 1972, A&A 16, 247

Branch, D. et al. 2002, ApJ 566, 1005 (B02)

Branch, D., Baron, E., Jeffery, D. J. 2002, in: K. W. Weiler (ed.), Supernovae and Gamma–Ray Bursts (New York: Springer), in press; astro-ph/0111573

Clocchiatti, A. et al. 1997, ApJ 483, 675

Clocchiatti, A. et al. 2001, ApJ 553, 886

Clocchiatti, A., Wheeler, J. C. 1997, ApJ 491, 375

Clocchiatti, A., Wheeler, J. C., Brotherton, M. S., Cochran, A. L., Wills, D., Barker, E. S., Turatto, M. 1996, ApJ 462, 462

Deng, J., Qiu, Y. L., Hu, J. 2002, ApJ submitted; astro-ph/0106404

Deng, J., Qiu, Y. L., Hu, J., Hatano, K., Branch, D. 2000, ApJ 540, 452

Filippenko, A. V. 1988, AJ 96, 1941

Filippenko, A. V. 1992, ApJ 384, L37

Filippenko, A. V. 1997, ARA&A 35 309

Filippenko, A. V. et al. 1995, ApJ 450, L11

Filippenko, A. V., Porter, A., Sargent, W. L. W. 1990, AJ 100, 1575

Hamuy, M. et al. 2002, AJ, 124, 417

Harkness, R. P. et al. 1987, ApJ 317, 355

Jeffery, D. J., Branch, D., 1990, in: J.C. Wheeler, T. Piran, & S. Weinberg (eds.), Supernovae, Sixth Jerusalem Winter School for Theoretical Physics (Singapore: World Scientific), 149

Jeffery, D. J., Branch, D., Filippenko, A. V., Nomoto, K. 1991, ApJ 317, 717

Kurucz, R. L. 1993, CD-ROM 1, Atomic Data for Opacity Calculations (Cambridge: Smithsonian Astrophysical Observatory)

Lucy, L. B. 1991, ApJ 383, 308

Matheson, T. et al. 2000, AJ 120, 1487

Matheson, T., Filippenko, A. V., Li, W., Leonard, D. C., Shields, J. C. 2001, AJ 121, 1648 (M01)

Millard, J. et al. 1999, ApJ 527, 746

Qiu, Y., Li, W., Qiao, Q, Hu, J. 1999, AJ 117, 736

Swartz, D. A., Filippenko, A. V., Nomoto, K., Wheeler, J. C. 1993, ApJ 411, 313

Turatto, M. 2002, in: K. W. Weiler (ed.), Supernovae and Gamma–Ray Bursts (New York: Springer), in press

Wheeler, J. C., Harkness, R. P., Clocchiati, A., Benetti, S., Brotherton, M. S., DePoy, D. L., Elias, J. 1994, ApJ 436, L135


text:
# Quantum Limit on Computational Time and Speed

## Abstract

We investigate if physical laws can impose limit on computational time and speed of a quantum computer built from elementary particles. We show that the product of the speed and the running time of a quantum computer is limited by the type of fundamental interactions present inside the system. This will help us to decide as to what type of interaction should be allowed in building quantum computers in achieving the desired speed.

Any computer, be it classical or quantal, stores information in the physical states and processes the same according to the laws of physics . Last century has witnessed tremendous growth of computational power in solving complex problems and in optimising computational resources. In the saga of information age it is impetuous to know the ultimate limitations on the speed and the maximal running time or the life-time of a computer. Since a computer is a physical device made up of basic elements, its underlying dynamics, its ability, its performance and life time will depend on the laws of physics. The present day computers store information in macroscopic elements and process information according to the laws of classical physics . For example, all the electronic computers employ silicon memory chips and are controlled by electrostatic or electromagnetic interactions. However, the quantum information revolution has offered us possibility of realizing computers that can be built out of a collection of interacting two-state systems . Using the quantum features such as linear superposition and quantum entanglement, it is hoped that quantum computers can gain some extra power as compared to classical computers . For example, one can factorise an integer in polynomial time  and search a data base in square root number of steps  in a quantum computer. In practical realisation of quantum computers a crucial factor is that the interaction between subsystems should be controlled in such a way that the speed and life time of the computer should be increased. Also the interaction between the computer and external world should be as small as possible to avoid decoherence .

It is often the case that quantum mechanical and relativity principles together with the existence of fundamental constants in nature such as Planck’s constant $`\mathrm{}`$, speed of light $`c`$ and universal Gravitational constant $`G`$ some times provide important bound on the physical quantities of interest. For example, it was shown that there is a limit on the maximal acceleration of a quantum particle and accurate clocks are those which can be accelerated maximally . The maximal acceleration was found to be the Planck acceleration $`a_p=\sqrt{\frac{\mathrm{}G}{c^3}}`$. Similarly, there is a limit on the power radiated by charged particles in external force field . Therefore, it is natural to seek if the ability of a computer is limited by laws of physics, existence of fundamental constants and fundamental forces in the universe. Recently, there have been attempts to put limits on the speed and memory capacity of a computer. Margolus and Levitin  have shown that the number of elementary operations that a physical system can perform per second is limited by $`\frac{2E}{\pi \mathrm{}}`$, where $`E`$ is average energy of the system. Remarkably, Lloyd  has found that the speed of a computer is limited by the energy available to the machine and memory (the total number of bits available for a physical system to process information) is by its entropy. Ng  has argued that the product of speed and the clock rate of a computer is limited by the reciprocal of squared Planck time $`t_p^2=c^5/\mathrm{}G`$. This bound arises again from laws of quantum physics and gravitation. However, bounds on time and speed has not been shown to depend on the type of fundamental interactions present in the universe.

In recent years one of the important goals is to enhance the speed and the life time (or running time) of a computer. In view of the fact that physical world is ultimately quantum mechanical, there have been momentous developments in imagining quantum computers. To build a quantum computer one needs to know what type of interactions would be most appropriate among its subsystems. In this paper we ask the question: In quantum world, is there a limit on the running time (or life time) and speed of a computer arising due to the fundamental physical interactions between the subsystems? In nature, we know that there are foure types of fundamental interactions, namely, (i) strong interaction, (ii) weak interaction, (iii) electromagnetic interaction and (iv) gravitational interaction. Also it is known that fundamental interactions between elementary particles carrying information can be used for quantum logic operations . If a quantum computer is built from elementary particles subject to these interactions, then its speed and running time should depend on the type of interaction. By combining principles of quantum theory, relativity and particle physics empirical systematics, we show that the product of running time $`T`$ and the speed $`v`$ is upper bounded by $`2^n/n`$, where $`n`$ is an integer depending on the type of fundamental interaction present in the quantum system. This can be interpreted as a complimentary relation between speed and time of a quantum computer for a given natural interaction.

First, let us note that quantum computers can be built out of collection of logical two-state systems (called qubits) with suitable physical interactions (from above four fundamental forces) allowed by laws of nature. In principle, we can utilise elementary particles with two distinct quantum states as our qubits. For example, in case of strong interaction, we can identify neutron and proton as two distinct states of a single neucleon with iso-spin interaction. Hence, in the presence of iso-spin interaction a neucleon can be regarded as a qubit. In case of weak interaction, one has to look for elementary particles that are subjected to weak forces. In this case there is a well-known phenomena of neutrino oscillation. By coherence properties  one can be regarded it as a qubit. In case of electromagnetic interaction, there are numerous examples. Simplest example, here, is that in the presence of electromagnetic laser pulse, a two-state atom under goes oscillation between its ground and excited states and this can be regarded as a qubit . Or we could think of spin of nuclei being manipulated using magnetic field such as in NMR devices. In case of gravitational interaction, in principle, one can think of a quantum system in a superposition of two distinct mass states and if it is allowed that would constitute a qubit. Once one identifies qubits, then using the desired one-qubit and two-qubits interaction  one can construct universal logic gates to manipulate the collection of quantum systems.

Suppose, we have a quantum computer made out of elementary two-state systems with any one of the four fundamental interaction between them. Let the composite quantum system consists of $`𝒩`$ elementary subsystems each having mass $`m`$. Let $`M`$ be the rest mass and $`\mathrm{\Psi }(X)`$ be the initial state of the quantum computer. Let us assume that the wavefunction has a linear spread $`\delta X`$ at an initial time. By the Heisenberg’s uncertainty relation its initial momentum spread will be of the order of $`\mathrm{}/\delta X`$. Therefore, if the computer is allowed to evolve for a time $`t`$, the position of the wavepacket will be given by

$$\delta X(t)\delta X+\frac{\mathrm{}t}{M\delta X}+(\delta X)_{\text{int}},$$
(1)
where the last term gives the spread due to interaction with the surroundings. We are considering the spread along one dimension but it applies equally well to other dimensions. We wish to operate the quantum computer such that $`(\delta X)_{\text{int}}`$ is much smaller than the linear spread. To ensure this, it is enough to have an interaction such that the system supports two time-scales, $`t`$ and $`ϵt`$ where $`ϵ`$ is an adiabaticity parameter. In such a situation, the diffusion sets in  at times of the order of $`1/ϵ`$. Thus, our arguments will hold if the decoherence times are much lesser than $`ϵ^1`$. In practice, this will always hold. Also, recently it has been shown that the decoherence time (which is same as life time or running time) is $`(\mathrm{\Lambda }h_{KS})^1`$ for complex (chaotic) systems which decay, where $`\mathrm{\Lambda }`$ and $`h_{KS}`$ are respectively the Lyapunov exponent and the Kolmogorov-Sinai entropy of the fractal repeller containing all the periodic orbits residing in the system .

The minimum value of the spread occurs for $`(\delta X(t))^2(\delta X)^2\frac{\mathrm{}t}{M}`$. Hence, if the computation takes a time $`T`$ before the quantum computer decoheres, the resolution one can get for the spread of the wave packet is limited by “standard quantum limit”, i.e., $`(\delta X)_{SQL}\sqrt{\frac{\mathrm{}T}{M}}`$. Therefore, we have

$$\delta X\sqrt{\frac{\mathrm{}T}{M}}.$$
(2)
The total time $`T`$ is also identified as the life time of a computer, because in order to do any useful computation in a quantum computer the system should not decay into some ‘unwanted’ states. Next, we recall ‘Wigner’s clock’ argument for a general quantum mechanical system. Wigner  has argued that if a quantum device can distinguish time-intervals to within an accuracy of $`\tau `$, then the wave packet of the system will be limited to a length scale $`\delta Xc\tau `$. This means that the wave packet of the quantum computer is limited within the same length scale. By combining the above two, we have the following inequality for these dimensionless quantities

$$\frac{Mc^2T}{\mathrm{}}\frac{T^2}{\tau ^2}.$$
(3)
Now, we bring another important empirical observation from particle physics. In a series of papers a unifying formalism of elementary particles was developed that remarkably relates their masses and life-times . If we have an elementary quantum system with mass $`m`$ and life time $`T`$ in presence of certain force field, then it  has been empirically shown that the dimensionless quantity constructed from $`m,T,c,`$ and $`\mathrm{}`$ obey the following relation

$$\frac{mc^2T}{\mathrm{}}=\frac{2^n}{n},$$
(4)
where $`n`$ is an integer that characterises the strength and type of physical interactions present. Multiplying both sides with $`𝒩`$ we have $`\frac{Mc^2T}{\mathrm{}}=𝒩\frac{2^n}{n}`$, where $`𝒩`$ denotes the number of units of mass $`m`$ placed in making the quantum device. The total mass $`M`$ of the quantum computer will be given by $`Mm𝒩`$. The corrections due to binding energy is neglected here. The above relation has been substantiated for various elementary particles that exists in nature as well as for nuclei . For example, using mass-life time relation it was shown that  the life time of proton is $`5.33\times 10^{33}`$ years with $`n=225`$. This approach is unique because it incorporates two discrete quantities together in a way that is independent of choosing a particular unit of mass and time.

By combining Wigner inequality (3) and the empirical, but exact relation (4) we obtain an inequality

$$\frac{T^2}{\tau ^2}𝒩\frac{2^n}{n}.$$
(5)
We notice that $`\frac{1}{\tau }=\nu `$ is the clock rate of the computer which is same as number of operations per bit per unit time . Moreover, $`T`$ is the total running time of a computer before it decays (in other words for practical purposes before the quantum computer decoheres). $`T/\tau =I`$ is the maximum number of steps that a computer can sustain in information processing. On defining $`v=I\nu `$, where $`v`$ is nothing but the number of logical operations that one can perform per unit time in a quantum computer, it is actually the speed of a computer. Therefore, we have an upper bound on the product of speed and running time of a quantum computer given by

$$vT𝒩\frac{2^n}{n}.$$
(6)
Alternatively, we can interpret the above bound by saying that fundamental forces also can set a limit on the number of steps $`I`$ given by

$$I\sqrt{𝒩\frac{2^n}{n}}.$$
(7)
The most crucial aspect of the above relation is that the rhs of above equation is a function of an integer that characterises the type of interaction present in the system. This suggest that one can label all quantum computer according to their speed, running time and physical interaction and assign an index $`n`$. The above relation can be interpreted as a complimentary relation between speed and running time of a quantum computer. For a given interaction, the more the speed is, the less time it takes for doing a computation. It is also clear that more the $`n`$ is, more can we raise the upper bound for speed for a given running time. Quantum systems subjected to strong interaction correspond to values of $`n`$ less than $`10`$. If the interaction is of electromagnetic in origin then the value of $`n`$ lies between $`10`$ and $`40`$. For weak interaction the values of $`n`$ can be more than $`40`$. However, for gravitational interaction the value of $`n`$ is not yet established because we still do not have a full quantum theory of gravity nor do we have enough data about particles decaying through gravitational interaction. All present day proposals manipulate quantum states using electromagnetic interaction. If we insert the value of $`n`$ lying between $`10`$ to $`40`$, our bound suggests that the number of coherent steps that a physical system can sustain with electromagnetic interaction can vary between $`I10\sqrt{𝒩}`$ to $`10^6\sqrt{𝒩}`$. Interestingly, in a universe if one makes a quantum computer with protons then the maximum number of steps $`I`$ goes as $`I10^{36}\sqrt{𝒩}`$. Therefore, proton based quantum computers could process maximum amount of information in principle.

In standard model of quantum computation one assumes that it is possible to do quantum error correction by adjoining additional qubits (for encoding a single qubit in many qubits such as $`5`$-bit code or $`9`$-bit code) . This is done typically to protect quantum information from undergoing decoherence, thus increasing the life time of a computer. Since our arguments hold for any general composite quantum system, it is expected to hold also under the situation when one attaches additional quantum systems. In fact, one can see from (6) that quantum computers that uses additional qubits will enhance the upper bound on speed and time which is indeed expected. Thus our limit holds when one takes into account robust quantum computation and quantum error correction. Further, we will show that our limit gives an upper bound on the quality of coherence of a qubit. If one defines the quality factor of coherence for a qubit as $`Q=\pi \nu T`$, then it has been known that to surpass active decoherence mechanism we need $`Q`$ to be larger than $`10^4\nu t_{\mathrm{op}}`$, where $`t_{\mathrm{op}}=1/v`$ is the time taken for an elementary operation . From (6) one can show that the quality factor of a qubit obey the following inequality

$$Q\frac{\pi 2^n}{n}\nu t_{\mathrm{op}}.$$
(8)
For example, in the case of electromagnetic interaction $`Q`$ should be less than (roghly) $`10^{12}\nu t_{\mathrm{op}}`$. Thus, our limit (8) can tell us what type of interaction can give the desired quality factor for a qubit. It may be worth mentioning that a recent experiment reports  that a qubit in a superconducting junction circuit has been designed with a quality factor of quantum coherence $`Q2.5\times 10^4`$. In principle one can go still beyond as suggested here.

Before concluding, we can argue that the entropy of a quantum computer will be limited by the type of interactions present within the system. Recall that  $`I`$ can also be regarded as the amount of information $``$ that can be registered by the computer (apart from factors like $`\mathrm{ln}2`$). Since $`S=k\mathrm{ln}2`$, where $`k`$ is Boltzmann constant, using (7) one can show that the entropy of the computer will be limited by $`S\sqrt{𝒩\frac{2^n}{n}}`$ Thus depending on the strength of interaction, the number of available states to a quantum system is also limited.

To end with, we have shown that the laws of physics suggest that there exist a limit on the product of speed and running time of a quantum computer. The ultimate limits on the performance of any quantum computer are governed by the physical processes in the universe and we know that all the processes are described by these four fundamental interactions. Our bound is able to grasp this feature succinctly. We hope that this simple, yet novel result based partly on exact and partly on empirical relation, will throw new light in designing future quantum computers built from elementary particles with desired speed and life time. Further, our result suggests that we can assign an index integer ‘$`n`$’ to a class of computers based on its coherence quality that depends on fundamental forces of nature. In addition, following Lloyd  if we view our universe as a computer then our bound will be important in deciding the running time and speed of the computation that universe is performing.

Acknowledgements: AKP and AM thank H. D. Parab for useful discussions.