text:
# Forbidden Information

## 1 Introduction.

D.Hilbert asked if Peano Arithmetic (PA: consisting of logic and algebraic axioms and an infinite family of Induction Axioms) can be consistently extended to a complete theory. The question was somewhat vague since an obvious answer was “yes”: just add to PA axioms a maximal consistent set, clearly existing albeit hard to find.111I assume PA is consistent: a separate can of worms. K.Gödel formalized this question as existence, among such extensions, of recursively enumerable (r.e.) ones and gave it a negative answer. Its mathematical essence is the absence of total recursive extensions of universal partial recursive predicates (p.r.p.). This negative answer apparently was never accepted by Hilbert, and Gödel himself had reservations:

> “Namely, it turns out that in the systematic establishment of the axioms of mathematics, new axioms, which do not follow by formal logic from those previously established, again and again become evident. It is not at all excluded by the negative results mentioned earlier that nevertheless every clearly posed mathematical yes-or-no question is solvable in this way. For it is just this becoming evident of more and more new axioms on the basis of the meaning of the primitive notions that a machine cannot imitate.” \[Gödel 61\]

As is well known, \[Barzdin 69, Jockusch, Soare 72\], the absence of algorithmic solutions is no obstacle when the task does not make a solution unique.222Note that no such problems arise for the less dramatic version of Gödel Theorem which makes the completion unique by requiring (unfalsifiable, thus too abstract for Hilbert’s program) $`\omega `$-consistency, i.e., that $`xA(x)`$ cannot be proven if $`A(x)`$ is refutable for each specific constant $`x`$. A notable example is generating strings of linear Kolmogorov complexity, e.g., those that cannot be compressed to half their length. Algorithms fail, but a set of dice does a perfect job! Thus, while r.e. sets of axioms cannot complete PA, completion by other realistic means remained an open possibility: one can so construct an r.e. theory $`R`$ that, like PA, allows no consistent completion with r.e. axiom sets. Yet, $`R`$ allows a recursive set of pairs of axioms such that random choice of one in each pair assures such completion with probability 99%. This cannot be done for PA itself. In fact, \[Stephan 06\] shows that any Martin-Löf random sequence that computes (i.e. allows computing from it) a consistent completion of PA also computes the Halting Problem $`H`$; and by \[dLMSS 56\], only a recursive sequence (which $`H`$ is not) can be computed with a positive probability by randomized algorithms.

Of course, Gödel did not envision Math axioms to be chosen at random :-).
But for arbitrary, not random, PA completions the reduction arguments do not work: only a recursive predicate can be computed from all consistent completions of PA.

However, the impossibility of a task can be formulated more generically. \[Kolmogorov 65\] defined a concept of mutual information in two finite strings. It can be refined and extended to infinite sequences, so that it satisfies conservation inequalities: cannot be increased by deterministic algorithms or in random processes or with any combinations of both. In fact, it seems reasonable to assume that no physically realizable process can increase information about a specific sequence.

In this framework one can ask if non-mechanical means could really enable the Hilbert-Gödel task of consistent completion for PA (as they can for the artificial system $`R`$ just mentioned). A negative answer follows from the existence of a specific sequence $`\rho `$ that has infinite mutual information with each total extension of a universal p.r.p. $`\rho `$ plays a role of a password: no substantial information about it can be guessed, no matter what methods are allowed.

Note that invoking Gödel’s name, does not mean my intent to consider widely discussed complexity aspects and implications of incompleteness theorem. In particular, I ignore complexity of completions of PA. Much of this was considered in the 60-s,333The original publications, such as \[Barzdin 68\], gave the technical cores of the results and avoided discussion of straightforward implications for formal theories, Gödel Theorem, etc. These implications were discussed in talks, e.g., mentioned in \[Kolmogorov 72\] with some technical references. Also, extensive discussions were subsequently made by G. Chaitin. I omit details, since these results are only superficially related to the issues I address here. but does not answer our question: are such completions really possible? Strings of any complexity are easy to generate.

There are other interesting situations with a similar gap between the proven result and its usual interpretation. Let me mention tiling, a cute task studied in many areas of CS, Math, Physics, etc. A tile is a unit size square with colored edges. A palette is a finite set of tiles with copies of which one can tile the plane so that adjacent edges match in colors. Classical papers by Berger, Meyers, and others constructed palettes $`P`$ that can tile an infinite plane, but only non-recursively, which is typically interpreted as an impossibility of tiling. There, any program $`t:\text{ I}\text{N}^2P`$ can tile only finitely many frames $`F=\{(i,j):\mathrm{max}(|i|,|j|)=n\}`$, $`F\stackrel{\text{df}}{=}n`$ so that $`t|_F`$ appear on $`P`$-tiled planes. \[Durand, Levin, Shen 01\] pushes these results to the limit, with a $`P`$ for which $`F<t`$.

Such palettes, thus, only allow tilings with frames of linear complexity. This stronger result, though, makes the standard interpretation suspicious: may these frames be just random, thus easy to generate with dice? Or could more sophisticated and yet realistic means work?
For some palettes this is, indeed, the case, but not for all. Like all co-r.e. sets, the set of planar tilings with any given palette has members with information about any specific sequence growing with radius $`n`$ as slowly as $`\mathrm{log}n`$. Still, this bound cannot be improved for some palettes.

The same holds for complete extensions of universal p.r.p. and formal systems. Thus, Gödel Theorem is not really misleading. The proof of this (much trickier than Gödel’s) is the main point of this article. The interpretation of these results relies on Independence Postulate — an extended form of Church-Turing Thesis discussed in the last section. It is much stronger and can be applied where CT cannot. Other examples are results of \[L 16\] or older ones in \[L 84\].

## 2 Complexity Tools.

#### Informal Overview.

A universal measure m is a largest up to a constant factor enumerable by algorithms probability distribution. Its entropy ($`\mathrm{log}`$ of probability) is Kolmogorov Complexity K; it is also the least length of programs generating $`x`$. Rarity $`\text{d}(x|\mu )`$ of $`x`$ for a measure $`\mu `$ is $`\mathrm{log}\mu (x)`$ minus complexity of $`x`$, i.e., the difference between entropies of $`\mu `$ and m for $`x`$. Mutual information in $`x,y`$ is $`\text{K}(x)+\text{K}(y)\text{K}(x,y)`$: it allows to encode $`x,y`$ together with fewer bits than separately. It is also their non-independence: rarity for distribution $`\text{m}(x)\text{m}(y)`$ (universal on each, but independent on the pair). It satisfies conservation inequalities: cannot be increased in processing $`x`$, by deterministic algorithms, random transformations, any their combinations, etc.

#### Conventions.

Let $``$,  IQ,  IN, $`B=\{0,1\}`$, $`S=B^{}`$, $`\mathrm{\Omega }=B^{\text{ I}\text{N}}`$ be, respectively, the sets of non-negative reals, rationals, integers, bits, finite, and infinite binary sequences; $`x_{[n]}`$ is the $`n`$-bit prefix and $`x`$ is the bit-length of $`xS`$. A real function $`f`$ and its values are enumerable or r.e. ($`f`$ is co-r.e. ) if its subgraph $`\{(x,q):f(x)>q\text{ I}\text{Q}\}`$ is. Elementary ($`f`$) are functions $`f:\mathrm{\Omega }\text{ I}\text{Q}`$ depending on a finite number of digits. $`[A]\stackrel{\text{df}}{=}1`$ if a statement $`A`$ holds, else $`[A]\stackrel{\text{df}}{=}0`$. I identify objects (e.g., integers) with their binary encodings; $`xS`$ with $``$ functions $`\omega [x=\omega _{[n]}]`$ for $`n=x`$, etc. Majorant is an r.e.  function largest, up to a constant factor, among r.e. functions in its class. $`f`$, $`f`$, and $`f`$ denote $`<f+O(1)`$, $`>fO(1)`$, $`=f\pm O(1)`$, respectively.

### 2.1 Integers: Complexity, Randomness.

Let us define Kolmogorov complexity $`\text{K}(x)`$ as $`1\mathrm{log}\text{m}(x)`$ where $`\text{m}:\text{ I}\text{N}`$ is the universal measure, i.e., a majorant r.e. function with $`_x\text{m}(x)1`$. It was introduced in \[ZL 70\], and noted in \[L 73, L 74, Gacs 74\] to be a modification (restriction to self-delimiting codes) of the least length of binary programs for $`x`$ defined in \[Kolmogorov 65\]. While technically different, m relies on intuition similar to that of \[Solomonoff 64\]. The proof of the existence of the largest function was a straightforward modification of proofs in \[Solomonoff 64, Kolmogorov 65\] which have been a keystone of the informational complexity theory.

For $`x\text{ I}\text{N},y\text{ I}\text{N}`$ or $`y\mathrm{\Omega }`$, similarly, $`\text{m}(|)`$ is the largest r.e. real function with $`_x\text{m}(x|y)1`$; $`\text{K}(x|y)\stackrel{\text{df}}{=}1\mathrm{log}\text{m}(x|y)`$ ($`=`$ the least length of self-delimiting programs transforming $`y`$ into $`x`$).

