text:
# A semidefinite representation for some minimum cardinality problems

### Notation

We note $`\text{R}[x_1,\mathrm{},x_n]`$ (or $`\text{R}[x]`$ when there is no ambiguity) the ring of multivariate polynomials $`p(x)=p(x_1,\mathrm{},x_n)`$ on a variable $`x\text{R}^n`$. We say that $`p(x)\text{R}[x]`$ is $`SOS`$ when $`p(x)`$ is a sum of squares of polynomials in $`\text{R}[x]`$. For $`x\text{R}^n`$, $`𝐂𝐚𝐫𝐝(x)`$ will be the cardinal of the set $`\{i:x_i0\}`$. We note $`\text{S}^n`$ the set of $`n\times n`$ symmetric matrices. For multivariate polynomials, we adopt the multiindex notation $`p(x)=_\alpha p_\alpha x^\alpha `$, where $`x^\alpha :=x_1^{\alpha _1}x_2^{\alpha _2}\mathrm{}x_n^{\alpha _n}`$, and we note $`d=_{i=1}^n\alpha _i`$ the degree of $`p(x).`$ $`\text{R}_d[x]`$ is the set of polynomials of degree at most $`d`$. Finally, $`C(p)`$ will be the Newton polytope of the polynomial $`p(x)`$, with $`C(p)=𝐂𝐨\left(\{\alpha :p_\alpha 0\}\right)`$.

## 1 Introduction

Given a convex set $`𝒞\text{R}^n`$, we are interested in solving the following problem:

$$\begin{array}{cc}\text{minimize}\hfill & 𝐂𝐚𝐫𝐝(x)\hfill \\ \text{subject to}\hfill & x𝒞,\hfill \end{array}$$
(1)
in the particular case where $`𝒞`$ is described by a set of linear inequalities. Except in certain rare instances, this problem is very hard to solve (see \[VB96\]). Excellent heuristics exist however, a classical one (see \[HHB99\] for example) replacing the function $`𝐂𝐚𝐫𝐝(x)`$ by $`x_1`$, its largest convex lower bound on the unit cube.

A related problem is that of minimizing the rank of a p.s.d. matrix subject to LMI constraints:

$$\begin{array}{cc}\text{minimize}\hfill & 𝐑𝐚𝐧𝐤(X)\hfill \\ \text{subject to}\hfill & X𝒞,\hfill \end{array}$$
(2)
where $`𝒞`$ is here an affine subset of the semidefinite cone (a LMI). In this case also, minimizing the nuclear norm $`X_{}`$ of $`X`$ will produce excellent approximate solutions (see \[FHB00\]).

In this paper, using results by \[Cas84\], \[Sho87\], \[Put93\], \[CLR95\], \[Nes00\], \[Las01\], \[PS01\] and \[Las02\], we show that the $`\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x)`$ and $`\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X)`$ problems in (1) and (2) are equivalent to large semidefinite programs (see \[NN94\]). To be precise, based on a reformulation à la \[Sho87\] of problems (1) and (2), we use the technique in \[Las02\] to produce a finite (possibly exponential) sequence of increasingly tighter semidefinite relaxations.

The rest of the paper is organized as follows. In section 2, we recall some key definitions and properties on semidefinite representability and the sum of squares representation of positive polynomials. We also summarize the application of these representations to semialgebraic problems. In section 3, we show that both the $`\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x)`$ and the $`\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X)`$ problems are equivalent to large scale semidefinite programs. Based on the work by \[Put93\], \[Nes00\] and \[Las02\] we explicitly construct in section 4 a sequence of semidefinite programs solving problems (1) and (2). We also show how the problem of finding optimal convex lower bounds on the objective function can be represented in a similar way. Finally, in section 5, we discuss the complexity of these techniques.

## 2 Sums of squares and semidefinite programming

We quickly recall here some key definitions and properties linking semidefinite and semialgebraic problems.

Hilbert’s 17th problem (see \[Rez96\] for an overview), which asked if all positive polynomials could be written as sums of squares of other polynomials, has a positive answer in dimension one. \[Nes00\] provides an efficient way of computing the $`SOS`$ representation of a given positive univariate polynomial in the following result from \[Nes00\].

###### Proposition 1

Let $`p(x)\text{R}[x]`$ be a univariate polynomial of degree $`d`$. Then $`p(x)`$ for all $`x\text{R}`$ iff there exists a matrix $`X\text{S}^v`$ such that:

$$p(x)=y_x^TXy_x\text{, with }X0,\text{for all }x\text{R}$$
(3)
with $`v=d/2`$ and $`y_x=(1,x,x^2,\mathrm{},x^v)`$ is the list of univariate monomials up to degree $`v`$.

The coefficients of the polynomials in the representation are then computed as the eigenvectors of the matrix $`X`$.

In the general multivariate case, that representation property of positive polynomials is lost. It can be shown (see \[Ber80\]) that the set of multivariate $`SOS`$ polynomials is dense in the set of positive polynomials, but there are simple examples of positive polynomials that are not $`SOS`$. However, recent results in semialgebraic geometry (see \[Cas84\], \[Sch91\], \[Put93\] or \[PV99\]) bridge the gap between positive and $`SOS`$ polynomials on compact semialgebraic sets. We cite here the result in \[Put93\]. Let $`g_k(x)`$ $`\text{R}[x_1,\mathrm{},x_n]`$ for $`j=1,\mathrm{},r,`$ and we note $`K`$, the semialgebraic set defined by $`K=\{x\text{R}^n:g_k(x)0,k=1,\mathrm{},r\}`$. We suppose that $`K`$ is compact and that there exists $`u(x)\text{R}[x_1,\mathrm{},x_n]`$ such that $`\left\{u(x)0\right\}`$ is compact with

$$u(x)=u_0(x)+\underset{k=1}{\overset{r}{}}g_k(x)u_k(x),\text{for all }x\text{R}^n$$
(4)
where the polynomials $`u_k(x)`$ $`\text{R}[x_1,\mathrm{},x_n]`$ are $`SOS`$ for $`k=1,\mathrm{},r`$. Under this assumption, we can represent all polynomials positive on $`K`$ using $`SOS`$ polynomials as in \[Put93\] or \[PV99\].

###### Proposition 2

Suppose (4) holds. A polynomial $`p(x)`$ $`\text{R}[x_1,\mathrm{},x_n]`$ is positive on $`K`$ iff:

$$p(x)=q_0(x)+\underset{k=1}{\overset{r}{}}g_k(x)q_k(x),\text{for all }x\text{R}^n$$
(5)
where the polynomials $`q_k(x)\text{R}[x_1,\mathrm{},x_n]`$ are $`SOS`$ for $`k=0,\mathrm{},r`$.

Now, as in \[Par00\] or \[Las01\], we can write the multivariate version of the relation (3) mapping $`SOS`$ polynomials to the semidefinite cone.

###### Proposition 3

Let $`p(x)`$ $`\text{R}[x_1,\mathrm{},x_n]`$ be a polynomial and $`K`$a semialgebraic set defined by $`K=\{x\text{R}^n:g_k(x)0,k=1,\mathrm{},r\}`$, satisfying assumption (4). Then $`p(x)0`$ on $`K`$ iff there is an integer $`m𝐙_+`$ and matrices $`X_k\text{S}^N`$, with $`X_k0`$ for $`k=0,\mathrm{},r`$ such that:

$$p(x)=y_x^TX_0y_x+\underset{k=1}{\overset{r}{}}\left(y_x^TX_ky_x\right)g_k(x),\text{for all }x\text{R}^n,$$
(6)
where $`N=\left(\genfrac{}{}{0pt}{}{n+m1}{m}\right)/2`$ and $`y_x=(1,x_1,\mathrm{},x_n,x_1^2,x_1x_2,\mathrm{},x_1x_n,x_2x_3,\mathrm{},x_n^2,\mathrm{},x_1^m,\mathrm{},x_n^m)`$ is the vector of all monomials in $`\text{R}[x_1,\mathrm{},x_n]`$, up to degree $`m`$, listed in graded lexicographic order.

The result on polynomials above shows that testing the positivity of a multivariate polynomial on a semialgebraic set $`K`$ satisfying the assumption (4) can be cast as a semidefinite program. In general, the result in \[Las01\] shows that all compact semialgebraic problems, i.e. problems seeking to minimize a polynomial over a compact semialgebraic set, are equivalent to large-scale semidefinite programs. This provides a positive answer in the compact multivariate case to all the open questions in §4.10.2 in \[BTN01\]. A converse result is also true (and much simpler). Because the positive semidefiniteness of a matrix is equivalent to that of all its principal minors, all semidefinite programs are semialgebraic programs, with additional convexity and invariance properties.

The central result of moment theory exploited in \[Las01\] sets polynomial positivity problems and moment problems as duals (see e.g. \[Ber80\]). Let $`s`$ be a positive semidefinite sequence $`s\text{R}^N`$, we have

$$\begin{array}{c}s\text{ is p.s.d.}\\ \\ s,p_\alpha 0,\text{for all }p(x)\text{R}_m[x]\text{ with }p(x)\text{ }SOS\text{,}\end{array}$$

and

$$\begin{array}{c}s\text{ is a moment sequence}\\ \\ \text{ }s,p_\alpha 0,\text{for all }p(x)\text{R}_m[x]\text{ with }p(x)0\text{ on }\text{R}^n\text{,}\end{array}$$

hence the cone of coefficients of$`SOS`$ polynomials and that of p.s.d. sequences are polar, and so are the cones of moment sequences and positive polynomials.

From \[Put93\] then, we know that the problem of testing if a sequence $`y`$ is the moment sequence of some measure $`\mu `$ with support in a compact semialgebraic set

$$K=\{x\text{R}^n:g_k(x)0,k=1,\mathrm{},r\}$$

and the problem of representing positive polynomials on $`K`$ as $`g_k(x)`$ weighted sums of $`SOS`$ polynomials are dual of each other and both representable as linear matrix inequalities.

## 3 Semidefinite representation of the MinCard(x) and MinRank(X) problems.

As above $`K`$ is the semialgebraic set defined by $`K=\{x\text{R}^n:g_k(x)0,k=1,\mathrm{},r\}`$ and we assume that (4) holds. Let $`p(x)`$ $`\text{R}[x_1,\mathrm{},x_n]`$ and as $`K`$ is compact, we also note $`t^{}=\mathrm{min}_Kp(x)`$. Of course, $`p(x)t^{}0`$ on $`K`$, hence there are $`SOS`$ polynomials $`q_k(x)`$ $`\text{R}[x_1,\mathrm{},x_n]`$ for $`k=1,\mathrm{},r`$ such that (5) holds for $`p(x)t^{}`$ on $`K`$. We first show that the $`\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x)`$ problem can be cast as a semialgebraic program, hence a semidefinite program, using the results from section 2.

###### Proposition 4

Let $`A\text{R}^{m\times n}`$ and $`b\text{R}^m`$. There are polynomials $`g_k(x)\text{R}[x_1,\mathrm{},x_n],`$ for $`k=0,\mathrm{},r`$ such that the optimum values of:

$$\begin{array}{cc}\text{minimize}\hfill & 𝐂𝐚𝐫𝐝(x)\hfill \\ \text{subject to}\hfill & Axb,\hfill \end{array}$$
(7)
and

$$\begin{array}{cc}\text{minimize}\hfill & g_0(x)\hfill \\ \text{subject to}\hfill & g_k(x)0,\text{for }i=1,\mathrm{},r,\hfill \end{array}$$

are equal.

