text:
# Bandwidth reduction in rectangular grids

## 1 Introduction

We consider only simple undirected graphs (no loops, no multiple edges). A *vertex numbering* of a graph $`G=(V,E)`$ is a bijective map $`\nu :V[k]`$ from the vertex set $`V`$ of $`G`$ to the set of the first $`k`$ positive integers $`[k]=\{1,2,\mathrm{},k\}`$, where $`k=|V|`$. The absolute value of the difference between the numbers at the two endpoints of an edge $`e`$ in $`E`$ is denoted by $`f_\nu (e)`$ and called the *length* of $`e`$ induced by $`\nu `$. Thus any vertex numbering of $`G`$ induces an edge labelling $`f_\nu :E_+`$ of $`G`$ by positive integers. The largest length of an edge in $`E`$ (i.e. the largest label used by $`f_\nu `$) is called the *bandwidth of the numbering* $`\nu `$. If the edge set is empty the bandwidth is 0 by definition. The smallest possible bandwidth, taken over all possible vertex numberings of $`G`$, is called the *bandwidth* of the graph $`G`$. Sometimes the adjective “linear” is used due to the following physical interpretation. Every vertex numbering $`\nu `$ corresponds to a *linear arrangement* of the graph $`G`$ in which the vertex $`v`$ in $`V`$ is placed at the number $`\nu (v)`$ on the real line. The (linear) bandwidth of a linear arrangement is then just the length of the longest wire needed to assemble the graph $`G`$ and the minimal such bandwidth, taken over all possible linear arrangements of $`G`$, is the (linear) bandwidth of $`G`$.

The two-dimensional *rectangular grid* $`G_{m,n}`$, for $`mn1`$, is the graph whose vertices are the points in the set $`V=[m]\times [n]=\{(i,j)|1im,1jn\}`$ with an edge between two vertices if and only if the Euclidean distance between them is 1 (think of the natural embedding of the vertex set in the Cartesian plane). We write $`G_n`$ for the square grid $`G_{n,n}`$. It is well known that the bandwidth of the rectangular grid $`G_{m,n}`$ is $`n`$, unless $`m=n=1`$.

###### Theorem 1 (J. Chvátalová ).

Let $`mn1`$. If $`m2`$, then the bandwidth of the two-dimensional rectangular grid $`G_{m,n}`$ is $`n`$.

The bandwidth is, in some sense, a measure of how difficult it is to embed the graph on a line. The following result provides some refinement of this measure for the rectangular grids.

###### Theorem 2 (P. Fishburn and P. Wright ).

Let $`mn1`$. Every vertex numbering of $`G_{m,n}`$ of bandwidth $`n`$ induces at least

$$2(n1)+n(mn)$$

edges of length $`n`$. Moreover, the *down diagonal lexicographic linear arrangement* induces exactly $`2(n1)+n(mn)`$ edges of length $`n`$.

As an example, the down diagonal lexicographical linear arrangement on the square grid $`G_n`$ is given by

$$\begin{array}{ccccc}t+1\hfill & \hfill & \mathrm{}\hfill & \hfill & n^2\hfill \\ \mathrm{}\hfill & t+2\hfill & \hfill & \mathrm{}\hfill & \hfill \\ 4\hfill & \mathrm{}\hfill & \mathrm{}\hfill & \hfill & \mathrm{}\hfill \\ 2\hfill & 5\hfill & \mathrm{}\hfill & \mathrm{}\hfill & \hfill \\ 1\hfill & 3\hfill & 6\hfill & \mathrm{}\hfill & t+n\hfill \end{array},$$

where $`t=(n1)n/2`$. This numbering has bandwidth $`n`$ and induces exactly $`2(n1)`$ edges of length $`n`$ (all horizontal edges incident to the main diagonal vertices).

Note that the down diagonal lexicographical vertex numbering of $`G_n`$ that we just displayed indicates that we sometimes think of $`G_{m,n}`$ as a rectangular board of dimension $`n\times m`$ (meaning $`n`$ rows and $`m`$ columns) in which the squares represent the vertices and any pair of squares that have common side are considered to be neighbors.

By the result of Chvátalová, we know that in order to make a linear arrangement of the square grid $`G_n`$ we must be ready to use pieces of wire of length at least $`n`$. Moreover, by the result of Fishburn and Wright, in order to make an arrangement that does not use any pieces longer than $`n`$, we must be ready to use at least $`2(n1)`$ pieces of length $`n`$.

But what if we do not have such long pieces? In such a case the most practical thing one can do is to try to assemble as large part of the graph as possible, which amounts to deletion of some of the edges.

## 2 Bandwidth reduction

The bandwidth of the path $`P_n`$ of length $`n11`$ is 1, of the cycle $`C_n`$ of length $`n3`$ is 2, and of the complete graph $`K_n`$ on $`n1`$ vertices is $`n1`$. The deletion of any edge in the cycle $`C_n`$ produces the path $`P_n`$ and thus reduces the bandwidth by 1. Similarly, the deletion of any edge in $`K_n`$ also reduces the bandwidth by 1. We are interested in the minimal number of edges that need to be deleted in an arbitrary graph in order to reduce its bandwidth.

###### Definition 1.

The *bandwidth reduction number* of a graph $`G`$ of bandwidth $`b`$, $`b1`$, is the minimal number of edges that need to be deleted from $`G`$ in order to obtain a subgraph of bandwidth no greater than $`b1`$.

For example, cycles and complete graphs have bandwidth reduction number 1, while paths have bandwidth reduction number equal to their length. As a more interesting example, consider the wheel $`W_m`$, $`m4`$, a graph on $`m`$ vertices that consists of a cycle of length $`m1`$ together with an “center” vertex connected to every vertex in the cycle by an edge. The following table provides the bandwidth and bandwidth reduction number of the wheel graphs. We do not provide the easy proofs, but we note the exceptional case of $`W_7`$, which is the only wheel whose bandwidth reduction number is 3.

| graph | $`W_4`$ | $`W_5`$ | $`W_6`$ | $`W_7`$ | $`W_{2n}(n4)`$ | $`W_{2n+1}(n4)`$ |
| --- | --- | --- | --- | --- | --- | --- |
| bandwidth | $`3`$ | $`3`$ | $`3`$ | $`3`$ | $`n`$ | $`n`$ |
| bandwidth reduction n. | $`1`$ | $`1`$ | $`2`$ | $`3`$ | $`1`$ | $`2`$ |

Another relatively easy example is provided by the complete bipartite graphs $`B_{m,n}`$, for $`mn1`$.

| graph | $`B_{2,2}`$ | $`B_{2k+1,n}`$ | $`B_{2k,n}(k1\text{ or }n2)`$ |
| --- | --- | --- | --- |
| bandwidth | $`2`$ | $`k+n`$ | $`k+n1`$ |
| bandwidth reduction number | $`1`$ | $`1`$ | $`2`$ |

The notion of bandwidth reduction can be further extended as follows.

###### Definition 2.

Let $`G`$ be a graph of bandwidth $`b`$. For $`k=1,\mathrm{},b`$, the $`k`$-th bandwidth reduction number of $`G`$, denoted by $`br_k(G)`$, is the minimal number of edges that need to be deleted from $`G`$ in order to obtain a subgraph of bandwidth no greater than $`bk`$.

We note that the $`k`$-th bandwidth reduction number of a graph $`G`$ of bandwidth $`b`$ is the minimal number of edges $`e`$ of induced length $`f_\nu (e)`$ greater than $`bk`$, taken over all possible numberings $`\nu `$ of $`G`$, i.e.,

$$br_k(G)=\underset{\nu }{\mathrm{min}}\left|\{eE|f_\nu (e)>bk\}\right|.$$

For example, in the case of the complete graph $`K_n`$ we have

$$br_k(K_n)=1+2+\mathrm{}k=\frac{k(k+1)}{2},$$

for $`k=1,\mathrm{},n1`$, since the bandwidth of $`K_n`$ is $`n1`$ and every numbering of $`K_n`$ induces $`i`$ edges of length $`ni`$, for $`i=1,\mathrm{},n1`$. This implies that if a graph on $`n`$ vertices has more than

$$\frac{n(n1)}{2}\frac{k(k+1)}{2}$$

edges, then its bandwidth is at least $`nk`$, for $`k=1,\mathrm{},n1`$.

Before we move on, we observe that the bandwidth of a graph can be reduced by more than 1 by deletion of a single edge. This is why we require the newly obtained graph to have bandwidth no greater than $`bk`$ rather than exactly $`bk`$ in the definition of the $`k`$-th bandwidth reduction number.

Consider the graph $`G`$ that consists of two copies of the wheel $`W_7`$ with an additional edge between the wheel centers (two wheels with an axis between them). Since an arbitrary graph on $`v`$ vertices with diameter $`d`$ and bandwidth $`b`$ satisfies

$$1+dbv,$$

the bandwidth of the graph $`G`$ is at least 5 ($`v`$=14 and $`d=3`$). However the deletion of the edge between the centers of the two wheels leads to a graph of bandwidth 3. Thus $`br_1(G)=br_2(G)=1`$ for this graph.

We give now an upper bound on the $`k`$-th bandwidth reduction number in rectangular grids, for small $`k`$.

###### Theorem 3.

Let $`mn>2k`$. The $`k`$-th bandwidth reduction number of the rectangular grid $`G_{m,n}`$ satisfies

$$br_k(G_{m,n})mn+2k.$$

###### Proof.

We construct an example of a numbering $`\nu `$ of $`G_{m,n}`$ in which only $`mn+2k`$ edges are longer than $`nk`$. The example is a modification of the down diagonal lexicographical linear arrangement.

Think of $`G_{m,n}`$ as of rectangular board of dimension $`n\times m`$. First modify the board by cutting out the lower right part of the board of dimension $`k\times (mn+k+1)`$ and flipping it over as indicated in Figure 1.

Enumerate all the squares in the modified board in the down diagonal lexicographical fashion. Consider a “typical” vertex $`A`$ that lives on a diagonal of length $`nk1`$. The vertical edges incident to $`A`$ have length $`nk1`$ and the horizontal ones have length $`(nk1)+1=nk`$. A “typical” vertex $`B`$ that lives on a diagonal of length $`nk`$ is incident to horizontal edges of length $`nk`$ and vertical edges of length $`(nk)1`$. A “typical” vertex $`C`$ that lives on a diagonal of length $`k`$ is incident to vertical edges of length $`k`$ and horizontal edges of length $`k+1=2k+1knk`$, where the inequality comes from the assumption that $`2k<n`$. In all “atypical” cases, near the bottom left or the upper right corner(s) of the modified board, the diagonals are even shorter, which implies that the incident edges are also shorter.