\[Kolmogorov 65\] defines rarity (non-randomness) $`\text{d}(x)`$ of uniformly distributed $`x`$ as $`x\text{K}(x)`$. Our modified K allows extending this to other measures $`\mu `$ on  IN. A $`\mu `$-test is $`f:\text{ I}\text{N}`$ with mean $`\mu (f)1`$ (and, thus, small values $`f(x)`$ on randomly chosen $`x`$). For computable $`\mu `$, a majorant r.e. test is $`\text{m}(x)/\mu (x)`$. This suggests defining $`\text{d}(x|\mu )`$ as $`\mathrm{log}\text{m}(x)/\mu (x)\mathrm{max}\{0,\mathrm{log}\mu (x)\text{K}(x)\}`$.

### 2.2 Integers: Information.

In particular, $`x=(a,b)`$ distributed with $`\mu =\text{m}\text{m}`$, is a pair of two independent, but otherwise completely generic, finite objects. Then, $`\text{I}(a:b)\stackrel{\text{df}}{=}\text{d}((a,b)|\text{m}\text{m})=\text{K}(a)+\text{K}(b)\text{K}(a,b)`$ is seen as dependence and also measures mutual information in $`a,b`$. It was shown (see \[ZL 70\]) by Kolmogorov and Levin to be close (within $`\pm O(\mathrm{log}\text{K}(a,b))`$) to the expression $`\text{K}(a)\text{K}(a|b)`$ of \[Kolmogorov 65\]. Our I equals $`\text{K}(a)\text{K}(a|(b,\text{K}(b)))`$. Unlike the 1965 expression (see \[Gacs 74\]), it is symmetric, monotone: $`\text{I}(a:b)\text{I}((a,a^{}):b)`$ (which will allow extending I to $`\mathrm{\Omega }`$), and satisfies the following Independence Conservation inequalities \[L 74, L 84\]: For any computable transformation $`A`$, measure $`\mu `$, and some family $`t_{a,b}`$ of $`\mu `$-tests

$$\text{I}(A(a):b)\text{I}(a:b),\text{I}((a,w):b)\text{I}(a:b)+\mathrm{log}t_{a,b}(w).$$

(The $`O(1)`$ error terms reflect the constant complexities of $`A,\mu `$.) So, independence of $`a`$ from $`b`$ is preserved in random processes, in deterministic computations, their combinations, etc. These inequalities are not obvious (and false for the original 1965 expression $`\text{I}(a:b)=\text{K}(a)\text{K}(a/b)`$ ) even with $`A`$, say, simply cutting off half of $`a`$. An unexpected aspect of I is that $`x`$ contains all information about $`k=\text{K}(x)`$, $`\text{I}(x:k)\text{K}(k)`$, despite $`\text{K}(k|x)`$ being $`k`$ or $`\mathrm{log}x`$, in the worst case \[Gacs 74\]. One can view this as an “Occam Razor” effect: with no initial information about it, $`x`$ is as hard to obtain as its simplest ($`k`$-bit) description.

All this works as well for the $`\text{I}_z`$ variation of I allowing all algorithms access to oracle $`z`$.

### 2.3 Complexity, Randomness, and Information for Reals.

We now extend these concepts to reals $`\alpha \mathrm{\Omega }`$. This abstraction is often convenient (if not taken too far) for concealing $`O(1)`$ terms and other small mismatches in formulas for finite objects.

#### Reals: Randomness.

A measure on $`\mathrm{\Omega }`$ is a function $`\mu (x)=\mu (x0)+\mu (x1)`$, for $`xS`$. Its mean $`\mu (f)`$ is a linear functional on $``$: $`\mu (f+g)=\mu (f)+\mu (g)`$. It extends to other functions, as usual. $`\mu `$-tests are lower semicontinuous $`f`$, $`\mu (f)1`$; computable $`\mu `$ have universal (i.e., majorant r.e.) Martin-Löf tests $`T_\mu (\alpha )=_i\text{m}(\alpha _{[i]})/\mu (\alpha _{[i]})`$. Random are $`\alpha \mathrm{\Omega }`$ with rarity $`\text{d}(\alpha |\mu )\stackrel{\text{df}}{=}\mathrm{log}T_\mu (\alpha )<\mathrm{}`$.

#### Random R.e. Reals.

P. Martin-Löf noted that some random reals are definable in arithmetic.
In fact, the least real $`L[0,1]`$ with minimal rarity (see, e.g., \[ZL 70\], section 4.4) is random and r.e. If $`(Y+Z)/X\text{ I}\text{Q}`$, we say $`X`$ dominates r.e. reals $`Y,Z`$ (Solovay reducibility, \[Solovay 75, Downey, Hirschfeldt 10\]). By \[Kucera, Slaman 01\], random are exactly those r.e. reals that dominate all others.444Indeed, let $`X=L+Y`$, $`T`$ be an r.e. test with $`T(X)=\mathrm{}`$, $`Y=sup_iy_i`$, $`L=sup_il_i`$, $`T=_it_i`$; $`l_i,y_i,t_i`$ computable. We can choose $`T`$ with $`t_i(r)`$ non-increasing for $`rl_i+y_i`$. Then $`T^{}(r)\stackrel{\text{df}}{=}_it_i(r+y_i)`$ is an r.e. test with $`T^{}(L)=\mathrm{}`$. Conversely, let $`Z,X[0,1]`$ be enumerated as $`Z=sup_iz_i`$, $`X=_ix_i`$. Let $`s_{k,i}=\mathrm{max}\{z_i,s_{k,i1}+x_i/2^k\}`$ and $`t_k(V)\stackrel{\text{df}}{=}2^ksup_i[z_iV<s_{k,i}]`$. Then $`t_k`$ and $`T=_kt_k/k^2`$ are r.e. tests. Let $`y_i=s_{k,i}(s_{k,i1}+x_i/2^k)`$, and $`Y=_iy_i`$. $`S_k=sup_is_{k,i}=X/2^k+Y`$ dominates $`X`$. If $`ZS_k`$ for all $`k`$, then $`z_iZ<s_{k,i}`$ for some $`i`$, so $`t_k(Z)=2^k`$ and $`T(Z)=\mathrm{}`$. Any random r.e. $`\rho `$ is $`_n\text{m}(n)`$ for some universal m: $`\rho `$ dominates all such sums and replacing m with $`\text{m}+x/i`$ for an r.e. $`x`$ concentrated in $`0`$, preserves universality. \[Chaitin 75\] contains probably the first published discussion of randomness of $`_n\text{m}(n)`$.

#### Reals: Information.

\[L 74\] extends I to reals as $`\text{I}(\alpha :\beta )\stackrel{\text{df}}{=}\mathrm{log}_{i,j}\text{m}(i|\alpha )\text{m}(j|\beta )2^{\text{I}(i:j)}`$.
(As always, we average in the linear scale and switch to the logarithmic scale for the final expression.)

For $`\alpha ,\beta \text{ I}\text{N}`$, this equals our previous expression $`\text{K}(\alpha )+\text{K}(\beta )\text{K}(\alpha ,\beta )`$ since both satisfy the Independence Conservation Inequalities. In fact, this extension of I to $`\mathrm{\Omega }`$ is the smallest satisfying the independence conservation. It suffices for the present paper and is used hereafter.

For other applications of Independence Postulate mentioned at the end, a stronger (larger) expression can be used \[L 84, L 12\]. It defines $`\text{I}(\alpha :\beta )`$ as $`\text{d}((\alpha ,\beta )|\text{M}\text{M})`$, where M is the universal r.e. distribution on $`\mathrm{\Omega }`$ (i.e., semimeasure: $`\text{M}(x)\text{M}(x0)+\text{M}(x1)`$). This requires a (quite tricky) extension of the definition of rarity d from computable measures to r.e. distributions.

## 3 Consistent Objects.

Consistency of theories and of other objects can be expressed as membership in co-r.e. sets of reals. It is convenient to define such sets via co-r.e. trees, i.e., infinite sets $`TS`$ containing all prefixes and some extensions of each member. Let $`\stackrel{~}{T}`$ be the set of those $`\omega \mathrm{\Omega }`$ with all prefixes in $`T`$. Some co-r.e. trees have only strings of linear Kolmogorov complexity. Contrast this with

###### Proposition 1

For each $`\beta \mathrm{\Omega }`$, each co-r.e. tree $`T`$ has $`\alpha \stackrel{~}{T}`$ with $`\text{I}(\alpha _{[n]}:\beta )5\mathrm{log}n`$.

###### Lemma 1

For each co-r.e. tree $`T`$ there is a measure $`\mu (x)=\mu (x0)+\mu (x1)`$ with $`\mu (\stackrel{~}{T})>1/2`$,
computable as $`\mu (x)=G(x,\rho _{[5\mathrm{log}x]})`$ by an algorithm $`G`$ using $`5\mathrm{log}x`$ digits of a hint $`\rho \mathrm{\Omega }`$.

Lemma 1 implies Proposition 1. Indeed, algorithms can transform uniform distribution of inputs $`\omega `$ into any computable one; same holds for computations with oracle $`\rho `$. Consider an algorithm using $`\rho `$ to compute $`\mu `$ and transforming $`\omega `$ into a $`\mu `$-distributed $`\alpha `$ ($`\stackrel{~}{T}`$ with high probability). $`\text{I}(\rho _{[O(\mathrm{log}x)]}:\beta )=O(\mathrm{log}x)`$; random $`\omega `$ cannot add information with high probability, and the algorithm cannot increase it either (due to conservation inequalities).

#### Proof of Lemma 1:

$`G`$ uses $`\rho `$ to list all converging $`k`$-bit programs. As \[Barzdin 68\] noted, for this it needs just one of them, the slowest. $`\rho `$ can be any r.e. real with $`\text{K}(\rho _{[n]})=k=no(n)`$, e.g., a random one. Programs that use $`\rho _{[n]}`$ waiting for enumeration of $`\rho `$’s lower bounds to exceed $`\rho _{[n]}`$, are slower than any programs $`P`$ of complexity $`<k2\mathrm{log}n`$: otherwise $`\rho _{[n]}`$ can be generated from $`P,n`$.

$`G`$ computes $`\mu `$ recursively in slices $`\mu _i(x)`$ for $`x=n=2^{2^i}`$, assuming $`\mu _{i1}`$ already computed.
It will approximate $`TB^n`$ as $`T_i=T_i(\rho )`$ by limited co-enumeration and distribute $`\mu _{i1}(x)`$ uniformly on all $`xyT_i`$ (which always exist for $`xT`$) or, if none, on $`x0^{}B^n`$. Let $`h_i`$ be the Shannon entropy of $`\mu _i`$, with the fractional part rounded up to $`2\mathrm{log}2i`$ bits. Given $`\mu _{i1}`$, shrinking $`T_i`$ lowers $`h_i`$.

$`G`$ uses $`\rho `$ to compute the (lexicographically) least possible $`h_1,\mathrm{},h_i`$ and co-enumerates $`T_i`$ until reaching these bounds. Rounding $`h_i`$, leaves a fraction $`f_i`$ of $`xT_iT`$. Yet, $`_if_i<1/2`$.

In particular, randomized algorithms can generate strings of length $`n`$ of any co-r.e. tree $`T`$ with probability $`1/k^2n,k=\mathrm{log}n`$ by guessing $`k,\mathrm{log}TB^{2^k}`$.

### 3.1 Example: Tiling

An illustration is the tiling question from the introduction. \[Durand, Levin, Shen 01\] constructs a palette $`P`$ forcing, on each $`P`$-tiling, high complexity of all horizontal tile strings not crossing one specific column. The same construction works if complexity restriction is replaced with membership in any bi-tree, i.e., a (co-r.e.) tree containing all substrings (not only prefixes) of its members. To use it, we need to encode any co-r.e. tree $`T`$ as an equivalent bi-tree $`T_2`$.

Let $`b(2^k(2l+1))\stackrel{\text{df}}{=}`$ $`(lmod2)`$. The pattern of $`b(n)`$ for $`2^a`$ consecutive $`n`$ determines the $`a2`$ tail bits of $`n`$. Let $`\overline{i}`$ double each bit of $`i`$ and alter the result’s first bit. If $`n`$ ends with $`k`$ followed by $`\overline{k}`$, let $`\text{sf}(n)\stackrel{\text{df}}{=}k`$. Let $`\stackrel{~}{T}_1`$ be a tree of sequences $`\alpha :\text{ I}\text{N}B^2`$ such that $`\alpha (n)=(b(n),t)`$ and for some $`s\stackrel{~}{T}`$, whenever $`\text{sf}(n)`$ is defined, $`t=s(\text{sf}(n))`$. Let $`T_2`$ be a bi-tree of all segments of members of $`\stackrel{~}{T}_1`$. Each $`n`$-bit $`T_2`$-string represents the first $`n/O(n^2)`$ bits555Optimizing $`\overline{i}`$ coding to $`\overline{i}=\text{K}(i)`$ improves the overhead $`n^2`$ to $`1/\text{m}(n)`$ but cannot eliminate it. of a $`T`$-string $`s`$.

In particular, $`T`$ (and $`T_2`$) can force $`s`$ to be random i.e., have maximal complexity. This illustrates the point: all such tilings are highly non-recursive, yet they are easy to generate (with dice). They can be expressed in a formal system that allows trivial completions but no recursive ones.

## 4 The Taboo.

This example does not show that all co-r.e. trees, such as tilings with an arbitrary palette, allow easily generated members. Proposition 1 sets a small but growing bound on the information needed for that, leaving open the question the article started with. It is resolved by the following observation central to this paper. We represent in $`\mathrm{\Omega }`$ partial predicates as their graphs listed in arbitrary order. Let $`u`$ be a universal partial recursive predicate (p.r.p.).

###### Theorem 1

Let $`\rho _n`$ be an $`n+\text{K}(n)`$ bit prefix of a random r.e. real $`\rho `$ and $`U`$ be a partial predicate that on $`B^n`$ is a total extension666One can weaken this total extension condition to being consistent with $`u`$ and defined on the specific input $`px_n`$ if the simple I of \[L 74\] is strengthened to one of \[L 84\] and $`\text{M}(P(0^x)\mathrm{}P(x1))`$ replaces $`m_{x,i}`$ in $`P`$ of the proof. $`U_n`$ of $`u`$. Then $`\text{I}(U:\rho _n)n\text{K}(\text{K}(n)|n)`$.

This statement that $`U_n`$ carries almost all information on $`\rho _n`$ (or equivalently, on the domain size $`d_n`$ of $`u|_{B^n}`$ ) may seem paradoxical. Indeed, Andrei Muchnik noted that only a recursive sequence can be computed from all total extensions $`U`$ of $`u`$. Laurent Bienvenu noted that some such $`U`$ have $`\text{K}(\rho _n|U)n`$. The explanation is that unlocking information in $`U_n`$ to compute $`\rho _n`$ requires also knowing $`\text{K}(U_n)`$. \[Gacs 74\] ingeniously proves that $`\text{K}(\text{K}(x)|x)`$ can be $`\mathrm{log}(x)`$, i.e., $`n`$ for $`x=U_n`$. Theorem 1 provides an alternative proof of this.

Muchnik’s observation does not apply to sequences with computable complexities: indeed by \[Stephan 06\], any Martin-Löf random sequence that computes a total extension of $`u`$, also computes the domain of $`u`$. Of course, I do not assume the axioms chosen by math community to be random!

#### Proof.

We define a p.r.p. $`P:SB`$ inductively on $`B^n`$. If $`P(x)`$ is defined on $`[0^n,x1]`$, let $`\text{M}_{x,i}`$ denote the combined universal measure $`_Q\text{m}(Q|n)`$ of all total predicates $`Q`$ on $`B^n`$ that agree with $`P`$ on $`[0^n,x1]`$ and $`Q(x)iB`$. Then $`P(x)`$ enumerates lower bounds for $`\text{M}_{x,i}`$ until either exceeds $`2^n`$ and yields $`P(x)=i`$, decreasing $`_i\text{M}_{x+1,i}`$ by $`>2^n`$. For some $`x_n`$, $`\text{M}_{x_n,i}2^n`$ and $`P`$ diverges on $`[x_n,1^n]`$ with $`_Q\text{m}(Q|n)2/2^n`$ for all total extensions $`Q`$ of $`P`$ on $`B^n`$.

For all such $`Q`$, this bound allows $`2^n/O(1)`$-fold increase of $`\text{m}(Q|x_n)`$,777This also means $`nI_n(x_n:Q)I_n(d_n:Q)`$ (and already implies Corollary 1, even simplifies its bound to $`O(2^n)`$ ). So, $`\text{K}(d_n|(Q,\text{K}(Q|n))0`$ thus $`d_n`$ can be computed from $`U_n,\text{K}(U_n|n)`$, if not from $`U_n`$ itself. compared to just $`\text{m}(Q|n)=\text{m}(\text{K}(n)|n)\text{m}(Q)/O(\text{m}(n))`$. Now, $`u(px)`$, with a fixed $`p`$, computes $`P(x)`$, and $`U(px)`$ extends $`P(x)`$ on $`B_n`$ to a total $`Q_n`$, with $`\text{m}(Q_n|U)=\text{m}(n)/O(1)`$. Also, $`x_n,\rho _n,\text{K}(n)=\rho _nn`$ are r.e., so can be computed from one of them whose enumeration ends latest. This could only be $`\rho _n`$, being random and long enough to dominate in complexity (which computations cannot increase).

Thus, $`\text{m}(Q_n|\rho _n)=\text{m}(Q_n|x_n)/O(1)=2^n\text{m}(\text{K}(n)|n)\text{m}(Q_n)/O(\text{m}(n))`$. Then, $`\text{I}(U:\rho _n)`$ $`\mathrm{log}(\text{m}(Q_n|\rho _n)\text{m}(Q_n|U)/\text{m}(Q_n))\mathrm{log}2^n\text{m}(\text{K}(n)|n)n\text{K}(\text{K}(n)|n)`$.

Since random strings contain $`k`$ bits of information about $`\rho `$ only with probability $`2^k`$ and algorithms do not increase information (due to the Conservation Inequalities), Theorem 1 implies

###### Corollary 1

The probability that a randomized algorithm computes on $`B^n`$ a total extension
of $`u`$ is at most $`O(2^n)/\text{m}(\text{K}(n)|n)`$. (Strengthening the $`o(1)`$ bound of \[Jockusch, Soare 72\].)

(Thus, not all palettes, formal theories, etc. allow randomness-based tilings, completions, etc.)

While nobody envisioned choosing fundamental Math axioms by coin flips, Theorem 1 supports a more general impossibility. Just like the usual interpretation of Gödel Theorem is a matter of accepting Church-Turing Thesis, judging if Theorem 1 makes the completion task impossible is a matter of accepting the Independence Postulate discussed below.

## 5 The Independence Postulate.

#### IP:

Let $`X`$ be a sequence defined with an $`n`$-bit mathematical statement (e.g., in PA or set theory), and a sequence $`Y`$ can be located in the physical world with a $`k`$-bit instruction set (e.g., ip-address). Then $`\text{I}(X:Y)<k+n+c`$, for some small absolute constant $`c`$.

(Note that $`X`$ and $`Y`$ can each have much more than $`k+n+c`$ bits of information.)

Thus, a (physical) sequence of all mathematical publications has little information about the (mathematical) sequence of all true statements of arithmetic. This is of little concern because the latter has, in turn, little information about the stock market (a physical sequence). :-)

Of course, Kolmogorov information is not the only desirable commodity. Yet, IP has interesting applications \[L 84\]. It can be restated as a “finitary” version of the Church-Turing thesis (CT) by calling recursive those finite sequences with recursive descriptions nearly as short as any their “higher-level” math descriptions. IP postulates that only such recursive sequences exist in reality.

Let me add (in order of increasing relevance) some comparisons between IP and CT:

1. IP is stated with greater care than CT: Obviously not all strings we generate are algorithmic (non-communist election results better not be :-). Only mathematically defined strings need be algorithmic to be generatable. IP includes this math clause explicitly, CT rarely does.
2. IP is simpler, CT more abstract. All sequences we ever see are computable just by being finite: CT is useless for them! IP works equally well for finite and infinite sequences.
3. IP is easier to support: CT is usually stated with vague reasoning. IP has broad conservation laws to support it and a general intuition that target information cannot be increased.
4. IP is much more comprehensive: CT prohibits only generating the target math sequence itself; IP bars all strings with any significant information about it. So, IP can be applied where CT cannot. See, e.g., \[L 84\] or more recent results in \[L 16\].

One application is dousing Gödel’s hope cited in the Introduction, regardless of any realizable process of axiom selection. The argument is “inductive”. It seems, complicated processes we observe, can ultimately be explained, i.e., reduced to simpler ones. These reductions use deterministic models and random ones, but neither can increase the starting information about a target. The toolkit of our models may change (e.g., quantum amplitudes work somewhat differently than probabilities) but it is hard to expect new realistic primitives allowing such “information leaks”.

So, if complicated processes generate unlimited target information, so must do some elementary processes, that admit no further explanations (reductions to simpler processes). The existence of such elementary unexplainable information Sources cannot be ruled out. Yet Infidels :-) can postulate it away. Just like the impossibility of generating power from uniform heat, this is an unprovable postulate, supported by proven arguments.

Note that the above argument is based on Independence Conservation Inequalities (ICI) of \[L 74, L 84\]. They deal with generation of strings by deterministic algorithms or by random processes from other strings. If the preexisting string has no significant target information, neither will the generated one. And despite being intuitive, ICI are not technically trivial and should not be confused with the easy remark that randomized algorithms cannot generate from scratch information about math targets, such as e.g., r.e. reals. (Math community never tried choosing their fundamental axioms this way :-). But the difficulty pays off, being essential for the inductive nature of the support ICI give to IP.

## Acknowledgments

I am grateful to Robert Solovay, Alexander Shen, Bruno Durand, and Laurent Bienvenu for insightful discussions, and to Rod Downey, Denis Hirschfeldt, and Stephen Simpson for three references.


format: text

text:
# Ferromagnetism in Diluted Magnetic Semiconductor Heterojunction Systems

## I Introduction

In many semiconductor crystals, substitution of a transition metal element for a host element adds a local moment to the system’s low-energy degrees of freedom. Systems in which a transition element is substituted quasi-randomly on a finite fraction, $`x`$, of a host semiconductor element sites are known as diluted magnetic semiconductors (DMSs). The degeneracy of each isolated moment’s magnetic state manifold makes these materials very sensitive to the host material environment in which they are placed and to external perturbations. From a very general point of view, this circumstance is attractive for the development of electronic systems that have technologically useful properties. A ferromagnetic state, in which long range order is established among the local moments, is especially important for technology since the moments then act collectively leading to greater sensitivity and more robust phenomena. This idea has been pursued for nearly twenty years. Over time it has been established that the behavior of substitutional Mn elements is particularly simple in many host semiconductors, because of a strong tendency toward well defined $`S=5/2`$, Mn2+ local moments. In II-VI semiconductors, Mn substitutes on cation sites where it provides local moments but alters the host semiconductor valence and conduction bands very weakly. The Mn local moment and the conduction and valence band electrons are coupled by on-site exchange interactions, due to direct overlap between sp and d orbitals and to hybridization between d and p orbitals. The local moments are easily aligned by relatively weak magnetic fields, leading to a rich variety of magnetooptical effects. These materials are not ferromagnetic however. In III-V compound semiconductors on the other hand, substituted Mn2+ ions both lead to local moment formation and act as acceptors, introducing valence band holes and adding to the degrees of freedom that are important in determining the system’s electronic properties. The holes mediate interactions between the Mn moments, correlating their orientations and making ferromagnetism possible.

Since Mn is not soluble in III-V semiconductors, it can be incorporated only by non-equilibrium growth techniques. The discovery of ferromagnetism in low-temperature MBE grown (In,Mn)As, and the eventual realization that relatively high ferromagnetic transition temperatures could be achieved in (Ga,Mn)As, if the samples were suitably annealed after growth, has led to an explosion of interest. Room temperature ferromagnetism has been reported in several different Mn-doped DMS materials very recently. Equally exciting is a recent report that ferromagnetism occurs in DMS’s based on the the group IV element, Ge. The story is still unfolding as these words are being written; annoucements of new surprises have been appearing on e-print servers and in research journals with startling regularity.

An aspect of the ferromagnetism that is key for many potential applications is that the itinerant holes in the valence bands are full participants. The electronic structure of the quasiparticles that carry charge through the system and control its optical absorption and luminescence, are very sensitive to the magnetic state of the system. Considerable progress has been made in understanding the magnetic, transport, and optical properties of bulk DMS ferromagnets, although current understanding is certainly far from complete. A thorough review of this research can be found elsewhere in this issue of Semiconductor Science and Technology. An interactive web resource that provides information, for many different bulk and heterojunction DMS ferromagnet systems, on predictions made by the semi-phenomenological models we discuss below is available at http://unix12.fzu.cz/ms.

The purpose of this article is to address the physics of ferromagnetism in DMS ferromagnet heterojunction systems, a research topic that is far from mature and, in fact, relatively unexplored at present. It would appear that the band-structure engineering possibilities of heterojunction systems should open up unparalleled opportunities for tuning magnetic, magnetooptic, and magnetotransport properties of these low-dimensional and layered ferromagnets. These properties are likely to have technological impact only to the extent that ferromagnetism, or at least strongly enhanced paramagnetism, can be achieved at room temperature. It will likely be some years before materials science research motivated by the search for high-transition-temperature low-carrier-density DMS ferromagnets becomes mature. We attempt here to provide some guidance, based on simple theoretical considerations, that we hope will be helpful for what we expect to be an ongoing research effort. The scope of this article is limited by our incomplete perspective on this rapidly developing field; the topics on which emphasis has been placed are those on which we have worked ourselves.

The article is organized as follows. In Section II we introduce the semi-phenomenological model of DMS ferromagnets on which our discussion is based, and address the physics that controls the ferromagnetic critical temperature. In Section III, we review current experiments and theoretical predictions for different DMS heterojunction systems, pointing out research directions that might be helpful in sorting out the interplay of materials and fundamental physics issues that will need to be resolved to make progress. Section IV contains a summary of this article. Although we discuss only magnetic and dc transport properties here, the magnetooptical properties of DMS heterojunction ferromagnets will likely prove to be an equally exciting field of research over the coming decade. We restrict our attention in this article to the physics of ferromagnetism in DMS systems composed of different semiconductors stacked in layers formed by following an epitaxial growth protocol.

## II Remarks on models and theories of DMS ferromagnetism

### A Semi-phenomenological model

We discuss DMS ferromagnets here mainly in terms of a widely accepted semi-phenomenological model that has three terms:

* The coupling of the $`S=5/2`$ Mn spins to the external magnetic field, $`g\mu _B_I\stackrel{}{S}_I\stackrel{}{H}_{ext}`$ .
* The Hamiltonian of the host semiconductor valence bands, described using a multi-band envelope function formalism. For many properties it is absolutely essential to incorporate spin-orbit coupling in a realistic way. Six or eight band model that includes the ‘split-off’ band and/or the conduction band are sometimes desirable. This band Hamiltonian should include the effect of strain due to lattice matching between the epitaxially grown (II,Mn)VI, (III,Mn)V or (IV,Mn) films and the substrates on which they are grown.
* Antiferromagnetic exchange coupling between the $`S=5/2`$ Mn2+ spins and the valence band holes, $`J_{pd}_I\stackrel{}{S}_I\stackrel{}{s}(\stackrel{}{R}_I)`$. This interaction represents virtual coupling to states that have been integrated out of the model’s Hilbert space, in which electrons are exchanged between the Mn ion d shells and the valence band. These exchange interactions are isotropic to a good approximation because the Mn2+ ion has total angular momentum $`L=0`$.