> Proof. First, as in \[Sho87\] we notice that:
>
> $$\begin{array}{ccc}𝐂𝐚𝐫𝐝\left(x\right)=\hfill & \mathrm{min}\hfill & _{i=1}^nv_i\hfill \\ & \text{s.t.}\hfill & \left(v_i1\right)x_i=0\hfill \\ & & v_i0,\text{for }i=1,\mathrm{},n,\hfill \end{array}$$
>
> hence the $`\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x)`$ problem in (7) can be written:
>
> $$\begin{array}{ccc}\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝\left(x\right)\hfill & \text{min.}\hfill & _{i=1}^nv_i\hfill \\ & \text{s.t.}\hfill & \left(v_i1\right)x_i=0\hfill \\ & & v_i0,\text{for }i=1,\mathrm{},n\hfill \\ & & Axb.\hfill \end{array}$$
>
> which is a semialgebraic problem.

We now show a similar result on the $`\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X)`$, a minimum cardinality problem on the eigenvalues of the matrix $`X`$.

###### Proposition 5

Let $`A_i\text{S}^n`$, for $`i=1,\mathrm{},p`$ and $`b\text{R}^p`$. There are polynomials $`g_k(x)\text{R}[x_1,\mathrm{},x_n],`$ for $`k=0,\mathrm{},r`$ such that the optimum values of:

$$\begin{array}{cc}\text{minimize}\hfill & 𝐑𝐚𝐧𝐤(X)\hfill \\ \text{subject to}\hfill & Tr\left(A_iX\right)=b_i,\text{for }i=1,\mathrm{},p\hfill \\ & X0\hfill \end{array}$$
(8)
and

$$\begin{array}{cc}\text{minimize}\hfill & g_0(x)\hfill \\ \text{subject to}\hfill & g_k(x)0,\text{for }i=1,\mathrm{},M\hfill \end{array}$$

are equal.

> Proof. We note $`(\lambda _1,\mathrm{},\lambda _n)`$ the eigenvalues of the matrix $`X0`$ and
>
> $$\sigma _k\left(X\right)=\underset{\alpha \{1,\mathrm{},n\},\left|\alpha \right|=k}{}\lambda _\alpha $$
>
> the symmetric functions. We note $`\chi _t\left(X\right)`$ the characteristic polynomial of the matrix $`X,`$ with $`\chi _t\left(X\right)=_{i=1}^n\left(1\right)^i\sigma _i(X)t^i`$. Because the matrix $`X`$ is semidefinite positive, we have $`\sigma _k(X)=0`$ iff $`𝐑𝐚𝐧𝐤\left(X\right)<k`$, hence the $`\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X)`$ problem can be expressed as a minimum cardinality problem on the coefficients of the characteristic polynomial. With
>
> $$\begin{array}{ccc}𝐑𝐚𝐧𝐤\left(X\right)=\hfill & \mathrm{min}\hfill & v_i\hfill \\ & \text{s.t.}\hfill & \sigma _i\left(X\right)\left(v_i1\right)=0\hfill \\ & & v_i0,\text{for }i=1,\mathrm{},n,\hfill \end{array}$$
>
> we enforce the remaining constraints to get the following representation of $`\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X)`$:
>
> $$\begin{array}{cc}\text{minimize}\hfill & _{i=1}^nv_i\hfill \\ \text{s.t.}\hfill & \left(v_i1\right)\sigma _i\left(X\right)=0\hfill \\ & v_i0,\text{for }i=1,\mathrm{},n\hfill \\ & Tr\left(A_iX\right)=b_i,\text{for }i=1,\mathrm{},p\hfill \\ & d_I\left(X\right)0,\text{for }I\{1,\mathrm{},n\},\hfill \end{array}$$
>
> where $`d_I(X)`$ is the principal minor with index set $`I\{1,\mathrm{},n\}`$. This is a semialgebraic program in the coefficients of the matrix $`X`$.

These two results together with the results cited in section 2 show that the two problems considered are equivalent to very large scale semidefinite programs.

## 4 Semidefinite relaxations

In practice, the exact representations obtained in the last section can be exponentially large and in general, we cannot expect these problems to be tractable. Hence, the central contribution of these representations is not to reduce the complexity of these problems, but to provide a sequence of successively sharper relaxations covering the entire complexity spectrum, thus allowing the complexity/sharpness tradeoff to be tuned. This is what we intend to describe in this section.

We begin by recalling the construction of moment matrices as detailed in \[CF00\], \[Las01\] and \[Las02\]. Again, we let $`y_x=(1,x_1,\mathrm{},x_n,x_1^2,x_1x_2,\mathrm{},x_1x_n,x_2x_3,\mathrm{},x_n^2,\mathrm{},x_1^m,\mathrm{},x_n^m)`$ be the vector of all monomials in $`\text{R}[x_1,\mathrm{},x_n]`$, up to degree $`m`$, listed in increasing graded lexicographic order. We note $`s(m)`$ the size of the vector $`y_x`$. Let $`y\text{R}^{s(2m)}`$ be the vector of moments (indexed according to $`y_x`$) of some probability measure $`\mu `$ with support $`K=\{x\text{R}^n:g(x)0\}`$, we note $`M_m(y)\text{S}^{s(m)}`$, for the moment matrix defined by

$$M_m(y)_{i,j}=_K\left(y_x\right)_i\left(y_x\right)_j\mu \left(dx\right),\text{for }i,j=1,\mathrm{},s(m)$$
(9)
i.e. the (symmetric) matrix of moments with rows and columns indexed as in $`y_x`$. We note $`\beta (i)`$ the exponent of the monomial $`\left(y_x\right)_i`$ and conversely, we note $`i(\beta )`$ the index of the monomial $`x^\beta `$ in $`y_x`$. For a given moment vector $`y\text{R}^{s(m)}`$ ordered as in (4), the first row and columns of the matrix $`M_m(y)`$ are then equal to $`y`$. The rest of the matrix is then constructed following:

$$M_m(y)_{i,j}=y_{\alpha +\beta }\text{ if }M_m(y)_{1,i}=y_\alpha \text{ and }M_m(y)_{j,1}=y_\beta .$$

Similarly, let $`g(x)\text{R}[x_1,\mathrm{},x_n]`$, we derive the moment matrix for the measure $`g(x)\mu \left(dx\right)`$ on $`K`$ (called the localizing matrix), noted $`M_m(gy)\text{S}^{s(m)}`$, from the matrix of moments $`M_m(y)`$ by:

$$M_m(gy)_{i,j}=_K\left(y_x\right)_i\left(y_x\right)_jg(x)\mu \left(dx\right)$$
(10)
for $`i,j=1,\mathrm{},s(m)`$. The coefficients of the matrix $`M_m(gy)`$ are then given by:

$$M_m(gy)_{i,j}=\underset{\alpha }{}g_\alpha M_m(y)_{i\left(\beta (i)+\beta (j)+\alpha \right)}$$
(11)
We can remark as in \[Las01\] that if the measure $`\mu `$ has its support included in $`K=\{x\text{R}^n:g(x)0\}`$, then for all coefficient vectors $`v\text{R}^{s(m)}`$:

$$v,M_m(gy)v=_Kv(x)^2g(x)\mu \left(dx\right)0$$

hence $`M_m(gy)0`$.

In dimension one, for a given vector $`y\text{R}^{s(2m)}`$, $`M_m(y)0`$ (which is a LMI) is also a sufficient condition in order for $`y`$ to the moment sequence of a probability measure. In $`\text{R}^n`$, this equivalence does not hold in general. The compact semialgebraic case is called the K-moment problem and is dual to the compact $`SOS`$ problem in (6). Following \[Las01\], we now exploit this duality to compute a sequence of semidefinite relaxations for the $`\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x)`$and $`\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X)`$ problems.

### 4.1 The MinCard(x) problem

In section 3, we saw that the optimum value of the $`\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x)`$ problem can be computed as the optimum value of the semialgebraic program:

$$\begin{array}{cc}\text{min.}\hfill & _{i=1}^nv_i\hfill \\ \text{s.t.}\hfill & (v_i1)x_i=0\hfill \\ & v_i0,\text{for }i=1,\mathrm{},n\hfill \\ & a_j^Txb_j,\text{for }j=1,\mathrm{},m.\hfill \end{array}$$
(12)
As in \[Las01\], to ensure compactness, we impose the additional constraint $`x_1^2+\mathrm{}+x_n^2\alpha `$ for some constant $`\alpha >1`$. It is easy to check that the program above, together with this additional bound on the feasible set, satisfies the constraints qualification assumption (4). For $`N1`$, a lower bound $`l_N`$ on the optimal value of the above problem is then computed as:

$$\begin{array}{ccc}l_N:=\hfill & \text{inf}\hfill & _{i=1}^ny_i\hfill \\ & \text{s.t.}\hfill & M_N(y)0\hfill \\ & & M_{N1}\left(x_i(v_i1)y\right)=0\hfill \\ & & M_{N1}\left((\alpha x^Txv^Tv)y\right)0\hfill \\ & & M_{N1}\left(v_iy\right)0,\text{for }i=1,\mathrm{},n\hfill \\ & & M_{N1}\left(\left(a_j^Txb_j\right)y\right)0,\text{for }j=1,\mathrm{},m,\hfill \end{array}$$
(13)
in the variable $`y\text{R}^{2n}`$. Theorem 3.2 in \[Las02\] then states that there exists some $`N^{}`$ such that

$$l_N=\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x),\text{for all }NN^{},$$

and the optimum is achieved whenever the rank of the matrices $`M_N(\left(\mathrm{}\right)y)`$ stabilizes.

### 4.2 The MinRank(X) problem

In section 3, for $`X\text{S}^n`$, we saw that the optimum of the $`\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X)`$ problem can be computed as the optimum value of the semialgebraic program:

$$\begin{array}{cc}\text{min.}\hfill & _{i=1}^nv_i\hfill \\ \text{s.t.}\hfill & (v_i1)\sigma _i(X)=0\hfill \\ & v_i0,\text{for }i=1,\mathrm{},n\hfill \\ & Tr\left(A_jX\right)=b_j,\text{for }j=1,\mathrm{},p\hfill \\ & d_I(X)0,\text{for }I[1,n],\hfill \end{array}$$

To further simplify this program, we can substitute to the $`2^n`$ constraints on the principal minors a more economical semialgebraic constraint. The modified program then reads:

$$\begin{array}{cc}\text{min.}\hfill & _{i=1}^nv_i\hfill \\ \text{s.t.}\hfill & (v_i1)\sigma _i(X)=0\hfill \\ & v_i0,\text{for }i=1,\mathrm{},n\hfill \\ & Tr\left(A_iX\right)=b_i,\text{for }i=1,\mathrm{},p\hfill \\ & u^TXu0,\text{for }u\text{R}^n,\hfill \end{array}$$

and again, to ensure compactness, we impose $`X^TX+v^Tv+u^Tu\alpha `$ for some constant $`\alpha >1`$. If we set the variable $`x=(u,X,v),`$ for $`N\frac{n+1}{2}`$, a lower bound $`l_N`$ on the optimal value of the above problem is computed as:

$$\begin{array}{ccc}l_N:=\hfill & \text{inf}\hfill & _{i=1}^nu_i\hfill \\ & \text{s.t.}\hfill & M_N(y)0\hfill \\ & & M_{N\frac{i+1}{2}}\left((v_i1)\sigma _i(X)y\right)=0\hfill \\ & & M_{N1}\left(v_iy\right)0\hfill \\ & & M_{N1}\left(\left(Tr\left(A_iX\right)b_i\right)y\right)=0\hfill \\ & & M_{N1}\left(\left(\alpha X^TX+v^Tv+u^Tu\right)y\right)0\hfill \\ & & M_{N2}\left(\left(u^TXu\right)y\right)0\hfill \end{array}$$
(14)
for $`i=1,\mathrm{},n`$ and $`j=1,\mathrm{},p`$, in the variable $`y\text{R}^{2n}`$, where the matrices $`M(q(x)y)`$ are computed as in (11). Theorem 3.2 in \[Las02\] then states that there exists some $`N^{}`$ such that