Thus the bandwidth of the given numbering of the modified board is $`nk`$. After we flip back the modified part of the board to its original position the newly created $`k`$ horizontal edges (between the non-shaded and the shaded part of the board) will have length longer than $`nk`$ and all but one of the newly created $`mn+k+1`$ vertical edges will have length longer than $`nk`$. Indeed the induced length of the rightmost vertical edge between the shaded and the non-shaded part is exactly $`nk`$, since its endpoints (denoted by $`D`$ and $`E`$ in Figure 1) were already neighbors in the modified board. ∎

We provide one example to illustrate the preceding result. Assume that we want to reduce the bandwidth of $`G_8`$ to 6. Thus $`m=n=8`$, $`k=2`$ and the numbering of the modified board is given by

| $`26`$ | $`32`$ | $`38`$ | $`44`$ | $`50`$ | $`56`$ | $`61`$ | $`64`$ |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $`21`$ | $`27`$ | $`33`$ | $`39`$ | $`45`$ | $`51`$ | $`57`$ | $`62`$ |  |  |
| $`16`$ | $`22`$ | $`28`$ | $`34`$ | $`40`$ | $`46`$ | $`52`$ | $`58`$ |  |  |
| $`11`$ | $`17`$ | $`23`$ | $`29`$ | $`35`$ | $`41`$ | $`47`$ | $`53`$ | $`59`$ | $`63`$ |
| $`7`$ | $`12`$ | $`18`$ | $`24`$ | $`30`$ | $`36`$ | $`42`$ | $`48`$ | $`54`$ | $`60`$ |
| $`4`$ | $`8`$ | $`13`$ | $`19`$ | $`25`$ | $`31`$ | $`37`$ | $`43`$ | $`49`$ | $`55`$ |
| $`2`$ | $`5`$ | $`9`$ | $`14`$ | $`20`$ |  |  |  |  |  |
| $`1`$ | $`3`$ | $`6`$ | $`10`$ | $`15`$ |  |  |  |  |  |

Another way to state Theorem 3 is to say that the incidence matrix of $`G_{m,n}`$ can be written in such a way that all non-zero entries, except for $`mn+2k`$ symmetric pairs, are within distance $`nk`$ from the main diagonal.

For example, this means that the incidence matrix of the square grid $`G_n`$ can be written in such a way that all non-zero entries, except for 2 symmetric pairs, are within distance $`n1`$ from the main diagonal. This contrasts nicely with Theorem 2, which implies that if all non-zero entries of the incidence matrix of $`G_n`$ are within distance $`n`$ from the main diagonal then there are at least $`2(n1)`$ symmetric pairs of non-zero entries at distance $`n`$ from the main diagonal.

We show now that the bandwidth of square grids cannot be reduced if only 1 edge is deleted. The exceptional cases are $`n=1`$ and $`n=2`$. Indeed, $`G_1`$ has bandwidth 0 which cannot be reduced, while $`G_2`$ is the cycle $`C_4`$ and its bandwidth reduction number is 1.

###### Theorem 4.

Let $`n3`$. The bandwidth reduction number of $`G_n`$ is 2, i.e., the minimal number of edges that needs to be deleted from $`G_n`$ in order to obtain a graph of bandwidth $`n1`$ is 2. Moreover, the edges that need to be deleted may, but do not have to, share a common endpoint.

###### Proof of Theorem 4.

For an arbitrary numbering $`\nu `$ of $`G_n`$, call an edge *long* if its induced length is at least $`n`$ and call it *short* otherwise. An example of a numbering of $`G_n`$, for $`n3`$, with only two long edges is already provided in the proof of Theorem 3. We note that the two long edges in that example share a common vertex, namely the vertex in row $`n`$ column $`n1`$. The lengths of the long edges are $`5n7`$ and $`3n4`$.

Rather than providing a general example of a numbering with only two long edges that are not adjacent, we provide an example for the case $`n=6`$, from which one can easily extract the general pattern. The two long edges, which are the two leftmost vertical edges between the top two rows, have lengths $`5n8`$ and $`3n5`$.

$$\begin{array}{cccccc}33\hfill & 29\hfill & 25\hfill & 30\hfill & 34\hfill & 36\hfill \\ 11\hfill & 16\hfill & 21\hfill & 26\hfill & 31\hfill & 35\hfill \\ 7\hfill & 12\hfill & 17\hfill & 22\hfill & 27\hfill & 32\hfill \\ 4\hfill & 8\hfill & 13\hfill & 18\hfill & 23\hfill & 28\hfill \\ 2\hfill & 5\hfill & 9\hfill & 14\hfill & 19\hfill & 24\hfill \\ 1\hfill & 3\hfill & 6\hfill & 10\hfill & 15\hfill & 20\hfill \end{array}.$$

It remains to show that every numbering of $`G_n`$, $`n3`$, has at least two long edges.

Let $`\nu `$ be an arbitrary labelling of $`G_n`$. Choose the smallest $`k`$ such that all rows or all columns of $`G_n`$ have a label in $`[k]`$. Without loss of generality we may assume that all rows have a label in $`[k]`$. Define the partial numbering $`\kappa `$ of $`G_n`$ to be the numbering of the vertices obtained from the numbering $`\nu `$ by deletion of the labels greater than $`k`$ (thus only $`k`$ vertices have a label).

Claim 1. The label $`k`$ is alone in its row in the partial numbering $`\kappa `$.

Otherwise each row would have a label from $`[k1]`$ which contradicts the minimality in the choice of $`k`$.

Claim 2. No row is completely numbered by $`\kappa `$.

Otherwise each column would have a label from $`[k1]`$ which contradicts the minimality in the choice of $`k`$.

Call an edge between vertex numbered by an element in $`[k]`$ and an element not in $`[k]`$ a *boundary edge*. If there are at least $`n+1`$ boundary edges then at least two of them would have to be long. A direct corollary of Claim 2 is that each row has at least one horizontal boundary edge. This already means that there must be at least one long edge (apropos, this proves Theorem 1 in the case of square grids). Thus, we assume in the sequel that there are exactly $`n`$ horizontal boundary edges and only one of them is long. Moreover, we assume that this is the only long edge in $`\nu `$ and we seek a contradiction.

Claim 3. The endpoints of the $`n1`$ short horizontal boundary edges are numbered by the pairs

$$(k,k+n1),(k1,k+n2),(k2,k+n3),\mathrm{},(kn+2,k+1),$$

while the endpoints of the long edge come from a pair $`(s,\mathrm{})`$, where $`s`$ is a “small” number less than or equal to $`kn+1`$ and $`\mathrm{}`$ is a “large” number greater or equal to $`k+n`$.

Indeed, any other numbering of the endpoints of the boundary edges would result in at least two long horizontal edges.

Claim 4. For every row $`i`$ in $`G_n`$, the vertices labelled by the partial numbering $`\kappa `$ form a horizontal path $`p_i`$ that ends at the leftmost or the rightmost column.

This follows from the fact that every row has exactly one horizontal boundary edge.

Thus each row contains a unique maximal path that consists of vertices numbered by $`\kappa `$. These $`n`$ paths will be called $`\kappa `$-paths.

Claim 5. The $`\kappa `$-path in any row next to $`k`$ consist of a single vertex in the column of $`k`$.

Indeed, if the neighboring row has a vertex labelled by $`\kappa `$ that is not in the same column as $`k`$, this vertex would be involved in a vertical edge that would have to be long (all vertices in the row of $`k`$ are labelled by numbers greater or equal to $`k+n1`$).

Without loss of generality we may assume that the vertex $`k`$ (together with its vertical neighbors from $`[k]`$) is in the leftmost column in $`G_n`$.

Claim 6. If the $`\kappa `$-path $`p`$ is no longer than $`n2`$, then the $`\kappa `$-path $`q`$ in any neighboring row occupies the same columns as $`p`$ or differs in exactly one column.

Again, in any other case there would be a long vertical edge involving a number from $`[k]`$ and a number outside of $`[k]`$. Note that we required that the length of $`p`$ be no longer than $`n2`$, since if the length is $`n1`$ the neighboring $`\kappa `$-path $`q`$ may also have length $`n1`$ and start at the opposite end without creating additional long vertical edge(s). However, we will see that this does not happen.

Claim 7. No horizontal $`\kappa `$-path is longer than $`n2`$ and they all start at the left end.

The length of the $`\kappa `$-path $`k`$ is 1 and so is the length of the neighboring $`\kappa `$-path(s). Going further away, the length of the $`\kappa `$-paths can only go up by 1 from one row to another, so the only way we can have a $`\kappa `$-path of length $`n1`$ is if $`k`$ is in the bottom or in the top row, the next $`\kappa `$-path has length 1 and the length of the remaining $`\kappa `$-paths grows by 1 as we move away from the row of $`k`$. Without loss of generality assume that $`k`$ is in the bottom left corner. Consider now the $`\kappa `$-path $`p_s`$, corresponding to the row with a long horizontal edge, together with the horizontal path $`q`$ in the row below.

$$\begin{array}{ccccc}\hfill & \mathrm{}\hfill & \hfill & s\hfill & \mathrm{}\hfill \\ \hfill & \mathrm{}\hfill & \hfill & x\hfill & \hfill \end{array},$$

where the stars represent arbitrary numbers in $`[k]`$. Clearly, if $`x`$ is not in $`[k]`$ we obtain a long vertical edge with endpoints $`x`$ and $`s`$. Thus $`x`$ is in $`[k]`$ and the lengths of $`p_s`$ and $`q`$ are equal. Since the lengths of the $`\kappa `$-paths start at 1 and repeat at the row of $`k`$ and at the row of $`s`$, the longest $`\kappa `$-path can only reach the length $`n2`$.

Claim 8. The $`\kappa `$-path $`p_s`$ corresponding to the row with the long horizontal edge $`(s,\mathrm{})`$ has the same length as the $`\kappa `$-paths in the rows next to it.