The most fundamental assumption of this model is that the Mn $`d`$ electrons are localized by their strong Coulomb interactions. The low-energy degrees of freedom are then valence band holes and one $`S=5/2`$ local moment for each Mn ion; other terms that involve these degrees of freedom can be added to the Hamiltonian if they are believed to be important. For example, the present discussion neglects Coulomb interactions between holes and Mn acceptors, and short-range antiferromagnetic interactions between Mn spins, among other terms, that can be of importance in the most general circumstances. Since we are interested here in the strongly metallic limit, Coulomb interactions are not expected to play an essential role in the ferromagnetism. We will also make the approximation that the Mn ions can be replaced by a continuum density that can have a prescribed dependence on the growth direction coordinate, $`N_{Mn}(z)`$. This approximation has the advantage of removing disorder in the direction perpendicular to growth (due to randomness in Mn ion locations) from the model, profoundly simplifying its analysis. Disorder plays an essential role, of course, in determining the magnitude of transport coefficients. For many purposes, however, the continuum Mn density approximation can be a reasonable one provided that the typical distance between Mn ions is smaller than other characteristic lengths such as the average distance between valence band holes, the Bohr radius, or quantum well widths. The utility of this approximation is often improved by the fact that compensation of Mn acceptors by antisite defects is present in all these DMS ferromagnets. From a microscopic point of view, neglect of Mn ion site disorder is equivalent to a virtual crystal approximation.

In using a model with one $`S=5/2`$ local moment per Mn and valence band holes to discuss DMS ferromagnetism we are following Occam’s razor. Although this model is well established by experiment in the most heavily studied bulk systems, (Ga,Mn)As and (Ga,In)As, it may not apply to all bulk systems; possibly not to nitrides for example. It also may not fully capture the physics of systems in which it is common for Mn ions to be in neighboring positions, for example in the $`\delta `$-doped layers discussed below. It also could turn out that the most useful DMS ferromagnets will ultimately be created by intentional clustering of magnetic elements that invalidates our model’s assumptions. At this stage however, it seems appropriate to determine how much of the rich behavior of these electrons can be understood assuming that the Mn d-electrons are always localized. The alert reader should keep in mind the possibility that the model on which the theoretical discussion in this article is based may not always apply.

A useful zeroth order picture of DMS ferromagnets follows from combining the Mn-continuum (virtual crystal) approximation with a mean-field treatment of the kinetic exchange interaction. The mean-field treatment does not allow any fluctuations in the magnitude or direction of Mn ion or valence band hole spin polarizations. In this picture each Mn ion is described by a mean-field Hamiltonian $`_I\stackrel{}{S}_I[g\mu _B\stackrel{}{H}_{ext}+J_0(z)]`$ where $`J_0(z)=J_{pd}\stackrel{}{s}(z)`$ and $`\stackrel{}{s}(z)`$ is the valence band spin polarization. $`J_0`$ is an effective field seen by the local moments due to spin-polarization of the band holes, analogous to the nuclear Knight shift. Similarly the band holes have an additional mean-field term in their Hamiltonian: $`_i\stackrel{}{s}_i\stackrel{}{h}(z)`$, where $`\stackrel{}{s}_i`$ is the i-th hole spin, $`\stackrel{}{h}(z)=J_{pd}N_{Mn}(z)\stackrel{}{S}(z)`$ is an effective magnetic field experienced by the valence band holes and $`\stackrel{}{S}(z)`$ is the mean spin polarization of the Mn spins. This quantity is given in magnitude and direction by the free-spin Brillouin function expression using the total mean field, $`\stackrel{}{H}_{eff}=\stackrel{}{H}_{ext}+J_0/g\mu _B`$. The hole spin polarization, $`\stackrel{}{s}(z)`$, is determined by solving the hole Schroedinger equation with a space-dependent external Zeeman field. This self-consistency condition closes the mean-field equations, and allows any artificial spatial structure to be described.

The value of $`J_{pd}`$ in (Ga,Mn)As is approximately $`60\mathrm{m}\mathrm{e}\mathrm{V}\mathrm{n}\mathrm{m}^3`$. This parameter is not expected to vary widely from material to material, so we can use this value to get a feeling for the strength of these mean-fields in different circumstances. For 5 % Mn substitution $`x=0.05`$, the density of Mn ions is $`N_{Mn}1\mathrm{n}\mathrm{m}^3`$. At present the highest values of $`T_c`$ tend to occur near this value of $`x`$. It is not yet known whether or not there is a material strategy that will avoid the tendency of $`T_c`$ to decrease at larger value of $`x`$. The density of valence band holes in the bulk for this case has been measured to be $`p0.35\mathrm{nm}^3`$, although this quantity is expected to be sensitive to growth temperature and annealing procedure. Using these values we obtain a characteristic energy scales of the Mn spin mean-field at complete hole spin-polarization which is $`J_010\mathrm{m}\mathrm{e}\mathrm{V}`$. Similarly, the valence band mean Zeeman-field at full Mn spin polarization is $`h150\mathrm{m}\mathrm{e}\mathrm{V}`$. We note that the band spin-splitting field is comparable to the Fermi energy, $`ϵ_F`$. This important property explains why transport, optical and other quasiparticle properties of DMS ferromagnets are extremely sensitive to the system’s magnetic state.

### B Comments on simple $`T_c`$ estimates

The most important property of a DMS ferromagnet, from a practical point of view, is its ferromagnetic transition temperature $`T_c`$. With this in mind, it is useful to discuss prospects and strategies for obtaining large values of this parameter in DMS heterojunction systems. An important objective of this paper is to provide some theoretical guidance for efforts to achieve high $`T_c`$ values in delta-doped and quantum well systems. It turns out that in bulk systems, mean-field theory implies a critical temperature $`T_chJ_0/k_Bϵ_FSJ_0/k_B100\mathrm{K}`$. We will argue below that both the mean-field expression and $`SJ_0/k_B`$ provide loose upper bounds for $`T_c`$ and that both parameters must be made large if high ferromagnetic transition temperatures are to be achieved.

Several different arguments can be given to estimate the ferromagnetic critical temperature of DMS ferromagnets. While each is useful, it is important to understand their limitations, especially when applying them to the wide variety of different circumstances that can be realized in heterojunction systems. Mean-field theory has been a very useful guide for bulk systems. The mean-field theory critical temperature $`T_c^{MF}`$ is the temperature below which the free energy can be lowered by creating uniform oppositely directed spin-polarizations in Mn ion and valence-band-hole subsystems. Spin-polarization results in a reduction of entropy of the Mn system, and an increase in the band energy of the valence band, and a compensation gain in kinetic exchange energy. For a single-parabolic band $`k_BT_c^{MF}=(SJ_0h/ϵ_F)(1+1/S)/4`$. Using $`J_010\mathrm{m}\mathrm{e}\mathrm{V}`$, $`h150\mathrm{m}\mathrm{e}\mathrm{V}`$ and $`ϵ_F100\mathrm{m}\mathrm{e}\mathrm{V}`$, gives $`T_c100K`$ for typical bulk $`T_c`$ estimates. This formula gives a fairly solid upper bound on the critical temperature, and certainly allows for room temperature ferromagnetism under favorable circumstances, but can overestimate $`T_c`$ by a larger fraction in some cases.

A second loose upper limit on the critical temperature is especially relevant to quantum well and other heterojunction systems. It follows from noting that $`J_0`$ is an upper bound on the cost in energy for a single Mn spin to flip in a fully ferromagnetic background. The fact that $`J_0`$ overestimates the cost of an uncorrelated spin-flip follows from a variational argument. If the electronic system state is held fixed, the change in energy when a Mn spin orientation is changed, reducing its projection along the order direction by one unit, is equal to the expectation value of the change in the Hamiltonian operator, i.e. to $`J_0>0`$. The actual change in ground state energy will be smaller, since the electronic system will respond to the change in the Hamiltonian and the new ground state will have a lower, energy. The entropy gain from uncorrelated spin fluctuations will destroy ferromagnetism when this energy cost is too small compared to the thermal energy $`k_BT`$. A loose $`T_c`$ upper bound is $`k_BT_c^{SF}=SJ_0=SJ_{pd}p/2`$, which will be smaller than $`T_c^{MF}`$ in many heterojunction systems. Using this $`T_c`$ bound, it follows that ferromagnetic transition temperatures in excess of $`100\mathrm{K}`$ are impossible, given our model and the estimate we use for $`J_{pd}`$, unless the 3D carrier density exceeds $`0.1\mathrm{nm}^3`$. It follows that high ferromagnetic transition temperatures will not be possible in modulation doped II-VI quantum well systems where 2D carrier densities are limited by electrostatic and band-alignment considerations to $`10^{12}\mathrm{cm}^2=10^2\mathrm{nm}^2`$, even when high transition temperatures are predicted by mean-field theory.

The typical energy required to flip a single Mn spin can be substantially smaller than $`J_0`$, if the hole system response is strong. This strong response occurs when the semiconductor band dispersion is weak or when the band electrons are strongly localized; in both cases the energetic cost for a response in band-electron spin orientation that maintains the full kinetic exchange energy is small, so that the overall cost of spin reorientations is reduced substantially below $`J_0`$, reducing the ferromagnetic critical temperature even below this estimate.

Disorder can also have an important effect on the critical temperature. When disorder is included, the hole density tends to increase at Mn spin sites, and $`J_0`$ increases proportionately. The same peak in hole density tends, however, to decrease coupling between Mn spins. It appears likely that the net effect of disorder is always to decrease the maximum temperature at which long range magnetic order can be maintained, although it has not been established that this is the case. Higher ferromagnetic transition temperatures will tend to occur in heterojunction systems in which Mn spins are coupled by more weakly disordered valence band holes.