$$l_N=\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X),\text{for all }NN^{},$$

and the optimum is reached whenever the rank of the matrices $`M_N(\left(\mathrm{}\right)y)`$ stabilizes. Alternatively, one could use the fact that if we note $`\chi _t(X)`$ the characteristic polynomial of $`X`$, then $`X0`$ is equivalent to $`\chi _{t^2}(X)`$ being $`SOS`$ as a univariate polynomial in $`t`$.

### 4.3 Convex envelope

Suppose that instead of having only one $`\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x)`$ or $`\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X)`$ problem to solve, we need to solve a (long) sequence of these problems with only some variation in the constraints. Here, instead of computing an exact relaxation for every instance of the problem, we are interested in finding an efficient heuristic method for approximating the solution to all the problems to be solved. The complexity of the first ”bound design” program will be high, but that of the subsequent programs will then be much lower. The heuristics in \[FHB00\] replaced the $`𝐂𝐚𝐫𝐝(x)`$ (resp. $`𝐑𝐚𝐧𝐤(X)`$) functions by their convex envelope on the sets $`0x1`$ (resp. $`0XI`$), i.e. the largest convex function $`f(x)`$ such that $`f(x)𝐂𝐚𝐫𝐝(x)`$ if $`0x1`$ (resp. $`f(X)𝐑𝐚𝐧𝐤(X)`$ if $`0XI`$). In this section, we extend these bounds to semialgebraic sets with more complex shapes.

Of course, a function and its convex envelope share the same global minimum, so solving for this optimal lower bound is at least as hard as finding the global minimum. Here however we look for a convex lower bound for the problem in (7) inside the set of polynomials of degree at most $`d`$. This becomes a semialgebraic program:

$$\begin{array}{cc}\text{maximize}\hfill & _{[0,1]^n}p(x)𝑑x\hfill \\ \text{subject to}\hfill & tp(x)0\text{ on }K\hfill \\ & _{i=1}^nv_ip(x)0\text{ on }K\hfill \\ & u^T^2p(x)u0\text{ on }u^2=1\hfill \end{array}$$
(15)
in the coefficients $`p_\alpha `$ of the polynomial $`p(x)\text{R}_d[x_1,\mathrm{},x_n]`$, where $`K`$ is the compact semialgebraic set given by:

$$\begin{array}{cc}K=(v,x)\text{R}^{2n}:\hfill & \left(v_i1\right)x_i=0\hfill \\ & Axb0\hfill \\ & x,v0.\hfill \end{array}$$
(16)
Again, this can be cast as a LMI using the technique in \[Las02\]. We notice that the $`l_1`$ heuristic is a particular case when the constraint $`Axb0`$ is dropped.

## 5 Complexity

Of course, the two semidefinite programs detailed in the last section are far from tractable if the dimension $`n`$ and the relaxation order $`N`$ grow beyond textbook example sizes. The $`\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x)`$ problem is equivalent to solving $`2^n`$ linear programs, so it is right to ask whether the programs above provide any benefit over, for example, branch-and-bound methods?

Even if these two methodologies have similar worst-case complexities, the semidefinite relaxations in (13) and (14) do sometimes produce the global optimum for low order $`N`$ (see \[Las02\]) and because the objective is integer valued here, they only need to be solved up to an absolute precision of 1/2. We quickly detail below some other possible simplifications.

But the results above have to be considered first as representations, providing an insight of the relative complexity of minimum cardinality problems versus that of tractable convex optimization problems.

### 5.1 Structure, sparsity and symmetry

The first element that can be used to simplify the programs in (13) and (14) is structure. In \[Las02\] for example, the constraints $`x\{1,1\}`$, that translate into $`x^2x=0`$ and $`M_m(\left(x^2x\right)y)=0`$ also imply that the variables $`y_\alpha ,`$ for $`\alpha 𝐙_+^n`$, can be replaced by $`y_{𝐂𝐚𝐫𝐝(\alpha )}`$ in the program. Secondly, if the constraints in (13) and (14) include some symmetry, we could use the results in \[Gat00\] and \[GP02\] to preprocess and simplify the original semialgebraic program. The simplest example of these symmetries is of course when the constraints are invariant with respect to a change of basis, in which case $`\mathrm{𝐌𝐢𝐧}𝐑𝐚𝐧𝐤(X)`$ reduces to a $`\mathrm{𝐌𝐢𝐧}𝐂𝐚𝐫𝐝(x)`$ problem and as in \[GP02\] p. 31, the asymptotic complexity goes from being exponential in $`n`$ to being exponential in $`\sqrt{n}`$.

In general, the complexity of algorithms in semialgebraic geometry grows at least exponentially with the dimension. Efficiency is then very often measured by the ability of a method to maintain sparsity. Some results on Newton polytopes and $`SOS`$ polynomials can then be used to efficiently handle sparsity in the SOS representations. In particular, a result of \[Rez78\] shows that if $`p(x),h_i(x)\text{R}[x]`$, for $`i=1,\mathrm{},r`$, with $`p(x)=_{i=1}^rh_i^2(x)`$, then $`C(h_i)\frac{1}{2}C(p)`$. That result however does not hold as is for the representation in (5).

Finally, a lower bound on the optimal value can be obtained by simply dropping some of the constraints in (13) and (14).

## 6 Conclusion

One of the central contributions of semidefinite programs to the optimization toolbox is their ability to efficiently solve a wide class of convex eigenvalue problems. In this work, we have illustrated how the method described in \[Las01\] for solving semialgebraic programs, by lifting them to semidefinite programs, can also be used to represent some semialgebraic eigenvalue problems and convex envelope relaxations. This contribution is centered around semidefinite representations and the insight they can provide on the theoretical complexity of these problems. Wether or not they also improve the practical complexity of computing relaxations to these problems remains to be explored.


format: text

text:
# Search for the Supersymmetric Partner of the Top Quark in Dilepton Events from 𝐩𝐩̄ Collisions at √𝐬=1.8 TeV

## Abstract

We have searched for the supersymmetric partner of the top quark (stop) in 107 $`\mathrm{pb}^1`$of $`p\overline{p}`$ collisions at $`\sqrt{s}`$= 1.8 TeV collected by the Collider Detector at Fermilab (CDF). Within the framework of the Minimal Supersymmetric extension of the Standard Model (MSSM) each of the pair-produced stops is assumed to decay into a lepton, bottom quark and supersymmetric neutrino. Such a scenario would give rise to events with two leptons, two hadronic jets, and a substantial imbalance of transverse energy. No evidence of such a stop signal has been found. We calculate a 95% confidence level (C.L.) upper limit on the stop production cross section, which excludes stop masses in the region ($`80m_{\stackrel{~}{t}}135`$ GeV/$`c^2`$) in the mass plane of stop versus sneutrino.