We already proved that the $`\kappa `$-path below $`p_s`$ cannot be shorter than $`p_s`$. It cannot be longer as well, since the configuration

$$\begin{array}{ccccc}\hfill & \mathrm{}\hfill & \hfill & s\hfill & \mathrm{}\hfill \\ \hfill & \mathrm{}\hfill & \hfill & \hfill & x\hfill \end{array},$$

with $`x`$ in $`[k]`$, indicates that $`\mathrm{}`$ and $`x`$ are the endpoints of a long vertical edge. By symmetry, the $`\kappa `$-path above $`p_s`$ also has length equal to the length of $`p_s`$. This finishes the proof of Claim 8.

We now consider the partial numbering $`\tau `$ that corresponds to the set of numbers $`[k+n1]`$. As observed before, the numbers $`k+1,k+2,\mathrm{},k+n1`$ are placed in different rows, one in each row except for the row of the long horizontal edge $`s\mathrm{}`$. Thus $`n1`$ horizontal boundary edges are now formed between the vertices numbered by $`[k+n1]`$ and those not numbered by $`[k+n1]`$. In addition, there exist at least one vertical boundary edge with endpoints in an element of $`[k+n1]`$ and $`\mathrm{}`$. These $`n`$ boundary edges of the partial numbering $`\tau `$ must contain a long edge, a contradiction. ∎

## 3 Final remarks

We conjecture that in order to reduce the bandwidth of $`G_{m,n}`$ by $`k`$, for $`k<n/2`$, we need to delete at least $`mn+2k`$ edges, i.e., we conjecture that the upper bound provided by Theorem 3 is the actual value of the bandwidth reduction number for all sufficiently small values of $`k`$. Theorem 4 shows that this conjecture is true when $`m=n`$ and $`k=1`$.

The proof of Theorem 4 indicates an easy way to see that at least $`k`$ edges need to be deleted in order to reduce the bandwidth of $`G_{m,n}`$ by $`k`$. Namely, the first time some partial numbering has a representative in each row (or each column) there would be at least $`n`$ horizontal (or vertical) boundary edges at least $`k`$ of which must have length at least $`nk+1`$.

For a numbering $`\nu `$ of a graph $`G=(V,E)`$ one can define the *vertex-isoperimetric* number of $`\nu `$ to be the maximal number of vertices in $`G`$ numbered by $`[k]`$ that have neighbors that are not numbered by $`[k]`$, where the maximum is taken over all $`k=0,\mathrm{},|V|`$. The smallest possible vertex-isoperimetric number, taken over all numberings of $`G`$, is the *vertex-isoperimetric number* of the graph $`G`$. If $`b(G)`$ is the bandwidth of $`G`$ and $`vi(G)`$ is its vertex-isoperimetric number then

$$b(G)vi(G).$$

It is well known that the vertex-isoperimetric number of the square grid $`G_n`$ is $`n`$. The down diagonal lexicographical linear arrangement provides an example of a numbering with vertex-isoperimetric number $`n`$ and the proof of Theorem 4 essentially contains a proof that this number cannot be less than $`n`$. Thus in order to reduce the bandwidth of $`G_n`$ we need to delete enough edges so that at least the vertex-isoperimetric number is reduced. However, one can reduce the vertex-isoperimetric number of $`G_n`$ by deleting only one edge. For example, consider the case of $`n=4`$ and the numbering given by

$$\begin{array}{cccc}7\hfill & 13\hfill & 15\hfill & 16\hfill \\ 4\hfill & 8\hfill & 12\hfill & 14\hfill \\ 2\hfill & 5\hfill & 9\hfill & 11\hfill \\ 1\hfill & 3\hfill & 6\hfill & 10\hfill \end{array}.$$

If the edge with endpoints labelled by 7 and 13 is deleted, the newly obtained graph has vertex-isoperimetric number 3. This indicates that, in general, the problem of bandwidth reduction is more difficult than the problem of vertex-isoperimetric number reduction. It also explains why, in the course of the proof of Theorem 4, it was relatively easy to show that at least one edge needed to be deleted, but one had to work harder for the second edge.

Finally, we note that the $`k`$-th bandwidth reduction number of the square grid $`G_n`$ is bounded linearly by $`2k`$, for $`k<n/2`$, i.e, one has to delete relatively small number of edges to reduce the bandwidth substantially. However, it is clear that for $`kn/2`$ the bandwidth reduction gets more difficult. A linear bound on the bandwidth reduction number simply cannot be found for all $`k`$. After all, for $`k=n`$, one needs to remove all $`2n(n1)`$ edges to get to bandwidth 0.

## Acknowledgments

Thanks to Kiran Kedlaya for his input and interest.


format: text

text:
# Parallel Reconstruction of CLEO III Data

## I INTRODUCTION

CLEO III cleo-ref  raw data is reconstructed using the tools provided by the CLEO III software infrastructure storage-helpers-ref  rapid-ref . All the raw data runs for a dataset are collected and then processed collectively on a compute farm comprising 133 UltraSPARCTM Netra computers. CPU allocation is performed using Sun Grid Engine (SGE) sge-ref ; sge-linux-ref . Raw data are read from Objectivity/DBTM objectivity-ref  and the resulting reconstructed data are written back to the same database. Since the data are strictly “write once, read many”, the storage methods attempt to optimize for read performance. One of the design decisions that flowed from this was to store the events in event-number order.

The first implementation of the reconstruction software processed an entire run sequentially using a single CPU. A histogram file for monitoring and quality checking was produced. The reconstructed data was written directly to the Objectivity/DB database. Many runs were processed in parallel by assigning one run to each of the available reconstruction farm CPUs. However, a large run of about 250K events could take up to 9 days to process.

This system had a large number of serious deficiencies:

1. It took a long time to stop the processor farm gracefully. Many CPUs were idle for long periods while everything was halted. Scheduling periodic maintenance or stopping the farm for emergency maintenance was fraught with difficulty.
2. Load-balancing the various CPU farms was difficult. Once a CPU was loaned to the reconstruction farm it might be committed for 9 days, or it might be returned in just 2 or 3 days if it was assigned a short run, or there was a software failure.
3. Database locks were held for up to 9 days. With more than 100 runs being processed at once, there was a heavy load on the database lock server, which hurt performance and interfered with database administration activities.
4. Reconstruction averaged about 1.5 to 2 seconds per event. This resulted in a very low write rate to the database. Caching efficiencies were lost.
5. Any failures left the database in an invalid state. Scarce database administrator (DBA) time was required to clean out the partial results. If failures went undetected for some time, an attempt may have been made to use the corrupted database, resulting in more wasted time, computing and human resources.
6. There was a very large window of opportunity for failures to occur while the database was open. For example, power failure, CPU failure or reconstruction software bugs resulted in lost CPU time, extra operator intervention and DBA intervention.
7. When starting a new dataset, it is necessary to check the output of a few (short) runs to ensure that the software and the constants are combining to produce reasonable output. If a problem occurs, the fault must be corrected and processing of the entire dataset restarted. This took from several days to a week. Waiting several days for a few short runs to complete so that the output could be checked led to a substantial waste of resources.
8. Debugging the reconstruction software components was painful. It could take days to rerun a job to isolate the bug, fix it and test the fix. Then the entire run had to be reprocessed to inject the data into the database.
9. Failed jobs were not automatically restarted because the database clean-up required human intervention. For transient failures, automatic restart would improve resource utilization, reduce operator intervention and potentially reduce the time taken to complete a dataset.

This litany is by no means the complete list of problems. These were the problems that needed to be addressed urgently.

## II THE SOLUTION

Reducing the wall-clock time to analyze an entire run would clearly resolve or ameliorate problems a, b, c, g and h. It was decided to leverage the experience gained from Nile nile-ref ; nilebib-ref  to use more parallelism. Each run could be split into several chunks, and each chunk assigned to a separate CPU. However, splitting a run into modest-sized chunks of events and processing the chunks in parallel potentially conflicts with writing the events out in event-number order. Writing the data directly to the database in event-number order would be almost impossible, and would not address problems e and f. Fortunately, the CLEO III software infrastructure was designed to handle different file formats simultaneously. Therefore each run is split into chunks but the results are not written directly to the database. Instead, an efficient binary format is used to temporarily store the reconstructed data. Within each chunk, the intermediate output is still in event-number order. Once all the chunks are reconstructed, a single job injects the reconstructed data into the database in event-number order by collating the intermediate files in the correct order. This process is limited by the write performance of the database. Now problems c, d, e and f have been dealt with. Extra fault tolerance is gained because now the failures in reconstruction are no longer failure modes for updating the database. No database updates occur until the reconstruction is complete. An extra benefit is that we are assured that the reconstruction data can be read and is moderately well-formed.

To further improve fault tolerance, a “job manager” process is created for each run. It splits the run up into chunks and submits a reconstruction subjob for each chunk. All the subjobs run in parallel. Each subjob produces an intermediate output file and a histogram file. The job manager process monitors the log files of the reconstruction subjobs to determine when they are all complete. If any fail it will attempt to restart them, unless it determines that the failure is permanent (rather than due to a transient problem). Once all reconstruction subjobs complete it starts the collation of the intermediate files into the database and merges the histograms. In principle, these two jobs can occur in parallel.

Web pages showing the status and statistics of completed runs and runs in process are produced automatically. In addition to vital statistics about each run (such as event count, subjob state, beam energy, luminosity and cross-sections), they contain reasonably accurate predictions of the completion time for each process. The predictions are based on the number of events remaining and the average time per event so far for a subjob or a run. They also contain a prediction for the completion time of the entire dataset. (The prediction extrapolates the average processing time per event for the runs so far processed to the runs awaiting processing.) This is used to ensure that the data for the next dataset to be processed are staged in a timely fashion so that the time delay between the completion of one dataset and the start of the next is minimal. In fact, we have even started processing a new dataset while the last few runs of the previous dataset complete. Any web page entries that have suspicious values are colored in orange or red to attract the attention of the operator and senior physicists.

## III THE IMPLEMENTATION

There are many utilities to simplify the work of the operator. Only the core of the implementation is described here.

The system is mostly written in object-oriented Perl perl-ref . A small number of shell scripts are used to start the reconstruction and collation software. The software is not general purpose. It is closely tailored to the CLEO III environment. However, the ideas behind it should be applicable to many other domains.