## III DMS Ferromagnet Heterojunction Systems

In this section we distinguish and discuss separately four classes of systems; i) layered DMS ferromagnet thin films in which the semiconductor layers are thick enough that quantum confinement effects within each layer do not play an important role in the physics, ii) quantum wells in which quantum confinement effects plays a central role and only one or two subbands are occupied, iii) delta-doped layers in which a high concentration of Mn acceptors is placed at specific growth direction coordinates, resulting in the occupation of several growth direction subbands, and iv) superlattices that consist of alternating magnetic and non-magnetic layers thin enough for quantum confinement to play an essential role. The artificial spatial structure introduced by semiconductor heterojunctions plays different roles in these different cases. Although we find this classification scheme useful, there are obviously grey areas between these four cases which can be usefully explored.

### A Layered DMS Ferromagnet Thin Films

We first discuss the case of thick films in which quantum-size effects play no important role in determining magnetic properties like the ferromagnetic transition temperature. Because carrier densities in these semiconductor ferromagnets are lower than in metals, quantum size effects will start to become important at larger film thicknesses. We will argue below that it will not be possible to obtain large $`T_c`$’s in DMS ferromagnets unless the typical 3D carrier density $`p`$ is comparable to that in the high $`T_c`$ bulk samples. The number $`I`$ of occupied 2D subbands in a film of width $`w`$ can be roughly estimated for semiconductors using the particle-in-a-box expression $`I^2pw^3`$. For $`p0.3\mathrm{nm}^3`$, $`I`$ is larger than 15, and we can safely assume properties similar to those of the bulk, for $`w`$ larger $`10\mathrm{n}\mathrm{m}`$. In this section we have in mind heterojunction systems with ferromagnetic layer thicknesses in excess of this value.

Magnetoresistance effects in layered structures of magnetic and non-magnetic metals have been studied extensively, following the discovery of the giant magnetoresistance effect in magnetic multilayers. The basic physics is simplest and the opportunities for applications are greatest in the spin valve structure, in which two ferromagnetic metals are separated by a non-magnetic metal. The role of the non-magnetic metal is to weaken the exchange coupling between the two ferromagnets to a negligible value so that the magnetizations of the two magnetic layers can be manipulated independently. The resistance for current flow between the two magnetic layers tends to be substantially larger when the their magnetizations have opposite orientations. The fundamental origin of the effect is the spin-dependent effective potential experienced by the quasiparticles that carry current through the system because of their exchange interactions with other quasiparticles in the ferromagnetic state. When the magnetization configuration changes, the spin-dependent effective potential changes, and all quasiparticle properties of the metal change. A similar and actually somewhat simpler effect known as tunnel magnetoresistance occurs when the ferromagnetic metals are separated by an insulating barrier, allowing transport to be described using a tunneling Hamiltonian formalism. As emphasized above, the current-carrying quasiparticle states of DMS ferromagnets also experience very strong spin-dependent effective potentials, due to exchange interactions with both local moments and other quasiparticles, that are sensitive to their magnetic configuration. We should therefore expect that very strong magnetoresistance effects will occur in layered DMS ferromagnet thin film systems. This property already has clearly been established in experiment.

DMS Ferromagnet/ Nonmagnetic semiconductor/ DMS Ferromagnet trilayers have been prepared and studied by the Ohno et al. and Tanaka et al.. The (Ga,Mn)As magnetic layer thicknesses were $`30\mathrm{n}\mathrm{m}`$ in the Ohno group case and $`50\mathrm{n}\mathrm{m}`$ in the Tanaka group case, both safely in the bulk film limit. Ohno et al. samples had (Al,Ga)As barrier layers with a relatively small Al fraction, while the Tanaka et al. grew pure AlAs barriers with a range of thicknesses. By growing magnetic layers with different Mn fractions, these authors were able to make the coercive fields of the two magnetic layers distinct. Growth direction resistance in these samples shows a large increase over the relatively narrow field range where the magnetization has reversed in one film but not the other, as expected from the theories of giant magnetoresistance and tunnel magnetoresistance and the strong spin-polarization of DMS ferromagnet valence bands at low-temperatures. In the Tanaka et al. samples, relative changes in the growth direction resistance (the tunnel magnetoresistance ratio) approaching 80 % were obtained at low temperatures for $`1.5\mathrm{nm}`$ thick AlAs barrier layers. Using a simple parabolic band model, the authors attribute the dependence of the TMR ratio on barrier thickness to the combined effect of differences between majority and minority spin Fermi radii and the dependence of tunneling amplitude on growth direction velocity. These results demonstrate that it will be possible to achieve very high resistance ratios in DMS ferromagnet trilayer structures. In addition it should prove possible to tune between tunnel magnetoresistance (TMR) and spin-valve regimes by adjusting the height and width of the barrier both chemically, by varying the Al content in the barrier for example, or by doping the barrier with non-magnetic acceptors like Be to reduce its electrostatic height.

A layered structure that has been studied extensively in non-magnetic bulk semiconductors is the double-barrier resonant tunneling diode. Ohno and collaborators have studied the quasiparticle states of bulk DMS ferromagnets by examining the current-voltage characteristics of resonant-tunneling diodes with ferromagnetic emitters. These experiments are important because they establish experimentally two key features of the ferromagnetic state. First they established the approximate reliability of the mean-field picture of ferromagnetism in DMS ferromagnets because they are able to follow the temperature dependence of the splitting of features in the semiconductor bands that are, at least approximately, proportional to the band effective Zeeman field $`h`$. The experiments show that $`h`$ approaches zero near the $`T_c`$ value established by bulk magnetization measurements. If mean-field theory were not applicable, the bands would be expected to be locally and instantaneously spin polarized at temperatures much larger than the thermodynamic critical temperature, which is the temperature at which long range magnetic order is established. The demonstration of band spin-splitting is also an experimental proof that the quasiparticle bands are full participants in the magnetic state, as implied by the mean-field theory picture. The quasiparticle bands do indeed experience a spin-dependent effective potential in the magnetic state. The demonstration that these splittings vanish at the critical temperature provides important guidance for the development of reliable theoretical descriptions of these materials, since the fact that mean-field theory is relatively accurate, at least for $`x0.05`$ high-$`T_c`$ (Ga,Mn)As, is still not universally accepted.

A unique property of DMS thin films was demonstrated by Ohno et al. who used a field-effect transistor structure to vary reversibly the ferromagnetic transition temperature by applying external electric field. The magnetic (In,Mn)As layer in this system is very thin, only 5 nm, so that the sample actually lies at the border between 3D thin films and 2D quantum wells. When approached from the 3D side, a part of the $`T_c`$ dependence on bias can be attributed to a change in the carrier density induced by the applied electric field. Another contribution to the effect can be understood from the quantum well point of view in which the overlap between the growth-direction wavefunction and the Mn-doped region increases or decreases with applied bias, enhancing or suppressing ferromagnetism in the magnetic layer. The latter contribution belongs to the class of quantum confinement effects that are essential for quantum wells with one or few occupied subbands, a condition easily achieved in modulation doped (II,Mn)VI quantum wells that we discuss next.

Finally we mention the possibility of completely altering the magnetic anisotropy of DMS ferromagnet thin films by changing the substrate on which they are grown, a property which was already established by early experiments. The origin of magnetic anisotropy in DMS ferromagnets is the strong spin-orbit interactions in semiconductor valence bands. Spin-orbit interactions have a strong influence on details of the coupling between Mn moments and on the energy of correlated Mn spin-fluctuations, but are fully responsible for magnetic anisotropy. The systematics of the dependence of magnetic easy axis on substrate, appear to be fully explained by including the influence of lattice-matching strains on the host valence band electronic structure. These strains lift the cubic symmetry of the semiconductor and in so doing dominate the magnetic anisotropy.

### B Quantum Wells

Ferromagnetism in modulation doped II-VI DMS semiconductor quantum well systems was predicted by Dietl et al. and confirmed by Kossacki et al... For the case of a parabolic band, the mean-field-theory expression for the critical temperature is a simple generalization of its bulk counterpart:

$$T_c^{MF}=\frac{S(S+1)}{12}\frac{J_{pd}^2}{k_B}\frac{m^{}}{\pi \mathrm{}^2}𝑑z|\psi (z)|^4N_{Mn}(z).$$
(1)
where $`N_{Mn}(z)`$ is the Mn density distribution in the quantum well, $`m^{}`$ is the 2D band mass, and $`\psi (z)`$ is the occupied subband wavefunction. This expression suggests possibilities for manipulating magnetic properties with gates that are an important part of what is interesting about these ferromagnets.

In Fig. 1 we plot mean-field theory $`T_c`$ results we calculated for a quantum well that is partially filled with Mn ions with a density of $`1\mathrm{n}\mathrm{m}^3`$, using a heavy-hole band in-plane mass $`m^{}=0.11m_0`$. The figure illustrates the increase of $`T_c`$ with an applied bias voltage which draws electrons into the magnetic ion region, an effect mentioned in the previous section. As also emphasized in this figure, when hole-hole interactions are included in mean-field theory, $`T_c`$ estimates are enhanced, especially at lower 2D densities. The situation illustrated here is fairly typical of potential modulation doped II-VI semiconductor DMS ferromagnets.