D. Acosta,14 T. Affolder,25 H. Akimoto,51 M. G. Albrow,13 D. Ambrose,37 D. Amidei,28 K. Anikeev,27 J. Antos,1 G. Apollinari,13 T. Arisawa,51 A. Artikov,11 T. Asakawa,49 W. Ashmanskas,10 F. Azfar,35 P. Azzi-Bacchetta,36 N. Bacchetta,36 H. Bachacou,25 W. Badgett,13 S. Bailey,18 P. de Barbaro,41 A. Barbaro-Galtieri,25 V. E. Barnes,40 B. A. Barnett,21 S. Baroiant,5 M. Barone,15 G. Bauer,27 F. Bedeschi,38 S. Behari,21 S. Belforte,48 W. H. Bell,17 G. Bellettini,38 J. Bellinger,52 D. Benjamin,12 J. Bensinger,4 A. Beretvas,13 J. Berryhill,10 A. Bhatti,42 M. Binkley,13 D. Bisello,36 M. Bishai,13 R. E. Blair,2 C. Blocker,4 K. Bloom,28 B. Blumenfeld,21 S. R. Blusk,41 A. Bocci,42 A. Bodek,41 G. Bolla,40 A. Bolshov,27 Y. Bonushkin,6 D. Bortoletto,40 J. Boudreau,39 A. Brandl,31 C. Bromberg,29 M. Brozovic,12 E. Brubaker,25 N. Bruner,31 J. Budagov,11 H. S. Budd,41 K. Burkett,18 G. Busetto,36 K. L. Byrum,2 S. Cabrera,12 P. Calafiura,25 M. Campbell,28 W. Carithers,25 J. Carlson,28 D. Carlsmith,52 W. Caskey,5 A. Castro,3 D. Cauz,48 A. Cerri,38 L. Cerrito,20 A. W. Chan,1 P. S. Chang,1 P. T. Chang,1 J. Chapman,28 C. Chen,37 Y. C. Chen,1 M.-T. Cheng,1 M. Chertok,5 G. Chiarelli,38 I. Chirikov-Zorin,11 G. Chlachidze,11 F. Chlebana,13 L. Christofek,20 M. L. Chu,1 J. Y. Chung,33 W.-H. Chung,52 Y. S. Chung,41 C. I. Ciobanu,33 A. G. Clark,16 M. Coca,41 A. P. Colijn,13 A. Connolly,25 M. Convery,42 J. Conway,44 M. Cordelli,15 J. Cranshaw,46 R. Culbertson,13 D. Dagenhart,4 S. D’Auria,17 S. De Cecco,43 F. DeJongh,13 S. Dell’Agnello,15 M. Dell’Orso,38 S. Demers,41 L. Demortier,42 M. Deninno,3 D. De Pedis,43 P. F. Derwent,13 T. Devlin,44 C. Dionisi,43 J. R. Dittmann,13 A. Dominguez,25 S. Donati,38 M. D’Onofrio,38 T. Dorigo,36 N. Eddy,20 K. Einsweiler,25 E. Engels, Jr.,39 R. Erbacher,13 D. Errede,20 S. Errede,20 R. Eusebi,41 Q. Fan,41 H.-C. Fang,25 S. Farrington,17 R. G. Feild,53 J. P. Fernandez,40 C. Ferretti,28 R. D. Field,14 I. Fiori,3 B. Flaugher,13 L. R. Flores-Castillo,39 G. W. Foster,13 M. Franklin,18 J. Freeman,13 J. Friedman,27 Y. Fukui,23 I. Furic,27 S. Galeotti,38 A. Gallas,32 M. Gallinaro,42 T. Gao,37 M. Garcia-Sciveres,25 A. F. Garfinkel,40 P. Gatti,36 C. Gay,53 D. W. Gerdes,28 E. Gerstein,9 S. Giagu,43 P. Giannetti,38 K. Giolo,40 M. Giordani,5 P. Giromini,15 V. Glagolev,11 D. Glenzinski,13 M. Gold,31 N. Goldschmidt,28 J. Goldstein,13 G. Gomez,8 M. Goncharov,45 I. Gorelov,31 A. T. Goshaw,12 Y. Gotra,39 K. Goulianos,42 C. Green,40 A. Gresele,36 G. Grim,5 C. Grosso-Pilcher,10 M. Guenther,40 G. Guillian,28 J. Guimaraes da Costa,18 R. M. Haas,14 C. Haber,25 S. R. Hahn,13 E. Halkiadakis,41 C. Hall,18 T. Handa,19 R. Handler,52 F. Happacher,15 K. Hara,49 A. D. Hardman,40 R. M. Harris,13 F. Hartmann,22 K. Hatakeyama,42 J. Hauser,6 J. Heinrich,37 A. Heiss,22 M. Hennecke,22 M. Herndon,21 C. Hill,7 A. Hocker,41 K. D. Hoffman,10 R. Hollebeek,37 L. Holloway,20 S. Hou,1 B. T. Huffman,35 R. Hughes,33 J. Huston,29 J. Huth,18 H. Ikeda,49 C. Issever,7 J. Incandela,7 G. Introzzi,38 M. Iori,43 A. Ivanov,41 J. Iwai,51 Y. Iwata,19 B. Iyutin,27 E. James,28 M. Jones,37 U. Joshi,13 H. Kambara,16 T. Kamon,45 T. Kaneko,49 J. Kang,28 M. Karagoz Unel,32 K. Karr,50 S. Kartal,13 H. Kasha,53 Y. Kato,34 T. A. Keaffaber,40 K. Kelley,27 M. Kelly,28 R. D. Kennedy,13 R. Kephart,13 D. Khazins,12 T. Kikuchi,49 B. Kilminster,41 B. J. Kim,24 D. H. Kim,24 H. S. Kim,20 M. J. Kim,9 S. B. Kim,24 S. H. Kim,49 T. H. Kim,27 Y. K. Kim,25 M. Kirby,12 M. Kirk,4 L. Kirsch,4 S. Klimenko,14 P. Koehn,33 K. Kondo,51 J. Konigsberg,14 A. Korn,27 A. Korytov,14 K. Kotelnikov,30 E. Kovacs,2 J. Kroll,37 M. Kruse,12 V. Krutelyov,45 S. E. Kuhlmann,2 K. Kurino,19 T. Kuwabara,49 N. Kuznetsova,13 A. T. Laasanen,40 N. Lai,10 S. Lami,42 S. Lammel,13 J. Lancaster,12 K. Lannon,20 M. Lancaster,26 R. Lander,5 A. Lath,44 G. Latino,31 T. LeCompte,2 Y. Le,21 J. Lee,41 S. W. Lee,45 N. Leonardo,27 S. Leone,38 J. D. Lewis,13 K. Li,53 C. S. Lin,13 M. Lindgren,6 T. M. Liss,20 J. B. Liu,41 T. Liu,13 Y. C. Liu,1 D. O. Litvintsev,13 O. Lobban,46 N. S. Lockyer,37 A. Loginov,30 J. Loken,35 M. Loreti,36 D. Lucchesi,36 P. Lukens,13 S. Lusin,52 L. Lyons,35 J. Lys,25 R. Madrak,18 K. Maeshima,13 P. Maksimovic,21 L. Malferrari,3 M. Mangano,38 G. Manca,35 M. Mariotti,36 G. Martignon,36 M. Martin,21 A. Martin,53 V. Martin,32 J. A. J. Matthews,31 P. Mazzanti,3 K. S. McFarland,41 P. McIntyre,45 M. Menguzzato,36 A. Menzione,38 P. Merkel,13 C. Mesropian,42 A. Meyer,13 T. Miao,13 R. Miller,29 J. S. Miller,28 H. Minato,49 S. Miscetti,15 M. Mishina,23 G. Mitselmakher,14 Y. Miyazaki,34 N. Moggi,3 E. Moore,31 R. Moore,28 Y. Morita,23 T. Moulik,40 M. Mulhearn,27 A. Mukherjee,13 T. Muller,22 A. Munar,38 P. Murat,13 S. Murgia,29 J. Nachtman,6 V. Nagaslaev,46 S. Nahn,53 H. Nakada,49 I. Nakano,19 R. Napora,21 F. Niell,28 C. Nelson,13 T. Nelson,13 C. Neu,33 M. S. Neubauer,27 D. Neuberger,22 C. Newman-Holmes,13 C.-Y. P. Ngan,27 T. Nigmanov,39 H. Niu,4 L. Nodulman,2 A. Nomerotski,14 S. H. Oh,12 Y. D. Oh,24 T. Ohmoto,19 T. Ohsugi,19 R. Oishi,49 T. Okusawa,34 J. Olsen,52 W. Orejudos,25 C. Pagliarone,38 F. Palmonari,38 R. Paoletti,38 V. Papadimitriou,46 D. Partos,4 J. Patrick,13 G. Pauletta,48 M. Paulini,9 T. Pauly,35 C. Paus,27 D. Pellett,5 A. Penzo,48 L. Pescara,36 T. J. Phillips,12 G. Piacentino,38 J. Piedra,8 K. T. Pitts,20 A. Pompoš,40 L. Pondrom,52 G. Pope,39 T. Pratt,35 F. Prokoshin,11 J. Proudfoot,2 F. Ptohos,15 O. Pukhov,11 G. Punzi,38 J. Rademacker,35 A. Rakitine,27 F. Ratnikov,44 H. Ray,28 D. Reher,25 A. Reichold,35 P. Renton,35 M. Rescigno,43 A. Ribon,36 W. Riegler,18 F. Rimondi,3 L. Ristori,38 M. Riveline,47 W. J. Robertson,12 T. Rodrigo,8 S. Rolli,50 L. Rosenson,27 R. Roser,13 R. Rossin,36 C. Rott,40 A. Roy,40 A. Ruiz,8 D. Ryan,50 A. Safonov,5 R. St. Denis,17 W. K. Sakumoto,41 D. Saltzberg,6 C. Sanchez,33 A. Sansoni,15 L. Santi,48 S. Sarkar,43 H. Sato,49 P. Savard,47 A. Savoy-Navarro,13 P. Schlabach,13 E. E. Schmidt,13 M. P. Schmidt,53 M. Schmitt,32 L. Scodellaro,36 A. Scott,6 A. Scribano,38 A. Sedov,40 S. Seidel,31 Y. Seiya,49 A. Semenov,11 F. Semeria,3 T. Shah,27 M. D. Shapiro,25 P. F. Shepard,39 T. Shibayama,49 M. Shimojima,49 M. Shochet,10 A. Sidoti,36 J. Siegrist,25 A. Sill,46 P. Sinervo,47 P. Singh,20 A. J. Slaughter,53 K. Sliwa,50 F. D. Snider,13 R. Snihur,26 A. Solodsky,42 J. Spalding,13 T. Speer,16 M. Spezziga,46 P. Sphicas,27 F. Spinella,38 M. Spiropulu,10 L. Spiegel,13 J. Steele,52 A. Stefanini,38 J. Strologas,20 F. Strumia, 16 D. Stuart,7 A. Sukhanov,14 K. Sumorok,27 T. Suzuki,49 T. Takano,34 R. Takashima,19 K. Takikawa,49 P. Tamburello,12 M. Tanaka,49 B. Tannenbaum,6 M. Tecchio,28 R. J. Tesarek,13 P. K. Teng,1 K. Terashi,42 S. Tether,27 J. Thom,13 A. S. Thompson,17 E. Thomson,33 R. Thurman-Keup,2 P. Tipton,41 S. Tkaczyk,13 D. Toback,45 K. Tollefson,29 D. Tonelli,38 M. Tonnesmann,29 H. Toyoda,34 W. Trischuk,47 J. F. de Troconiz,18 J. Tseng,27 D. Tsybychev,14 N. Turini,38 F. Ukegawa,49 T. Unverhau,17 T. Vaiciulis,41 J. Valls,44 A. Varganov,28 E. Vataga,38 S. Vejcik III,13 G. Velev,13 G. Veramendi,25 R. Vidal,13 I. Vila,8 R. Vilar,8 I. Volobouev,25 M. von der Mey,6 D. Vucinic,27 R. G. Wagner,2 R. L. Wagner,13 W. Wagner,22 N. B. Wallace,44 Z. Wan,44 C. Wang,12 M. J. Wang,1 S. M. Wang,14 B. Ward,17 S. Waschke,17 T. Watanabe,49 D. Waters,26 T. Watts,44 M. Weber,25 H. Wenzel,22 W. C. Wester III,13 B. Whitehouse,50 A. B. Wicklund,2 E. Wicklund,13 T. Wilkes,5 H. H. Williams,37 P. Wilson,13 B. L. Winer,33 D. Winn,28 S. Wolbers,13 D. Wolinski,28 J. Wolinski,29 S. Wolinski,28 M. Wolter,50 S. Worm,44 X. Wu,16 F. Würthwein,27 J. Wyss,38 U. K. Yang,10 W. Yao,25 G. P. Yeh,13 P. Yeh,1 K. Yi,21 J. Yoh,13 C. Yosef,29 T. Yoshida,34 I. Yu,24 S. Yu,37 Z. Yu,53 J. C. Yun,13 L. Zanello,43 A. Zanetti,48 F. Zetti,25 and S. Zucchelli3

(CDF Collaboration)

1 Institute of Physics, Academia Sinica, Taipei, Taiwan 11529, Republic of China

2 Argonne National Laboratory, Argonne, Illinois 60439

3 Istituto Nazionale di Fisica Nucleare, University of Bologna, I-40127 Bologna, Italy

4 Brandeis University, Waltham, Massachusetts 02254

5 University of California at Davis, Davis, California 95616

6 University of California at Los Angeles, Los Angeles, California 90024

7 University of California at Santa Barbara, Santa Barbara, California 93106

8 Instituto de Fisica de Cantabria, CSIC-University of Cantabria, 39005 Santander, Spain

9 Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

10 Enrico Fermi Institute, University of Chicago, Chicago, Illinois 60637

11 Joint Institute for Nuclear Research, RU-141980 Dubna, Russia

12 Duke University, Durham, North Carolina 27708

13 Fermi National Accelerator Laboratory, Batavia, Illinois 60510

14 University of Florida, Gainesville, Florida 32611

15 Laboratori Nazionali di Frascati, Istituto Nazionale di Fisica Nucleare, I-00044 Frascati, Italy

16 University of Geneva, CH-1211 Geneva 4, Switzerland

17 Glasgow University, Glasgow G12 8QQ, United Kingdom
18 Harvard University, Cambridge, Massachusetts 02138

19 Hiroshima University, Higashi-Hiroshima 724, Japan

20 University of Illinois, Urbana, Illinois 61801

21 The Johns Hopkins University, Baltimore, Maryland 21218

22 Institut für Experimentelle Kernphysik, Universität Karlsruhe, 76128 Karlsruhe, Germany

23 High Energy Accelerator Research Organization (KEK), Tsukuba, Ibaraki 305, Japan

24 Center for High Energy Physics: Kyungpook National University, Taegu 702-701; Seoul National University, Seoul 151-742; and SungKyunKwan University, Suwon 440-746; Korea

25 Ernest Orlando Lawrence Berkeley National Laboratory, Berkeley, California 94720

26 University College London, London WC1E 6BT, United Kingdom

27 Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

28 University of Michigan, Ann Arbor, Michigan 48109

29 Michigan State University, East Lansing, Michigan 48824

30 Institution for Theoretical and Experimental Physics, ITEP, Moscow 117259, Russia

31 University of New Mexico, Albuquerque, New Mexico 87131

32 Northwestern University, Evanston, Illinois 60208

33 The Ohio State University, Columbus, Ohio 43210

34 Osaka City University, Osaka 588, Japan

35 University of Oxford, Oxford OX1 3RH, United Kingdom

36 Universita di Padova, Istituto Nazionale di Fisica Nucleare, Sezione di Padova, I-35131 Padova, Italy

37 University of Pennsylvania, Philadelphia, Pennsylvania 19104

38 Istituto Nazionale di Fisica Nucleare, University and Scuola Normale Superiore of Pisa, I-56100 Pisa, Italy

39 University of Pittsburgh, Pittsburgh, Pennsylvania 15260

40 Purdue University, West Lafayette, Indiana 47907

41 University of Rochester, Rochester, New York 14627

42 Rockefeller University, New York, New York 10021

43 Instituto Nazionale de Fisica Nucleare, Sezione di Roma, University di Roma I, ‘‘La Sapienza," I-00185 Roma, Italy
44 Rutgers University, Piscataway, New Jersey 08855