Each run is managed by a job manager process. When the raw data for a run has been staged to disk, the operator starts the job manager process for that run. A submission script is used to start the job managers for pre-staged runs. When the SGE job queue is short enough the submission script submits more runs, one at a time, until the queue is considered long enough.

The job manager does not do any processing of Raw data. Instead it accepts four arguments:

1. run number
2. reconstruction script
3. collation script
4. histogram merge script

The three scripts are responsible for all data analysis activities. The job manager performs the following tasks:

* It splits its run into roughly equal-sized chunks. We chose approximately 20K events so that reconstruction subjobs would finish in about six hours.
* It uses configuration files to estimate the approximate output volume for each script and selects a disk for the output of each reconstruction subjob and collation subjob. The output disk selection system attempts to avoid overfilling any output disks and overloading any of the output disk servers. If necessary, a job is delayed until a server with sufficient capacity to handle it becomes available. The histogram output is quite small and is stored in a fixed directory for each dataset.
* It starts a subjob (using SGE) to reconstruct that run, writing the output to an intermediate file.
* It waits for all the reconstruction subjobs to complete.
* If any fail due to transient problems it attempts to rerun the failed jobs. Any permanent failures result in email to the operator.
* Once all the reconstruction subjobs complete successfully the job manager starts the collation subjob. This takes from 6 to 18 hours, depending on the size of the run. If it fails, the job manager sends email to the operator and terminates. It cannot be rerun automatically because the DBA must clean out the mess left by the failed attempt.
* Once the collation completes successfully, the histograms are merged using PAW paw-ref . This takes between 5 and 15 seconds. It could be done in parallel with the collation subjob, but the extra code required for the parallelism is not worth the complexity.

Note that the job manager can be restarted if it is killed or if the CPU where it is running fails. When started it detects any subjobs that are still running, detects any subjobs that have completed while it was gone, and then resumes where it left off. If the job manager detects any failures it sends email to the operator, so the operator does not need to perform as much system monitoring. The automatic retrying of jobs also reduces operator intervention and ensures timely completion of jobs. It can result in wasted CPU power if it is retrying jobs with permanent failures, but the waste is slight compared with the benefits.

Figure 1) gives an overview of the process as time increases from left to right. The output file marked “PDS” is the intermediate file. The output files labeled “.rzn” are the histogram files.

The reconstruction command passed to the job manager can be any executable. For CLEO III it is a shell script that runs the appropriate CLEO III software for reconstruction. Likewise for the collation subjob. The merge histograms subjob is also a shell script, but it runs a simple PAW program that merges the histograms produced by the reconstruction subjobs.

## IV RESULTS

We selected a chunk size such that it takes about 6 hours for the reconstruction phase. The amount of time for a job can be predicted more accurately after about 10% of the events are done. An estimate can also be made for the collation job. The estimates are calculated and displayed on the status web pages. This greatly assists in load balancing and the shorter execution time greatly increases the flexibility for transferring CPUs from one farm to another to meet spikes in demand.

The total run time for a job has been reduced to 12-24 hours. The long time required to inject the data into the Objectivity/DB database is due, in part, to the serial injection of each event. No mechanism has been devised for injecting the data in parallel. Implementation issues in Objectivity/DB make it undesirable to have a separate database for each chunk - database identifiers would run out too quickly.

Fault tolerance has been dramatically improved.

1. If one event triggers a failure in the reconstruction software, only the events in that small chunk need to be reprocessed instead of the entire run.
2. Bugs in reconstruction do not result in a run partially populated into the Objectivity/DB, which reduces the administrative overhead of cleaning out partial runs. Failures in collation still occur, but far less frequently.
3. Because there is a process monitoring the progress of each run much of the fault detection and some recovery is automated.

Reviewing the initial problems described in the introduction:

1. The time to stop the processor farm has been reduced to between 6 and 18 hours, depending on the size of the collation subjobs that are running. Much of the time, few collation jobs are running, and a decision could be made to stop the farm almost immediately and clean out the handful of runs in collation phase. Reconstruction jobs can be stopped at any time, since restarting the job manager at a later time will cause the interrupted jobs to be automatically rerun.
2. The relatively short runtime for each subjob, and the completion time estimates for each subjob greatly simplify the CPU farm load balancing issues.
3. Database locks are now held only during collation, which is the minimum possible time for holding the locks.
4. The write rate to the database is now about 3 to 4 events per second, compared with several seconds per event under the old system. The performance is disappointing, but as good as we can do with the current database schema.
5. The only failure modes during writing the database are hardware problems and collation failures. The reconstruction failures have been eliminated.
6. The window for failures (especially hardware and power failures) has been reduced from 9 days to 18-24 hours. This is a dramatic improvement.
7. The potential CPU waste at the start of a new dataset when checking the reasonableness of the reconstruction output for the first few runs of a dataset has been reduced to substantially lower than 24 hours, and as little as 12 hours if we use a small run.
8. Reproducing bugs is much easier and quicker.
9. The automatic rerunning of failed reconstruction jobs often results in quicker processing of a dataset. It also aids in debugging, since a second attempt is quickly made, which will indicate if a fault is transient, pseudo-random or reproducible.

Some potential disadvantages of the new system are worth noting.

* The data delivery rate to the Objectivity/DB disk servers is much higher but for shorter periods. In pathogenic situations this may result in performance degradation. Normally it is not a problem, since only a few collation jobs are running at the same time, and each may be assigned a different disk server for its output. However, since the collation subjob tends to run for much longer than the reconstruction subjob, towards the end of a dataset it is possible that a large number of collation jobs are running simultaneously. Because the output disk selection system prevents overloading a server, it may be the case that some collation jobs are delayed until a server has sufficient capacity to handle the job.
* The total number of CPU cycles used by this method of running reconstruction is greater than the old system. The compensation is that the wall-clock time to complete a dataset is much less. By consuming slightly more CPU cycles to do the work, far fewer CPU cycles are wasted or idle.
* There are more log files, requiring somewhat more disk space. This is not a significant burden.
* The operator frequently gets bored and drifts off to refill printers or load tapes.

The rate of reconstruction has increased about 20% due to the introduction of finer-grained parallelism. Several factors led to this. The most significant is having accurate estimates for the completion time of a dataset. This allows data for the next dataset to be processed to be staged to disk from tape “just in time”. Several bugs have been fixed as a result of the easier debugging, so there are fewer crashes. Automatic submission of new jobs when the job queue is almost empty also ensures almost full utilization of the available CPU power.

## V FUTURE DEVELOPMENTS

The next step in the automation of reconstruction is to automatically stage raw data from the HSM file systems to cache disk and then feed the staging information directly to the reconstruction system. In this way, newly staged runs are almost immediately available for processing. No operator intervention will be required for them to be reconstructed. Automatically staging the reconstruction output back to the HSM file system is the final step in the process.

The SGE is available on Linux sge-linux-ref . Both the CLEO III software infrastructure and Objectivity/DB are being ported to Linux. Once these ports are available we hope to be able to run CLEO III reconstruction on low-cost Linux nodes, which should yield substantially better price/performance.

Major performance gains will be made by replacing Objectivity/DB with a simpler and faster database management system that allows dramatically faster storage of the reconstruction output.

## VI CONCLUSIONS

The reconstruction system described above would not have been possible without support for multiple input and output formats in the CLEO III software infrastructure. The flexibility it provides has been of great benefit here and in other respects.

It is true that more CPU cycles are used to process the reconstruction than in the old system. However, since far fewer cycles are wasted, and CPUs are idle for a much smaller percentage of the time, the CPU utilization is much higher, and the time to complete a dataset has decreased. The extra cost of the fault tolerance is a worthwhile trade-off.

Accurately predicting the completion time for processing of a dataset substantially reduces delays between the completion of one dataset and the start of the next.

Quantizing the time for each job greatly simplifies system management. Predictable behavior brings huge benefits.

Automating many of the tasks catches more problems and catches them much earlier than human searching of log files. Since there are hundreds of log files to check on, and the computer is well suited to the task, reducing human involvement is worthwhile. The operator has fewer details to attend to, is more productive and less stressed as a result. He is most grateful.

The fault-tolerance features demonstrated their utility when Ithaca experienced an ice storm in the first week of January 2003. After cleaning out the database for the 4 or 5 collation jobs killed by the power failure, the job managers were restarted. All the failed subjobs were correctly rerun automatically. Almost no time was spent checking log files and cleaning up the entrails. That freed staff to focus on other recovery matters and lightened the workload in a time of crisis. Under the old system, 133 jobs would have had to have been cleaned out of the database. The restart could have taken several days to prepare for, rather than just a few minutes.

###### Acknowledgements.

The authors would like to thank the following people: Jean Duboscq and David Kreinick for removing obstacles (as good managers should), Dan Riley for excellent technical advice and Curtis Jastremsky for keeping a positive attitude during testing, and giving us the insights that only an operator has.


text:
# 1 Introduction

## 1 Introduction

The Randall-Sundrum (RS) model provides a natural geometric picture for the hierarchy between the weak scale and the apparent gravitational scale, $`\overline{M}_{Pl}`$. In this model, two 3-branes truncate a 5-dimensional curved spacetime. In the original RS construction, the Standard Model (SM) fields reside on the SM (or TeV) brane where a scale, which is exponentially smaller than the fundamental 5-d scale, is induced by the geometry. Gravity is localized on the second brane, known as the Planck brane. This exponential hierarchy is controlled by the distance $`r_c`$ between the two branes and can generate the weak scale on the SM brane. The physics of the graviton Kaluza-Klein (KK) modes is governed by the same scale. It has been shown that $`r_c`$ can be stabilized by bulk scalar fields, resulting in the appearance of a single weak scale radion field.

The most generic and distinctive signature of this model is the presence of TeV-scale spin-2 graviton KK resonances at colliders. It is important to examine whether modifications arising in a more realistic RS scenario could affect the KK graviton phenomenology. One such modification is the introduction of brane curvature terms for the graviton. These terms respect all 4-d symmetries, and are expected to be present in a 4-d effective theory, leading to Brane Localized Kinetic Terms (BLKT’s) for the graviton. It has been argued that brane quantum effects can generate BLKT’s, and that these terms are required as brane counter terms for bulk quantum effects. In addition, since the Higgs field is assumed to reside on the SM brane, a Higgs-curvature mixing term can be included in the brane action. Such a term is allowed by all 4-d symmetries and leads to Higgs-radion mixing with important phenomenological consequences. We observe that the same Higgs-curvature mixing term can also induce a BLKT for the graviton on the SM brane. Thus, there are many good theoretical reasons for assuming the presence of such terms for gravitons.

