text:
# A New Mechanism for the 𝛼 to 𝜔 Martensitic Transformation in Pure Titanium

## Abstract

We propose a new direct mechanism for the pressure driven $`\alpha `$$``$$`\omega `$ martensitic transformation in pure titanium. A systematic algorithm enumerates all possible mechanisms whose energy barriers are evaluated. A new, homogeneous mechanism emerges with a barrier at least four times lower than other mechanisms. This mechanism remains favorable in a simple nucleation model.

Martensitic transformations are abundant in nature and are commonly used in engineering technologies martensites . Materials from steel to shape-memory alloys are governed by their underlying martensitic transformations shape-memory . The pressure driven $`\alpha \text{(hcp)}\omega \text{(hexagonal)}`$ transformation in pure titanium, discussed here and reviewed extensively by Sikka et al. sikka , has significant technological implications in the aerospace industry because the $`\omega `$ phase formation lowers toughness and ductility. This transformation was first observed by Jamieson jamieson , and has since been extensively studied using static high-pressure static  and shockwave methods shockwave . Because of experimental difficulties in directly observing martensitic transformation mechanisms, they are usually inferred from the orientation relationships between the initial and final phases. Such an approach may result in multiple transformation mechanisms for any given set of orientation relations, and requires one to guess the appropriate transformation mechanism. Thus, despite several attempts, the mechanism for this transformation is still unclear.

We calculate the energy barrier for homogeneous transformation for different titanium $`\alpha `$$``$$`\omega `$ transformation mechanisms and compare the values using a simplified nucleation model. We systematically generate and sort possible $`\alpha `$$``$$`\omega `$ mechanisms by their energy barriers. A new direct mechanism emerges whose barrier is lowest both homogeneously and when considered in a simple nucleation model.

Figure 1 shows our new low energy barrier mechanism for the $`\alpha `$$``$$`\omega `$ transformation in Ti, called TAO-1, for “Titanium Alpha to Omega.” This direct 6-atom transformation requires no intermediary phase, and has small shuffles and strains. The 6 atoms divide into a group of 4 atoms that shuffle by 0.63 Å and 2 atoms that shuffle by 0.42 Å. Combining these shuffles with strains of $`\epsilon _x=0.91`$, $`\epsilon _y=1.12`$, and $`\epsilon _z=0.98`$ produces a final $`\omega `$ cell from our $`\alpha `$ cell. The original $`\alpha `$ matrix is then oriented relative to the $`\omega `$ matrix such that $`(0001)_\alpha (0\overline{1}11)_\omega `$ and $`[11\overline{2}0]_\alpha [01\overline{1}1]_\omega `$. These orientation relations are seen in some experiments, but not others static ; shockwave ; usikov .

Our mechanism identification method matches possible supercells of $`\alpha `$ and $`\omega `$ to determine the lattice strain, and atom positions to determine the necessary internal relaxations; similar to comsubs . While there are infinitely many possible supercells, we consider only 6 and 12 atom supercells with principal strains less than 1.333 and greater than $`0.75=1.333^1`$. For each supercell, there are multiple ways to shuffle the atom positions from $`\alpha `$ to $`\omega `$; we consider mechanisms where, relative to the center of mass, no atom moves more than 2.0 Å. We also limit the closest distance of approach between any two atoms during the transformation. Each supercell has one mechanism with the largest closest approach distance; we consider all mechanisms for that supercell within 0.1 Å of that value.

To efficiently compare the enthalpy barriers of the possible mechanisms, we use three methods of increasing computational sophistication and accuracy. 1. For each mechanism, we calculate an approximate barrier based only on the strain, using the elastic approximation. Such a calculation of the “elastic barrier” relies only on the elastic constants for each phase, and the supercell geometry 111If $`E_{\mathrm{s}\alpha }`$ and $`E_{\mathrm{s}\omega }`$ are the energies of the fully strained $`\alpha `$ and $`\omega `$ within the elastic approximation, the elastic barrier is $`E_{\mathrm{s}\alpha }E_{\mathrm{s}\omega }/(E_{\mathrm{s}\alpha }^{1/3}+E_{\mathrm{s}\omega }^{1/3})^3`$.. 2. For mechanisms with a low elastic barrier, we calculate an energy landscape using a strain variable ($`\epsilon `$) and a single concerted shuffle variable ($`\delta `$). The energies $`E(\epsilon ,\delta )`$ are calculated using a tight-binding (TB) model tight-binding  on a grid between $`\alpha `$ at $`E(0,0)`$ and $`\omega `$ at $`E(1,1)`$. The energy at the transition state in this reduced space gives a “landscape barrier.” 3. For mechanisms with the lowest landscape barriers, we calculate the exact barrier using the nudged elastic band (NEB) method jonsson  together with our TB model tight-binding  or ab initio VASP simulations VASP , or both. During the NEB calculation, the cell shape and size are allowed to change in response to the applied pressure. In general, we expect the elastic barrier to underestimate the TB landscape barrier, and the TB landscape barrier to overestimate the TB-NEB barrier. The most probable mechanism should have the smallest ab initio NEB enthalpy barrier.

We calculate total energies using a TB model and carefully converged ab initio calculations. The TB calculations are performed with OHMMS ohmms  and use Mehl and Papaconstantopoulos’s functional form tight-binding  with parameters that are refit to reproduce LAPW total energies for hcp, bcc, fcc, omega, and sc to within 0.5 meV/atom. For each mechanism, we use a k-point mesh equivalant to $`12\times 12\times 8`$ in hcp with a 63 meV thermal smearing to give an energy convergence of 1 meV/atom. For our ab initio calculations 222VASP VASP  is a plane-wave based code using ultra-soft Vanderbilt type pseudopotentials pseudo1  as supplied by G. Kresse and J. Hafner pseudo2 . The calculations were performed using the generalized gradient approximation of Perdew and Wang perdew . we include $`3p`$ electrons in the valence band, and use a plane-wave kinetic-energy cutoff of 400 eV and a $`7\times 7\times 7`$ k-point mesh to ensure energy convergence to within 1 meV/atom. We relax the atomic positions and the unit cell shape and volume until the total electronic energy changes by less than 1 meV.

The elastic and landscape energy barrier calculations reduce our initial set of 977 candidate mechanisms to the 3 lowest barrier mechanisms. From the initial list of 134 supercells, we reject all but 57 because their elastic barriers are large (greater than 100 meV/atom). For the remaining 57 supercells, we generate 977 mechanisms (6 6-atom mechanisms and 971 12-atom mechanisms), and compute TB landscape barriers. Figure 2 shows that the elastic barrier underestimates the landscape barrier. We select the three mechanisms with the smallest landscape barriers—TAO-1, TAO-2, and Silcock—for careful study.

Figure 3 illustrates the Silcock mechanism silcock . Her mechanism, determined from observed orientation relations, involves significant atomic shuffle, relatively small strains, and is a direct transformation mechanism with no intermediate state. In each $`\alpha `$ stacking plane, 3 out of every 6 atoms shuffle by 0.74 Å along $`[11\overline{2}0]_\alpha `$, while the other 3 shuffle in the opposite direction $`[\overline{1}\overline{1}20]_\alpha `$. This shuffle is accompanied by a strain $`\epsilon _x=1.05`$ along $`[1\overline{1}00]_\alpha `$ and $`\epsilon _y=0.95`$ along $`[11\overline{2}0]_\alpha `$ to produce a hexagonal $`\omega `$ cell with the correct $`c/a`$ ratio. Despite the lack of direct conclusive evidence to support the Silcock mechanism, it is still widely invoked to describe the $`\alpha `$$``$$`\omega `$ transformation because it is a direct mechanism silcock-evidence .

The remaining two mechanisms, TAO-1 and TAO-2, are related to Usikov and Zilbershtein’s usikov  proposed composite mechanism involving the thermodynamically unstable $`\beta \text{(bcc)}`$ intermediary phase, and proceeding as $`\alpha `$$``$$`\beta `$$``$$`\omega `$. Using the $`\alpha `$-$`\omega `$ orientation relations, they proposed an $`\alpha `$$``$$`\beta `$ transformation via an inverse Burgers mechanism burgers  followed by a $`\beta `$$``$$`\omega `$ transformation via the collapse of 2 out of 3 $`(111)_\beta `$ planes. This produced two unique mechanisms, called Variant I and Variant II, depending on the direction of $`\{111\}_\beta `$ planes to collapse. The TAO-1 and TAO-2 mechanisms could have been constructed from Variant I and II, respectively, by using the $`\beta `$ intermediate system to construct a 6 atom supercell. Allowing Variant I and II to relax away from the $`\beta `$ phase would have resulted in direct transformation mechanisms.

Table 1 summarizes the energy barriers for the three mechanisms of interest and identifies TAO-1 as having the lowest energy barrier. The TAO-1 mechanism provides the best trade off between shuffle and strain; during the transformation, the closest nearest neighbor distance is 2.63 Å, which is larger than the 2.55 Å value for TAO-2 and 2.57 Å for Silcock. Because the nearest-neighbor distances in $`\alpha `$ and $`\omega `$ are 2.95 Å and 2.65 Å, respectively, it is not surprising that TAO-1 has the lowest barrier. The barrier to pass through the intermediate $`\beta `$ phase, as suggested by Usikov and Zilbershtein usikov , is 108 meV/atom—drastically larger than TAO-1’s barrier of 9 meV/atom.

Figure 4 shows the enthalpy along the $`\alpha `$$``$$`\omega `$ transformation path for the three mechanisms as a function of pressure. Our calculation shows $`\omega `$ slightly lower in energy than $`\alpha `$ at 0 GPa. The crystal structure at 0 K has not been determined experimentally; however, extrapolation of the $`\alpha `$-$`\omega `$ phase boundary indicates $`\omega `$ as the ground state sikka . As pressure increases, the enthalpy of $`\omega `$ relative to $`\alpha `$ drops, and all three mechanisms decrease their enthalpy barrier. For the next four lowest landscape barrier mechanisms in Figure 2, we find 0 GPa ab initio NEB barriers of 32, 37, 68, and 69 meV/atom. The barrier of the TAO-1 mechanism is lowest, even up to 40 GPa.

We use classical nucleation theory to relate the homogeneous barriers to the energy scales relevant for microscopic transformation mechanics, given by the formation energy of a critical nucleus. If the formation energy of the critical nuclei is of the same order as the barrier, our mechanism prediction is not expected to change. In classical nucleation theory, nuclei of new material grow only if they are larger than a critical size where the nucleation energy is an extrema. The nucleation energy consists of three terms: the interfacial energy, the enthalpy difference, and the stress from the volume difference.

In estimating the energy to create the critical nucleus, we use the $`\alpha `$-Ti surface energy of 125 meV/Å2 as an upper bound for the $`\alpha `$-$`\omega `$ interfacial energy. The enthalpy difference at the experimental shock transition pressure of 10 GPa is $`20`$ meV/atom, and the stress from the volume difference is 3.5 meV/atom. We use the same critical nucleus size for each mechanism in Table 1 because they each have a plane with no strain after the transformation, so the nuclei likely grow as oblate spheroids to minimize stress. Classical nucleation theory estimates a critical nucleus radius of 240 Å, (3.5 million atoms) with a formation energy of 30 keV. For that sized nucleus the 9 meV/atom barrier of TAO-1 becomes a homogeneous barrier of 28 keV. In contrast, the competing TAO-2 and Silcock mechanisms have barriers of 200 and 120 keV respectively; far above the formation energy and the TAO-1 barrier.

Our systematic search, involving both tight-binding and ab initio calculations, combined with a nucleation analysis leads to the direct TAO-1 mechanism as the preferred $`\alpha `$$``$$`\omega `$ mechanism in pure titanium. Our approach allows us to find the lowest barrier mechanism for any martensitic phase transformation by generating and comparing all relevant possible mechanisms. Indeed this method provides an invaluable starting point for investigating any martensitic transformation.

###### Acknowledgements.

Acknowledgments. We thank G. T. Gray III and C. W. Greeff for helpful discussions, and M. I. Baskes and R. B. Schwarz for reviewing the manuscript. DRT thanks Los Alamos National Laboratory for its hospitality and was supported by a Fowler Fellowship at Ohio State University. This research is supported by DOE grants DE-FG02-99ER45795 (OSU) and W-7405-ENG-36 (LANL). Computational resources were provided by the Ohio Supercomputing Center and NERSC.


format: text

text:
# 1 Abstract

## 1 Abstract

A quantum statistical system with energy dissipation is studied. Its statisitics is governed by random complex-valued non-Hermitean Hamiltonians belonging to complex Ginibre ensemble. The eigenenergies are shown to form stable structure in thermodynamical limit (large matrix dimension limit). Analogy of Wigner and Dyson with system of electrical charges is drawn.

## 2 Summary