45 Texas A&M University, College Station, Texas 77843

46 Texas Tech University, Lubbock, Texas 79409

47 Institute of Particle Physics, University of Toronto, Toronto M5S 1A7, Canada

48 Istituto Nazionale di Fisica Nucleare, University of Trieste/ Udine, Italy

49 University of Tsukuba, Tsukuba, Ibaraki 305, Japan

50 Tufts University, Medford, Massachusetts 02155

51 Waseda University, Tokyo 169, Japan

52 University of Wisconsin, Madison, Wisconsin 53706

53 Yale University, New Haven, Connecticut 06520

(Submitted to Physical Review Letters)

One of the most promising theories beyond the Standard Model (SM)  is the Minimal Supersymmetric Standard Model (MSSM) . It predicts that each SM particle has a superpartner (sparticle) with the same quantum numbers, except for spin which differs by one half unit. Experimental results indicate that supersymmetric (SUSY) particles are generally not as light as their SM partners. SUSY, therefore, is broken at or above the electroweak scale, and we treat the sparticle masses as free parameters. Due to the large top quark mass, there may be a large mixing between the superpartners of the left and right helicity states of the top quark . This can lead to substantial mass splitting of the stop mass eigenstates ($`\stackrel{~}{t}_1`$, $`\stackrel{~}{t}_2`$) with the lighter one (denoted $`\stackrel{~}{t}`$ from now on) potentially being the lightest squark.

Stop-antistop pairs ($`\stackrel{~}{t}\overline{\stackrel{~}{t}}`$) are strongly produced in the $`p\overline{p}`$ collisions at the Fermilab Tevatron if kinematically accessible. The production cross section has been calculated using QCD in the next-to-leading order (NLO) approximation . For a given stop mass ($`m_{\stackrel{~}{t}}`$) the cross section depends only weakly on the other parameters of the MSSM. In the mass region of interest to our search ($`m_{\stackrel{~}{t}}`$=80-140 GeV/$`c^2`$), the cross section drops from 44 pb to 1 pb.

We assume SUSY $`R`$-parity  conservation, from which the stability of the lightest supersymmetric particle (LSP) follows. All SUSY particles, including the stop, eventually decay into this LSP. Stop decays into the top quark are kinematically not accessible in our region of interest due to the high top mass ($`m_{\stackrel{~}{t}}<m_t`$). For the stop decay into a bottom quark and an on-shell chargino ($`\stackrel{~}{\chi }_1^\pm `$), only a very small window of opportunity remains at the Tevatron due to the high $`\stackrel{~}{\chi }_1^\pm `$ mass limit from LEP2 . Another possible 2-body stop decay would be the flavor-changing, $`\stackrel{~}{t}c\stackrel{~}{\chi }_1^0`$, decay . It would proceed via higher order loop diagrams and is thus highly suppressed. The 3-body decay into a charged supersymmetric lepton, $`\stackrel{~}{t}\stackrel{~}{l}\nu b`$, is closed for most of the stop region currently within the reach of CDF because of the slepton mass limit of LEP2 . The existing mass limit of the supersymmetric neutrino, $`m_{\stackrel{~}{\nu }}45`$ GeV/$`c^2`$ , leaves the decay into sneutrino, $`\stackrel{~}{t}l\stackrel{~}{\nu }b`$, open. This 3-body decay proceeds via a virtual chargino, and is expected to yield equal $`e,\mu `$, and $`\tau `$ branching ratios.

Stop pair production with the $`\stackrel{~}{t}l\stackrel{~}{\nu }b`$ decay will yield two leptons with opposite electric charge, two hadronic jets from the bottom quarks and considerable transverse energy imbalance ($`\mathrm{}\mathrm{E}_\mathrm{T}`$) in the detector  due to the escaping sneutrinos. CDF has reported earlier on an analysis based on $`B`$ identification . In this Letter we use dilepton events. Only a few SM processes yield dileptons and can thus potentially mimic our stop signature. The most significant ones are (1) $`t\overline{t}`$ production with leptons from $`W`$ and/or bottom decays; (2) heavy flavor, i.e. $`b\overline{b}`$ and $`c\overline{c}`$ with semileptonic decays; (3) Drell-Yan production with hadronic jets from higher order processes; (4) diboson production, $`WW`$, $`WZ`$ and $`ZZ`$; (5) lepton pairs from the decay of vector mesons, such as $`J/\psi `$ and $`\mathrm{{\rm Y}}`$; (6) events without two genuine prompt leptons, where a hadron is misidentified as a lepton, or decays in flight to a lepton.

The search presented here is based on 107 $`\mathrm{pb}^1`$of $`p\overline{p}`$ collisions at $`\sqrt{s}`$ = 1.8 TeV collected by the Collider Detector at Fermilab (CDF) during the 1992 to 1995 running period of the Tevatron. A detailed description of the CDF detector can be found in Ref. . Online triggers selected approximately 6.4 million single lepton events and an additional 3.3 million dilepton events. All of those events have been reconstructed, and 13,295 events were selected as a dilepton sample, by requiring at least one tight electron ($`\mathrm{E}_\mathrm{T}10`$ GeV, $`|\eta |1.0`$) or muon ($`\mathrm{p}_\mathrm{T}10`$ GeV/$`c`$, $`|\eta |0.6`$) candidate, and a second loose electron ($`\mathrm{E}_\mathrm{T}6`$ GeV, $`|\eta |1.0`$) or muon ($`\mathrm{p}_\mathrm{T}6`$ GeV/$`c`$, $`|\eta |1.0`$) candidate. No explicit tau lepton identification was done, but taus can enter the search sample if they decay leptonically. Electrons are identified by energy deposition in the electromagnetic calorimeter with a track of corresponding energy in the central drift chamber (CTC) pointing to it. Muons are identified by track segments in both the CTC and the muon drift chambers that are located behind 4.5 to 10 interaction lengths of absorber. Standard lepton identification cuts are used and described elsewhere . Each lepton is required to be isolated, i.e. we require the total $`\mathrm{p}_\mathrm{T}`$ of all other tracks within a cone $`\mathrm{\Delta }R\sqrt{(\mathrm{\Delta }\eta )^2+(\mathrm{\Delta }\varphi )^2}0.4`$ around the lepton’s track not to exceed 4 GeV/$`c`$. The jets were reconstructed with a cone algorithm with cone radius $`\mathrm{\Delta }R=0.7`$ . We require at least one jet in the central region of the calorimeter ($`|\eta |1.0`$) with $`\mathrm{E}_\mathrm{T}`$ 15 GeV, that is separated by $`\mathrm{\Delta }R0.7`$ from both leptons in the event. For increased efficiency, we require only one of the two jets to be identified. Sequential $`B`$ decays, $`J/\psi `$, $`\mathrm{{\rm Y}}`$ and $`Z`$ events were removed requiring the invariant dilepton masses $`m_{ll^{}}6`$ GeV/$`c^2`$ or $`m_{ll}12`$ GeV/$`c^2`$ and excluding $`76<m_{ll}<106`$ GeV/$`c^2`$ (where prime indicates any mixture of $`e`$ and $`\mu `$ flavors and no prime indicates same-flavor dileptons). At the preselection level we start with $`\mathrm{}\mathrm{E}_\mathrm{T}15`$ GeV. Experimental backgrounds, like electrons from conversions and muons from cosmic rays are removed with additional cuts . 176 events fulfill the above preselection requirements.

To estimate the number of SM and stop events in the sample, events of the various physics processes are generated by ISAJET  and simulated for the CDF detector. We have used CTEQ-3 parton distribution functions (PDF) . The stop production cross section was calculated with PROSPINO  and the ISAJET cross section was adjusted accordingly. We have generated events over a large range of stop (80-140 GeV/$`c^2`$) and sneutrino (45-90 GeV/$`c^2`$) masses.

The Drell-Yan and $`t\overline{t}`$ production cross sections were normalized to CDF measurements . The Monte Carlo (MC) $`b\overline{b}`$ and $`c\overline{c}`$ cross sections were verified by inclusive electron-muon samples . The $`B^0\overline{B^0}`$ oscillation effect was added based on the CDF measured inclusive $`\chi `$ mixing fraction . The diboson production cross sections of the MC were scaled to those of NLO calculations .

For low $`\mathrm{p}_\mathrm{T}`$ leptons the contribution due to misidentification can be significant and is calculated in two steps . First we measure in various data samples the so-called “fake lepton probabilities” (momentum-dependent, separately for electrons and muons, and dependent on detector region). These “fake lepton probabilities” include hadrons being misidentified as electrons or muons, and also include leptons from in-flight decays of pions and kaons. The data samples used were (i) a minimum-bias trigger sample and (ii) a sample with a 50 GeV jet trigger threshold. We remove events in those samples similarly to the dilepton analysis, and, to be unbiased, we exclude all hadrons associated with a jet required by the online trigger. We measure misidentification probabilities between 0.4% and 7% for both $`e`$’s and $`\mu `$’s , and the results are consistent between the two data samples.

Second, in a single lepton sample we use these “fake lepton probabilities” successively on each other track in the event to simulate dilepton events. We use the “fake lepton probabilities” to simulate both the number of misidentified-lepton events as well as their kinematic properties.

The major background to the preselection sample comes from heavy flavor production, with about a quarter of the events having leptons of the same charge. Another significant background comes from Drell-Yan processes. In those events the $`\mathrm{}\mathrm{E}_\mathrm{T}`$ comes from $`\tau `$ decays or jet and lepton energy mismeasurements due to uninstrumented detector regions. We expect a total background of 155 $`\pm `$ 55 events, while a stop and sneutrino mass combination of 100 and 75 GeV/$`c^2`$ would contribute 24 $`\pm `$ 9 events. Table I shows the expected contributions in detail for like sign and opposite sign leptons. To verify our background calculation further, we compare kinematic distributions of the data and the expected background. Figure 1 shows a few such distributions. Top and diboson production yield generally more energetic leptons than $`b\overline{b}`$, $`c\overline{c}`$ or misidentified leptons. The $`\mathrm{p}_\mathrm{T}`$ distributions of the leptons show that both high and low $`\mathrm{p}_\mathrm{T}`$ lepton sources agree well with the observed data. The observed $`\mathrm{}\mathrm{E}_\mathrm{T}`$ distribution agrees both at low $`\mathrm{}\mathrm{E}_\mathrm{T}`$, where detector effects dominate, and at high $`\mathrm{}\mathrm{E}_\mathrm{T}`$, where neutrinos from $`W`$ and $`Z`$ bosons determine the spectrum. We also note that the parton shower MC describes well the observed jet multiplicity. From the signal to background ratio, it is clear that the preselection sample does not have sufficient sensitivity to answer the question of stop pair production. In contrast to an earlier search  we select a kinematic region in which we expect higher S/B where S is the stop signal and B is the background which includes SM processes and misidentified leptons. This decreases the systematic uncertainty associated with low $`\mathrm{p}_\mathrm{T}`$ leptons in our analysis.