The effects of BLKT’s on graviton physics have been studied for flat spacetimes and result in novel features. Boundary terms have also been shown to significantly modify the KK phenomenology of bulk gauge fields in flat and warped geometries. For the case of an alternative RS model with only one brane and an uncompactified 5th dimension, the gravitational and cosmological effects of these terms have been analyzed. However, the case of the compactified RS model, which is relevant for weak scale physics, in principle involves graviton boundary terms on both branes and has yet to be examined. We study this case here and investigate the effects on the phenomenology of the weak scale KK gravitons in the presence of localized curvature terms.

We derive the modified graviton KK spectrum and couplings and show that a significant dependence on the size of such terms emerges. We illustrate that this leads to considerable changes in the low energy 4-d phenomenology of the RS model. These changes could have important implications for future searches and the potential discovery of model signatures. In addition, we derive bounds on the magnitude of the localized curvature terms on the Planck and TeV branes, by requiring the absence of graviton and radion ghost states.

The outline of this paper is as follows. In the next section, we derive the necessary formalism. Our numerical analysis is presented in section 3 and section 4 contains some concluding remarks.

## 2 Formalism

Here, we present our formalism and notation. We work in the RS background, as given by the following metric

$$ds^2=e^{2\sigma }\eta _{\mu \nu }dx^\mu dx^\nu +r_c^2d\varphi ^2,$$
(1)
where $`\sigma =kr_c|\varphi |`$, $`k`$ is the curvature scale of order $`\overline{M}_{Pl}`$, $`r_c`$ is the radius of compactification, and $`\varphi [\pi ,\pi ]`$. The extra dimension is here compactified on an $`S^1/Z_2`$ orbifold. The gravitational action $`S_G`$, augmented by brane localized curvature terms on the Planck and TeV branes, is assumed to be given by

$$S_G=\frac{M_5^3}{4}d^4xr_c𝑑\varphi \sqrt{G}\left\{R^{(5)}+[g_0\delta (\varphi )+g_\pi \delta (\varphi \pi )]R^{(4)}+\mathrm{}\right\},$$
(2)
where $`M_5`$ is the 5-d reduced Planck mass, $`Gdet(G_{\mu \nu })`$ and $`g_{0,\pi }`$ are numerical coefficients which are treated as phenomenological inputs in our calculations; one may expect $`g_{0,\pi }1`$ based on naturalness aguments. Here, $`R^{(5)}`$ denotes the 5-d gravitational curvature and $`R^{(4)}`$ is the 4-d curvature which is constructed only out of 4-d Minkowski metric components and derivatives. The terms proportional to $`g_{0,\pi }`$ represent the only modifications to the original RS proposal  that we study in this work. Note that we have assumed that the form of the brane terms are exactly the same as the bulk term except that they are calculated with the relevant 4-d metrics. In principle, one can imagine brane terms which are quadratic or even higher order in $`R`$, but these terms are small and would violate the philosophy of the original model where classical general relativity is applicable. As we will see below, brane terms of the type we consider here only alter the detailed structure while retaining the general nature of the usual RS solutions.

We will consider metric perturbations of the form

$$G_{\mu \nu }=e^{2\sigma }(\eta _{\mu \nu }+\kappa _5h_{\mu \nu }),$$
(3)
with $`\kappa _5=2M_5^{3/2}`$; $`h_{\mu \nu }`$ is the 5-d graviton field. The transverse-traceless gauge will be implemented in our calculations; this corresponds to taking $`^\mu h_{\mu \nu }=h_\mu ^\mu =0`$. We use a KK expansion for $`h_{\mu \nu }`$ of the form

$$h_{\mu \nu }(x,\varphi )=\underset{n}{}h_{\mu \nu }^{(n)}(x)\frac{\chi ^{(n)}(\varphi )}{\sqrt{r_c}},$$
(4)
where $`h_{\mu \nu }^{(n)}(x)`$ are the KK modes and $`\chi ^{(n)}(\varphi )`$ are the wavefunctions along the extra dimension. With this expansion, Eqs.(2) and (3) imply the following equation of motion

$$\frac{d}{d\varphi }\left(e^{4\sigma }\frac{d}{d\varphi }\chi ^{(n)}\right)+[1+g_0\delta (\varphi )+g_\pi \delta (\varphi \pi )]e^{2\sigma }r_c^2m_n^2\chi ^{(n)}=0,$$
(5)
where $`m_n`$ is the mass of the $`n^{th}`$ KK mode. Away from the boundaries at $`\varphi =0,\pi `$, for $`n1`$, we have

$$\chi ^{(n)}(\varphi )=\frac{e^{2\sigma }}{N_n}\zeta _2(z_n),$$
(6)
where $`N_n`$ are normalization constants, $`\zeta _q(z_n)J_q(z_n)+\alpha _nY_q(z_n)`$, with $`z_n(\varphi )(m_n/k)e^\sigma `$, and $`\alpha _n`$ are numerical coefficients to be fixed below; $`J_q`$ and $`Y_q`$ are Bessel functions of order $`q`$.

Let $`\epsilon _nz_n(0)`$ and $`x_nz_n(\pi )`$. Integrating Eq.(5) around $`\varphi =0,\pi `$ yields

$$\zeta _1(\epsilon _n)+\gamma _0\epsilon _n\zeta _2(\epsilon _n)=0$$
(7)
and

$$\zeta _1(x_n)\gamma _\pi x_n\zeta _2(x_n)=0,$$
(8)
respectively, with $`\gamma _{0,\pi }g_{0,\pi }kr_c/2`$. Addressing the hierarchy problem requires $`kr_c10`$, hence, we expect $`|\gamma _{0,\pi }|<\mathrm{\hspace{0.17em}\hspace{0.17em}10}`$. Eq.(7) yields

$$\alpha _n=\frac{J_1(\epsilon _n)+\gamma _0\epsilon _nJ_2(\epsilon _n)}{Y_1(\epsilon _n)+\gamma _0\epsilon _nY_2(\epsilon _n)}.$$
(9)
Here, we note that for $`\gamma _01/2`$ Later we will show that $`\gamma _0=1/2`$ is not a physically allowed value., $`\alpha _n\epsilon _n^2`$, where $`\epsilon _n10^{15}`$ for the lowest lying KK modes. The roots of Eq.(8) give the masses $`m_n=x_nke^{kr_c\pi }`$. Note that with $`\alpha _n`$ sufficiently small we can safely neglect the $`Y_q`$ components of the eigenvalue equation. This implies that the masses of the KK graviton tower are $`\gamma _0`$ independent unlike what happens in the corresponding case with gauge bosons in the bulk. It can be shown that for $`\gamma _\pi 1`$, an additional root $`x^{}1`$ is obtained, where

$$x^{}2(\gamma _\pi +1/2)^{1/2}.$$
(10)
This implies that there is a light mode in the spectrum for $`\gamma _\pi 1`$. We will show that this signals an instability in this background.

Next, we will fix the normalization $`N_n`$ of the KK modes by requiring

$$𝑑\varphi e^{2\sigma }[1+g_0\delta (\varphi )+g_\pi \delta (\varphi \pi )]\chi ^{(n)\mathrm{\hspace{0.17em}2}}=1.$$
(11)
For $`n=0`$, this equation yields the zero mode wavefunction

$$\chi ^{(0)}=\left(\frac{kr_c}{1+2\gamma _0}\right)^{1/2},$$
(12)
which demonstrates that we must have $`\gamma _0>1/2`$ in order for the zero mode to be a physical state. For $`n1`$, Eq.(11) gives

$$N_n^2=\frac{e^{2kr_c\pi }\zeta _2^2(x_n)}{kr_c}(1+\gamma _\pi ^2x_n^22\gamma _\pi ),$$
(13)
where terms of order $`e^{2kr_c\pi }`$ have been ignored. In the limit that we can neglect the $`\alpha _n`$, this form implies that the graviton wavefunctions are $`\gamma _0`$ independent. Note that this normalization factor remains positive for all values of $`\gamma _\pi `$ so that this parameter is not constrained by these considerations.

We can now obtain the couplings of the KK gravitons to the energy momentum tensor $`T_{\mu \nu }`$ of the fields residing on the TeV brane at $`\varphi =\pi `$. To do this, first we note that the action (2) yields

$$\overline{M}_{Pl}^2=\frac{M_5^3}{k}(1+2\gamma _0),$$
(14)
where $`\overline{M}_{Pl}`$ is the 4-d reduced Planck mass and terms of order $`e^{2kr_c\pi }`$ have been ignored. The Lagrangian for the interactions of $`h_{\mu \nu }`$ and the 4-d fields on the TeV brane is given by

$$=\frac{1}{M_5^{3/2}}h_{\mu \nu }(x,\pi )T^{\mu \nu }(x).$$
(15)
Eqs.(6), (12), (13), and (14) then yield

$$=\frac{1}{\overline{M}_{Pl}}h_{\mu \nu }^{(0)}(x)T^{\mu \nu }(x)+\frac{1}{\mathrm{\Lambda }_\pi }T^{\mu \nu }(x)\underset{n=1}{\overset{\mathrm{}}{}}\lambda _nh_{\mu \nu }^{(n)}(x),$$
(16)
with $`\mathrm{\Lambda }_\pi \overline{M}_{Pl}e^{kr_c\pi }`$ as usual and

$$\lambda _n\left(\frac{1+2\gamma _0}{1+\gamma _\pi ^2x_n^22\gamma _\pi }\right)^{1/2}.$$
(17)
As expected, the zero mode coupling is $`\overline{M}_{Pl}^1`$ and for $`\gamma _0,\gamma _\pi 0`$, the original RS model coupling for the non-zero mode KK states, $`\mathrm{\Lambda }_\pi ^1`$ , is retrieved. Choosing $`\gamma _\pi 0`$ renders the KK couplings mode dependent, through $`\lambda _n`$. We see that for $`\gamma _\pi x_n1`$ these couplings have suppressions $`(\gamma _\pi x_n)^1`$.