A complex quantum system with energy dissipation is considered. The quantum Hamiltonians $`H`$ belong the complex Ginibre ensemble. The complex-valued eigenenergies $`Z_i`$ are random variables. The second differences $`\mathrm{\Delta }^1Z_i`$ are also complex-valued random variables. The second differences have their real and imaginary parts and also radii (moduli) and main arguments (angles). For $`N`$=3 dimensional Ginibre ensemble the distributions of above random variables are provided whereas for generic $`N`$\- dimensional Ginibre ensemble second difference distribution is analytically calculated. The law of homogenization of eigenergies is formulated. The analogy of Wigner and Dyson of Coulomb gas of electric charges is studied.

## 3 Introduction

We study generic quantum statistical systems with energy dissipation. The quantum Hamiltonian operator $`H`$ is in given basis of Hilbert’s space a matrix with random elements $`H_{ij}`$ . The Hamiltonian $`H`$ is not hermitean operator, thus its eigenenergies $`Z_i`$ are complex-valued random variables. We assume that distribution of $`H_{ij}`$ is governed by Ginibre ensemble . $`H`$ belongs to general linear Lie group GL($`N`$, C), where $`N`$ is dimension and C is complex numbers field. Since $`H`$ is not hermitean, therefore quantum system is dissipative system. Ginibre ensemble of random matrices is one of many Gaussian Random Matrix ensembles GRME. The above approach is an example of Random Matrix theory RMT . The other RMT ensembles are for example Gaussian orthogonal ensemble GOE, unitary GUE, symplectic GSE, as well as circular ensembles: orthogonal COE, unitary CUE, and symplectic CSE. The distributions of the eigenenergies $`Z_1,\mathrm{},Z_N`$ for $`N\times N`$ Hamiltonian matrices is given by Jean Ginibre’s formula :

$`P(z_1,\mathrm{},z_N)=`$ (1)
$`={\displaystyle \underset{j=1}{\overset{N}{}}}{\displaystyle \frac{1}{\pi j!}}{\displaystyle \underset{i<j}{\overset{N}{}}}|z_iz_j|^2\mathrm{exp}({\displaystyle \underset{j=1}{\overset{N}{}}}|z_j|^2),`$
where $`z_i`$ are complex-valued sample points ($`z_i𝐂`$). For Ginibre ensemble we define complex-valued spacings $`\mathrm{\Delta }^1Z_i`$ and second differences $`\mathrm{\Delta }^2Z_i`$:

$$\mathrm{\Delta }^1Z_i=Z_{i+1}Z_i,i=1,\mathrm{},(N1),$$
(2)
$$\mathrm{\Delta }^2Z_i=Z_{i+2}2Z_{i+1}+Z_i,i=1,\mathrm{},(N2).$$
(3)
The $`\mathrm{\Delta }^2Z_i`$ are extensions of real-valued second differences

$$\mathrm{\Delta }^2E_i=E_{i+2}2E_{i+1}+E_i,i=1,\mathrm{},(N2),$$
(4)
of adjacent ordered increasingly real-valued energies $`E_i`$ defined for GOE, GUE, GSE, and Poisson ensemble PE (where Poisson ensemble is composed of uncorrelated randomly distributed eigenenergies) .

There is an analogy of Coulomb gas of unit electric charges pointed out by Eugene Wigner and Freeman Dyson. A Coulomb gas of $`N`$ unit charges moving on complex plane (Gauss’s plane) C is considered. The vectors of positions of charges are $`z_i`$ and potential energy of the system is:

$$U(z_1,\mathrm{},z_N)=\underset{i<j}{}\mathrm{ln}|z_iz_j|+\frac{1}{2}\underset{i}{}|z_i^2|.$$
(5)
If gas is in thermodynamical equilibrium at temperature $`T=\frac{1}{2k_B}`$ ($`\beta =\frac{1}{k_BT}=2`$, $`k_B`$ is Boltzmann’s constant), then probability density function of vectors of positions is $`P(z_1,\mathrm{},z_N)`$ Eq. (1). Complex eigenenergies $`Z_i`$ of quantum system are analogous to vectors of positions of charges of Coulomb gas. Moreover, complex-valued spacings $`\mathrm{\Delta }^1Z_i`$ are analogous to vectors of relative positions of electric charges. Finally, complex-valued second differences $`\mathrm{\Delta }^2Z_i`$ are analogous to vectors of relative positions of vectors of relative positions of electric charges.

The $`\mathrm{\Delta }^2Z_i`$ have their real parts $`\mathrm{Re}\mathrm{\Delta }^2Z_i`$, and imaginary parts $`\mathrm{Im}\mathrm{\Delta }^2Z_i`$, as well as radii (moduli) $`|\mathrm{\Delta }^2Z_i|`$, and main arguments (angles) $`\mathrm{Arg}\mathrm{\Delta }^2Z_i`$.

## 4 Second Difference Distributions

We define following random variables for $`N`$=3 dimensional Ginibre ensemble:

$$Y_1=\mathrm{\Delta }^2Z_1,A_1=\mathrm{Re}Y_1,B_1=\mathrm{Im}Y_1,$$
(6)
$$R_1=|Y_1|,\mathrm{\Phi }_1=\mathrm{Arg}Y_1,$$
(7)
and for the generic $`N`$-dimensional Ginibre ensemble : $`W_1=\mathrm{\Delta }^2Z_1`$.

Their distributions for are given by following formulae :

$`f_{Y_1}(y_1)=f_{(A_1,B_1)}(a_1,b_1)=`$ (8)
$`={\displaystyle \frac{1}{576\pi }}[(a_1^2+b_1^2)^2+24]\mathrm{exp}({\displaystyle \frac{1}{6}}(a_1^2+a_2^2)).`$
$$f_{A_1}(a_1)=\frac{\sqrt{6}}{576\sqrt{\pi }}(a_1^4+6a_1^2+51)\mathrm{exp}(\frac{1}{6}a_1^2),$$
(9)
$$f_{B_1}(b_1)=\frac{\sqrt{6}}{576\sqrt{\pi }}(b_1^4+6b_1^2+51)\mathrm{exp}(\frac{1}{6}b_1^2),$$
(10)
$`f_{R_1}(r_1)=`$ (11)
$`\mathrm{\Theta }(r_1){\displaystyle \frac{1}{288}}r_1(r_1^4+24)\mathrm{exp}({\displaystyle \frac{1}{6}}r_1^2),`$
$`f_{\mathrm{\Phi }_1}(\varphi _1)={\displaystyle \frac{1}{2\pi }},\varphi _1[0,2\pi ].`$
$`P_3(w_1)=`$ (12)
$`=\pi ^3{\displaystyle \underset{j_1=0}{\overset{N1}{}}}{\displaystyle \underset{j_2=0}{\overset{N1}{}}}{\displaystyle \underset{j_3=0}{\overset{N1}{}}}{\displaystyle \frac{1}{j_1!j_2!j_3!}}I_{j_1j_2j_3}(w_1),`$
$`I_{j_1j_2j_3}(w_1)=`$ (13)
$`=2^{2j_2}{\displaystyle \frac{^{j_1+j_2+j_3}}{^{j_1}\lambda _1^{j_2}\lambda _2^{j_3}\lambda _3}}F(w_1,\lambda _1,\lambda _2,\lambda _3)|_{\lambda _i=0},`$
$`F(w_1,\lambda _1,\lambda _2,\lambda _3)=`$ (14)
$`=A(\lambda _1,\lambda _2,\lambda _3)\mathrm{exp}[B(\lambda _1,\lambda _2,\lambda _3)|w_1|^2],`$
$`A(\lambda _1,\lambda _2,\lambda _3)=`$ (15)
$`={\displaystyle \frac{(2\pi )^2}{(\lambda _1+\lambda _2\frac{5}{4})(\lambda _1+\lambda _3\frac{5}{4})(\lambda _11)^2}},`$
$`B(\lambda _1,\lambda _2,\lambda _3)=`$ (16)
$`=(\lambda _11){\displaystyle \frac{2\lambda _1\lambda _2\lambda _3+\frac{1}{2}}{2\lambda _1+\lambda _2+\lambda _3\frac{9}{2}}}.`$
## 5 Conclusions

We compare second difference distributions for different ensembles by defining following dimensionless second differences:

$$C_\beta =\frac{\mathrm{\Delta }^2E_1}{<S_\beta >},$$
(17)
$$X_1=\frac{A_1}{<R_1>},$$
(18)
where $`<S_\beta >`$ are the mean values of spacings for GOE(3) ($`\beta =1`$), for GUE(3) ($`\beta =2`$), for GSE(3) ($`\beta =4`$), for PE ($`\beta =0`$) , and $`<R_1>`$ is mean value of radius $`R_1`$ for $`N`$=3 dimensional Ginibre ensemble .

On the basis of comparison of results for Gaussian ensembles, Poisson ensemble, and Ginibre ensemble we formulate homogenization law : Eigenenergies for Gaussian ensembles, for Poisson ensemble, and for Ginibre ensemble tend to be homogeneously distributed. The second differences’ distributions assume global maxima at origin for above ensembles. For Coulomb gas the vectors of relative positions of vectors of relative positions of charges statistically vanish. It can be called stabilisation of structure of system of electric charges.

## 6 Acknowledgements

It is my pleasure to most deeply thank Professor Jakub Zakrzewski for formulating the problem.


text:
# The uncertainty principle for operators determined by Lie groups

## Abstract.

For unbounded operators $`A,B`$ and $`C`$ in general, the commutation relation $`[A,B]=C`$ does not lead to the uncertainty relation $`AuBu\frac{1}{2}|\overline{C}u,u|.`$ If $`A,B`$ and $`C`$ are part of the generators of a unitary representation of a Lie group then the uncertainty principle above holds.

The author wishes to thank Henrik Schlichtkrull for his proofreading and kind supervision

If $`A`$ and $`B`$ are self-adjoint or skew-adjoint operators then

(1)
$$AuBu\frac{1}{2}|[A,B]u,u|\text{for all }uD([A,B])$$

The operator $`[A,B]`$ need not be closed, and if $`C=\overline{[A,B]}`$, the extended inequality

(2)
$$AxBx\frac{1}{2}|Cx,x|\text{for all }xD(A)D(B)D(C).$$

need not be valid. K. Kraus  showed that (2) holds when $`A,B`$ and $`C`$ are infinitesimal generators of a unitary representation of a Lie group of dimension $`3`$. The result of K. Kraus was slightly extended by G.B. Folland and A. Sitaram in \[1, Theorem 2.4\], but the necessity of the dimension constraint was left as an open problem. In the present paper the dimension constraint is shown to be unnecessary, by means of some results by I.E. Segal in .

If $`(H,\pi )`$ is a unitary representation of a Lie group $`G`$ and $`R`$ is a right-invariant vector field, then by Stone’s theorem one can define the closed skew-adjoint (by Lemma 3.1.13 in ) operator $`\pi (R)`$ such that $`\pi (\mathrm{exp}tR)=\mathrm{exp}(\pi (tR))`$ for all $`t.`$ Then $`[\pi (X),\pi (Y)]\pi ([X,Y])`$.

###### Theorem.

Let $`G`$ be a Lie group with Lie algebra $`𝔤`$, and let $`(H,\pi )`$ be a unitary representation of $`G`$. Suppose that $`X,Y𝔤`$. Then

$$AxBx\frac{1}{2}|Cx,x|\text{for all }xD(A)D(B)D(C)$$

holds with $`A=\pi (X)`$,$`B=\pi (Y)`$ and $`C=\pi ([X,Y])`$.

###### Lemma.

Let $`\sigma `$ be the modular function on $`G`$. Given a right-invariant vector field $`R`$ on $`G`$, let $`L`$ be the corresponding left-invariant vector field, and let $`\gamma =\frac{d}{dt}\sigma (\mathrm{exp}(tR))|_{t=0}`$.

1. If $`fC_c^{\mathrm{}}(G)`$ and $`f^{}(g)=\overline{f(g^1)}\sigma (g)`$, then $`\pi (Rf^{})^{}=\pi (Lf)+\gamma \pi (f)`$.
2. There is a sequence $`\{f_n\}`$ in $`C_c^{\mathrm{}}(G)`$ such that $`\pi (f_n)uu`$ and $`\pi (Rf_n)u+\pi (Lf_n)u+\gamma \pi (f_n)u0`$ for all $`uH`$.

###### Proof.

(a) is simply Lemma 3.1.7 in  using the fact that $`f^{}=f`$. (b) is Lemma 3.1.8 and Lemma 3.1.9 in , and $`\pi (f_n)uu`$ has been proved in \[3, p.56\]. ∎

To prove the theorem I will first show that for $`R𝔤`$ it holds that $`\pi (R)\pi (f_n)u\pi (R)u`$ for $`uD(\pi (R))`$. Fix $`R𝔤`$ and let $`L`$ be the left-invariant vector field corresponding to $`R`$. Note that for all $`fC_c^{\mathrm{}}(G)`$ it holds that $`\pi (f)\pi (R)\pi (Rf^{})^{},`$ since $`\pi (f)\pi (R)u,v=u,\pi (Rf^{})v`$ for all $`uD(\pi (R))`$ and $`vH.`$ Hence