In less than 5% of stop events the two leptons will have the same electric charge due to the semileptonic decay of one of the $`b`$-quarks. However, 20% of the SM background yields like-sign (LS) lepton events. We thus focus our search on events with opposite-sign charge (OS) leptons. For $`R_p`$-conserving supersymmetry we expect large missing energy from the rather heavy sneutrinos. In Fig. 1 we see most of the background events clustering at low missing $`\mathrm{E}_\mathrm{T}`$. A $`\mathrm{}\mathrm{E}_\mathrm{T}`$ cut of 30 GeV removes 77% of the SM background but keeps about 57% of the stop events. Energy mismeasurement of leptons, or the presence of neutrinos from Drell-Yan $`\tau `$ decays, would cause the leptons (and the dilepton system as well) to be aligned with the $`\mathrm{}\mathrm{E}_\mathrm{T}`$ direction. This is not typical for the signal, where we expect true $`\mathrm{}\mathrm{E}_\mathrm{T}`$ from the sneutrinos in the stop decay. We therefore require the azimuthal angles between $`\mathrm{}\mathrm{E}_\mathrm{T}`$ and the individual leptons and the dilepton system $`\mathrm{\Delta }\varphi _{l_1}^{\mathrm{}\mathrm{E}_\mathrm{T}}`$, $`\mathrm{\Delta }\varphi _{l_2}^{\mathrm{}\mathrm{E}_\mathrm{T}}`$, and $`\mathrm{\Delta }\varphi _{l_1l_2}^{\mathrm{}\mathrm{E}_\mathrm{T}}`$ to be larger than $`30^{}`$.

In Drell-Yan plus jets events or when $`b\overline{b}`$ or $`c\overline{c}`$ events originate from gluon splitting (initial or final state) events, the two leptons balance the jets in the transverse plane. We veto events where the angle between either lepton and the most energetic central jet, $`\mathrm{\Delta }\varphi _{l_1}^{\mathrm{jet}}\mathrm{and}\mathrm{\Delta }\varphi _{l_2}^{\mathrm{jet}}`$, is larger than $`90^{}`$.

Events from top pair production pass the above cuts with efficiencies similar to stop pair events and are now the dominant source of SM background. In top events the leptons come from $`W`$ decay and are very energetic. In the case of stop, we have 3-body decays containing a very heavy sneutrino. The amount of available energy in the decay depends on the stop-sneutrino mass difference, $`\mathrm{\Delta }m_{\stackrel{~}{t}\stackrel{~}{\nu }}`$. For small mass difference, the leptons and jets are quite soft and a large fraction of the event energy escapes detection through the sneutrinos, unlike a $`t\overline{t}`$ event. For best stop sensitivity at small $`\mathrm{\Delta }m_{\stackrel{~}{t}\stackrel{~}{\nu }}`$ we require the scalar sum of lepton $`\mathrm{p}_\mathrm{T}`$, $`\mathrm{p}_\mathrm{T}^{l_1}+\mathrm{p}_\mathrm{T}^{l_2}75`$ GeV/$`c`$, and the $`\mathrm{p}_\mathrm{T}`$ of the dilepton system, $`\mathrm{p}_\mathrm{T}^{l_1l_2}30`$ GeV/$`c`$. Although a large amount of energy escapes undetected, the sneutrinos tend to be back-to-back, thus reducing the measured $`\mathrm{}\mathrm{E}_\mathrm{T}`$. We also require the sum of the most energetic central jet $`\mathrm{E}_\mathrm{T}`$ and the missing $`\mathrm{E}_\mathrm{T}`$, $`\mathrm{E}_{\mathrm{T}}^{}{}_{}{}^{\mathrm{jet}}+\mathrm{}\mathrm{E}_\mathrm{T}160`$ GeV.

For large stop-sneutrino mass difference, the leptons are more energetic and we can increase our lepton $`\mathrm{p}_\mathrm{T}`$ requirement to 10 GeV/$`c`$ without much loss in stop efficiency. However, leptons and jets are still significantly softer than in $`t\overline{t}`$ events. We place the same jet, missing $`\mathrm{E}_\mathrm{T}`$, and lepton requirements as at small $`\mathrm{\Delta }m_{\stackrel{~}{t}\stackrel{~}{\nu }}`$, $`\mathrm{E}_{\mathrm{T}}^{}{}_{}{}^{\mathrm{jet}}+\mathrm{}\mathrm{E}_\mathrm{T}160`$ GeV and $`\mathrm{p}_\mathrm{T}^{l_1}+\mathrm{p}_\mathrm{T}^{l_2}75`$ GeV/$`c`$, but loosen the requirement on the dilepton $`\mathrm{p}_\mathrm{T}`$ to $`\mathrm{p}_\mathrm{T}^{l_1l_2}55`$ GeV/$`c`$.

Table II shows the expected number of stop events for the two search regions. We start our search at stop masses of 80 GeV/$`c^2`$ to overlap with previous LEP limits. Near the kinematic limit of the stop decay, $`m_{\stackrel{~}{t}}=m_{\stackrel{~}{\nu }}+m_b`$, lepton and jet energies become very soft, limiting our stop detection capabilities. At high stop mass our sensitivity is limited by the steeply falling production cross section. In the region of interest to this search the final stop event acceptance varies between 0.3% and 2.3%.

The biggest source of uncertainty on the number of expected stop events arises from the choice of the renormalization and factorization scale, $`Q^2`$, which characterizes the amount of energy transferred during the collision. The $`\mathrm{}\mathrm{E}_\mathrm{T}`$ is reduced (due to the sneutrinos being more back-to-back) when $`Q`$ is increased, and the jet $`\mathrm{E}_\mathrm{T}`$ gets softer when $`Q`$ is decreased. By varying $`Q`$ by a factor of two up and down, we determine the uncertainty due to the choice of $`Q^2`$ to be 32%. Other significant sources of uncertainty are: (1) the choice of PDF (11%) (2) the absolute energy scale of the detector (11%) (3) the amount of gluon radiation (7%) (4) trigger, lepton and isolation efficiency (5%), and (5) the luminosity measurement (4%). The statistical uncertainties of the MC samples are about 8%. Combining the statistical and systematic uncertainties we obtained a total uncertainty of 38% for the signal expectation. Similarly, we evaluated the uncertainty of the background calculation to be 30%.

After establishing the selection cuts by using a “blind” analysis technique, we then apply the cuts to the preselection data. We observe zero events for both the small and the large $`\mathrm{\Delta }m_{\stackrel{~}{t}\stackrel{~}{\nu }}`$ sets of cuts, consistent with our background expectation of 1.52$`\pm `$0.47 and 2.07$`\pm `$0.46 events. We used the frequentist method  with zero observed events, no background subtraction and a total uncertainty of 38% on the predicted signal to calculate a 95% confidence level upper limit of 4.01 stop events. Consequently, we exclude all stop-sneutrino mass combinations that would yield more than 4.01 events. Figure 2 shows our result compared to LEP2  and $`\mathrm{DO}\text{/}`$. The improvement in the small $`\mathrm{\Delta }m_{\stackrel{~}{t}\stackrel{~}{\nu }}`$ region is due to our increased signal to background ratio of 4:1.

In conclusion, we have searched for stop pair production in 107 $`\mathrm{pb}^1`$of data from $`p\overline{p}`$ collisions at $`\sqrt{s}=`$ 1.8 TeV collected by CDF. The observed dilepton, jet, and missing $`\mathrm{E}_\mathrm{T}`$ events are consistent with expectations from SM sources. Failing to find a signal of supersymmetry, we establish mass limits at 95% C.L.: we exclude stop masses up to $`m_{\stackrel{~}{t}}=135`$ GeV/$`c^2`$ (at $`m_{\stackrel{~}{\nu }}`$ of 72-79 GeV/$`c^2`$) and sneutrino masses up to 88.4 GeV/$`c^2`$ (at $`m_{\stackrel{~}{t}}`$ of 126 GeV/$`c^2`$).

We thank the Fermilab staff and the technical staffs of the participating institutions for their vital contributions. This work was supported by the U.S. Department of Energy and National Science Foundation; the Italian Istituto Nazionale di Fisica Nucleare; the Ministry of Education, Culture, Sports, Science, and Technology of Japan; the Natural Sciences and Engineering Research Council of Canada; the National Science Council of the Republic of China; the Swiss National Science Foundation; the A.P. Sloan Foundation; the Bundesministerium für Bildung und Forschung, Germany; and the Korea Science and Engineering Foundation (KoSEF); the Korea Research Foundation; and the Comision Interministerial de Ciencia y Tecnologia, Spain.


text:
# How To Treat An N–Level System : A Proposal This is prepared for the coming 11–th Numazu Meeting (6–8/March/2003)

## Abstract

In this paper we propose a Hamiltonian of the n–level system by making use of generalized Pauli matrices.

An atom has usually many (finite or infinite) energy levels. However, to treat infinitely many ones at the same time is not realistic, so we treat an atom with finite energy levels. In the following we would like to consider an atom with $`n`$ energy levels interacting with external (periodic) fields like $`\text{cos}(\omega t+\varphi )`$ (an $`n`$–level system in our terminology).

In Quantum Optics it is standard to consider a $`2`$–level system, see for example  and . The $`n`$–level system might be considered as a composite of $`2`$–level systems. As for recent developments of the $`2`$–level system including constructions of solutions in the strong coupling regime, see , , , ,  and their references. See also  as a general introduction to two–level system, and ,  as some applications to Quantum Optics. However we would like to treat an $`n`$–level system in a direct manner. Then we meet some troubles. First what is a Hamiltonian describing such a system ? As far as we know such a Hamiltonian has not been known. As for some examples of $`n`$–level system see , ,  and their references.

In this paper we propose such a Hamiltonian. In the $`2`$–level system the Hamiltonian is written by making use of Pauli matrices $`\{\sigma _1,\sigma _3\}`$ (see the references above), so in the $`n`$–level system the Hamiltonian should be given by making use of generalized Pauli matrices $`\{\mathrm{\Sigma }_1,\mathrm{\Sigma }_3\}`$. We will write down it. We believe that it is a natural generalization

Our real aim of this study is to apply some developments in this paper to the theory of qudits in Quantum Computation, see for example  and . In it we must first of all construct all unitary elements in $`U(n)`$ (a universality of $`1`$–qudit).

We expect that this work will become a starting point toward this direction 111This paper may be deeply connected to  in Quantum Information Theory..

Let $`\{\sigma _1,\sigma _2,\sigma _3\}`$ be Pauli matrices and $`\mathrm{𝟏}_2`$ a unit matrix :

$$\sigma _1=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),\sigma _2=\left(\begin{array}{cc}0& i\\ i& 0\end{array}\right),\sigma _3=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),\mathrm{𝟏}_2=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),$$
(1)
and $`\sigma _+=(1/2)(\sigma _1+i\sigma _1)`$, $`\sigma _{}=(1/2)(\sigma _1i\sigma _1)`$.

First list the well–known properties of $`\sigma _1`$ and $`\sigma _3`$ :

$$\sigma _1^2=\sigma _3^2=\mathrm{𝟏}_2,\sigma _1^{}=\sigma _1,\sigma _3^{}=\sigma _3,\sigma _3\sigma _1=\sigma _1\sigma _3=\text{e}^{\pi i}\sigma _1\sigma _3.$$
(2)
Let $`W`$ be the Walsh–Hadamard matrix

$$W=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)=W^1,$$
(3)
then we can diagonalize $`\sigma _1`$ as $`\sigma _1=W\sigma _3W^1`$ by making use of this $`W`$.

Let us consider an atom with $`2`$ energy levels $`E_0`$ and $`E_1`$. Its Hamiltonian is in the diagonal form given as

$$H_0=\left(\begin{array}{cc}E_0& 0\\ 0& E_1\end{array}\right).$$
(4)
This is rewritten as

$$H_0=\frac{E_0+E_1}{2}\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)+\frac{E_0E_1}{2}\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)=\mathrm{\Delta }_0\mathrm{𝟏}_2+\mathrm{\Delta }_1\sigma _3,$$
(5)
where $`\mathrm{\Delta }_0=(1/2)(E_0+E_1)`$ and $`\mathrm{\Delta }_1=(1/2)(E_0E_1)`$. Since we usually take no interest in constant terms, we set