Before continuing, we consider if there are any further constraints which can be imposed upon the parameters $`\gamma _{0,\pi }`$. Though here we are concerned with the effect of brane terms on the masses and couplings of the KK gravitons, the RS metric yields another excitation, the radion, whose properties may also be modified by such terms. Using the results of Csaki et al., for example, the effects of the brane terms on the radion can be determined since they are similar in form to those which induce Higgs-radion mixing. A short analysis shows that the brane terms lead to a multiplicative correction to the usual radion kinetic term, in the absence of the Higgs field, by a factor of $`1\gamma _\pi `$; the corresponding $`\gamma _0`$-dependent contribution is found to be suppressed by powers of the exponential warp factor and we will ignore it in the following discussion. To avoid a radion ghost this implies that $`\gamma _\pi 1`$, suggesting that negative or small positive values of $`\gamma _\pi `$ are allowed. This multiplicative factor can then be absorbed by a suitable field rescaling so that the radion field becomes canonically normalized. However, once the Higgs-radion mixing term is included, this bound becomes a bit more complex since mixing and brane term contributions can compensate for one another. If the brane localized curvature for gravitons arises from solely the same source as Higgs-radion mixing  then we find that similar bounds on $`\gamma _\pi `$ can also be obtained. §§§In the notation of Csaki et al., we find that the induced value of $`\gamma _\pi `$ is given by $`\gamma _\pi =\xi (1+2\gamma _0)(v/\mathrm{\Lambda }_\pi )^2`$, where $`v`$ is the SM Higgs vev and $`\xi `$ is the radion-Higgs mixing parameter. Putting in some reasonable numbers, we see that the induced $`\gamma _\pi `$ is of order unity or less in magnitude. Of course, such brane terms can arise from many other sources so that a much wider range of values of $`\gamma _\pi `$ are certainly possible. Naturalness suggests that $`\gamma _\pi 10`$ as discussed above and we will assume this soft bound in our discussion below.

## 3 Analysis

The first step in our analysis is to examine how the mass spectrum of the graviton KK modes is influenced by the presence of the brane kinetic terms parameterized via $`\gamma _{0,\pi }`$. As was noted above, both the root equation and the wave functions for the graviton KK modes in the extra dimension are found to be independent of $`\gamma _0`$ when powers of the warp factor, $`e^{\pi kr_c}`$, are neglected; this implies that the $`x_n`$ for the range of interest to us are essentially $`\gamma _0`$ independent. Recall that the masses of the KK states are now given by $`m_n=x_n(\gamma _\pi )ke^{kr_c\pi }`$. Fig. 1 displays these roots as a functions $`\gamma _\pi `$. (For purposes of comparison we note that the first root in the usual RS model without brane terms is given by $`x_13.83`$.) For all KK modes, other than the case $`n=1`$, the $`x_n`$ are essentially constant away from the transition region near $`\gamma _\pi =0`$. As we see from the root equation above, once $`|\gamma _\pi |`$ gets large the $`x_n`$ are essentially just the roots of the equation $`J_2(x_n)=0`$ which accounts for their mostly $`\gamma _\pi `$ independent behaviour. The root $`x_1`$ behaves somewhat differently and scales as $`2/\sqrt{\gamma _\pi }`$ for large positive $`\gamma _\pi `$ as seen from Eq.(10) above. Note that this causes the ratio of the first two roots $`x_2/x_1`$ to grow substantially in the large and positive $`\gamma _\pi `$ region.

Once the $`x_n`$ are known the effective couplings of the KK modes to SM matter on the TeV brane can be immediately calculated and are shown in Fig. 2 for the case $`\gamma _0=0`$; for other values of $`\gamma _0`$ these results are scaled by a factor of $`\sqrt{1+2\gamma _0}`$. Except for the lowest KK mode when $`\gamma _\pi >0`$, the couplings of all KK modes are observed to fall off drastically as the magnitude of $`\gamma _\pi `$ increases, demonstrating the $`1/|x_n\gamma _\pi |`$ behavior, as expected. Clearly, the reduced couplings of these graviton KK modes will have a important impact on the ability to detect these states either directly or indirectly at colliders. This will be true in particular in the case of of positive $`\gamma _\pi `$, where as we saw above the second KK mode is significantly heavier than the first mode and has a much weaker coupling to the SM brane fields. However, we note that the absence of a radion ghost would exclude this extreme situation if we apply the analysis as given in Ref. .

Perhaps the most important experimental signature for the RS model is the appearance of spin-2 KK resonances at colliders. As shown above, when $`\gamma _\pi `$ is non-zero the masses and couplings of these KK states are altered from the usual expectations for which the phenomenology has by now been well explored. Figs. 3 and 4 show some of the possible modifications in the presence of the boundary terms to the production cross section and KK spectrum for the cases $`k/\overline{M}_{Pl}=1`$ and 0.1, respectively, for the process $`e^+e^{}\mu ^+\mu ^{}`$ at a linear collider assuming the mass of the first KK resonance is 600 GeV. For the case of $`k/\overline{M}_{Pl}=1`$ in the usual RS model, which corresponds to $`\gamma _\pi =0`$ and is represented by the dotted curve in Fig. 3, the KK states are sufficiently strongly coupled to smear out the individual resonance structures and produce only a large shoulder in the cross section. For non-zero $`\gamma _\pi `$, there is a significant change in these expectations due to the reduced values of the couplings and the additional mass spectrum modifications. This is seen explicitly in these two figures. Note that the widths of these graviton resonances scale as $`\mathrm{\Gamma }_n/m_n(x_n\lambda _nk/\overline{M}_{Pl})^2`$ where $`\lambda _n`$ is the relative coupling strength for the $`n`$-th KK mode calculated in Eq.(17) and shown in Fig. 2. For positive values of $`\gamma _\pi `$ the lowest KK mode is well separated in mass from the next more massive state. For $`\gamma _\pi <0`$ the strong constructive interference between the resonances rapidly vanishes and individual peaks become observable. As $`\gamma _\pi `$ decreases further this results in a series of very narrow, spike-like peaks once values of $`10`$ are reached.

When $`k/\overline{M}_{Pl}=0.1`$ the effects of the brane terms are in some sense much more severe as can be seen from Fig. 4 due to the further reduction in the resonance widths by a factor of 100. The usual resonances, the first few of which are reasonably narrow in the standard RS scheme in this case, are converted into narrow spikes some if not all of which will yield event rates which are quite small compared to the continuum background in any given mass bin. For $`\gamma _\pi `$ positive and of order unity the unique feature here is the large mass gap between the first and second resonances. For $`\gamma _\pi `$ negative the resonance structures are also narrow but with a smaller mass gap. With this or even smaller values of $`k/\overline{M}_{Pl}`$, it may be difficult to observe anything, even the first KK graviton excitation, over much of the range of $`\gamma _\pi `$ unless use is made of radiative returns or one is lucky choosing the collider center of mass energy in performing a scan. It is clear from our discussion that it is important to see at least two of these resonance peaks to uniquely identify the model and extract out the relevant parameters.

The shifts in the mass spectrum and couplings of the KK resonances induced by the brane kinetic terms are so large that even for values of $`|\gamma _\pi |=0.2`$, there are substantial modifications to the shape of the production cross section. This is seen explicitly in Fig. 5.

If the graviton KK modes are kinematically accessible they will most likely be first observed at a hadron collider. As discussed in our earlier work, the lack of observation of KK graviton resonances in, e.g., the Drell-Yan channel at the Tevatron already places a constraint on the RS model parameter space. This analysis can be modified in order to examine the influence of brane kinetic terms for the graviton; the results are presented in Figs. 6, 7 and 8 keeping in mind that values of $`k/\overline{M}_{Pl}<\mathrm{\hspace{0.17em}\hspace{0.17em}0.1}`$ are theoretically preferred. These figures show the search reach for the first graviton KK resonance in Drell-Yan production as a function of $`\gamma _\pi `$ for different values of $`k/\overline{M}_{Pl}`$.

The search reach from Run I of the Tevatron, which constitutes the present lower bound on the mass of the first KK graviton excitation, is shown in Fig. 6. Here we see that, as expected, the search reach degrades quite rapidly as we move away from the canonical value of $`\gamma _\pi =0`$. Note that for negative values of $`\gamma _\pi `$ it is still quite possible for the mass of this lightest state to be less than 200 GeV (provided this is not excluded by LEP searches for narrow resonances). For negative values of $`\gamma _\pi `$ the corresponding bound on $`\mathrm{\Lambda }_\pi `$ can be approximately obtained from the $`m_1`$ constraint by dividing by $`5k/\overline{M}_{Pl}`$.

Fig. 7 shows that future running of the Tevatron during Run II can be useful in covering some of the large $`|\gamma _\pi |`$, small KK mass region. The higher energy and integrated luminosity will result in a reasonable increase in the overall parameter space coverage compared to Run I but, as can be seen from the figure, will still allow for the existence of very light KK gravitons.

Fig. 8 shows the potential search reach for the first KK graviton resonance at the LHC. Even in this case one sees that there is a significant degradation in the reach away from $`\gamma _\pi =0`$. Unlike in the standard RS scenario without brane terms we see that the LHC can no longer cover all of the interesting parameter space for this model due to the reduced coupling of the first KK resonance. For example we see from the figure that for large negative $`\gamma _\pi `$, a first KK graviton resonance with a mass of 600 GeV and $`k/\overline{M}_{Pl}=0.01`$ may still miss detection - even at the LHC.

It is possible that the indirect effects of graviton KK tower exchange in particle pair production may be observed. This may be more important than direct graviton searches in some regions of parameter space. These indirect effects are similar to those of contact interactions, except that the graviton exchange operator is dimension-8. Graviton virtual effects have been computed for the case of large extra dimensions in Ref. , where it was noted that the angular distributions of the final state particles may reveal the spin-2 nature of the indirect graviton exchange. Here, the 4-fermion matrix element is obtained from that for the large extra dimensions scenario with the replacement

$$\frac{\lambda }{M_H^4}\frac{\overline{M}_{Pl}^2}{8k^2\mathrm{\Lambda }_\pi ^4}\underset{n}{}\frac{\lambda _n(\gamma _\pi ,\gamma _0)^2}{x_n(\gamma _\pi )^2},$$
(18)
in the limit of $`m_n^2s`$. In this model the sum rapidly converges. The coupling weighted sum over the KK tower exchanges differs from the conventional RS model by the ratio