$$\pi (f)\pi (R)\pi (Lf)\gamma \pi (f)$$

by (a) of the lemma. But then

$`\pi (R)\pi (f_n)u\pi (f_n)\pi (R)u`$ $`=\pi (Rf_n)u+\pi (Lf_n)u+\gamma \pi (f_n)u`$
for any $`uD(\pi (R)).`$ By (b) in the lemma this tends to $`0`$ and since $`\pi (f_n)\pi (R)u\pi (R)u`$ it follows that $`\pi (R)\pi (f_n)u\pi (R)u`$.

Now let $`A,B`$ and $`C`$ be as in the theorem. For any $`uD(A)D(B)D(C)`$ it follows that $`\pi (f_n)uu`$, $`A\pi (f_n)uAu`$, $`B\pi (f_n)uBu`$ and $`C\pi (f_n)uCu`$. Since the Gårding vector $`\pi (f_n)u`$ is in $`D([A,B])`$ by \[3, p.56\] the inequality (1) gives (2) as desired.


text:
# 1 Introduction

## 1 Introduction

Consider a convex polytope $`P`$ in the $`n`$-dimensional hyperbolic space $`IH^n`$.

A polytope is called a Coxeter polytope if its dihedral angles are integer parts of $`\pi `$. Any Coxeter polytope is a fundamental domain of the discrete group generated by the reflections with respect to its facets.

We are interested in Coxeter polytopes of finite volume. In fact, there is no complete classification of such polytopes, but some partial results are obtained. For example, Coxeter polytopes in $`IH^3`$ are completely characterized by Andreev ; all the hyperbolic simplices are classified ().

There are some results about hyperbolic $`n`$-polytopes with $`n+2`$ facets. Kaplinskaja  described all Coxeter simplicial prisms, and Esselmann  obtained the classification of compact Coxeter hyperbolic $`n`$-polytopes with $`n+2`$ facets. In this paper, we complete the classification of Coxeter hyperbolic $`n`$-polytopes of finite volume with $`n+2`$ facets.

The author is grateful to Prof. R. Kellerhals who brought the work  to his attention.

## 2 Gale diagrams

The essential facts about convex polytopes and Gale diagrams which are used in this paper are quoted below. Proofs and details may be found in .

Every combinatorial type of $`n`$-polytope with $`k`$ facets can be represented by a Gale diagram. This consists of $`m`$ points $`a_1,\mathrm{},a_m`$ of the unit sphere in $`IR^{k(n+1)}`$ centered at the origin and (possibly) the origin $`a_0`$ which are labeled according to the following rules:

1) Each label is a positive integer, and the sum of labels equals $`k`$.

2) The points that lie in any open half-space bounded by a hyperplane through the origin have labels whose sum is at least two.

The combinatorial type of a convex polytope can be read off from the Gale diagram in the following way. Each point $`a_i`$ with label $`\mu _i`$ corresponds to $`\mu _i`$ facets $`f_{i,1},\mathrm{},f_{i,\mu _i}`$ of $`P`$. For any subset $`I`$ of the set of facets of $`P`$ the intersection of facets $`\{f_{j,\gamma }|(j,\gamma )I\}`$ is a face of $`P`$ if and only if $`0`$ is contained in the relative interior of $`conv\{a_j|(j,\gamma )I\}`$.

By pyramid in $`IH^n`$ we mean a convex hull of a point (apex) and an $`(n1)`$-dimensional polytope which is not a simplex. A polytope $`P`$ is called a multipyramid  if $`P`$ is a pyramid over a pyramid.

Now let $`P`$ be a $`n`$-polytope with $`n+2`$ facets. In this case the Gale diagram is one-dimensional, and each point in the diagram is equal to $`1`$, $`0`$ or $`+1`$. The multiplicity of $`1`$, $`0`$ and $`+1`$ is defined to be the label of correspondent point in the Gale diagram. Suppose that the multiplicities are $`p`$, $`q`$ and $`r`$ respectively, $`p+q+r=n+2`$. There exists a polytope correspondent to a Gale diagram if and only if $`p,r2`$ holds.

In the case $`q=0`$ the combinatorial type of $`P`$ is a product of two simplices of dimension $`p1`$ and $`r1`$. The set of facets is a union of two disjoint sets $`J_p`$ and $`J_r`$ of order $`p`$ and $`r`$ respectively. Any vertex of $`P`$ is an intersection of $`p1`$ facets from $`J_p`$ and $`r1`$ facets from $`J_r`$.

If $`q=1`$ then the combinatorial type of $`P`$ is a pyramid over a product of two simplices. If $`q>1`$ then the combinatorial type of $`P`$ is a multipyramid over a product of two simplices.

###### Lemma 1.

Let $`P`$ be a Coxeter polytope in $`IH^n`$ with $`n+2`$ facets. Then the combinatorial type of $`P`$ is either a product of two simplices or a pyramid over a product of two simplices.

###### Proof.

It is sufficient to prove that any pyramid over a pyramid is not a Coxeter polytope.

Suppose that $`P`$ is a pyramid over a pyramid $`P^{}`$. Since $`P^{}`$ is a pyramid, it is not simple. Hence, the apex $`A`$ of the pyramid $`P`$ is an ideal vertex of $`P`$. Consider a small horosphere $`h`$ centered in $`A`$. The combinatorial type of the intersection $`hP`$ coincides with the combinatorial type of $`P^{}`$. At the same time, $`hP`$ is a compact Euclidean Coxeter $`(n1)`$-polytope. But any compact Euclidean Coxeter polytope is simple.

Any Coxeter polytope $`P`$ can be represented by its Coxeter diagram $`\mathrm{\Sigma }(P)`$. Nodes of Coxeter diagram correspond to the facets of $`P`$. Two nodes are joined by a $`(m2)`$-fold edge or a $`m`$-labeled edge if the corresponding dihedral angle equals $`\frac{\pi }{m}`$. If the corresponding facets are parallel the nodes are joined by a bold edge, and if they diverge then the nodes are joined by a dotted edge labeled by $`cosh(\rho )`$, where $`\rho `$ is the distance between the facets.

Let $`\mathrm{\Sigma }`$ be a diagram of order $`k`$ with nodes $`v_1`$,…,$`v_k`$. Define a symmetric $`k\times k`$ matrix $`G(\mathrm{\Sigma })`$ with $`g_{ii}=1`$, $`i=1,\mathrm{},k`$, and $`g_{ij}=cos(\frac{\pi }{k})`$ ($`g_{ij}=1`$ or $`g_{ij}=cosh(\rho )`$) if $`v_i`$ and $`v_j`$ are joined by $`k`$-labeled edge (by a bold edge or by a dotted edge labeled by $`cosh(\rho )`$ respectively).

If $`\mathrm{\Sigma }`$ is a Coxeter diagram of a polytope $`P`$ then the matrix $`G(\mathrm{\Sigma })`$ coincides with the Gram matrix of $`P`$. See  for details.

By the signature and the determinant of a diagram $`\mathrm{\Sigma }`$ we mean the signature and the determinant of the matrix $`G(\mathrm{\Sigma })`$.

## 3 Products of two simplices

In this section, we classify all the non-compact $`n`$-polytopes of finite volume with $`n+2`$ facets, combinatorial type of which is a product of two simplices of dimension greater than one. For the classification of compact polytopes of this combinatorial type see . All simplicial prisms are listed in  (see also ).

The result of this section is

###### Theorem 1.

There exists a unique non-compact Coxeter polytope of finite volume which is combinatorially equivalent to a product of two simplices of dimension greater than one. It is shown in Fig. 1.

A diagram $`\mathrm{\Sigma }`$ is called a Lannér diagram if any subdiagram of $`\mathrm{\Sigma }`$ is elliptic, and the diagram $`\mathrm{\Sigma }`$ is neither elliptic nor parabolic. All Lannér diagrams are classified in .

###### Lemma 2.

Let $`P`$ be a hyperbolic Coxeter polytope which combinatorial type is a product of two simplices and $`\mathrm{\Sigma }`$ be a Coxeter diagram of $`P`$. Then $`\mathrm{\Sigma }`$ satisfies the following three conditions:

* $`\mathrm{\Sigma }`$ is a union of two disjoint Lannér diagrams $`L_1`$ and $`L_2`$.
* For any $`v_1L_1`$ and $`v_2L_2`$ a diagram $`\mathrm{\Sigma }\{v_1,v_2\}`$ is either elliptic or parabolic.
* $`Det(\mathrm{\Sigma })=0`$.

###### Proof.

According to Section 2, $`\mathrm{\Sigma }`$ is a union of two disjoint diagrams, say $`L_1`$ and $`L_2`$, where $`L_1`$ consists of facets correspondent to $`1`$ in the Gale diagram of $`P`$, and $`L_2`$ consists of facets correspondent to $`1`$. Any vertex of $`P`$ corresponds to a subdiagram of $`\mathrm{\Sigma }`$ that is $`\mathrm{\Sigma }\{v_1,v_2\}`$, where $`v_1L_1`$, $`v_2L_2`$. Conversely, for any $`v_1L_1`$ and $`v_2L_2`$ a diagram $`\mathrm{\Sigma }\{v_1,v_2\}`$ corresponds to a vertex of $`P`$. Thus, $`\mathrm{\Sigma }\{v_1,v_2\}`$ is either elliptic or parabolic. Any subdiagram of $`\mathrm{\Sigma }\{v_1,v_2\}`$ is elliptic. In particular, $`L_1v_1`$ and $`L_2v_2`$ are elliptic for any $`v_1L_1`$ and $`v_2L_2`$.

By , Th. 3.1, a subdiagram of $`\mathrm{\Sigma }`$ defines a proper face of $`P`$ if and only if it is elliptic. Hence, $`L_1`$ and $`L_2`$ are not elliptic. By , Th. 4.1, $`L_1`$ and $`L_2`$ are not parabolic. Therefore, $`L_1`$ and $`L_2`$ are Lannér diagrams, and we have proved (i) and (ii). Condition (iii) follows immediately from the fact that the hyperbolic $`n`$-polytope $`P`$ has more than $`n+1`$ facets.

Conditions (i) and (ii) are satisfied by a big number of Coxeter diagrams. All the diagrams containing parabolic subdiagrams are listed in Table 1. The rest diagrams can not correspond to non-compact polytope. To compute the determinants of diagrams shown in the left column we use technical tools from  (Prop. 13, Prop. 15 and Table 2). No of these polytopes has $`Det=0`$.

A direct computation of other determinants shows that the only Coxeter diagram with $`Det=0`$ is one shown in Fig. 1. Denote it by $`\mathrm{\Sigma }_0`$. Denote its nodes as shown in Fig. 1.

Now we shall check the signature of $`\mathrm{\Sigma }_0`$. Since $`\mathrm{\Sigma }_0\{v_1,v_2,v_3\}`$ is a Lannér diagram, the negative inertia index is at least one. $`\mathrm{\Sigma }_0\{v_1,v_4\}`$ is elliptic, and the positive inertia index is at least 4. The determinant of $`\mathrm{\Sigma }_0`$ equals 0. Thus, the signature is (4,1,1), where the first number is the positive inertia index, the second is the negative inertia index and the third one is the corank of $`\mathrm{\Sigma }_0`$.

By Theorem 2.1 of  for any Coxeter diagram of signature $`(n,1,l)`$ there exists a polytope in $`IH^n`$ correspondent to this diagram. Hence, there exists a Coxeter polytope with the Coxeter diagram $`\mathrm{\Sigma }_0`$. According to , Prop. 4.2, this polytope has finite volume.

## 4 Pyramids

In this section, we classify all the $`n`$-polytopes of finite volume with $`n+2`$ facets, combinatorial type of which is a pyramid over a product of two simplices.

We need the following

###### Lemma 3 (, Prop. 12).

Let $`\mathrm{\Sigma }`$ be a Coxeter diagram and $`v`$ be a node of $`\mathrm{\Sigma }`$. Suppose that $`\mathrm{\Sigma }v`$ is a union of two disjoint parabolic diagrams. Then $`Det(\mathrm{\Sigma })=0`$.

A diagram $`\mathrm{\Sigma }`$ is called a quasi-Lannér diagram if any subdiagram of $`\mathrm{\Sigma }`$ is either elliptic or parabolic, and the diagram $`\mathrm{\Sigma }`$ is neither elliptic nor parabolic. The complete list of quasi-Lannér diagrams can be found in .

###### Lemma 4.

Let $`P`$ be a hyperbolic Coxeter pyramid over a product of two simplices and $`\mathrm{\Sigma }`$ be a Coxeter diagram of $`P`$. Then $`\mathrm{\Sigma }`$ satisfies the following three conditions:

* $`\mathrm{\Sigma }`$ is a union of two quasi-Lannér diagrams $`L_1`$ and $`L_2`$. The intersection of $`L_1`$ and $`L_2`$ is a unique node $`v`$. $`L_1v`$ and $`L_2v`$ are not adjacent.
* The diagrams $`L_1v`$ and $`L_2v`$ are parabolic. Any other subdiagram of $`L_1`$ or $`L_2`$ is elliptic.
* For any $`v_1L_1v`$ and $`v_2L_2v`$ a diagram $`\mathrm{\Sigma }\{v_1,v_2\}`$ is either elliptic or parabolic.

Any Coxeter diagram satisfying (i)(iii) determines a hyperbolic Coxeter pyramid over a product of two simplices.

###### Proof.

1. Let $`A`$ be the apex of the pyramid $`P`$ and $`v`$ be the node of $`\mathrm{\Sigma }`$ correspondent to the facet of $`P`$ opposite to $`A`$. Consider a small horosphere $`h`$ centered in $`A`$. The intersection $`hP`$ is a direct product of two Euclidean simplices. Thus, $`\mathrm{\Sigma }v`$ is a union of two disjoint parabolic diagrams, say $`S_1`$ and $`S_2`$. Clearly, $`S_1`$ and $`S_2`$ are not adjacent.

Any vertex of $`P`$ except $`A`$ corresponds to a subdiagram $`\mathrm{\Sigma }\{v_1,v_2\}`$, where $`v_1S_1`$, $`v_2S_2`$. Hence, $`\mathrm{\Sigma }\{v_1,v_2\}`$ is either elliptic or parabolic. Since $`S_1`$ contains at least two vertices, the diagram $`\mathrm{\Sigma }\{S_1,v_2\}`$ is a proper subdiagram of $`\mathrm{\Sigma }\{v_1,v_2\}`$. Thus, it is elliptic.

Denote by $`L_1`$ and $`L_2`$ subdiagrams $`S_1v`$ and $`S_2v`$ respectively. We have proved that for any node $`uL_1`$ the diagram $`L_1u`$ is either parabolic (if $`u`$ coincides with $`v`$) or elliptic (otherwise). Hence, $`L_1`$ is a quasi-Lannér diagram with the only parabolic subdiagram $`S_1`$. Analogously, $`L_2`$ is a quasi-Lannér diagram with the only parabolic subdiagram $`S_2`$.

2. We have shown that conditions (i)(iii) are necessary. Now, suppose that $`\mathrm{\Sigma }`$ satisfies all the three conditions. The negative inertia index of $`\mathrm{\Sigma }`$ equals 1, since $`\mathrm{\Sigma }`$ has a Lannér subdiagram $`L_1`$ and the subdiagram $`\mathrm{\Sigma }v`$ is parabolic. For any $`v_1L_1v`$ and $`v_2L_2v`$ the subdiagram $`\mathrm{\Sigma }\{v,v_1,v_2\}`$ is elliptic. Hence, the positive inertia index of $`\mathrm{\Sigma }`$ is at least $`n1`$. By Lemma 3 $`Det(\mathrm{\Sigma })=0`$. Thus, the signature of $`\mathrm{\Sigma }`$ is either (n-1,1,2) or (n,1,1). According to , Th. 2.1, there exists a Coxeter polytope in $`IH^k`$ with Coxeter diagram $`\mathrm{\Sigma }`$, where $`k`$ is either $`n1`$ or $`n`$.

Suppose that the signature of $`\mathrm{\Sigma }`$ is (n-1,1,2). Then there exists a Coxeter polytope $`P`$ in $`IH^{n1}`$ with Coxeter diagram $`\mathrm{\Sigma }`$. This is impossible, since $`\mathrm{\Sigma }v`$ is a parabolic subdiagram of $`\mathrm{\Sigma }`$ of rank $`n1`$.

Hence, the signature of $`\mathrm{\Sigma }`$ equals (n,1,1), and $`\mathrm{\Sigma }`$ determines a Coxeter polytope $`P`$ in $`IH^n`$. By Lemmas 1 and 2, $`\mathrm{\Sigma }`$ determines a hyperbolic Coxeter pyramid over a product of two simplices. This polytope is of finite volume by , Prop. 4.2.

Considering all the quasi-Lannér diagrams with exactly one parabolic subdiagram, we obtain the following

###### Theorem 2.

All the Coxeter polytopes of finite volume the combinatorial type of which is a pyramid over a product of two simplices are listed in Tables 213.

Remark. Black nodes in Tables 213 correspond to the bases of pyramids.


text:
# Exploring isospin, strangeness and charm distillation in nuclear collisionsSupported by DFG, BMBF, GSI and BCPL

## Acknowledgement

We thank A. Kostyuk, L. Gerland, R. Vogt, and L. Csernai for many fruitful discussions.


text:
# Checking 2×𝑀 separability via semidefinite programming

## I Introduction

In the last decade entanglement has been recognized to be a fundamental notion in quantum information processing. While initially entanglement lead to “paradoxes” in quantum mechanics, it was later discovered to be a useful tool in teleportation, secure key distribution (quantum cryptography), quantum computation, etc. (see, e.g., Nielsen and Chuang (2000) and Brylinski and Chen (2002)). Despite its importance there does not yet exist a tractable conclusive test to check for entanglement or the lack thereof (separability). There are several partial tests the most famous of which is the Peres test Peres (1996) which says that a separable state remains positive under taking partial transposes. In some cases the Peres test is also conclusive, namely in the low dimensional cases $`2\times M`$, $`M=2,3`$ (see Horodecki et al. (1996)) and in cases where the density matrix is of low rank (see Horodecki et al. (2000)). Recently, in Doherty et al. (2002) the partial positive test was combined with an extendibility property to obtain a sequence of tests stronger than the Peres test, that all separable matrices need to pass. It is not known whether failure to pass this sequence of tests yields entanglement. Our main result concerns a sequence of tests that for the $`2\times M`$ separability problem do the opposite. Namely, passing one of the tests yields $`2\times M`$ separability. This sequence of tests yields a definite answer to the $`2\times M`$ separability problem in the sense that any $`2\times M`$ separable matrix is arbitrarily close to a matrix satisfying one of the tests. Let us present the details.

Let $`M_p(K)`$ denote $`p\times p`$ matrices whose entries belong to $`K`$. Recall that a matrix $`\rho M_2(M_M())`$ is called $`2\times M`$ separable if there exists $`x_i^2`$ and $`y_i^M`$ so that

$$\left(\begin{array}{cc}A& B\\ B^{}& D\end{array}\right)=\underset{i}{}x_ix_i^{}y_iy_i^{}.$$

Here $`^{}`$ denotes the conjugate transpose and $``$ denotes the Kronecker product. Let $`n1`$ and $`\rho =\left(\begin{array}{cc}A& B\\ B^{}& D\end{array}\right)`$, where $`A,B,`$ and $`D`$ are $`M\times M`$ matrices. We introduce the following convex set, which may be empty. Let $`𝒢(\rho ;n)M_{n+1}(M_2(M_M()))`$ consist of all positive semidefinite block matrices $`\mathrm{\Gamma }=(\mathrm{\Gamma }_{ij})_{i,j=0}^n`$ (notation: $`\mathrm{\Gamma }0`$) where

$$\mathrm{\Gamma }_{ij}=\left(\begin{array}{cc}\mathrm{\Gamma }_{ij}^{(a)}& \mathrm{\Gamma }_{ij}^{(b)}\\ \mathrm{\Gamma }_{ij}^{(c)}& \mathrm{\Gamma }_{ij}^{(d)}\end{array}\right)M_2(M_M()),0i,jn,$$

satisfy the conditions

* $`_{i=0}^n\mathrm{\Gamma }_{ii}^{(a)}=A`$,
* $`_{i=0}^n\mathrm{\Gamma }_{ii}^{(d)}=D`$,
* $`_{i=0}^{n1}\frac{1}{2}(\mathrm{\Gamma }_{i,i+1}^{(c)}+\mathrm{\Gamma }_{i,i+1}^{(b)})=B`$,
* $`_{i=0}^n(\mathrm{\Gamma }_{i,i}^{(c)}\mathrm{\Gamma }_{i,i}^{(b)})=0`$, and
* $`_{i=0}^{nk}(\mathrm{\Gamma }_{i,i+k}^{(c)}\mathrm{\Gamma }_{i,i+k}^{(b)})=0`$, $`k=1,\mathrm{},n`$.

We will be interested in matrices $`\rho `$ for which $`𝒢(\rho ;n)`$ is nonempty. Therefore we define

$$𝒜_n:=\{\rho M_2(M_M()):𝒢(\rho ;n)\mathrm{}\}.$$

It is straightforward to check that $`𝒜_n`$ is a closed convex cone. Moreover, since $`𝒢(\rho ;n)0_{2M}𝒢(\rho ;n+1)`$ one obtains that $`𝒜_n𝒜_{n+1}`$, $`n1`$.

It is an important feature of the set $`𝒢(\rho ;n)`$ that it is the intersection of the cone of positive semidefinite matrices (PSD) and an affine set. As such, the question of whether the set is empty or not, falls into a class of well studied problems, called semidefinite programming (SDP). Checking the nonemptyness of such an intersection is called the feasibility problem in SDP, and several software packages (e.g., Alizadeh et al. (1997), Vandenberghe and Boyd (1994)) are readily available to solve the feasibility problem numerically. A good overview article on SDP is Vandenberghe and Boyd (1996).

We now state the main result.

###### Theorem I.1

The matrix $`\rho M_2(M_M())`$ is $`2\times M`$ separable if and only if

$$\rho \overline{_{n1}𝒜_n}.$$

Based on the above theorem one may now formulate the following algorithm for checking for $`2\times M`$ separability. Given a time limit in which the check needs to be performed, make $`n`$ as large as possible so that $`\rho 𝒜_n`$ may be checked via SDP within the given time limit. In case the test comes out affirmatively, the given matrix $`\rho `$ is $`2\times M`$ separable. When the test shows that $`\rho 𝒜_n`$ the test is inconclusive. Still, given the content of Theorem I.1, the negative outcome may be an indication that the matrix is entangled. Of course, the larger $`n`$ was chosen, the stronger the indication is.

This is certainly not the first instance where SDP has been used for a quantum information problem. In fact, the earlier mentioned tests in Doherty et al. (2002) may be done by SDP. Moreover, in the papers Audenaert and De Moor (2002), Rains (2001), Ježek et al. (2002), Eldar et al. (preprint at quant-ph/0205178) connections have been made between several other problems in quantum information and the versatile SDP tool.

We will prove Theorem I.1 by characterizing positive maps (also known as entanglement witnesses) acting on $`2\times 2`$ matrices. This characterization shall come about from the analysis of quadratic matrix polynomials in a complex variable.

## II Positive maps

We say that a linear map $`\mathrm{\Phi }:^{2\times 2}^{M\times M}`$ is positive when $`\mathrm{\Phi }(G)0`$ whenever $`G0`$. By linearity it suffices to check this condition for rank 1 matrices $`G`$. Furthermore, we may assume that $`G`$ has the form

$$G=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)\text{or}G=\left(\begin{array}{c}z\\ 1\end{array}\right)\left(\begin{array}{cc}\overline{z}& 1\end{array}\right),z.$$

If we let $`P=\mathrm{\Phi }(E_{11})`$, $`Q=\mathrm{\Phi }(E_{12})`$ and $`R=\mathrm{\Phi }(E_{22})`$, where $`E_{ij}`$ is the $`2\times 2`$ matrix with a $`1`$ in entry $`(i,j)`$ and zeros elsewhere, checking $`\mathrm{\Phi }(G)0`$ for all $`G`$ as above amounts to checking that $`P0`$ and

$$|z|^2P+zQ+\overline{z}Q^{}+R0,z.$$
(1)
Since $`P0`$ is automatically satisfied when (1) holds (let $`|z|\mathrm{}`$) it therefore suffices to check (1). In other words, we have the following lemma.

###### Lemma II.1

The map $`\mathrm{\Phi }:^{2\times 2}^{M\times M}`$ is positive if and only if $`P=\mathrm{\Phi }(E_{11})`$, $`Q=\mathrm{\Phi }(E_{12})`$ and $`R=\mathrm{\Phi }(E_{22})`$ satisfy (1).

We therefore need to study quadratic matrix polynomials in a complex variable.

## III Quadratic matrix polynomials in complex variables

For $`M\times M`$ matrices $`P`$, $`Q`$ and $`R`$, consider the matrix inequalities (1). As observed, (1) implies $`P0`$, and clearly it also implies $`R0`$. Our analysis is based on the observation that we can eliminate arg$`z`$ and subsequently $`|z|`$ in inequality (1). We do this as follows. Write $`z=re^{j\theta }`$ with $`r,\theta `$. Then (1) is equivalent to