$$H_0=\mathrm{\Delta }_1\sigma _3,\text{where}\mathrm{\Delta }_1=(1/2)(E_0E_1).$$
(6)
Next we would like to extend $`2`$–level system to general $`n`$–level system. For that we consider the $`3`$–level one in detail as a test case. The Hamiltonian with three energy levels $`E_0`$, $`E_1`$, $`E_2`$ is

$$H_0=\left(\begin{array}{ccc}E_0& & \\ & E_1& \\ & & E_2\end{array}\right).$$
(7)
We want to rewrite this as (5). Let $`\sigma `$ be $`\text{exp}(\frac{2\pi i}{3})`$, then it is easy to see

$$\sigma ^3=1,\overline{\sigma }=\sigma ^2,1+\sigma +\sigma ^2=0.$$
(8)
Since the matrix corresponding to $`\sigma _3`$ is considered as

$$\mathrm{\Sigma }_3=\left(\begin{array}{ccc}1& & \\ & \sigma & \\ & & \sigma ^2\end{array}\right),$$
(9)
we solve the equation

$$H_0=\mathrm{\Delta }_0\mathrm{𝟏}_3+\mathrm{\Delta }_1\mathrm{\Sigma }_3+\mathrm{\Delta }_2\mathrm{\Sigma }_3^2$$
(10)
with indeterminants $`\mathrm{\Delta }_0`$, $`\mathrm{\Delta }_1`$, $`\mathrm{\Delta }_2`$. Then we have

$$\{\begin{array}{cc}\hfill \mathrm{\Delta }_0+\mathrm{\Delta }_1+\mathrm{\Delta }_2=E_0& \\ \hfill \mathrm{\Delta }_0+\sigma \mathrm{\Delta }_1+\sigma ^2\mathrm{\Delta }_2=E_1& \\ \hfill \mathrm{\Delta }_0+\sigma ^2\mathrm{\Delta }_1+\sigma \mathrm{\Delta }_2=E_2& \end{array}\left(\begin{array}{ccc}1& 1& 1\\ 1& \sigma & \sigma ^2\\ 1& \sigma ^2& \sigma \end{array}\right)\left(\begin{array}{c}\mathrm{\Delta }_0\\ \mathrm{\Delta }_1\\ \mathrm{\Delta }_2\end{array}\right)=\left(\begin{array}{c}E_0\\ E_1\\ E_2\end{array}\right),$$
(11)
so we obtain

$$\left(\begin{array}{c}\mathrm{\Delta }_0\\ \mathrm{\Delta }_1\\ \mathrm{\Delta }_2\end{array}\right)=\left(\begin{array}{ccc}1& 1& 1\\ 1& \sigma & \sigma ^2\\ 1& \sigma ^2& \sigma \end{array}\right)^1\left(\begin{array}{c}E_0\\ E_1\\ E_2\end{array}\right)=\frac{1}{3}\left(\begin{array}{ccc}1& 1& 1\\ 1& \sigma ^2& \sigma \\ 1& \sigma & \sigma ^2\end{array}\right)\left(\begin{array}{c}E_0\\ E_1\\ E_2\end{array}\right),$$
(12)
or

$$\{\begin{array}{c}\mathrm{\Delta }_0=\frac{1}{3}(E_0+E_1+E_2),\hfill \\ \mathrm{\Delta }_1=\frac{1}{3}(E_0+\sigma ^2E_1+\sigma E_2),\hfill \\ \mathrm{\Delta }_2=\frac{1}{3}(E_0+\sigma E_1+\sigma ^2E_2).\hfill \end{array}$$
(13)
Therefore the Hamiltonian which neglects the constant term is written as

$$H_0=\mathrm{\Delta }_1\mathrm{\Sigma }_3+\mathrm{\Delta }_2\mathrm{\Sigma }_3^2=\mathrm{\Delta }_1\mathrm{\Sigma }_3+\overline{\mathrm{\Delta }}_1\mathrm{\Sigma }_3^{}.$$
(14)
These $`\mathrm{\Delta }_1`$ and $`\mathrm{\Delta }_2`$ may be considered as a complex ”energy difference” among $`E_0`$, $`E_1`$, $`E_2`$.

By the way, the matrix in the right hand side of (12) (replaced $`1/3`$ with $`1/\sqrt{3}`$)

$$W=\frac{1}{\sqrt{3}}\left(\begin{array}{ccc}1& 1& 1\\ 1& \sigma ^2& \sigma \\ 1& \sigma & \sigma ^2\end{array}\right)U(3)$$
(15)
is very familiar to us. Let $`\mathrm{\Sigma }_1`$ and $`\mathrm{\Sigma }_3`$ be generators of generalized Pauli matrices in the case of $`n=3`$, namely

$$\mathrm{\Sigma }_1=\left(\begin{array}{ccc}0& & 1\\ 1& 0& \\ & 1& 0\end{array}\right),\mathrm{\Sigma }_3=\left(\begin{array}{ccc}1& & \\ & \sigma & \\ & & \sigma ^2\end{array}\right).$$
(16)
Then it is easy to see

$$\mathrm{\Sigma }_1^3=\mathrm{\Sigma }_3^3=\mathrm{𝟏}_3,\mathrm{\Sigma }_1^{}=\mathrm{\Sigma }_1^2,\mathrm{\Sigma }_3^{}=\mathrm{\Sigma }_3^2,\mathrm{\Sigma }_3\mathrm{\Sigma }_1=\sigma \mathrm{\Sigma }_1\mathrm{\Sigma }_3.$$
(17)
Now we can show that $`\mathrm{\Sigma }_1`$ can be diagonalized by making use of $`W`$ above

$$\mathrm{\Sigma }_1=W\mathrm{\Sigma }_3W^{}=W\mathrm{\Sigma }_3W^1.$$
(18)
In fact

$`W\mathrm{\Sigma }_3W^{}`$ $`=`$ $`{\displaystyle \frac{1}{3}}\left(\begin{array}{ccc}1& 1& 1\\ 1& \sigma ^2& \sigma \\ 1& \sigma & \sigma ^2\end{array}\right)\left(\begin{array}{ccc}1& & \\ & \sigma & \\ & & \sigma ^2\end{array}\right)\left(\begin{array}{ccc}1& 1& 1\\ 1& \sigma & \sigma ^2\\ 1& \sigma ^2& \sigma \end{array}\right)`$ (28)
$`=`$ $`{\displaystyle \frac{1}{3}}\left(\begin{array}{ccc}1& \sigma & \sigma ^2\\ 1& 1& 1\\ 1& \sigma ^2& \sigma \end{array}\right)\left(\begin{array}{ccc}1& 1& 1\\ 1& \sigma & \sigma ^2\\ 1& \sigma ^2& \sigma \end{array}\right)={\displaystyle \frac{1}{3}}\left(\begin{array}{ccc}0& 0& 3\\ 3& 0& 0\\ 0& 3& 0\end{array}\right)=\mathrm{\Sigma }_1,`$ (38)
where we have used the relations of $`\sigma `$ in (8).

A comment is in order. Since $`W`$ corresponds to the Walsh–Hadamard matrix (3), so it may be possible to call $`W`$ the generalized Walsh–Hadamard matrix.

Let us proceed with general case. The Hamiltonian with $`n`$ energy levels $`E_0`$, $`E_1`$, $`E_2`$, $`\mathrm{}`$, $`E_{n1}`$ is

$$H_0=\left(\begin{array}{cccccc}E_0& & & & & \\ & E_1& & & & \\ & & E_2& & & \\ & & & & & \\ & & & & & \\ & & & & & E_{n1}\end{array}\right).$$
(39)
From the discussion in the case of $`n=3`$ it is easy to rewrite the Hamiltonian. Let $`\{\mathrm{\Sigma }_1,\mathrm{\Sigma }_3\}`$ be generalized Pauli matrices (see , Appendix B)

$$\mathrm{\Sigma }_1=\left(\begin{array}{cccccc}0& & & & & 1\\ 1& 0& & & & \\ & 1& 0& & & \\ & & & & & \\ & & & & & \\ & & & & 1& 0\end{array}\right),\mathrm{\Sigma }_3=\left(\begin{array}{cccccc}1& & & & & \\ & \sigma & & & & \\ & & \sigma ^2& & & \\ & & & & & \\ & & & & & \\ & & & & & \sigma ^{n1}\end{array}\right)$$
(40)
where $`\sigma `$ is a primitive element $`\sigma =\text{exp}(\frac{2\pi i}{n})`$ which satisfies

$$\sigma ^n=1,\overline{\sigma }=\sigma ^{n1},1+\sigma +\mathrm{}+\sigma ^{n1}=0.$$
(41)
Then it is easy to see

$$\mathrm{\Sigma }_1^n=\mathrm{\Sigma }_3^n=\mathrm{𝟏}_n,\mathrm{\Sigma }_1^{}=\mathrm{\Sigma }_1^{n1},\mathrm{\Sigma }_3^{}=\mathrm{\Sigma }_3^{n1},\mathrm{\Sigma }_3\mathrm{\Sigma }_1=\sigma \mathrm{\Sigma }_1\mathrm{\Sigma }_3.$$
(42)
If we define a Vandermonde matrix $`W`$ based on $`\sigma `$ as

$$W=\frac{1}{\sqrt{n}}\left(\begin{array}{ccccccc}1& 1& 1& & & & 1\\ 1& \sigma ^{n1}& \sigma ^{2(n1)}& & & & \sigma ^{(n1)^2}\\ 1& \sigma ^{n2}& \sigma ^{2(n2)}& & & & \sigma ^{(n1)(n2)}\\ & & & & & & \\ & & & & & & \\ 1& \sigma ^2& \sigma ^4& & & & \sigma ^{2(n1)}\\ 1& \sigma & \sigma ^2& & & & \sigma ^{n1}\end{array}\right),$$
(43)
then it is not difficult to see

$$\mathrm{\Sigma }_1=W\mathrm{\Sigma }_3W^{}=W\mathrm{\Sigma }_3W^1.$$
(44)
That is, $`\mathrm{\Sigma }_1`$ can be diagonalized by making use of $`W`$.

We set for simplicity

$$𝚫=(\mathrm{\Delta }_0,\mathrm{\Delta }_1,\mathrm{},\mathrm{\Delta }_{n2},\mathrm{\Delta }_{n1})^t,𝐄=(E_0,E_1,\mathrm{},E_{n2},E_{n1})^t,$$
(45)
and the relation like (12) between them is given by

$$𝚫=\frac{1}{\sqrt{n}}W𝐄,$$
(46)
or explicitly

$$\mathrm{\Delta }_j=(1/n)\left(E_0+\sigma ^{nj}E_1+\sigma ^{2(nj)}E_2+\mathrm{}+\sigma ^{(n1)(nj)}E_{n1}\right)$$

for $`0jn1`$. Then the Hamiltonian which neglects the constant term is written as

$$H_0=\underset{j=1}{\overset{n1}{}}\mathrm{\Delta }_j\mathrm{\Sigma }_3^j.$$
(47)
Next let us incorporate an interaction into the model. We consider an atom with two energy levels which interacts with external (periodic) field with $`g\text{cos}(\omega t)`$. The Hamiltonian in the dipole approximation is given by

$$H=H_0+g\text{cos}(\omega t)\sigma _1=\mathrm{\Delta }_1\sigma _3+g\text{cos}(\omega t)\sigma _1,\text{cos}(\omega t)=(1/2)(\text{e}^{i\omega t}+\text{e}^{i\omega t}),$$
(48)
where $`\mathrm{\Delta }_1`$ is the constant in (6), $`\omega `$ the frequency of the external field, $`g`$ the coupling constant between the external field and the atom. In the following we cannot assume the rotating wave approximation (which neglects the fast oscillating terms), namely the Hamiltonian given by

$$H=\mathrm{\Delta }_1\sigma _3+\frac{g}{2}\left(\text{e}^{i\omega t}\sigma _++\text{e}^{i\omega t}\sigma _{}\right).$$
(49)
We would like to extend this to the general case. We again note that $`\mathrm{\Sigma }_1`$ is not hermitian, so we must take this fact into consideration. The interaction term corresponding to $`\text{cos}(\omega t)\sigma _1`$ is considered to be

$$\frac{1}{2}\left(\text{e}^{i\omega t}\mathrm{\Sigma }_1+\text{e}^{i\omega t}\mathrm{\Sigma }_1^{}\right)$$
(50)
near to the above (49). Let us explain the reason. The diagonalized form of $`\text{cos}(\omega t)\sigma _1`$ is given by

$$\text{cos}(\omega t)\sigma _1=W\left(\begin{array}{cc}\text{cos}(\omega t)& \\ & \text{cos}(\omega t)\end{array}\right)W^1=W\left(\begin{array}{cc}\text{cos}(\omega t)& \\ & \text{cos}(\omega t+\pi )\end{array}\right)W^1$$

by making use of $`W`$ in (3). On the other hand it is easy to see

$$\frac{1}{2}\left(\text{e}^{i\omega t}\mathrm{\Sigma }_1+\text{e}^{i\omega t}\mathrm{\Sigma }_1^{}\right)=WDW^1$$
(51)
by making use of $`W`$ in (43), where D is a diagonal matrix

$$D=\left(\begin{array}{cccccc}\text{cos}(\omega t)& & & & & \\ & \text{cos}(\omega t+2\pi /n)& & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \text{cos}(\omega t+2\pi (n1)/n)\end{array}\right).$$
(52)
Therefore this is a natural generalization of $`\text{cos}(\omega t)\sigma _1`$.

Now we are in a position to state our proposal :

Proposal The Hamiltonian in the general case is

$$H=H_0+\frac{g}{2}\left(\text{e}^{i\omega t}\mathrm{\Sigma }_1+\text{e}^{i\omega t}\mathrm{\Sigma }_1^{}\right)=\underset{j=1}{\overset{n1}{}}\mathrm{\Delta }_j\mathrm{\Sigma }_3^j+\frac{g}{2}\left(\text{e}^{i\omega t}\mathrm{\Sigma }_1+\text{e}^{i\omega t}\mathrm{\Sigma }_1^{}\right)$$
(53)
where $`g`$ is a coupling constant of the system. In particular in the case of $`n=3`$

$$H=\mathrm{\Delta }_1\mathrm{\Sigma }_3+\overline{\mathrm{\Delta }}_1\mathrm{\Sigma }_3^{}+\frac{g}{2}\left(\text{e}^{i\omega t}\mathrm{\Sigma }_1+\text{e}^{i\omega t}\mathrm{\Sigma }_1^{}\right)$$
(54)
by (14).

We have written down the Hamiltonian in the general case in terms of generalized Pauli matrices, however don’t know whether or not it is actually reasonable in Quantum Optics or Condensed Matter Physics (refer to ). Further considerations will be needed.

We conclude this paper by stating that constructions of solutions under some ansatz (in the weak or strong coupling regime) are not difficult and will be published in another paper, .


text:
# Chapter 1 The VERITAS Project

## Chapter 1 The VERITAS Project

### Abstract

VERITAS is a new, major ground-based $`\gamma `$-ray observatory designed to significantly advance our understanding of extreme astrophysical processes in the universe. The observatory comprises seven large-aperture (12 m diameter) Cherenkov telescopes, each equipped with an imaging camera. The first phase of VERITAS (consisting of four telescopes) is currently under construction. Here we outline the key features of VERITAS and provide an update on its status .

### 1. Introduction

Ground-based $`\gamma `$-ray astronomy came of age in the last decade. The discovery of numerous sources by telescopes using the imaging atmospheric Cherenkov technique proved that very high energy (VHE) astronomy can be done from the ground. Roughly one dozen VHE sources have now been detected with varying levels of significance . The established sources include pulsar-powered nebulae, active galaxies of the BL Lac type, and shell type supernova remnants.

These exciting discoveries strongly motivate the construction of new instruments to substantially increase the VHE source catalog and to enable much more detailed studies of individual sources. VERITAS combines the successful features of the Whipple Observatory (large-aperture reflector, imaging camera) with those of HEGRA (array of reflectors). Relative to current operating imaging telescopes, VERITAS will have substantially better flux sensitivity (factor of five to ten improvement, depending on energy), reduced energy threshold (peak energy near 100 GeV), improved energy resolution (resolution of 10-15% over a broad energy range), and improved angular resolution (4.3 arc-min at 1 TeV).

### 2. VERITAS Design

Serious consideration of VERITAS started in 1996, and its design was developed and finalized over the next several years. The design uses modular construction and proven technology to a large degree, but it also encompasses new technical innovations where appropriate. VERITAS will be an array of seven telescopes, each employing a $`12`$m diameter optical reflector. Each telescope has a camera of 499 photomultiplier tube elements, covering a field of view of 3.5 diameter. The photomultiplier tubes are read out through high-bandwidth electronics by a Flash ADC (FADC) system sampling at 500 MSps. The FADC sampling, a flexible trigger system, and extensive electronic and optical calibration systems are among the important new capabilities of VERITAS. Details on the design and expected performance of VERITAS have been published earlier . This report provides an update on the key developments that have happened recently.

VERITAS will be sited on Mt. Hopkins in southern Arizona, USA, near the Basecamp of the Whipple Observatory (1350 m altitude). The site will be well protected from light pollution (within 20% of the darkest sites available in the U.S.). The construction will be carried out in two phases. During the first phase (VERITAS-4), four telescopes will be constructed and deployed as shown in Figure 1. In the second phase, three additional telescopes will be added to complete the hexagonal array.

### 3. VERITAS-4 Performance

We have carried out detailed simulation studies to estimate the expected performance of the four telescope array, VERITAS-4 – some key results are shown in Table 1. In quoting sensitivity, we make the conservative requirement of at least a five standard deviation $`\gamma `$-ray excess in each energy bin, of width one-quarter decade.

### 4. Technical Progress

A great deal of technical progress has been made on VERITAS, and we are well on our way towards the construction of a prototype telescope encompassing all important design elements. Here we describe the salient features of the VERITAS design and recent progress made on the construction of the prototype that will become operational in mid-2003.

#### 4.1. Telescope, Optical Support Structure, and Mirrors

The VERITAS telescopes consist of a tubular-steel, space-frame optical support structure (OSS) mounted on a commercial positioner. In the OSS design, as shown in Figure 1, quadrapod arms penetrate the mirror surface to hold up the camera. We expect excellent optical performance from the OSS – the blur will be well less than $`0.01^{}`$ over the usable elevation range of the telescope, and the de-centering will be less than $`0.002^{}`$. The positioner for the prototype telescope will be delivered in April 2003.

We use the Davies-Cotton optical design in which the telescope reflecting surface is spherical and the mirror facets are identical in shape. Each $`12`$m diameter (f/1.0) mirror is made from 350 hexagonal facets and has a total mirror area of 110 m2. The facets are made of float glass that has been slumped and polished by the manufacturer (DOTI Technologies). They are aluminized and anodized in a dedicated facility near the Whipple Observatory Basecamp. All the facets for the prototype telescope have been received; mirror coating is in progress. Laser measurements indicate that the optical quality of the facets is better than originally specified: 1) the tolerance of the radius of curvature is better than $`0.4`$% (as opposed to 1.0% specified), and 2) the average blur is less than 0.5 cm (as opposed to 1.0 cm specified).