It is important to mention at this point that mean-field $`T_c`$ estimates can be too high in quantum well systems. For the parameters used to obtain Fig. 1, at a typical point in the quantum well $`J_0=J_{pd}p_{2D}/w0.016\mathrm{meV}`$, whereas $`T_c^{MF}1\mathrm{m}\mathrm{e}\mathrm{V}`$ (neglecting interactions). We have argued above that $`T_c`$ cannot exceed $`SJ_00.04\mathrm{meV}`$, so in retrospect it seems unlikely that mean-field theory estimates are reliable for the case illustrated. Using $`J_{pd}`$ values closer to those now believed to be accurate reduces the discrepancy between mean-field-theory $`T_c`$ estimates and this approximate bound, reducing the former quantity by a factor $`10`$ and the later by a factor $`3`$, but also reduces the predicted critical temperatures to less interesting values. These caveats do not alter the basic point that magnetic and other properties of DMS quantum well ferromagnets will be particularly easy to control, but they do have implications for strategies to achieve high $`T_c`$ values, as we discuss below.

In the quantum well systems studied experimentally by Kossacki et al., a critical temperature $`2\mathrm{K}`$ was extracted by looking for spontaneous spin-splitting of PL features. In this case the measured $`T_c`$ is in a good agreement with mean-field theory estimates predictions based on the smaller values of $`J_{pd}`$ favored by more recent experiments. The quantum well widths in these samples are narrower than for the situation illustrated above so that the mean-field theory is also reasonably compatible with the $`SJ_0`$ bound in this case.

Both mean-field theory and the $`SJ_0`$ bound should be considered in devising strategies for raising the ferromagnetic critical temperature. For example, mean-field-theory predicts very large transition temperatures when the normal-state density-of-states is extremely large, as often happens in valence-band quantum-well systems at densities slightly larger than those at which second subband is first occupied. In our view, the $`SJ_0`$ bound will place a severe limit on the $`T_c`$ increase that can be achieved in this way. $`T_c`$ values much higher than those obtained to date will require narrower quantum wells and higher 2D hole gas densities.

In general the mean-field theory is expected to provide more reliable predictions for the ground-state and low temperature properties of DMS heterojunctions on which we focus of the remaining parts of this article. As we now explain, low density II-VI DMS quantum wells can have very strong and tunable magnetic anisotropy. The interplay between local moment \- itinerant hole exchange coupling, Zeeman coupling of the localized moments to external magnetic field, and the coupling of an external electric field to the orbital degrees of freedom of itinerant holes, makes it possible to vary the coercive field by over an order of magnitude with rather modest external electric fields. As a result, the mean-field theory predicts that the magnetization orientation in quantum wells can be manipulated electrically without changing the magnetic field. Our calculations also suggest that capacitance measurements can be used to probe the magnetic state of biased ferromagnetic semiconductor quantum wells.

The magnetic anisotropy energies plotted in Fig.2 were obtained using the four-band Kohn-Luttinger model that describes only the total angular momentum $`j=3/2`$ bands, and is adequate at low hole densities when spin-orbit coupling is large. The degeneracy between heavy-hole ($`|j_z|=3/2`$) and light-hole ($`|j_z|=1/2`$) bands at the $`\mathrm{\Gamma }`$-point in the bulk is lifted by size quantization effects in a quasi-two-dimensional system. The resulting heavy-light gap is larger than the Fermi energy, in the relevant range of hole densities, allowing only the two heavy-hole bands to be occupied. The heavy holes have their spin aligned along $`\widehat{z}`$-axis ($`001`$ crystal direction) so that the band electron spin matrix elements get smaller when the magnetization tilts away from the growth direction. This leads to very strong magnetic anisotropy with easy axes along and opposite to the growth direction. This anisotropy is reduced in magnitude but is still large, as seen in Fig.2, when mixing between heavy- and light-hole bands is fully accounted for. Note that in DMS quantum wells, the magnetic anisotropy per itinerant carrier is several times larger than in bulk DMS systems and nearly three orders of magnitude larger than in cubic transition metal ferromagnets.

We have predicted that the magnetization reversal process is quite unusual in DMS quantum wells. When the magnetic field is applied, direct Zeeman coupling to a local moment competes with the local mean-field kinetic-exchange coupling, which is proportional to the local itinerant-hole spin-density. Since the carrier density is smaller at the edges of the quantum well than at the center, spin reversal starts from the well edges. This, in turn, creates an exchange barrier for the majority-spins which effectively narrows the quantum well in which they reside. At the same time an effective double-well potential, attractive at the outer edges of the quantum well, develops for the minority spins. As the external magnetic field increases, the minority-spin energy levels are lowered and the majority-spin energy levels are raised. When the lowest down-spin energy level reaches the Fermi energy, holes start to occupy the down-spin states. Our self-consistent calculations show that once this happens, the magnetization reversal is rapidly completed and only the uniform down-spin state is stable. Fig.3 illustrates the possibility of modifying hysteresis loops electrically which, in turn, allows the magnetization to be changed by the external electric field. This attractive feature of ferromagnetic semiconductor quantum well systems, somewhat reminiscent of recent interest in current driven magnetization reversal in metallic ferromagnets, is only a theoretical prediction at present. We expect that the true picture is more complex, but believe that this calculation illustrates one rather unique aspect of DMS ferromagnets that should be accessible to experimental study, once gateable systems can be reliably grown. This behavior originates from the fact that spin-splitting energies experienced by holes in a quantum well can easily be made larger than subband energy splittings, the characteristic energy for growth direction degrees of freedom. In very narrow quantum wells, where higher $`T_c`$’s may be possible, growth direction degrees of freedom will be less important.

### C Delta-Doped Layers

Another type of quasi two-dimensional DMS ferromagnet with relatively high ferromagnetic transition temperatures was realized by Kawakami et al. and Chen et al., by growing monolayers of Mn in bulk systems. Mn is expected to substitute for all group III elements in a single layer, with some diffusion of Mn into nearby layers likely. The growth of these samples is motivated by the expectation that high local Mn densities can be established without forming the decoupled Mn compound precipitates that occur in the bulk at high Mn concentrations. The highest ferromagnetic transition temperatures that have been achieved in isolated (Ga,Mn)As digital alloy layers are $`50\mathrm{K}`$ but transition temperatures larger than $`400\mathrm{K}`$ have been reported in the corresponding (Ga,Mn)Sb systems. (It has not yet been determined whether or not the very high apparent transition temperatures in the antimonide case are due to the formation of weakly linked MnSb islands.) Some insight into the nature of ferromagnetism in uniform digital-doped layers can be obtained by applying continuum Mn mean-field theory to this case. A digital layer of $`\mathrm{Ga}_{0.5}\mathrm{Mn}_{0.5}\mathrm{As}`$ provides a 2D density of acceptors equal to $`N_{Mn}^{2D}3\times 10^{14}\mathrm{cm}^2`$. Holes are electrostatically attracted to the delta-doped layer and, in the continuum Mn approximation, form quasi-2D subbands. The number of occupied subbands and the degree of localization of the subband wavefunctions both depend on the number of layers the Mn ions spread over and on the spatial distribution of antisites, the most common defects in low-temperature MBE grown III-V epilayers. In Fig. 4 we plot results obtained from self-consistent mean-field calculations when it is assumed that the Mn ions are spread over three atomic layers with a Gaussian distribution and that the antisite defects are spread uniformly over a width of $`12\mathrm{n}\mathrm{m}`$ surrounding the delta-doped layer. A compensation factor similar to the one measured for the bulk suggests an overall 2D density of $`10^{14}\mathrm{cm}^2`$, about an order of magnitude larger than a largest 2D density that could be completely removed with gates in typical structures. We find that in this circumstance four 2D subbands are partially occupied, with most of the 2D density in bands that have primarily majority spin heavy-hole and majority spin light-hole character. The magnetic anisotropy energy is sensitive to the degree of compensation as illustrated in Fig. 4. We remark that long-range ferromagnetic order can occur at finite temperatures in 2D only when magnetic anisotropy creates a magnetic easy-axis. The scale of the anisotropy energy per Mn ion that we find is $`20\mathrm{m}\mathrm{e}\mathrm{V}`$, much larger than thermal energies at the mean-field critical temperature $`T_c`$, demonstrating that delta-doped layer ferromagnets have strong Ising character. As indicated in Fig. 4, however, the magnetic anisotropy can accidentally become small at particular densities.

The anomalous Hall effect (AHE) in a ferromagnetic metal is commonly used as a convenient proxy for the magnetization, especially in quasi two-dimensional systems for which bulk magnetization measurements may be difficult. It has been demonstrated recently that the AHE measured in bulk DMS ferromagnets is related to the Berry phase acquired by a quasiparticle wavefunction upon traversing closed paths on the spin-split Fermi surface of a ferromagnetic state. Theoretical results for the AHE of digital-layer systems are summarized in Fig. 5 where we see that the anomalous Hall conductance depends not only on the quasi 2D hole density, but also on the spatial distribution of compensating defects. The AHE becomes small in the limit of small carrier densities, since all occupied states are nearly pure heavy-hole in character and their spinors vary only weakly with wavevector. It is also worth noting that the AHE is predicted by this theory to have extremely small values in electron modulation doped II-VI quantum well ferromagnets, because weak spin-orbit scattering in the conduction band gives quasiparticle spinors that are nearly independent of wavevector and have very small Berry phases. AHE measurements will not be effective in screening for ferromagnetism in n-type systems.