$$r^2P+r(e^{j\theta }Q+e^{j\theta }Q^{})+R0,r,\theta .$$
(2)
We now use the following well-known fact. For completeness we provide a proof. Useful references on Toeplitz operators include (Gohberg et al., 1993, Chapter XXIII) and Böttcher and Silbermann (1990).

###### Lemma III.1

Given is the operator-valued trigonometric polynomial $`H(z):=z^1S^{}+T+zS`$, with $`S`$ and $`T`$ bounded linear operators on a Hilbert space $``$. Then $`H(z)0`$, $`|z|=1`$, if and only if the Toeplitz operator

$$\left(\begin{array}{ccccc}T& S^{}& 0& 0& \mathrm{}\\ S& T& S^{}& 0& \mathrm{}\\ 0& S& T& S^{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\end{array}\right)$$
(3)
is positive semidefinite.

Proof. Consider the multiplication operator $`gHg`$ on the Lebesgue space $`L_2(𝕋,)`$ of square integrable Lebesgue measurable functions on the unit circle $`𝕋`$ with values in $``$. By identifying $`L_2(𝕋,)`$ with the Hilbert space $`\mathrm{}_2(,)`$ of square summable (in norm) sequences $`(h_j)_{j=\mathrm{}}^{\mathrm{}}`$, $`h_j`$, the positive semidefiniteness of $`H(z)`$ for all $`z𝕋`$ is equivalent to the positive semidefiniteness of the doubly infinite Toeplitz matrix $`\mathrm{\Lambda }`$ with symbol $`H(z)`$ (that is, $`\mathrm{\Lambda }`$ is the doubly infinite version of (3)). As (3) is the restriction of this doubly infinite Toeplitz matrix to $`\mathrm{}_2(,)`$, positive semidefiniteness of (3) follows.

Conversely, let $`h=(h_j)_{j=\mathrm{}}^{\mathrm{}}\mathrm{}_2(,)`$ be so that $`h_j=0`$, $`jB`$. Then it follows from the positive semidefiniteness of (3) that $`\mathrm{\Lambda }h,h0`$. Since sequences $`h`$ of the above form are dense in $`\mathrm{}_2(,)`$, $`\mathrm{\Lambda }0`$ follows. But since $`H(z)`$ is the symbol of this multiplication operator $`\mathrm{\Lambda }`$, it follows that $`H(z)0`$, $`|z|=1`$. $`\mathrm{}`$

Fixing $`r`$ and applying Lemma III.1 to (2), we obtain that (2) holds for all $`\theta `$ if and only if the following infinite block Toeplitz matrix is positive semidefinite:

$$\left(\begin{array}{ccccc}R+r^2P& rQ^{}& 0& 0& \mathrm{}\\ rQ& R+r^2P& rQ^{}& 0& \mathrm{}\\ 0& rQ& R+r^2P& rQ^{}& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\end{array}\right)0,r.$$
(4)
Notice that we may write (4) as

$$r^2K+rL+N0,r,$$
(5)
where $`K`$, $`L`$ and $`N`$ are infinite self-adjoint block Toeplitz matrices. Theorem 6.7 in Rosenblum and Rovnyak (1985) states that an operator polynomial of even degree, $`2q`$ say, that is positive semidefinite for all $`r`$ allows a factorization $`T(r)T(r)^{}`$, where $`T(r)`$ is an operator polynomial of degree $`q`$. In our case we obtain that

$$r^2K+rL+N=(rT+S)(rT+S)^{}.$$

This yields that $`K=TT^{}`$, $`L=TS^{}+ST^{}`$ and $`N=SS^{}`$. Consequently, if we let $`X=TS^{}\frac{L}{2}`$ we get that $`X`$ is skew-adjoint ($`X=X^{}`$) and

$$\left(\begin{array}{cc}K& \frac{L}{2}+X\\ \frac{L}{2}+X^{}& N\end{array}\right)0.$$
(6)
Thus (5) implies the existence of $`X=X^{}`$ such that (6) holds. The converse is also valid, as

$$r^2K+rL+N=\left(\begin{array}{cc}rI& I\end{array}\right)\left(\begin{array}{cc}K& \frac{L}{2}+X\\ \frac{L}{2}X& N\end{array}\right)\left(\begin{array}{c}rI\\ I\end{array}\right).$$

Applying this to our particular choice of $`K,L`$ and $`N`$ in terms of $`P`$, $`Q`$ and $`R`$, we get that (1) holds if and only if there exists a skew-adjoint $`X=(X_{ij})_{i,j0}`$ so that

$$\left(\begin{array}{cc}\left(\begin{array}{ccc}P& 0& \mathrm{}\\ 0& P& \mathrm{}\\ \mathrm{}& & \mathrm{}\end{array}\right)& \left(\begin{array}{cccc}X_{00}& \frac{Q^{}}{2}+X_{01}& X_{02}& \mathrm{}\\ \frac{Q}{2}+X_{10}& X_{11}& \frac{Q^{}}{2}+X_{12}& \mathrm{}\\ \mathrm{}& & \mathrm{}\end{array}\right)\\ \left(\begin{array}{cccc}X_{00}^{}& \frac{Q^{}}{2}+X_{10}^{}& X_{20}^{}& \mathrm{}\\ \frac{Q}{2}+X_{01}^{}& X_{11}^{}& \frac{Q^{}}{2}+X_{21}^{}& \mathrm{}\\ \mathrm{}& & \mathrm{}\end{array}\right)& \left(\begin{array}{ccc}R& 0& \mathrm{}\\ 0& R& \mathrm{}\\ \mathrm{}& & \mathrm{}\end{array}\right)\end{array}\right)0.$$
(7)
Performing a permutation, we may rewrite (7) as

$$\mathrm{\Lambda }_0:=\left(\begin{array}{cccc}\left(\begin{array}{cc}P& X_{00}\\ X_{00}^{}& R\end{array}\right)& \left(\begin{array}{cc}0& \frac{Q^{}}{2}+X_{01}\\ \frac{Q^{}}{2}+X_{10}^{}& 0\end{array}\right)& \left(\begin{array}{cc}0& X_{02}\\ X_{20}^{}& 0\end{array}\right)& \mathrm{}\\ \left(\begin{array}{cc}0& \frac{Q}{2}+X_{10}\\ \frac{Q}{2}+X_{01}^{}& 0\end{array}\right)& \left(\begin{array}{cc}P& X_{11}\\ X_{11}^{}& R\end{array}\right)& \left(\begin{array}{cc}0& \frac{Q^{}}{2}+X_{12}\\ \frac{Q^{}}{2}+X_{21}^{}& 0\end{array}\right)& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \end{array}\right)0.$$
(8)
Next we want to show that we may in fact choose $`X_{ij}=X_{ij}`$ for all $`i`$ and $`j`$. Perhaps the quickest way to do this is by using Banach limits (for the definition, see (Conway, 1985, Section III.7)). Carrying out some of the ideas related to Banach limits directly to the current situation, we obtain the following argument. Let $`\mathrm{\Lambda }_n`$ be the infinite principal submatrix obtained from $`\mathrm{\Lambda }_0`$ by omitting the first $`n`$ block rows and columns, each of size $`2M`$. Thus $`\mathrm{\Lambda }_n`$ has $`\left(\begin{array}{cc}P& X_{nn}\\ X_{nn}^{}& R\end{array}\right)`$ in the top right corner. Of course, $`\mathrm{\Lambda }_n0`$ for all $`n`$, and the sequence $`\{\mathrm{\Lambda }_n\}_{n0}`$ is bounded (by $`\mathrm{\Lambda }_0`$). Consider now the bounded sequence $`\{\mathrm{\Xi }_n\}_{n0}`$ of averages defined via

$$\mathrm{\Xi }_n:=\frac{1}{n+1}(\mathrm{\Lambda }_0+\mathrm{}+\mathrm{\Lambda }_n)0,n_0.$$

This sequence has a convergent subsequence $`\{\mathrm{\Xi }_{n_k}\}_{k0}`$ in the weak operator topology. Notice that $`\mathrm{\Xi }_{n_k}`$ has the same form as $`\mathrm{\Lambda }_0`$; only the operators $`X_{ij}`$ are different. Therefore, its limit $`\mathrm{\Xi }_{\mathrm{}}`$, which is positive semidefinite, must have the same form as $`\mathrm{\Lambda }_0`$ as well, with $`X_{ij}`$ replaced by $`Y_{ij}`$, say. We claim that $`Y_{ij}=Y_{i+1,j+1}`$ for all $`i`$ and $`j`$. Indeed, since $`lim_k\mathrm{}\frac{X_{ij}}{n_k+1}=0`$ and $`lim_k\mathrm{}\frac{X_{i+n_k+1,j+n_k+1}}{n_k+1}=0`$, we get that

$$Y_{ij}Y_{i+1,j+1}=\underset{k\mathrm{}}{lim}\frac{X_{ij}+\mathrm{}+X_{i+n_k,j+n_k}}{n_k+1}$$

$$\underset{k\mathrm{}}{lim}\frac{X_{i+1,j+1}+\mathrm{}+X_{i+n_k+1,j+n_k+1}}{n_k+1}=$$

$$\underset{k\mathrm{}}{lim}\frac{X_{ij}}{n_k+1}\frac{X_{i+n_k+1,j+n_k+1}}{n_k+1}=0.$$

In conclusion, we have obtained that (1) holds if and only if there exist $`X_i=X_i^{}`$, $`i`$ so that

$$\left(\begin{array}{cccc}\left(\begin{array}{cc}P& X_0\\ X_0& R\end{array}\right)& \left(\begin{array}{cc}0& \frac{Q^{}}{2}+X_1\\ \frac{Q^{}}{2}X_1& 0\end{array}\right)& \left(\begin{array}{cc}0& X_2\\ X_2& 0\end{array}\right)& \mathrm{}\\ \left(\begin{array}{cc}0& \frac{Q}{2}+X_1\\ \frac{Q}{2}X_1& 0\end{array}\right)& \left(\begin{array}{cc}P& X_0\\ X_0& R\end{array}\right)& \left(\begin{array}{cc}0& \frac{Q^{}}{2}+X_1\\ \frac{Q^{}}{2}X_1& 0\end{array}\right)& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \end{array}\right)0.$$
(9)
Let us denote the principal $`(n+1)\times (n+1)`$ block submatrix of (9) by $`𝒟(X_0,\mathrm{},X_n;P,Q,R)`$. Then we obtain the following result.

###### Proposition III.2

The matrices $`P,Q`$ and $`R`$ satisfy (1) if and only if there exist $`X_i=X_i^{}`$, $`i=0,1,\mathrm{}`$ so that $`𝒟(X_0,\mathrm{},X_n;P,Q,R)0`$ for all $`n`$.

Let $`𝒞_n`$ denote the cone of all matrices $`\sigma =\left(\begin{array}{cc}P& Q\\ Q^{}& R\end{array}\right)`$ so that there exist $`X_i=X_i^{}`$, $`i=0,\mathrm{},n`$, so that $`𝒟(X_0,\mathrm{},X_n;P,Q,R)0`$. Using this notation we obtain the following.

###### Proposition III.3

The matrices $`P,Q`$ and $`R`$ satisfy (1) if and only if

$$\sigma =\left(\begin{array}{cc}P& Q\\ Q^{}& R\end{array}\right)_{n1}𝒞_n.$$

Combining Lemma II.1 and Proposition III.3 we now obtain the following description of positive maps acting $`^{2\times 2}^{M\times M}`$.

###### Proposition III.4

The map $`\mathrm{\Phi }:^{2\times 2}^{M\times M}`$ is positive if and only if

$$\left(\begin{array}{cc}\mathrm{\Phi }(E_{11})& \mathrm{\Phi }(E_{12})\\ \mathrm{\Phi }(E_{21}& \mathrm{\Phi }(E_{22})\end{array}\right)_{n1}𝒞_n.$$

Next we need duality to get back to the separability problem. We first prove the following auxiliary result.

###### Lemma III.5

The cones $`𝒜_n`$ and $`𝒞_n`$ are one another’s dual.

Proof. Let $`\rho 𝒜_n`$. In order to show that $`\rho 𝒞_n^{}`$ we need to show that trace$`(\rho \sigma )0`$ for all $`\sigma 𝒞_n`$. Thus, let $`\sigma 𝒞_n`$, and let $`X_i=X_i^{}`$, $`i=0,\mathrm{},n`$, be so that $`D:=𝒟(X_0,\mathrm{},X_n;P,Q,R)0`$. Since $`\rho 𝒜_n`$ there exists a $`\mathrm{\Gamma }𝒢(\rho ;n)`$. It is now straightforward to check that trace$`(\rho \sigma )=\text{trace}(\mathrm{\Gamma }D)`$, and since $`D`$ and $`\mathrm{\Gamma }`$ are positive semidefinite, trace$`(\rho \sigma )0`$ follows. This shows that $`𝒜_n𝒞_n^{}`$.

For the converse inclusion, observe that when $`\rho =\left(\begin{array}{cc}A& B\\ B^{}& D\end{array}\right)𝒜_n`$, then for all $`\mathrm{\Gamma }_{ij}`$ satisfying (i)-(v) we have that $`(\mathrm{\Gamma }_{ij})_{i,j=0}^n0`$. Notice that the block matrices $`(\mathrm{\Gamma }_{ij})_{i,j=0}^n`$ satisfying (i)-(v) describe a affine space, which we may denote as $`G+`$ where $`G`$ is a fixed matrix and $``$ is a linear subspace (described by all matrices satisfying (i)-(v) with $`A=D=B=0`$). This affine space $`G+`$ is separated from the cone PSD of positive semidefinites. Thus by the Hahn-Banach theorem and the selfduality of PSD there exist a positive semidefinite $`W`$ so that $`\text{trace}(W(G+L))<0`$ for all $`L`$. But then $`W^{}`$ and thus $`W`$ is of the form $`𝒟(X_0,\mathrm{},X_n;P,Q,R)`$. Let $`\sigma =\left(\begin{array}{cc}P& Q\\ Q^{}& R\end{array}\right)`$, which belongs to $`𝒞_n`$. As trace$`(\sigma \rho )=\text{trace}(WG)<0`$, it follows that $`\rho 𝒞_n^{}`$. Thus $`𝒜_n=𝒞_n^{}`$.

Since $`𝒞_n`$ is closed, $`𝒜_n^{}=𝒞_n^{}=𝒞_n`$ follows also. $`\mathrm{}`$

We are now ready to prove the main result.

Proof of Theorem I.1 By Horodecki et al. (1996) we have that the cone of $`2\times M`$ separable matrices has the dual

$$\{\left(\begin{array}{cc}\mathrm{\Phi }(E_{11})& \mathrm{\Phi }(E_{12})\\ \mathrm{\Phi }(E_{21}& \mathrm{\Phi }(E_{22})\end{array}\right):\mathrm{\Phi }:^{2\times 2}^{M\times M}\text{is positive }\},$$

which by Proposition III.4 equals $`_{n=1}^{\mathrm{}}𝒞_n`$. The cone of $`2\times M`$ separable matrices therefore equals

$$(_{n=1}^{\mathrm{}}𝒞_n)^{}=\overline{_{n=1}^{\mathrm{}}𝒞_n^{}}=\overline{_{n=1}^{\mathrm{}}𝒜_n}.$$

In the last step we used Lemma III.5. $`\mathrm{}`$

###### Acknowledgements.

The research was done while the author was visiting the Electrical Engineering department at the Katholieke Universiteit Leuven and the Department of Mathematical Engineering at Université Catholique de Louvain. The author gratefully acknowledges the hospitality of his hosts Bart de Moor (KUL) and Paul Van Dooren (UCL). The author also thanks Paul Van Dooren and Yurii Nesterov for useful discussions on the topic of quadratic matrix functions, Jeroen Dehaene for his comments on the manuscript, and the referees for their helpful comments. Finally, the research was supported by the College of William and Mary (Faculty Research Assignment grant) and NSF grant DMS 9988579.


text:
# Subclassing errors, OOP, and practically checkable rules to prevent them

## 1 Introduction

Decoupling of abstraction from implementation is one of the holy grails of good design. Object-oriented programming is claimed to be conducive to such a separation, and therefore to more reliable code. In the end, productivity and quality are the only true merits a programming methodology is to be judged upon. This article will discuss a simple example that questions if Object-Oriented Programming (OOP) indeed helps separate interface from implementation. First we demonstrate how easily subclassing errors arise and how difficult (in general, undecidable) it is to prevent them. We later introduce a set of expressive rules that preclude the subclassing errors, and can be mechanically verified. Incidentally the rules run contrary to the OOP precepts.

We take a rather familiar example that illustrates the difference between subclassing and subtyping: the example of Sets and Bags. The example is isomorphic to that of circles vs. ellipses or squares vs. rectangles. Section 2 introduces the example and carries it one step further, to a rather unsettling result: a "transparent" change in an implementation suddenly breaks client code that was written according to public interfaces. We set out to follow good software engineering practices; this makes the resulting failure even more ominous. Section 3 brings up a subclassing vs. subtyping dichotomy and the Liskov principle of behavioral substitutability. We show that Sets and Bags viewed as mutable or immutable *objects* are not subtypes of each other. The indiscriminate use of implementation inheritance indeed prevents separation of interface and implementation. In Section 4 we take a contrary point of view, of bags and sets as values without a hidden state and whose responses to external messages cannot be overridden. We prove that a set truly *is-a* bag; a set *is* substitutable for a bag, a set can always be manipulated as a bag, a set maintains every invariant of a bag – and it is still a set. The section also shows that if we abide by practically checkable rules we obtain a guarantee that the subtle subclassing errors cannot occur in principle. We will also show that the rules do not diminish the power of a language.

Inheritance and encapsulation, two staples of OOP, make checking of the Liskov Substitution Principle (LSP) for derived objects generally undecidable. On the other hand, the proposed rules, which *can* be checked at compile time, make derived values satisfy LSP.

The article aims to give a more-or-less "real" example, which we can run and see the result for ourselves. By necessity the example had to be implemented in some language. The present article uses C++. It appears however that similar code and similar conclusions can be carried on in many other object-oriented languages (e.g., Java, Python, etc).

## 2 Coupling of interface and implementation

Suppose I was given a task to implement a Bag – an unordered collection of possibly duplicate items (integers in this example). I chose the following interface:

* typedef int const * CollIterator; // Primitive but will do

class CBag {

public:

int size(void) const;

int count(const int elem) const;

virtual void put(const int elem);

virtual bool del(const int elem);

CollIterator begin(void) const;

CollIterator end(void) const;

CBag(void);

virtual CBag * clone(void) const;

private: ... // implementation details elided

};

The class CBag defines usual methods to determine the number of all elements in a bag, to count the number of occurrences of a specific element, to put a new element into a bag and to remove one. The latter function returns false if the element to delete did not exist. We also define the standard enumerator interface  – methods begin() and end() – and a method to make a copy of the bag. Other operations of the CBag package are implemented without the knowledge of CBag’s internals: the print-on operator \< \<, the union (merge) operator +=, and operators to compare CBags and to determine their structural equivalence. These functions use only the public interface of the CBag class:

* void operator += (CBag& to, const CBag& from);

bool operator \<= (const CBag& a, const CBag& b);

inline bool operator \>= (const CBag& a, const CBag& b)

{ return b \<= a; }

inline bool operator == (const CBag& a, const CBag& b)

{ return a \<= b && a \>= b; }

The complete code of the whole example is available in . It has to be stressed that the package was designed to minimize the number of functions that need to know details of CBag’s implementation. Following good practice, I wrote validation code (file vCBag.cc ) that tests all the functions and methods of the CBag package and verifies common invariants.

Suppose you are tasked with implementing a Set package. Your boss defined a set as an unordered collection where each element has a single occurrence. In fact, your boss even said that a set is a bag with no duplicates. You have found my CBag package and realized that it can be used with few additional changes. The definition of a Set as a Bag, with some constraints, made the decision to reuse the CBag code even easier.

* class CSet : public CBag {

public:

bool memberof(const int elem) const

{ return count(elem) \> 0; }

// Overriding of CBag::put

void put(const int elem)

{ if(!memberof(elem)) CBag::put(elem); }

CSet * clone(void) const

{ CSet * new\_set = new CSet();

\*new\_set += \*this; return new\_set; }

CSet(void) {}

};

The definition of a CSet makes it possible to mix CSets and CBags, as in set += bag; or bag += set; These operations are well-defined, keeping in mind that a set is a bag that happens to have the count of all members exactly one. For example, set += bag; adds all elements from a bag to a set, unless they are already present. On the other hand, bag += set; is no different than merging a bag with any other bag. You too wrote a validation suite to test all CSet methods (newly defined as well as inherited from a bag) and to verify common expected properties, e.g., a+=a $``$ a.

In my package, I have defined and implemented a function that, given three bags a, b, and c, decides if a+b is a subbag of c:

* bool foo(const CBag& a, const CBag& b, const CBag& c)

{ // Clone a to avoid clobbering it

CBag & ab = \*(a.clone());

ab += b; // ab is now the union of a and b

bool result = ab \<= c;

delete &ab;

return result;

}

It was verified in the test suite. You have tried this function on sets, and found it satisfactory.

Later on, I revisited my code and found my implementation of foo() inefficient. Memory for the ab object is unnecessarily allocated on heap. I rewrote the function as

* bool foo(const CBag& a, const CBag& b, const CBag& c)

{

CBag ab;

ab += a; // Clone a to avoid clobbering it

ab += b; // ab is now the union of a and b

bool result = ab \<= c;

return result;

}

It has exactly the same interface as the original foo(). The code hardly changed. The behavior of the new implementation is also the same – as far as I and the package CBag are concerned. Remember, I have no idea that you are re-using my package. I re-ran the validation test suite with the new foo(): everything tested fine.

However, when you run your code with the new implementation of foo(), you notice that something *has* changed! The complete source code  contains tests that make this point obvious: Commands make vCBag1 and make vCBag2 run validation tests with the first and the second implementations of foo(). Both tests complete successfully, with the identical results. Commands make vCSet1 and make vCSet2 test the CSet package. The tests – other than those of foo() – all succeed. Function foo() however yields markedly different results. It is debatable which implementation of foo() gives truer results for CSets. In any case, changing internal algorithms of a pure function foo() while keeping the same interfaces is not supposed to break your code. What happened?

What makes this problem more unsettling is that both you and I tried to do everything by the book. We wrote a safe, typechecked code. We eschewed casts. g++ (2.95.2) compiler with flags -W and -Wall issued not a single warning. Normally these flags cause g++ to become very annoying. You did not try to override methods of CBag to deliberately break the CBag package. You attempted to preserve CBag’s invariants (weakening a few as needed). Real-life classes usually have far more obscure algebraic properties. We both wrote validation tests for our implementations of a CBag and a CSet, and they passed. And yet, despite all my efforts to separate interface and implementation, I failed. Should a programming language or the methodology take at least a part of the blame?

## 3 Subtyping vs. Subclassing

The breach of separation between CBag’s implementation and interface is caused by CSet design’s violating the Liskov Substitution Principle (LSP) . CSet has been declared a subclass of CBag. Therefore, C++ compiler’s typechecker permits passing a CSet object or a CSet reference to a function that expects a CBag object or reference. However, it is well known  that a CSet is not a *subtype* of a CBag. The next few paragraphs give a simple proof of this fact, for the sake of reference.

The previous section considered bags and sets from the OOP perspective – as objects that encapsulate state and behavior. Behavior means an object can accept a message, send a reply and possibly change its state. From this point of view, bags and sets are not subtypes of each other. Indeed, let us define a Bag as an object that accepts two messages: (send a-Bag ’put x) puts an element x into the Bag, and (send a-Bag ’count x) gives the occurrence count for x in the Bag (without changing a-Bag’s state). Likewise, a Set is defined as an object that accepts two messages: (send a-Set ’put x) puts an element x into a-Set unless it was already there, (send a-Set ’count x) gives the count of occurrences of x in a-Set (which is always either 0 or 1). Throughout this section we use a different, concise notation to emphasize the general nature of the argument.

Let us consider a function

* (define (fnb bag) (send bag ’put 5) (send bag ’put 5) (send bag ’count 5))

The behavior of this function, its contract, can be summed as follows: given a Bag, the function adds two elements into it and returns (+ 2 (send orig-bag ’count 5)). Technically you can pass to fnb a Set object as well. Just as a Bag, a Set object accepts messages ’put and ’count. However applying fnb to a Set object will break the function’s post-condition stated above. Therefore, passing a set object where a bag was expected changes the behavior of a program. According to the LSP, a Set is not substitutable for a Bag – a Set cannot be a subtype of a Bag.

Let us consider another function

* (define (fns set) (send set ’put 5) (send set ’count 5))

The behavior of this function is: given a Set, the function adds an element into it and returns 1. If you pass to this function a bag (which – just as a set – replies to messages ’put and ’count), the function fns may return a number greater than 1. This will break fns’s contract, which promised always to return 1.

One may claim that "A Set is not a Bag, but an ImmutableSet is an ImmutableBag." This is not correct either. An immutability per se does not confer subtyping to "derived" classes of data, as a variation of the previous argument shows . C++ objects are record-based. Subclassing is a way of extending records, with possibly altering some slots in the parent record. Those slots must be designated as modifiable by a keyword virtual. In this context, prohibiting mutation and overriding makes subclassing imply subtyping. This is the reasoning behind BRules introduced below. However merely declaring the state of an object immutable is not enough to guarantee that derivation leads to subtyping: An object can override parent’s behavior without altering the parent. This is easy to do when an object is implemented as a functional closure, when a handler for an incoming message is located with the help of some kind of reflexive facilities, or in prototype-based OO systems . Incidently, if we do permit a derived object to alter its base object, we implicitly allow behavior overriding. For example, an object A can react to a message M by forwarding the message to an object B stored in A’s slot. If an object C derived from A alters that slot it hence overrides A’s behavior with respect to M.

The OOP point of view thus leads to a conclusion that neither a Bag nor a Set are subtypes of the other. The interface or an implementation of a Bag and a Set appear to invite subclassing of a Set from a Bag, or vice versa. Doing so however will violate the LSP – and we have to brace for strikingly subtle errors. The previous section intentionally broke the LSP to demonstrate how insidious the errors are and how difficult it may be to find them. Sets and Bags are very simple types, far simpler than the ones that typically appear in a production code. Since LSP when considered from an OOP point of view is undecidable, we cannot count on a compiler for help in pointing out an error. As Section 2 showed, we cannot rely on validation tests either. We have to *see* the problem .

## 4 Mechanically preventing subclassing errors

Bags and sets – as objects – indeed are not subtypes. Subclassing them violates LSP, which leads to insidious errors. Bags and sets however do not have to be viewed as objects. We can take them as pure values, without any state or intrinsic behavior – just like the numbers are. In Section 2, CBag and CSet objects encapsulated a hidden state – a collection of integers. The objects had an ability to react to messages, e.g., put and del, by altering their state. In this section we re-do the example of Section 2 using a different approach. Bags and sets no longer have a state that is distinct from their identity and that can be altered. Equally important we do not allow any changes to the behavior of bags and sets with respect to applicable operations, by overriding or otherwise. In other words, every post-condition of a bag or a set constructor holds throughout the lifespan of the constructed values. This approach makes the subclassing problems and breach of encapsulation disappear. It turns out that a set truly *is-a* bag; a set is substitutable for a bag, a set can always be manipulated as a bag, a set maintains every invariant of a bag – and it is still a set.

The LSP says, “If for each object o1 of type S there is another object o2 of type T such that for all programs P defined in terms of T, the behavior of P is unchanged when o1 is substituted for o2, then S is a subtype of T.” If type T denotes a set of values that carry their own behavior, and if values of type S can override some of T values behavior, the LSP is undecidable. Indeed, a mechanical application of LSP must at least be able to verify that all methods overridden in S terminate whenever the corresponding methods in T terminate. This is generally impossible. On the other hand, if T denotes a set of (structured) data values, and S is a subset of these values – e.g., restricted by range, parity, etc. – the LSP is trivially satisfied.

This section also shows that if one abides by mechanically verifiable rules he obtains a guarantee that the subtle subclassing errors cannot occur in principle. The rules do not reduce the power of a language.

### 4.1 BRules

Suppose I was given a task to implement a Bag – an unordered collection of possibly duplicate items (integers in this example). This time my boss laid out the rules, which we will refer to as *BRules*:

* no virtual methods or virtual inheritance
* no visible members or methods in any public data structure (that is, in any class declared in an .h file)
* no mutations to public data structures

+ a strict form: no assignments or mutations whatsoever
    + a less strict form: no function may alter, directly or indirectly, any data it receives as arguments

The rules break the major tenets of OOP: for example, values no longer have a state that is separate from their identity. Prohibitions on virtual methods and on modifications of public objects are severe. It appears that not much of C++ is left. Surprisingly I still can implement my assignment without losing expressiveness – and perhaps even gaining some. The exercise will also illustrate that C++ does indeed have a pure functional subset , and that you can program in C++ without assignments.

### 4.2 Interface and implementation of a FBag

* class FBag {

public:

FBag(void);

FBag(const FBag& another); // Copy-constructor

~FBag(void);

private:

class Cell; // Opaque type

const Cell * const head;

FBag(const Cell * const cell); // Private constructor

// Declaration of three friends elided

};

Indeed, there are no virtual functions, no methods or public members. We also declare functions that take a FBag as (one of the) arguments and return the count of all elements or a specific element in the bag, print the bag, $`fold`$  over the bag, compare two bags for structural equivalence, verify bag’s invariants, merge two bags, add or delete an element. The latter three functions do not modify their arguments; they return a new FBag as their result. It must be stressed that the functions that operate on a FBag are not FBag’s methods; in particular, they are not a part of the class FBag, they are not inherited and they cannot be overridden. The implementation is also written in a functional style. FBag’s elements are held in a linked list of cells, which are allocated from a pre-defined pool. The pool implements a mark-and-sweep garbage collection, in C++.

Forgoing assignments does not reduce expressiveness as the following snippet from the FBag code shows; the snippet implements the union of two FBags:

* struct union\_f {

FBag operator() (const int elem, const FBag seed) const {

return put(seed,elem);

}

};

FBag operator + (const FBag& bag1, const FBag& bag2)

{

return fold(bag1,union\_f(),bag2);

}

Following good practice, I wrote a validation code (file vFBag.cc ) that tests all the functions of the FBag package and verifies common invariants.

### 4.3 Implementation of a FSet. FSet is a subtype of a FBag

Suppose you are tasked with implementing a Set package. Your boss defined a set as an unordered collection where each element has a single occurrence. In fact, your boss even said that a set is a bag with no duplicates. You have found my FBag package and realized that it can be used with few additional changes. The definition of a Set as a Bag (with some constraints) made the decision to reuse the FBag code even easier.

* class FSet : public FBag {

public:

FSet(void) {}

FSet(const FBag& bag) : FBag(remove\_duplicates(bag)) {}

};

bool memberof(const FSet& set, const int elem)

{ return count(set,elem) \> 0; }

Surprisingly, this is the *whole* implementation of a FSet. A set is fully a bag. Because FSet constructors eventually call FBag constructors and do no alter the latter’s result, every post-condition of a FSet constructor implies a post-condition of a FBag constructor. Since FBag and FSet values are immutable, the post-conditions that hold at their birth remain true through their lifespan. Because all FSet values are created by an FBag constructor, all FBag operations automatically apply to an FSet value. This concludes the proof that an FSet is a *subtype* of a FBag.

The FBag.cc package  has a function verify(const FBag&) that checks to make sure its argument is indeed a bag. The function tests FBag’s invariants, for example:

* const FBag bagnew = put(put(bag,5),5);

assert( count(bagnew,5) == 2 + count(bag,5) &&

size(bagnew) == 2 + size(bag) );

assert( count(del(bagnew,5),5) == 1 + count(bag,5) );

Your validation code passes a non-empty set to this function to verify the set is indeed a bag. You can run the validation code vFSet.cc  to see for yourself that the test passes. On the other hand, FSets do behave like Sets:

* const FSet a112 = put(put(put(FSet(),1),1),2);

assert( count(a112,1) == 1 );

const FSet donce = FSet() + a112;

const FSet dtwice = donce + a112;

assert( dtwice == a112 );

where a112 is a non-empty set. The validation code vFSet.cc you wrote contains many more tests like the above. The code shows that a FSet is able to pass all of FBag’s tests as well as its own. The implementation of FSets makes it possible to take a union of a set and a bag; the result is always a bag, which can be made a set if desired. There are corresponding test cases as well.

To clarify how an FSet may be an FBag at the same time, let us consider one example in more detail:

* // An illustration that an FSet is an FBag

int cntb(const FBag v) {

FBag b1 = put(v, 5); FBag b2 = put(b1, 5);

FBag b3 = del(b2, 5);

return count(b3, 5); }

const int cb1 = cntb(FBag()); // cb1 has the value of 1

const int cb2 = cntb(FSet()); // cb2 has the value of 1

// An illustration that an FSet does act as a set

int cnts(const FSet v) {

FSet s1 = put(v, 5); FSet s2 = put(s1, 5);

FSet s3 = del(s2, 5);

return count(s3, 5); }

const int cs = cnts(FSet()); // cs has the value of 0

This example is one of the test cases in vFSet.cc . You can run it and check the results for yourself. Yet it is puzzling: how come cs has the value different from that of cb1 if there is no custom del() function for FSets? The statement FSet s2 = put(s1, 5); is the most illuminating. On the right-hand side is an expression: putting an element 5 to a FBag/FSet that already has this element in it. The result of that expression is a FBag {5,5}, with two instances of element 5. The statement then constructs a FSet s2 from that bag. A FSet constructor is invoked. The constructor takes the bag {5,5}, removes the duplicate element 5 from it, and "blesses" the resulting FBag to be a FSet as well. Thus s2 will be a FBag and a FSet, with one instance of element 5. In fact, s1 and s2 are identical. A FSet constructor guarantees that a FBag it constructs contains no duplicates. As objects are immutable, this invariant holds forever.

### 4.4 Discussion

Surprising as it may be, assertions "a Set is a Bag with no duplicates" and "a Set always acts as a Bag" do not contradict each other, as the following two examples illustrate:

It has to be stressed that the two columns of the above table are not merely similar: they are isomorphic. Indeed, the right column is derived from the left column by the following substitution of words that preserves meaning: Bag $``$ integer, Set $``$ uf-integer, merge $``$ multiply, subtract $``$ reduce. The right column sounds more "natural" – so should the left column as integers and uf-integers are representations for resp. FBags and FSets.

From an extensional point of view , a type denotes a set of values. By definition of a FSet, it is a particular kind of FBag. Therefore, a set of all FSets is a subset of all FBags: FSet is a subtype of FBag. A FBag or a FSet do not have any "embedded" behavior – just as integers do not have an embedded behavior. Behavior of numbers is defined by operations, mapping from numbers to numbers. Any function that claims to accept every member of a set of values identified by a type T will also accept any value in a subset of T. Frequently a value can participate in several sets of operations: a value can have several types at the same time. For example, a collection { 42 } is both a Bag and a Set. This fact should not be surprising. In C++, a value typically denoted by a numeral 0 can be considered to have a character type, an integer type, a float type, a complex number type, or a pointer type, for any declared or yet to be declared pointer type. This lack of behavior is what puts FBag and FSet apart from CBag and CSet discussed in the previous article. FSet is indeed a subtype of FBag, while CSet is not a subtype of a CBag as CSet has a different behavior. Incidentally LSP is trivially satisfied for values that do not carry their own behavior. FBags and FSets are close to so-called predicate classes. Since instances of FSets are immutable, the predicate needs to be checked only at a value construction time.

### 4.5 Polymorphic programming with BRules

The FSet/FBag example above showed BRules in the context of subtypes formed by a restriction on a base type. As it turns out, BRules work equally well with existential (abstract) types. To illustrate this point, the source code accompanying this article  contains three implementations of a collection of polymorphic values. The collection is populated by Rectangles and Ellipses, which are instances of concrete classes implementing a common abstract base class Shape. A Shape is an existential type that knows how to draw, move and resize itself. A file Shapes-oop.cc gives the conventional, OOP-like implementation, with virtual functions and such. A file Shapes-no-oop.cc is another implementation, also in C++. The latter follows BRules, has no assignments or virtual functions. Any particular Shape value is created by a Shape constructor and is not altered after that. Shapes-no-oop.cc achieves polymorphic programming with the full separation of interface and implementation: If an implementation of a concrete Shape is changed, the code that constructs and uses Shapes does not even have to be recompiled! The file defines two concrete instances of the Shape: a Square and a Rectangle. The absence of mutations and virtual functions guarantees that any post-condition of a Square or a Rectangle constructor implies the post-condition of a Shape. Both particular shapes can be passed to a function set\_dim(const Shape& shape, const float width, const float height); Depending on the new dimensions, a square can *become* a rectangle or a rectangle square. You can compile Shapes-no-oop.cc and run it to see that fact for yourself.

It is instructive to compare Shapes-no-oop.cc with Shapes-h.hs, which implements the same problem in a purely functional, strongly-typed language Haskell. All three code files in the Shapes directory solve the same problem the same way. Two C++ code files – Shapes-oop.cc and Shapes-no-oop.cc – look rather different. On the other hand, the purely functional Shapes-no-oop.cc and the Haskell code Shapes-h.hs are uncanny similar – in some places, frighteningly similar. This exercise shows that BRules do not constrain the power of a language even when abstract data types are involved.

## 5 Conclusions

It is known, albeit not so well, that following the OOP letter and practice may lead to insidious errors . Section 2 of this article showed how subtle the errors can be even in simple cases. In theory, there are rules – LSP – that could prevent the errors. Alas, the rules are in general undecidable and not *practically reinforceable*.

In contrast, BRules introduced in this article can be statically checked at compile time. The rules outlaw certain syntactic constructions (for example, assignments in some contexts, and non-private methods) and keywords (e.g., virtual). It is quite straightforward to write a lint-like application that scans source code files and reports if they conform to the rules. When BRules are in effect, subtle subclassing errors like the ones shown in Section 2 become impossible. To be more precise, with BRules, *subclassing implies subtyping*. Subclassing by definition is a way of creating (derived) values by extending, restricting, or otherwise specializing other, parent values. A derived value constructor must invoke a parent value constructor to produce the parent value. The former constructor often has a chance to alter the parent constructor’s result before it is cast or incorporated into the derived value. If this chance is taken away, the post-condition of a derived value constructor implies the post-condition of the parent value. Disallowing any further mutations guarantees the behavioral substitutability of derived values for parent values at all times.

As the examples in this article showed, following BRules does not diminish the power of the language. We can still benefit from polymorphism, we can still develop practically relevant code. Yet BRules blur the distinction between the identity and the state, a characteristic of objects. BRules are at odds with the practice if not the very mentality of OOP. This begs the question: Is OOP indeed conducive to software development?

One can argue that OOP – as every powerful technique – requires extreme care: knives are sharp. Likewise, goto is expressive, and assembler- or microcode-level programming are very efficient. All of them can lead to bugs that are very difficult, statically impossible, to find. On the other hand, if you program, for example, in Scheme, you never have to deal with an "invalid opcode" exception. That error becomes simply impossible. Furthermore, “while opinions concerning the benefits of OOSD \[Object-Oriented Software Development\] abound in OO literature, there is little empirical proof of its superiority” .

#### Acknowledgments

I am grateful to Valdis Berzins for valuable discussions and suggestions on improving the presentation. This work has been supported in part by the National Research Council Research Associateship Program, Naval Postgraduate School, and the Army Research Office under contracts 38690-MA and 40473-MA-SP.


text:
# Spin-polarized electron injection through an Fe/InAs junction

## Abstract

We report on the spin-polarized electron injection through an Fe(100)/InAs(100) junction. The circularly polarized electroluminescence of injected electrons from epitaxially grown Fe thin film into InAs(100) in an external magnetic field is measured to investigate the spin injection efficiency. The obtained polarization of the electroluminescence is seen to increase up to about -12 % at the temperature of 6.5 K and the external magnetic field of 10 T. This result suggests that the efficient spin injection is possible through the ferromagnetic metal/semiconductor (FM/SC) interface without a tunneling barrier despite the contradictory arguments based on conductivity mismatch at the FM/SC interface.

Spin-polarized electron injection (spin injection) into semiconductor is indispensable to realize spin-related devices, such as spin transistors.1  Several candidates were proposed as a spin-polarized current source, e.g., ferromagnetic metals (FM),2 ; 3 ; 4 ; 5  diluted magnetic semiconductors (DMS),6 ; 7 ; 8  and half-metallic ferromagnetic metals.9  At first, the spin injection into semiconductors were demonstrated using DMS such as BexMnyZn1-x-ySe6  and (Ga,Mn)As.7 ; 8  However, the difficulty of room temperature operation of the device remained unsolved because of their low Curie temperatures. In addition, the BexMnyZn1-x-ySe spin aligner required a large external magnetic field. On the other hand, ferromagnetic metal/semiconductor (FM/SC) hybrid structures are supposed to be promising to realize high efficient spin injection even at room temperature and without any external magnetic field. Despite great efforts, the spin injection in the FM/SC hybrid structure remained a challenging task for a long time. Furthermore, there appeared theoretical predictions that spin injection in the FM/SC hybrid structure in the diffusive regime is hardly possible due to a large conductivity mismatch between a ferromagnetic metal and a semiconductor.10 ; 11  Recently, spin injections in FM/GaAs hybrid structures with a Schottky tunneling barrier were demonstrated.2 ; 3 ; 4 ; 5  Theoretically, the interfacial resistance, e.g., due to a tunneling barrier would be expected to enhance the spin injection efficiency.12 ; 13 ; 14  However, it is not still clear that the tunneling barrier is indeed necessary for spin injection. Yu et al.15 ; 16  pointed out that an electric-field enhances the spin injection efficiency in FM/SC hybrid structures even in the diffusive regime. Recent theoretical calculations of spin injection in the ballistic regime predict highly efficient spin injection at the FM/SC interface.17 ; 18 ; 19

In this paper, we demonstrate the spin injection through an Fe(100)/p-InAs(100) junction without a tunneling barrier. InAs has a significant advantage over GaAs for spin-related device applications, because of the following reasons: (1) InAs is expected to form an ideal ohmic contact to metal,20 ; 21  (2) a significant spin-orbit interaction is expected in an InAs 2DEG channel22 ; 23  compared with GaAs. We have confirmed that the epitaxial Fe(100) thin film can be grown on the InAs(100) at the low growth temperature of 23 C, which is expected to reduce the inter-diffusion at the interface, and the Fe/n-InAs junction showed a good ohmic behavior.21  Measurements of circularly polarized electroluminescence (EL) in Fe/p-InAs junctions were performed in order to investigate the electron injection and their spin states. The spin polarization of injected electrons was estimated from the degree of circular polarization of the luminescent light.

The Fe/p-InAs junction for the EL measurements was prepared in the following procedure. Prior to Fe deposition, 300nm-thick SiO2 island was formed for the non-magnetic bonding pad formation in the final step of the device preparation. In an ultra high vacuum (UHV) chamber, the InAs substrate was annealed at about 450 C without arsenic flux irradiation for thermal cleaning. Fe was deposited on the InAs substrate by an electron-beam evaporator with the substrate temperature of 23 C. After the Fe growth, the sample was taken out of the chamber to be subjected to the patterning process. The Fe thin film was patterned into an array of wires (pitch; $`p=`$4 $`\mu `$m, width; $`w=`$2 $`\mu `$m) whose axes were taken along the $`011`$ direction. Finally, a Au/Ti electrode pad was fabricated on the SiO2 island region. The effective contact area of the sample is approximately 0.5$`\times `$3 mm2. The cross-sectional schematic sample structure of the Fe/p-InAs junction is shown in Fig. 1. Note that the external magnetic field was applied perpendicular to the surface, and the luminescence was detected in the upper direction perpendicular to the surface and parallel to the external magnetic field.

The sample was mounted in a continuous flow He cryostat with a superconducting magnet and cooled down for the EL measurements. The luminescence was detected from the top of the sample surface by an InSb infrared detector. The right ($`\sigma ^+`$) and left ($`\sigma ^{}`$) circularly polarized components of the luminescence are analyzed using a first-order quarter waveplate and a polarizer. The degree of circular polarization of the luminescence $`P_L`$ is determined by $`P_L=(\sigma ^+\sigma ^{})/(\sigma ^++\sigma ^{})`$.

The spin polarization $`P_s`$ of injected electrons can be estimated from the circular polarization $`P_L`$ of the luminescence due to the optical selection rule in zincblende compound semiconductors.24  In a condition of constant carrier generation, such as constant bias voltage, $`P_L`$ is given by

$$P_L=\frac{1}{2}\frac{1}{(1+2\tau _{rec}/\tau _s)}P_s,$$

where $`\tau _{rec}`$ and $`\tau _s`$ are a recombination time and a spin relaxation time of electrons, respectively. Note that the polarization of the luminescence is reduced from the spin polarization of electrons by the factor $`\tau _{rec}/\tau _s`$. However, limited report is known for the carrier dynamics and the spin dynamics in bulk InAs so far. To the best of our knowledge, the spin relaxation in bulk InAs was reported only by Boggess et al.25 . According to their result, $`\tau _{rec}`$ and $`\tau _s`$ at 300 K are $``$ 1 ps and $``$ 20 ps, respectively. If we assume the relationship $`\tau _{rec}\tau _s`$ to hold even at low temperatures, the factor of $`1/(1+2\tau _{rec}/\tau _s)`$ becomes almost negligible. In that case, we obtain a simple factor of $`2`$ (i.e. $`P_s=2P_L`$). In general, temperature dependence of the $`P_L`$ would be expected by the temperature dependence of these time constants. It is to be added that the discussion above assumes that the heavy hole and light hole bands are degenerate.

The clear EL from the Fe/InAs hybrid structure was observed above the bias voltage of 300 mV. It was verified that the peak of the EL spectrum was about 3.08 $`\mu `$m (i.e. 0.403 eV), suggesting that the luminescence is caused by transitions between the conduction band and the valence band/the acceptor level in the p-InAs substrate. There was no threshold voltage difference in luminescence and current. Present result implies that injected electrons into the conduction band of InAs readily recombine with holes in the InAs substrate in the vicinity of the interface. The low ohmic resistance for electrons and the low bias operation of the Fe/InAs hybrid structure, which arise from the surface pinning level of InAs is located at 50 $``$ 100 meV above the conduction band,26 ; 27  are great advantages for electron injection into semiconductors. The detected luminescence is likely to come from the gap of the Fe wires because no luminescence was observed in a control sample which is completely covered with the Fe film.

For polarization measurements, the $`\sigma ^+`$ and $`\sigma ^{}`$ components of the luminescence were obtained by switching the angle of the quarter waveplate. Figure 2 shows the external magnetic field dependence of the $`P_L`$ from the Fe/p-InAs hybrid structure at T = 6.5, 50 and 70 K. The polarization was observed to increase up to about -12 % at B = 10 T. However, below B = 1 T, the polarization showed clear sign flip by $``$ 0.5 %. For higher temperatures (T = 50 or 70 K), the polarization showed obviously the positive value of about 7 % at B = 4 T. The temperature dependence of the $`P_L`$ at B = 6 T is shown in Fig. 3. As the temperature increases, the polarization decreases rapidly, and the polarity of the polarization is reversed from negative to positive. At about T = 80 K, the polarization seems to saturate or begin to reduce again. These complicated behaviors seem to be caused by two competing mechanisms. The positive dependence is probably due to the large Zeeman splitting in the conduction band of InAs.28  The negative dependence behavior, on the other hand, probably arises from the increase of majority spins in the Fe spin-injector as the magnetization proceeds. It should be mentioned that we have obtained preliminary results of non-magnetic sample showing similar behavior as high temperature (70 K) results.

Although the out-of-plane magnetization of Fe films are usually saturated at about B = 2 T, the measured $`P_L`$ does not follow the magnetization curve unlike the case of the Fe/GaAs systems.2  In the case of the Fe/InAs systems, the polarization of injected electrons is influenced by both the spin polarization of Fe and the spin splitting of the conduction band in InAs induced by the Zeeman effect. In addition to this, the heavy hole and the light hole valence bands also split by the external magnetic field. Therefore the $`P_L`$ would not necessarily follow the magnetization curve and show more complicated behavior. In addition to the spin polarization in Fe and the Zeeman spin splitting in InAs described above, there may be other effects which yield the circular polarization such as the magneto-optical effect of the Fe films and the effect of the fringe magnetic field around the Fe wires. The magneto-optical effect can be excluded in our experimental set-up (Fig 1) because the luminescent light barely penetrates through an Fe thin film. The fringe magnetic field is antiparallel to the external magnetic field near the center of the gap where most of the measurable recombination takes place, so that the total magnetic field in this region is always smaller than the external magnetic field.29  Furthermore, the effect of fringe magnetic field, which exhibits a weak temperature dependence in this temperature range, can not account for the temperature dependence of the $`P_L`$ shown in Fig. 3. Therefore we conclude that the $`P_L`$ data shown in Fig. 2 reflect the spin polarization of Fe spin-injector as well as the Zeeman effect in the InAs. Please note that the Zeeman effect acts oppositely against majority spin injection effect on $`P_L`$. The temperature dependence of the $`P_L`$ in the range between 6.5 K and 80 K shown in Fig 3 indicates that the negative dependence gradually disappears with increasing temperature. This is presumably caused by the decrease of $`\tau _s`$ and subsequent increase of $`\tau _{rec}/\tau _s`$ with increasing temperature

We conclude that the injection of majority spins dominates in the present Fe/InAs hybrid structure by taking into account the polarity of the polarization. This is in good agreement with the theoretical result calculated from first-principles by Zwierzycki et al.19 , but contrary to the spin injection in the FM/GaAs hybrid structure with the tunneling barrier, in which the minority spin makes dominant contribution.2 ; 3 ; 5

In conclusion, we have demonstrated that the spin-polarized electron injection through the Fe(100)/p-InAs(100) junction. The circular polarization of about -12 % at T =6.5 K and B = 10 T, implies that spin-polarized electrons are successfully injected from Fe into InAs, which reflect the spin polarization of Fe, even though the large Zeeman splitting in InAs also influences the polarization of the luminescence. This result is encouraging for future applications of FM/InAs hybrid structures or InAs-based heterostructures to spin-related devices.

We would like to thank to Prof. K. H. Ploog of Paul-Drude-Institut für Festkörperelektronik for helpful discussions. This work is partly supported by Grant-in-Aid for Scientific Research from the Japanese Ministry of Education, Culture, Sports, Science and Technology.