#### 4.2. Camera, Cables, & High Voltage

The cameras for VERITAS comprise 499 photomultiplier tubes (PMTs), arranged in a close-packed hexagonal pattern with an angular separation between PMTs of $`0.15^{}`$. Light cones increase the photon collection efficiency and protect the PMT’s from stray light pollution. A high-speed, custom-made amplifier is used to boost the signal before transmission through $`40`$m of high-bandwidth 75$`\mathrm{\Omega }`$ coaxial cable. The high voltage level for each PMT can be individually programmed, and custom-designed electronics monitor individual PMT anode currents.

All of the key camera components were tested in November 2001 when thirty PMT channels were installed in the focus box of the Whipple 10m telescope. Performance characteristics (e.g. linearity, rise time, noise levels, etc.) of the full electronics chain of VERITAS were verified. The assembly of the camera for the prototype telescope is currently in progress at the University of Chicago. The integrated camera will be shipped to Mt. Hopkins in spring 2003. Figure 2 shows the camera box during assembly and an FADC trace for a Cherenkov pulse.

#### 4.3. Flash ADCs (FADCs) and Data Acquisition

The custom-built FADCs digitize the Cherenkov pulse waveform at a rate of 500 MSps to provide the maximum possible information about the shape and time structure of the pulse. Each PMT signal is sampled by a separate FADC with an effective dynamic range of 11 bits and a memory depth of 64$`\mu `$s. The FADCs are packaged in 9U VME boards with 10 channels/board. The data acquisition is based around standard VME architecture, comprising a fast VME backplane and crate Single Board Computers (SBC’s) connected to a local event-building workstation via the fast SCI protocol. The FADC design has been finalized, and the boards for the prototype telescope are being built. The VME readout for the FADC system is also near completion; crate-to-crate transfer speeds of 100 MB/s have been achieved.

#### 4.4. Trigger Electronics and Calibration

VERITAS employs a three level trigger system to select Cherenkov events at the lowest possible energy threshold. Level 1 consists of constant fraction discriminators (CFDs) to determine when a PMT pulse exceeds a given threshold. The CFDs are mounted directly on the main FADC board to minimize noise and signal delay. Level 2 comprises a hardware pattern trigger designed to select compact Cherenkov events, as opposed to night sky background overlaps. Level 3 uses the Level 2 telescope triggers to determine when the array has triggered. The designs for all three trigger levels are well advanced and complete systems for the prototype telescope are now being integrated with the other electronics.

The calibration system is designed to calibrate and monitor the performance of each telescope and the combined array. There are three major calibration components: charge injection, optical injection, and atmospheric monitoring. The charge injection system distributes a calibrated amount of charge to the front-end electronics. The initial optical system uses a dye laser to simultaneously flash all PMTs in the camera.

#### 4.5. Software

The online software can be divided into a number of components: 1) FADC and VME data acquisition, 2) Telescope acquisition (event building), 3) Array acquisition/online analysis (Quicklook), and 4) Array Control and Database. The software uses object-oriented (C++) programs running on Intel-based Linux computers. Reliance is made on widely available software packages (e.g. CORBA, SQL, Qt, etc.) for database and graphic user interface tasks and for inter-process communication and control. The majority of the online code for the prototype telescope has been written, and now the major task is integration. Initial software systems for offline analysis and simulation are also in place; these will be augmented and refined in the future.

### 5. Schedule & Summary

VERITAS is a new state-of-the-art ground-based $`\gamma `$-ray observatory for VHE astronomy. An initial phase (VERITAS-4) consists of four atmospheric Cherenov telescopes. A prototype telescope will begin operating in summer 2003, and funding permitting, first light for the VERITAS-4 array is expected in late 2005, well before the launch of the Gamma-ray Large Area Space Telescope (GLAST).

### 6. References

1. Talk presented at the international symposium: The Universe Viewed in Gamma-Rays, 25-28 Sep 2002, Kashiwa, Japan. Symposium proceedings published by Universal Academy Press, Inc, edited by R. Enomoto.

2. Ong, R.A. 2003, these proceedings.

3. Quinn, J. et al. 2001, Proc. 27th. Int. Cosmic Ray Conf. (Hamburg) 7, 2781.

4. Weekes, T.C. et al. 2002, Astroparticle Physics 17, 221.