$$=\frac{\underset{n}{}\frac{\lambda _n(\gamma _\pi ,\gamma _0)^2}{x_n(\gamma _\pi )^2}}{_n\frac{\lambda _n(0)^2}{x_n(0)^2}},$$
(19)
which is displayed in Fig. 9. We see from the figure that for positive values of $`\gamma _\pi `$ the effects of the suppressed couplings and the modified roots exactly compensate each other. The standard RS predictions are thus maintained in this region. The contact interaction bounds on $`\mathrm{\Lambda }_\pi `$ obtained from the lepton pair invariant mass spectrum and forward-backward asymmetry in Drell-Yan production at the Tevatron and LHC are presented in Fig. 10 as a function of $`\gamma _\pi `$. The results from unpolarized (and polarized in the case of the Linear Collider) angular distributions, summing over $`e,\mu ,\tau ,c,b`$ (and $`t`$ if kinematically accessible) final states, as well as $`\tau `$ polarization distributions are shown in Fig. 11 for LEP II and the Linear Collider. From these figures we see that the constraints from 4-fermion interactions are rather weak for negative values of $`\gamma _\pi `$, even for the higher energy colliders. The searches from both direct graviton production at hadron colliders and the indirect exchange of graviton KK states in fermion pair production are thus difficult in this parameter space region and low mass graviton states may escape detection. It is possible that searches for narrow s-channel resonances in $`e^+e^{}`$ collisions or direct graviton production in $`e^+e^{}\gamma G`$ may extend the discovery reach in this region.

## 4 Conclusions

The most generic and distinctive signature of the RS model of the hierarchy is the appearance of weak scale, spin-2 KK resonances of the 5-d graviton. The discovery of such resonances at a collider will provide strong evidence for the RS picture. It is therefore important to understand how the spectrum and the couplings of these states could be affected by well-motivated theoretical modifications of the original proposal. The addition of brane localized curvature terms is such a modification. These terms yield contributions to the graviton BLKT’s and can be generated from brane and bulk quantum effects. They can also arise at tree level due to Higgs-curvature mixing.

In this paper, we studied the consequences of adding brane curvature terms in the RS model. We derived the modified spectrum and couplings of the graviton KK states to the fields on the SM brane. The presence of localized curvature on the SM brane leads to important changes in the weak scale phenomenology. Requiring that the effective theory is free of KK and radion ghosts places lower and upper bounds on the coefficients $`\gamma _0`$ and $`\gamma _\pi `$ of these terms on the Planck and SM branes, respectively.

We showed that, within the natural and allowed values of these coefficients, the variation in the shape and production cross sections of the resonances is significant. In particular, the KK resonances become very narrow for some regions of the parameter space and may be too narrow to be observed at colliders. We found that very light KK gravitons, of order 200-600 GeV may escape detection at the Tevatron and LHC. In the contact interaction limit, where the KK masses are too large for direct production, we observed that the collider reach for the SM scale $`\mathrm{\Lambda }_\pi `$ TeV varies considerably with $`\gamma _\pi <0`$. However, for $`\gamma _\pi >0`$, this reach remains constant. The cause of this behavior is the interplay of the modified masses and couplings of the KK states. In brief, we found that the modifications resulting from brane localized curvature terms in the RS model have interesting features and that they are important for future phenomenological studies and experimental searches.

Acknowledgements

One of us (H.D.) would like to thank G. Kribs and C. Wagner for discussions related to this work. The work of H.D. was supported by the US Department of Energy under contract DE-FG02-90ER40542.


text:
# Confirmation of solar-like oscillations in eta Bootis

## 1 Introduction

The search for solar-like oscillations is finally yielding success. Observations of the sub-giants Procyon (Martic et al., 1999; Barban et al., 1999) and $`\beta `$ Hydri (Bedding et al., 2001; Carrier et al., 2001) have shown very good evidence for oscillations. More recently, there has been an unambiguous detection of p-mode oscillations in the main sequence star $`\alpha `$ Cen A by Bouchy & Carrier (2001, 2002). All these results were based on velocity measurements obtained using high-dispersion spectrographs with stable reference sources.

Another method for detecting oscillations was suggested by Kjeldsen et al. (1995, hereafter Paper I). This involved monitoring changes in the equivalent widths (EWs) of temperature-sensitive spectral lines. In Paper I we reported evidence for oscillations in the G0 sub-giant $`\eta `$ Boo, based on measurements of Balmer-line EWs. We presented this as the first clear evidence of solar-like oscillations in a star other than the Sun. The observations were obtained over six nights with the 2.5 m Nordic Optical Telescope on La Palma, and consisted of 12684 low-dispersion spectra. In the power spectrum of the equivalent-width measurements, we found an excess of power at frequencies around 850 $`\mu `$Hz. The average amplitude inferred for the oscillations was about 7 times greater than solar, in rough agreement with the empirical scaling relation suggested by Kjeldsen & Bedding (1995). Comb analysis of the power spectrum, described in Paper I, suggested a regular spacing of $`\mathrm{\Delta }\nu =40.3`$$`\mu `$Hz. Based on this, we identified thirteen oscillation modes. Similar observations of the daytime sky showed the five-minute solar oscillations at the expected frequencies.

The frequencies for $`\eta `$ Boo reported in Paper I, taken with available estimates of the stellar parameters, were in good agreement with theoretical models (Christensen-Dalsgaard et al., 1995; Guenther & Demarque, 1996). Particularly exciting was the occurrence in theoretical models – and apparently in the observations – of ‘avoided crossings,’ in which mode frequencies are shifted from their usual regular spacing by effects of gravity modes in the stellar core. Since then, the improved luminosity estimate for $`\eta `$ Boo from Hipparcos measurements has given even better agreement with the measured value of $`\mathrm{\Delta }\nu `$ (Bedding et al., 1998).

Meanwhile, a search for velocity oscillations in $`\eta `$ Boo by Brown et al. (1997) has failed to detect a signal, setting limits at a level below the value expected on the basis of the EW results. Although the data were sparse (22 hours spread over 7 successive nights) and the precision was degraded by the relatively fast rotation of the star ($`v\mathrm{sin}i=13`$ km s-1), the analysis by Brown et al. (1997) was careful and thorough, and the results seem to be inconsistent with those of Paper I. More recently, Carrier et al. (2003, and paper in preparation) reported velocity measurements using the CORALIE and ELODIE spectrographs that showed a clear excess of power and a frequency spacing of $`39.6`$$`\mu `$Hz.

In this paper we present additional observations of $`\eta `$ Boo, obtained in 1998 in both EW and velocity. We also re-analyse our 1994 EW measurements and the velocity measurements of Brown et al. (1997). We confirm our earlier claim for oscillations in $`\eta `$ Boo and identify more than twenty oscillation frequencies from the combined data.

## 2 Data

### 2.1 Equivalent-width observations (NOT98)

We observed $`\eta `$ Boo over six nights during May 1998 using ALFOSC (Andalucia Faint Object Spectrograph and Camera) on the 2.5 m Nordic Optical Telescope on La Palma. This is the same telescope used in Paper I but with a different spectrograph. We obtained seven echelle orders covering the range 370–700 nm at a dispersion of 0.04 nm/pixel. The CCD was a Loral 2k by 2k device, of which we used 700 by 1200 pixels.

Spectra were taken with a typical exposure time of 11 s and a dead time between exposures of 17 s. They were averaged in groups of three before writing to disk, resulting in a total of 1843 spectra (sampling rate 1/84 s) in 44.2 hours over six consecutive nights (1998 May 1–6). The distribution of spectra over the six nights was: 88, 222, 377, 391, 358 and 407.

We used the method described by Kjeldsen et al. (1999) to measure equivalent widths of six strong temperature-sensitive lines: H$`\alpha `$, H$`\beta `$, H$`\gamma `$, Mgi, Nai and Fei. A weighted mean of these six values was calculated, taking into account the differing temperature sensitivities of the lines. The resulting time series is shown in Fig. 1.

### 2.2 Velocity observations (Lick98)

We also observed $`\eta `$ Boo in 1998 with the Hamilton Echelle Spectrometer and the 0.6-m Coudé Auxiliary Telescope (CAT) at Lick Observatory (Vogt, 1987). To produce high-precision velocity measurements, the star was observed through an iodine absorption cell mounted directly in the telescope beam.

We were allocated 56 of the 59 nights from 1998 April 6 to June 3, but the weather was unseasonably poor, permitting observations on only 26 nights (and many of these were partly lost). The exposure time was 120 s, with a dead time between exposures of the same amount. On the 11 best nights we obtained 95–120 spectra per night (sampling rate: 1/245 s), and the total number of spectra obtained was 1989 (about one third of that possible with no weather losses).

Extraction of radial velocities from the echelle spectra followed the method described by Butler et al. (1996). As mentioned in the Introduction, the precision is degraded by the relatively fast stellar rotation. The star is a spectroscopic binary with a period of 494 d (Bertiau, 1957), and the orbital motion was removed from the velocity time series by fitting and subtracting a fifth-order polynomial. The resulting velocity measurements are shown in Fig. 2. We are confident that the long-term velocity variations are not instrumental, given that velocities for $`\tau `$ Ceti, which we observed on most of the nights, were stable at the 5 m s-1 level. These night-to-night variations in $`\eta `$ Boo are presumably due to stellar activity, which is commonly observed in rotating G-type stars (see, e.g., Saar et al., 1998; Santos et al., 2000).

### 2.3 Published equivalent-width observations (NOT94)

We have included in this analysis the time series of 12684 EW measurements obtained with the Nordic Optical Telescope in 1994. These are identical to the data presented in Paper I, with the exception that a high-pass filter was not applied. The result is an increase in noise at low frequencies, as expected from a $`1/f`$ noise source, which more accurately reflects the actual stellar and instrumental noise (for more details, see Bedding & Kjeldsen, 1995).

### 2.4 Published velocity observations (AFOE95)

We have also analysed 555 velocity measurements of $`\eta `$ Boo obtained with the AFOE spectrograph during 22 hours spread over seven successive nights in 1995 March. These measurements were described by Brown et al. (1997) and were kindly provided to us in electronic form by Tim Brown.

## 3 Analysis and discussion