The mean-field theory of critical temperatures in digital layer DMS ferromagnets was discussed by Fernandez-Rossier and Sham. The authors were able to explain experimental observations qualitatively, although they used values of $`J_{pd}`$ substantially larger than those currently thought to be appropriate. This partial discrepancy might reflect inadequacies of mean-field theory in quasi-2D systems, but could also be due to the substantial importance of the antisite defect distribution. If these are spread out over a much larger volume than the Mn acceptors, holes are attracted more strongly to the Mn layers, producing higher mean-field transition temperatures. The average hole density in $`\delta `$-doped systems is comparable to that of bulk DMS ferromagnets, moving the $`J_0`$ bound beyond the critical temperatures predicted by mean-field theory, making the relationship between carrier density and critical temperature more complex. Still we expect that any strategy that increases the hole density near Mn ions will increase $`T_c`$. It seems possible that it will ultimately be possible to increase the $`T_c`$’s of $`\delta `$-doped layer systems by tailoring the distribution and density of antisite defects, and by adding heterojunction barrier layers to force carriers toward the magnetic ions.

### D Superlattices

DMS ferromagnet superlattices that mimic metallic giant magnetoresistance multilayers have been grown by several groups, with the most recent results reported by Sadowski et al.. The latter authors find that ferromagnetism can occur in systems with magnetic layers as thin as $`2.2\mathrm{nm}`$. In general these superlattice systems have Mn densities in the magnetic layers comparable to those of bulk samples. We would therefore expect comparable critical temperatures, as long as the holes do not leak out significantly beyond the Mn containing layers. The hole density distribution should fall to zero over a distance comparable to the bulk Fermi wavelength unless additional acceptor doping has been introduced in the non-magnetic layers.

A key property of giant magnetoresitance multilayers is an oscillatory dependence of the exchange coupling between magnetic layers on the thickness of the non-magnetic spacer. To illustrate that a similar effect may occur in DMS ferromagnet superlattices, we have considered a (Ga.Mn)As/GaAs superlattice with 2 nm thick magnetic layers, $`N_{Mn}=1`$ nm-3, and a homogeneous distribution of ionized impurities that neutralize the free-carrier charge. We look for two different mean-field solutions, a ferromagnetic (F) one with parallel ordered moments in all Mn-doped regions, and a solution with an antiferromagnetic (AF) alignment of adjacent magnetic layers. The interlayer exchange coupling $`E_c`$, is defined as the difference in energy between AF and F-states per area per (Ga,Mn)As layer. In Fig. 6 we present numerical results, obtained assuming parabolic bands with effective mass $`m^{}=0.5m_0`$, for $`E_c`$ as a function of a dimensionless parameter $`2d\overline{k}_F`$. Here $`\overline{k}_F`$ is the Fermi wavevector corresponding to the average 3D density of free carriers in the superlattice with a period $`d`$. Oscillations in the mean-field (solid lines) $`E_c`$ are qualitatively consistent with simple RKKY model estimates. The amplitude of oscillations in $`E_c`$ is $`10\times `$ smaller than in metallic systems measured in absolute units and $`10\times `$ larger if energy is measured relative to the Fermi energy of free carriers. In order to achieve substantial exchange coupling in experimental systems it will be important to achieve a fairly uniform profile of ionized acceptors and to limit disorder scattering. If acceptors are present only in the magnetic layers, we expect that their exchange coupling will be much weaker.

Fig. 7 shows occupied minibands in the superlattice Brillouin zone. The miniband dispersion is much weaker in the AF case because the barriers separating two adjacent minima in the effective potential are twice as thick and high as in the F case. Since the conductance is approximately proportional to the square of the largest miniband width in either coherent or incoherent transport limits, the minibands can be used to estimate the size of the current-perpendicular-to-plane (CPP) magnetoresistance effect. For the case illustrated, the AF state CPP conductance will be three orders of magnitude smaller than the F state CPP conductance. The large difference is expected since the bulk (Ga,Mn)As bands are half-metallic for these parameters. In general, mean-field theory predicts strong CPP magnetoresistance in DMS superlattices if the AF state can be realized.

In closing we remark that envelope-function modelling will fail in very short period superlattices. Vargaftman and Meyer have recently reported on calculations using an effective bond orbital method that is still accurate in this limit. Their approach will be useful, particularly for addressing the possibility of enhancing critical temperatures by surrounding narrow magnetic layers by barrier material with large band offsets.

## IV Concluding Remarks

Ferromagnetism in DMS occurs because of exchange interactions between magnetic ion local moments and itinerant hole or electron spins. As in other metallic ferromagnets, collective behavior of many degrees of freedom results in transport and optical properties that can be very sensitive to the ferromagnet’s magnetic configuration. This sensitivity is often strongest and most easily exploited in trilayer structures in which two ferromagnetic layers with weak magnetic coupling are separated by an insulating or metallic layer. DMS ferromagnets differ fundamentally from transition metal ferromagnets because the density of itinerant carriers is much smaller, less than $`10^{21}\mathrm{cm}^3`$. This lower carrier density, combined with the essential role that itinerant carriers play in the ferromagnetic coupling mechanism, causes magnetic and other properties of DMS ferromagnets to be sensitive to defect densities and distributions, to intentional doping, to strain, and to gates. Their have recently been a number of indications that room temperature ferromagnetism can occur in DMS systems, although important properties of these high $`T_c`$ systems like homogeneity, carrier-density, and sensitivity to defect densities, have not yet been thoroughly explored. If the same degree of malleability already established in lower ($`100\mathrm{K}`$) $`T_c`$ DMS ferromagnets can be extended to higher temperatures, these ferromagnets are likely to be useful, possibly for spintronics applications which currently use transition metals or for creative new ideas that integrate information processing and information storage functions.

Quantum engineering in semiconductor heterojunction systems is more interesting than in metallic systems because of the great flexibility for adjusting effective band Hamiltonians on super atomic but still characteristic length scales, such as the average distance between carrier. In this article we have summarized some of the experimental and theoretical work, performed mostly over the past five years, on semiconductor heterojunction systems containing DMS ferromagnets. Although we have made an effort to describe the most important experimental and materials developments, we have found it convenient to structure our discussion loosely around theoretical speculations, predictions, and proposals we have made over the past few years, mostly using simple mean-field theory ideas. It is easier to roam rapidly over the vast phase space of heterojunction possibilities theoretically than experimentally and, although our ability to make confident predictions of magnetic properties is still limited, we believe that the exercise is useful at this stage of the subject. We have commented here on the limitations of mean-field theory, especially for predicting the critical temperatures of quantum well DMS ferromagnets, and emphasized the importance of achieving relatively high carrier densities in order to get high transition temperatures.

Research on DMS ferromagnet heterojunction systems is just beginning. Although our crystal ball is foggy, and likely has a few serious scratches on its surface, we believe that we can see a few enduring truths and principles through the mists of uncertainty.

* It will not be possible to achieve high ferromagnetic transition temperatures in modulation doped II-VI quantum well DMS ferromagnets.
* Magnetic anisotropy is a key property of any magnetic material. DMS ferromagnet thin films with valence-band hole quasiparticles will always be hard magnetic materials because of strong spin-orbit interactions in the valence band, i.e. magnetostatics will play a relatively weak role in determining energetically preferred magnetic configurations. Magnetic anisotropy will be stronger in quasi two-dimensional p-type DMS ferromagnets and decrease in strength with the number of occupied subbands. n-type DMS ferromagnets, like those that could occur in modulation doped II-VI quantum well systems, will be very nearly isotropic purely two-dimensional ferromagnets, of which their are few examples in nature, and should be of some interest from a fundamental physics point of view.
* Itinerant holes or electrons are full participants in the ferromagnetism of DMS systems. Band quasiparticle energy splittings at low temperatures are comparable to the Fermi energy, lacking complete spin polarization primarily because of strong spin-orbit interactions in the valence band. It will therefore be relatively easy to achieve excellent spintronics functionalities in spin-valve, magnetic tunnel junction, spin-injector, and other geometries using DMS ferromagnets.
* The anomalous Hall effect (AHE) will be exceptionally strong in p-type DMS ferromagnets and exceptionally weak in n-type DMS ferromagnets. Ferromagnetism in n-type systems is unlikely to be detected by AHE measurements.
* Quasiparticle state spin-splitting due to magnetic order in quasi-two-dimensional DMS ferromagnets is comparable to the quantum confinement subband splitting in a 10 nm quantum well. The interplay between magnetic configurations and growth direction confinement will be responsible for new physics in quasi-2D DMS ferromagnets.

Material science, experimental, and theoretical work is currently in progress on these and many other related issues.

Our work on DMS ferromagnet heterojunctions has been supported by DARPA/ONR Award No. N00014-00-1-095, NSF grant DMR-0115947, the DOE, the Welch Foundation, the Indiana 21st Century Fund, the Grant Agency of the Czech Republic, and by the Ministry of Education of the Czech Republic. We have benefited from helpful discussions with many colleagues especially Ramin Abolfath, Bill Atkinson, David Awschalom, David Baxter, Jose Brum, Tomasz Dietl, Dimitri Culcer, Joaquin Fernandez-Rossier, Jacek Furdyna, Jürgen König, Jan Kučera, Hsiu-Hau Lin, Hong Luo, Bruce McCombe, Jerry Meyer, Qian Niu, Hideo Ohno, Nitin Samarth, Jairo Sinova, Peter Schiffer, John Schliemann, and S.-R. Eric Yang.