The power spectrum of each time series was calculated as a weighted least-squares fit of sinusoids (Frandsen et al., 1995; Arentoft et al., 1998), with a weight being assigned to each point according its uncertainty estimate. The results for the four data sets are shown in Figs. 36. In each case, we show both the conventional power spectrum (upper panels) and a smoothed version in which the vertical scale has been converted to power density (lower panels). As discussed by Kjeldsen & Bedding (1995, Appendix A.1) and Kjeldsen et al. (1999, Sec. 5), the conversion to power density is achieved by multiplying by the effective observing time, which we calculated in each case by integrating under the spectral window.

Some level of excess power in the range 600–1100 $`\mu `$Hz is apparent in all four data sets, although it is strongest in the NOT94 data. Further discussion of the measured power levels is given below in Sec. 3.4. First, however, we will discuss the oscillation frequencies.

Mode frequencies for low-degree solar-like oscillations are approximated reasonably well by the asymptotic relation:

$$\nu _{n,l}=\mathrm{\Delta }\nu (n+\frac{1}{2}l+\epsilon )l(l+1)D_0.$$
(1)
Here, $`n`$ and $`l`$ are integers that define the radial order and angular degree of the mode, respectively; $`\mathrm{\Delta }\nu `$ (the so-called large separation) reflects the average stellar density, $`D_0`$ is sensitive to the sound speed near the core and $`\epsilon `$ is sensitive to the surface layers. It is conventional to define $`\delta \nu _{02}`$, the so-called small separation, as the frequency spacing between adjacent modes with $`l=0`$ and $`l=2`$. We can further define $`\delta \nu _{01}`$ to be the amount by which $`l=1`$ modes are offset from the midpoint between the $`l=0`$ modes on either side. If the asymptotic relation holds exactly, then it is straightforward to show that $`D_0=\frac{1}{6}\delta \nu _{02}=\frac{1}{2}\delta \nu _{01}`$.

### 3.1 Extraction of frequencies

We extracted the frequencies of the strongest peaks in each power spectrum in the range 600–1100 $`\mu `$Hz. We used a simple iterative algorithm, in which the highest peak was identified and the corresponding sinusoidal variation was subtracted from the time series. The power spectrum of the residuals was then calculated and the process was iterated until all peaks with amplitudes more than 2.5 times the noise floor had been extracted. The numbers of peaks extracted from the four data sets are summarized in Table 1.

Setting the threshold at 2.5$`\sigma `$ gives us a chance to detect the weaker oscillation modes, but it also means we will select some noise peaks. To investigate this, we have conducted simulations in which we analysed noise spectra that contained no signal. The last column in Table 1 shows the number of peaks found above the 2.5$`\sigma `$ threshold. This indicates that about 6 of the 35 detected peaks are expected to be due to noise.

### 3.2 Large frequency separation

We next investigated whether the extracted frequencies have a regular spacing, as is expected for p-mode oscillations. In Paper I, we described a comb analysis of the NOT94 power spectrum that revealed a regular spacing of $`\mathrm{\Delta }\nu =40.3`$$`\mu `$Hz. Here, we analyse the 22 frequencies from the other three data sets (AFOE95, NOT98, Lick98) using autocorrelation, as follows. Firstly, each extracted frequency was allocated a power corresponding to the square of its S/N, in order to give higher weight to the more reliable peaks. Secondly, to allow for the likelihood that some of the extracted frequencies should be shifted by $`\pm `$1 d-1 ($`\pm `$11.57 $`\mu `$Hz), we extended the table of frequencies by a factor of three by including these side-lobes (but with half the power of the central peaks). We then calculated the autocorrelation of these 66 frequencies. This is shown, smoothed to a resolution of 3.5 $`\mu `$Hz, as the solid line in Fig. 7.

The three peaks in the autocorrelation correspond to the large separation and its daily aliases, leading us to estimate a value of $`\mathrm{\Delta }\nu =40.4`$$`\mu `$Hz. For comparison, the dotted line in Fig. 7 shows the autocorrelation for the 13 frequencies extracted from the NOT94 data, which yields a large separation of $`\mathrm{\Delta }\nu =40.5`$$`\mu `$Hz. The excellent agreement between these independent data sets confirms the result of Paper I and also agrees well with the value of $`39.6`$$`\mu `$Hz reported by Carrier et al. (2003). In summary, there can be no doubt that the large frequency separation of $`\eta `$ Boo is about 40 $`\mu `$Hz, which is in excellent agreement with theoretical models (Christensen-Dalsgaard et al., 1995; Guenther & Demarque, 1996).

### 3.3 Identification of frequencies

Given the large separation, we next attempted to identify the individual modes, remembering that some of them will need to be shifted by $`\pm `$11.57 $`\mu `$Hz. Figure 8 shows the 35 frequencies from all four data sets, displayed in an echelle diagram. We expect modes with a given $`l`$ value to form vertical ridges, for $`l=0`$, $`1`$ and $`2`$. We were able to achieve this by shifting 15 frequencies by $`\pm `$11.57 $`\mu `$Hz, as shown in the figure. The final frequencies are given in Table 2. Note that the number of peaks that are classified as noise is consistent with the estimates made above (see Table 1).

A possible problem is that, modulo the large separation, peaks corresponding to ($`\nu _{n,l}11.57`$$`\mu `$Hz) for $`l=1`$ are only separated by 1.1 $`\mu `$Hz from peaks corresponding to ($`\nu _{n,l}+11.57`$$`\mu `$Hz) for $`l=2`$. It is possible that some of those peaks have been shifted the wrong way and are therefore wrongly identified. The relevant peaks are $`699.6\mu \text{Hz}`$ (from Lick98), which we identified as an alias of an $`l=1`$ mode, and $`822.3\mu \text{Hz}`$ (from NOT94), which we identified as an alias of an $`l=2`$ mode. A similar comment, although to a lesser extent, applies to peaks corresponding to ($`\nu _{n,l}11.57`$$`\mu `$Hz) for $`l=0`$ and to ($`\nu _{n,l}+11.57`$$`\mu `$Hz) for $`l=1`$, which are only separated by 1.9 $`\mu `$Hz.

Note that we have identified the peak at 749.3 $`\mu `$Hz as possibly being an $`l=1`$ mode that is displaced by an avoided crossing. This peak has the second-highest S/N of all the peaks and is therefore not likely to be due to noise or to be an alias. In any case, shifting this peak by $`\pm `$11.57$`\mu `$Hz would not bring it into agreement with $`l=0`$ or 2.

Some of the frequencies are detected more than once, as indicated by the ditto marks (”) in Table 2. In those cases, we have combined the measurements into a weighted average. The final list of 21 frequencies is given in Table 3, and these are shown as an echelle diagram in Fig. 9. The uncertainties in the frequencies reflect the S/N of the relevant peak (or peaks).

We next estimated the large separation separately for each value of $`l`$, and the results are given in the last line of Table 3 (the two modes marked with an asterisk, which may be affected by avoided crossings, were excluded from the fit). The weighted average of these three $`\mathrm{\Delta }\nu _l`$ yields the value of $`\mathrm{\Delta }\nu `$ shown in Table 4. The other parameters in that table were calculated by fitting the same 19 frequencies to the asymptotic relation. All are consistent with the values given in Paper I but have smaller uncertainties, thanks to the larger number of detected frequencies.

In Fig. 9 we also show the 13 frequencies reported in Paper I. We can see that six were recovered in the new analysis, while five were not recovered but lie close to one of the ridges (within typical uncertainties), so perhaps can still be taken as reliable detections. Finally, two frequencies (786.2 and 950.3 $`\mu `$Hz) fall well away from the $`l=1`$ ridge and were not confirmed by the revised analysis. It is possible that they represent mixed modes that are shifted by avoided crossings, but further observations are needed to confirm this.

### 3.4 Oscillation amplitudes

The above analysis gives strong evidence that the highest peaks in the four power spectra are due to solar-like oscillations. However, we have also noted that the amplitude of the power excess is somewhat stronger in the NOT94 observations than in the other three data sets. It seems plausible that these differences reflect the stochastic nature of the excitation mechanism, but a more definite statement is hampered by our limited knowledge of the amplitudes of oscillations in subgiant stars. It is also possible that some contribution to the variations is due to an unidentified systematic error in the calibration that was used to convert equivalent-width amplitudes to velocities (see Paper I).

Taken at face value, the observations indicate that peak oscillation amplitudes in $`\eta `$ Boo are typically 3–5 times solar. This conclusion is consistent with the upper limits reported by Brown et al. (1997) from the AFOE95 data.

## 4 Conclusions

We have presented new observations of $`\eta `$ Boo in velocity (Lick98) and equivalent width (NOT98) that show some evidence for excess power in the range 600–1100 $`\mu `$Hz. The velocity measurements published by Brown et al. (1997, AFOE95) also show a slight power excess when smoothed. None of these signals is as strong as the original equivalent-width observations (Paper I, NOT94), which may reflect the stochastic nature of the excitation or may indicate a problem with the calibration of the NOT94 equivalent-width estimates.

We extracted the highest peaks in each data set and used the autocorrelation to search for regularity. The three newer data sets (AFOE95, NOT98 and Lick98) combined to give a clear autocorrelation signal at a spacing of $`\mathrm{\Delta }\nu =40.4`$$`\mu `$Hz, giving independent confirmation of the result of Paper I. This, combined with the recent work by Carrier et al. (2003), leaves little doubt that the large frequency separation of $`\eta `$ Boo is about 40 $`\mu `$Hz. This allowed us to identify 21 frequencies in $`\eta `$ Boo which have been compared with theoretical models by Di Mauro et al. (2003). The results confirm the claim made in Paper I for the first clear evidence of solar-like oscillations in a star other than the Sun. Future observations of $`\eta `$ Boo, particularly with the MOST spacecraft (Matthews et al., 2000), should measure more oscillation modes with greater frequency precision.

We would be pleased to make the data available on request. Please contact Tim Bedding (`bedding@physics.usyd.edu.au`).

We thank Tim Brown for providing the AFOE velocity measurements of $`\eta `$ Boo. This work was supported financially by the Australian Research Council (TRB and IKB), National Science Foundation Grant AST-9988087 (RPB), SUN Microsystems, and the Danish Natural Science Research Council and the Danish National Research Foundation through its establishment of the Theoretical Astrophysics Center (HK).