text:
# Entropy and perpetual computers

## I Introduction

The purpose of this lecture note is to illustrate a route for the definition of entropy using our experience with computers. In the process the connection between statistical physics and computations comes to the fore.

### I.1 What is entropy?

This is a question that plagues almost all especially beginning physics students. There are several correct ways to answer this.

1. It is the perfect differential that one gets by dividing the heat transfered by a quantity $`T`$ that gives us the hot-cold feeling (i.e. temperature). (thermodynamics)
2. It is the log of the number of states available. (Boltzmann)
3. It is something proportional to $`p_i\mathrm{ln}p_i`$ where $`p_i`$ is the probability that the system is in state i. (Gibbs)
4. It is just an axiom that there exists an extensive quantity $`S`$, obeying certain plausible conditions, from which the usual thermodynamic rules can be obtained. (Callen)

But the colloquial link between disorder or randomness and entropy remains unexpressed though, agreeably, making a formal connection is not easy. Our plan is to establish this missing link a la Kolmogorov.

Besides these conceptual questions, there is a practical issue that bugs many who do computer simulations where different configurations are generated by some set of rules. In the end one wants to calculate various thermodynamic quantities which involve both energy and entropy. Now, each configuration generated during a simulation or time evolution has an energy associated with it. But does it have an entropy? The answer is of course blowing in the wind. All thermodynamic behaviours ultimately come from a free energy, say, $`F=ETS`$ where $`E`$, the energy, generally known from mechanical ideas like the Hamiltonian, enters as an average, denoted by the angular brackets, but no such average for $`S`$. As a result, one cannot talk of “free energy” of a configuration at any stage of the simulation. All the definitions mentioned above associate $`S`$ to the ensemble, or distributions over the phase space. They simply forbid the question “what is the entropy of a configuration”. Too bad!

### I.2 On computers

Over the years we have seen the size of computers shrinking, speed increasing and power requirement going down. Centuries ago a question that tickled scientists was the possibility of converting heat to work or finding a perfect engine going in a cycle that would completely convert heat to work. A current version of the same problem would be: Can we have a computer that does computations but at the end does not require any energy. Or, we take a computer, draw power from a rechargeable battery to do the computation, then do the reverse operations and give back the energy to the battery. Such a computer is in principle a perpetual computer. Is it possible?

What we mean by a computer is a machine or an object that implements a set of instructions without any intelligence. It executes whatever it has been instructed to do without any decision making at any point. At the outset, without loss of generality, we choose binary (0,1) as the alphabet to be used, each letter to be called a bit. The job of the computer is to manipulate a given string as per instructions. Just as in physics, where we are interested in the thermodynamic limit of infinitely large number of particles, volumes etc, we would be interested in infinitely long strings. The question therefore is “can bit manipulations be done without cost of energy?”

## II Randomness

The problem that a configuration can not have an entropy has its origin in the standard statistical problem that a given outcome of an experiment cannot be tested for randomness. E.g., one number generated by a random number generator cannot be tested for randomness.

For concreteness, let us consider a general model system of a magnet consisting of spins $`s_i=\pm 1`$ arranged on a square lattice with $`i`$ representing a lattice site. If necessary, we may also use an energy (or Hamiltonian) $`E=J_{<ij>}s_is_j`$ where the sum is over nearest neighbours (i.e. bonds of the lattice). Suppose the temperature is so high that each spin can be in anyone of the two states $`\pm 1`$ with equal probability. We may generate such a configuration by repeated tossing of a fair coin. If we get $`+++++++`$ ($`+`$:H,$``$:T) is it a random configuration? Or Can the configurations of spins as shown in Fig. 1 be considered random?

With $`N`$ spins (or bits), under tossing of a fair coin, the probability of getting Fig. 1(A) is $`2^N`$ and so is the probability of (B) or (C). Therefore, the fact that a process is random cannot be used to guarantee randomness of the sequence of outcomes. Still, we do have a naive feeling. All Heads in $`N`$ coin toss experiments or strings like 1111111… (ferro state of Fig. 1(A)) or 10101010… (anti-ferro state of Fig 1(B)) are never considered random because one can identify a pattern, but a string like 110110011100011010001001… (or configuration of Fig 1(C)) may be taken as random. But what is it that gives us this feeling?

### II.1 Algorithmic approach

The naive expectation can be quantified by a different type of arguments, not generally emphasized in physics. Suppose I want to describe the string by a computer programme; or rather by an algorithm. Of course there is no unique “programming” language nor there is “a” computer - but these are not very serious issues. We may choose, arbitrarily, one language and one computer and transform all other languages to this language (by adding ”translators”) and always choose one particular computer. The two strings, the ferro and the anti-ferro states, can then be obtained as outputs of two very small programmes,

```
(A) Print 1   5 million times (ferro state)
(B) Print 10  2.5 million times (antiferro state)

```

In contrast, the third string would come from

```
(C) Print 110110011100...  (disordered state)

```

so that the size of the programme is same as the size of the string itself. This example shows that the size of the programme gives an expression to the naive feeling of randomness we have. We may then adopt it for a quantitative measure of randomness.

> Definition : Let us define randomness of a string as the size of the minimal programme that generates the string.

The crucial word is “minimal”. In computer parlance what we are trying to achieve is a compression of the string and the minimal programme is the best compression that can be achieved.

Another name given to what we called “randomness” is complexity, and this particular measure is called Kolmogorov algorithmic complexity. The same quantity, randomness, is also called information, because the more we can compress a string the less is the information content. Information and randomness are then two sides of the same coin: the former expressing a positive aspect while the 2nd a negative one!

Let $`K(𝖼)`$ be a programme for the string of configuration $`𝖼`$ and let us denote the length of any string by $`\mathrm{}`$. The randomness or complexity is

$$𝒮(𝖼)=\mathrm{min}K(𝖼)|.$$
(1)
We now define a string as random, if its randomness or complexity is similar to the length of the string, or, to be quantitative, if randomness is larger than a pre-chosen threshold, e.g, say, $`𝒮(𝖼)>𝖼|13`$. The choice of $`13`$ is surely arbitrary here and any number would do.

#### II.1.1 Comments

A few things need to be mentioned here. (i) By definition, a minimal programme is random, because its size cannot be reduced further. (ii) It is possible to prove that a string is not random by explicitly constructing a small programme, but it is not possible to prove that a string is random. This is related to Gödel’s incompleteness theorem. For example, the digits of $`\pi `$ may look random (and believed to be so) until one realizes that these can be obtained from an efficient routine for, say, $`\mathrm{tan}^1`$. We may not have a well-defined way of constructing minimal algorithms, but we agree that such an algorithm exists. (iii) The arbitrariness in the choice of language leads to some indefiniteness in the definition of randomness which can be cured by agreeing to add a translator programme to all other programmes. This still leaves the differences of randomness of two strings to be the same. In other words, randomness is defined upto an arbitrary additive constant. Entropy in classical thermodynamics also has that arbitrariness. (iv) Such a definition of randomness satisfies a type of subadditivity condition $`S(𝖼_1+𝖼_2)S(𝖼_1)+S(𝖼_2)+O(1)`$, where the $`O(1)`$ term cannot be ignored.

### II.2 Entropy

Accepting that this Kolmogorovian approach to randomness makes sense and since we connect randomness in a physical system with entropy, let us associate this randomness $`𝒮(𝖼)`$ with the entropy of that string or configuration $`𝖼`$. For an ensemble of strings or configurations with probability $`p_i`$ for the $`i`$-th string or configuration $`𝖼_i`$, the average entropy will be defined by

$$S_\mathrm{K}=\underset{i}{}p_i𝒮(𝖼_i)$$
(2)
(taking the Boltzmann constant $`k_B=1`$). We shall claim that this is the thermodynamic entropy we are familiar with.

Since the definition of entropy in Eq. (2) looks ad hoc, let us first show that this definition gives us back the results we are familiar with. To complete the story, we then establish the equivalence with the Gibbs definition of entropy.

### II.3 Example I: Mean filed theory for the Ising model

Consider the Ising problem. Let us try to write the free energy of a state with $`n_+`$ \+ spins and $`n_{}`$ spins with $`n_++n_{}=N`$. The number of such configurations is

$$\mathrm{\Omega }=\frac{N!}{n_+!n_{}!}.$$
(3)
An ordered list (say lexicographical) of all of these $`\mathrm{\Omega }`$ configurations is then made. If all of these states are equally likely to occur then one may specify a state by a string that identifies its location in the list of configurations. The size of the programme is then the number of bits required to store numbers of the order of $`\mathrm{\Omega }`$. Let $`S`$ be the number of bits required. For general $`N,n_+,n_{}`$, $`S`$ is given by

$$2^S=\mathrm{\Omega }S=\mathrm{log}_2\mathrm{\Omega }.$$
(4)
Stirling’s approximation then gives

$`S`$ $`=`$ $`n_+\mathrm{log}_2n_++n_{}\mathrm{log}_2n_{}`$ (5)
$`=`$ $`N[p\mathrm{log}_2p+(1p)\mathrm{log}_2(1p)],`$
with $`p=n_+/N`$, the probability of a spin being up. Resemblance of Eq. (4) with the Boltzmann formula for entropy (Sec. I) should not go unnoticed here. Eq. (5) is the celebrated formula that goes under the name of entropy of mixing for alloys, solutions etc.

#### II.3.1 Comments

It is important to note that no attempt has been made for “minimalizations” of the algorithm or in other words we have not attempted to compress $`\mathrm{\Omega }`$. For example, no matter what the various strings are, all of the N spin configurations can be generated by a loop (algorithm represented schematically)

```
     i = 0
10   i = i+1
     L = length of i in binary
     Print 0  (N-L) times, then  "i" in binary
     If  ( i < N ) go to 10
     stop

```

By a suitable choice of $`N`$ (e.g., $`N=11\mathrm{}\mathrm{..1}`$) the code for representation of $`N`$ can be shortened enormously by compressing $`N`$. This shows that one may generate all the spin configurations by a small programme though there are several configurations that would require individually much bigger programmes. This should not be considered a contradiction because it produces much more than we want. It is fair to put a restriction that the programmes we want should be self delimiting (meaning it should stop without intervention) and should produce just what we want, preferably no extra output. Such a restriction then automatically excludes the above loop.

Secondly, many of the numbers in the sequence from $`1`$ to $`\mathrm{\Omega }`$ can be compressed enormously. However, what enumeration scheme we use, cannot be crucial for physical properties of a magnet, and therefore, we do need $`S`$ bits to convey an arbitrary configuration. It is also reassuring to realize that there are random (i.e. incompressible) strings in $`2^N`$ possible $`N`$-bit strings. The proof goes as follows. If an $`N`$-bit string is compressible, then the compressed length would be $`N1`$. But there are only $`2^{N1}`$ such strings. Now the compression procedure has to be one to one (unique) or otherwise decompression will not be possible. Hence, for every $`N`$, there are strings which are not compressible and therefore random.

A related question is the time required to run a programme. What we have defined so far is the “space” requirement. It is also possible to define a “time complexity” defined by the time required to get the output. In this note we avoid this issue of time altogether.

#### II.3.2 Free energy

In the Kolmogorov approach we can now write the free energy of any configuration, $`𝖼_i`$ as $`F_i=E_iTS_i`$ with the thermodynamic free energy coming from the average over all configurations,

$$FF=ETS.$$

If we now claim that $`S`$ obtained in Eq. (5) is the entropy of any configuration, and since no compression is used, it is the same for all (this is obviously an approximation), we may use $`S=S`$. The average energy may be approximated by assuming random mixture of up and down spins with an average value $`s=p(1p)`$. If $`q`$ is the number of nearest neighbours ($`4`$ for a square lattice), the free energy is then given by

$$\frac{F}{N}=\frac{q}{2}J(2p1)^2T[p\mathrm{log}p+(1p)\mathrm{log}(1p)].$$
(6)
Note that we have not used the Boltzmann or the Gibbs formula for entropy. By using the Kolmogorov definition what we get back is the mean field (or Bragg-Williams) approximation for the Ising model. As is well-known, this equation on minimization of $`F`$ with respect to $`p`$, gives us the Curie-Weiss law for magnetic susceptibility at the ferro-magnetic transition. No need to go into details of that because the purpose of this exercise is to show that the Kolmogorov approach works.

### II.4 Example II: Perfect gas

A more elementary example is the Säckur-Tetrode formula for entropy of a perfect gas. We use cells of small sizes $`\mathrm{\Delta }V`$ such that each cell may contain at most one particle. For N particles we need $`\mathrm{\Omega }=(V/\mathrm{\Delta }V)^N`$ numbers to specify a configuration, because each particle can be in one of $`V/\mathrm{\Delta }V`$ cells. The size in bits is $`S=N\mathrm{log}_2\frac{V}{\mathrm{\Delta }V}`$ so that the change in randomness or entropy as the volume is changed from $`V_i`$ to $`V_f`$ is

$$\mathrm{\Delta }S=N\mathrm{log}_2\frac{V_f}{V_i}.$$
(7)
The indistinguishability factor can also be taken into account in the above argument, but since it does not affect Eq. (7), we do not go into that. Similarly momentum contribution can also be considered.

It may be noted here that the work done in isothermal expansion of a perfect gas is

$$_{V_i}^{V_f}P𝑑V=Nk_\mathrm{B}T\mathrm{ln}\frac{V_f}{V_i}=(k_\mathrm{B}\mathrm{ln}2)T\mathrm{\Delta }S.$$
(8)
Where $`P`$ is the pressure satisfying $`PV=Nk_\mathrm{B}T`$ and $`\mathrm{\Delta }S`$ is defined in Eq. (7). Both Eqs. (7) and (8) are identical to what we get from thermodynamics. The emergence of $`\mathrm{ln}2`$ is because of the change in base from $`2`$ to $`e`$.

It seems logical enough to take this route to the definition of entropy and it would remove much of the mist surrounding entropy in the beginning years of a physics student.

## III Computers

### III.1 On computation

For the computer problem mentioned in the Introduction, one needs to ponder a bit about reality. In thermodynamics, one considers a reversible engine which may not be practical, may not even be implementable. But a reversible system without dissipation can always be justified. Can one do so for computers?

#### III.1.1 Reversible computers?

To implement an algorithm (as given to it), one needs logic circuits consisting of say AND and NAND gates (all others can be built with these two) each of which requires two inputs (a,b) to give one output (c). By construction, such gates are irreversible: given c, one can not reconstruct a and b. However it is possible, at the cost of extra signals, to construct a reversible gate (called a Toffoli gate) that gives AND or NAND depending on a third extra signal. The truth table is given in Appendix A. Reversibility is obvious. A computer based on such reversible gates can run both ways and therefore, after the end of manipulations, can be run backwards because the hardware now allows that. Just like a reversible engine, we now have a reversible computer. All our references to computers will be to such reversible computers.

#### III.1.2 Laws of computation

Let us try to formulate a few basic principles applicable to computers. These are rephrased versions of laws familiar to us.

> Law I: It is not possible to have perpetual computation.

In other words, we cannot have a computer that can read a set of instructions and carry out computations to give us the output without any energy requirement. Proving this is not straight forward but this is not inconsistent with our intuitive ideas. We won’t pursue this. This type of computer may be called perpetual computer of type I. First law actually forbids such perpetual computers.

> Law II: It is not possible to have a computer whose sole purpose is to draw energy from a reversible source, execute the instructions to give the output and run backward to deliver the energy back to source, and yet leave the memory at the end in the original starting state.

A computer that can actually do this will be called a perpetual computer of second kind or type II.

#### III.1.3 What generates heat?

In order to see the importance of the second law, we need to consider various manipulations on a file (which is actually a string). Our interest is in long strings (length going to infinity as in thermodynamic limit in physics). Now suppose we want to edit the file and change one character, say, in the 21st position. We may then start with the original file and add an instruction to go to that position and change the character. As a result the edit operation is described by a programme which is almost of the same length (at least in the limit of long strings) as the original programme giving the string. Therefore there is no change in entropy in this editing process. Suppose we want to copy a file. We may attach the copy programme with the file. The copy programme itself is of small size. The copy process therefore again does not change the entropy. One may continue with all the possible manipulations on a string and convince oneself that all (but one) can be performed at constant entropy.

The exceptional process is delete or removal of a file. There is no need of elaboration that this is a vital process in any computation. When we remove a file, we are replacing the entire string by all zeros - a state with negligible entropy. It is this process that would reduce the entropy by $`N`$ for $`N`$ characters so that in conventional units the heat produced at temperature $`T`$ is $`Nk_\mathrm{B}T\mathrm{ln}2`$ (see Eq. (8)). We know from physics that entropy reduction does not happen naturally (we cannot cool a system easily).

#### III.1.4 Memory as fuel

We can have a reversible computer that starts by taking energy from a source to carry out the operations but to run it backward (via Toffoli gates) it has to store many redundant information in memory. Even though the processes are iso-entropic and can be reversed after getting the output to give back the energy to the source, we no longer have the memory in the same “blank” state we started with. To get back to that “blank” state, we have to clear the memory (remove the strings). This last step lowers the entropy, a process that cannot be carried out without help from outside. If we do not want to clear the memory, the computer will stop working once the memory is full.

This is the second law that prohibits perpetual computer of second kind. The similarity with thermodynamic rules is apparent. To complete the analogy, a computer is like an “engine” and memory is the fuel. From a practical point of view, this loss of entropy is given out as heat (similar to latent heat on freezing of water). Landauer in 1961 pointed out that the heat produced due to this loss of entropy is $`k_\mathrm{B}T\mathrm{ln}2`$ per bit or $`Nk_\mathrm{B}T\mathrm{ln}2`$ for $`N`$ bits. For comparison, one may note that $`Nk_\mathrm{B}\mathrm{ln}2`$ is the total amount of entropy lost when an Ising ferromagnet is cooled from a very high temperature paramagnetic phase to a very low temperature ferromagnetic phase. If the process of deletion on a computer occurs very fast in a very small region of space, this heat generation can create problem. It therefore puts a limit on miniaturization or speed of computation. Admittedly this limit is not too realistic because other real life processes would play major roles in determining speed and size of a computer. See Appendix C for an estimate of heat generated.

### III.2 Communication

#### III.2.1 The problem

Let us now look at another aspect of computers namely transmission of strings (or files) or communication. This topic actually predates computers. To be concrete, let us consider a case where we want to transmit images discretized into small cells of four colours, RGBY with probabilities

$$p(\mathrm{R})=1/2,p(\mathrm{G})=1/4,p(\mathrm{B})=p(\mathrm{Y})=1/8.$$

The question in communication is: “What is the minimal length of string (in bits) required to transmit any such image?”

#### III.2.2 Kolmogorov and Shannon’s theorem

There are two possible ways to answer this question. The first is given by the Kolmogorov entropy (= randomness = complexity) while the second is given by a different powerful theorem called Shannon’s noiseless coding theorem. Given a long string $`𝒞_j`$ of say $`N`$ characters, if we know its Kolmogorov entropy $`𝒮_j`$ then that has to be the smallest size for that string. If we now consider all possible $`N`$ character strings with $`𝒫_j`$ as the probability of the $`j`$th string, then $`S_\mathrm{K}=_j𝒫_j𝒮_j`$ is the average number we are looking for. Unfortunately it is not possible to compute $`𝒮_j`$ for all cases. Here we get help from Shannon’s theorem. The possibility of transmitting a signal that can be decoded uniquely is guaranteed with probability 1, if the average number of bits per character $`=p_i\mathrm{log}_2p_i`$ where $`p_i`$’s are the probabilities of individual characters. A proof of this theorem is given in Appendix B. Since the two refer to the same object, they are the same with probability 1, i.e.,

$$S_\mathrm{K}=Np_i\mathrm{log}_2p_i.$$

#### III.2.3 Examples

The applicability of the Shannon theorem is now shown for the above example. To choose a coding scheme, we need to restrict ourselves to prefix codes (i.e. codes that do not use one code as the “prefix” of another code. As an example, if we choose $`\mathrm{R}0,\mathrm{G}1,\mathrm{B}10,\mathrm{Y}11`$, decoding cannot be unique. E.g. what is 010? RGR or RB? Nonuniqueness here came from the fact that B ($`10`$) has the code of G ($`1`$) as the first string or prefix. A scheme which is prefix free is to be called a prefix code.

For our original example, we may choose $`\mathrm{R}0,\mathrm{G}10,\mathrm{B}110,\mathrm{Y}111`$ as a possible coding scheme to find that the average length required to transmit a colour is

$$l1\times \frac{1}{2}+2\times \frac{1}{4}+2\times 3\times \frac{1}{8}=\frac{7}{4}.$$
(9)
It is a simple exercise to show that any other method would only increase the average size. What is remarkable is that

$$\underset{i}{}p_i\mathrm{log}_2p_i=7/4,$$

an expression we are familiar with from the Gibbs entropy and also see in the Shannon theorem.

In case the source changes its pattern and starts sending signals with equal probability

$$p(\mathrm{R})=p(\mathrm{G})=p(\mathrm{B})=p(\mathrm{Y})=1/4,$$

we may adopt a different scheme with

$$\mathrm{R}00,\mathrm{G}10,\mathrm{B}01,\mathrm{Y}11,$$

for which the average length is

$$l=2=\underset{i}{}p_i\mathrm{log}_2p_i.$$

This is less than what we would get if we stick to the first scheme. Such simple schemes may not work for arbitrary cases as, e.g., for

$$p(\mathrm{R})=1/2,p(\mathrm{G})=\frac{1}{4}2ϵ,p(\mathrm{B})=p(\mathrm{Y})=\frac{1}{8}+ϵ.$$

In the first scheme we get $`l=\frac{7}{4}+2ϵ`$ while the second scheme would give $`l=2`$. In the limit of $`ϵ=1/8`$, we can opt for a simpler code

$$\mathrm{R}0,\mathrm{B}10,\mathrm{Y}11,\mathrm{with}l=3/2.$$

One way to reduce this length is then to make a list of all possible $`2^{NS}`$ strings, where $`S=p\mathrm{log}_2p`$ in some particular order and then transmit the item number of the message. This cannot require more than $`S`$ bits per character. We see the importance of the Gibbs formula but it is called the Shannon entropy.

#### III.2.4 Entropy

It is to be noted that the Shannon theorem looks at the ensemble and not at each string independently. Therefore the Shannon entropy $`S=_ip_i\mathrm{ln}p_i`$ is ensemble based, but as the examples of magnet or noninteracting gas showed, this entropy can be used to get the entropy of individual strings.

Given a set, like the colours in the above example, we can have different probability distributions for the elements. The Shannon entropy would be determined by that distribution. In the Kolmogorov case, we are assigning an “entropy” $`𝒮_j`$ to the $`j`$th long string or state but $`S_\mathrm{K}`$ is determined by the probabilities $`𝒫_j`$’s of the long strings which are in turn determined by the $`p`$’s of the individual characters. Since both refer to the best compression on the average, they have to be equivalent. It should however be noted that this equivalence is only in the limit and is a probability 1 statement meaning that there are configurations which are almost not likely to occur and they are not counted in the Shannon entropy. Instead of the full list to represent all the configurations (as we did in Eqs. (3) and (4)), it suffices to consider a smaller list consisting of the relevant or typical configurations. They are $`2^{N{\scriptscriptstyle p\mathrm{log}_2p}}`$ in number (see Appendix B for details), typically requiring $`S`$ bits per character. A physical example may illustrate this. Even though all configuration of molecules in a gas are allowed and should be taken into account, it is known that not much harm is done by excluding those configurations where all the molecules are confined in a small volume in one corner of a room. In fact giving equal weightage to all the configurations in Eq. (4) is one of the sources of approximations of meanfield theory.

## IV Statistical mechanics

We now try to argue that statistical mechanics can also be developed with the above entropy picture. To do so, we consider the conventional canonical ensemble, i.e., a system defined by a Hamiltonian or energy $`H`$ in contact with a reservoir or bath with which it can exchange only energy. In equilibrium, there is no net flow of energy from one to the other but there is exchange of energy going on so that our system goes through all the available states in phase space. This process is conventionally described by appropriate equations of motions but, though not done generally, one may think of the exchange as a communication problem. In equilibrium, the system is in all possible states with probability $`p_i`$ for the $`i`$th state and is always in communication with the reservoir about its configuration. The communication is therefore a long string of the states of the system each occurring independently and identically distributed (that’s the meaning of equilibrium). It seems natural to make the hypothesis that nature picks the optimal way of communication. We of course assume that the communication is noiseless. The approach to equilibrium is just the search for the optimal communication. While the approach process has a time dependence where the “time” complexity would play a role, it has no bearing in equilibrium and need not worry us. With that in mind, we may make the following postulates:

> (1) In equilibrium, the energy $`E=_ip_iE_i`$ remains constant.
> (2) The communication with the reservoir is optimal with entropy $`S=_ip_i\mathrm{ln}p_i`$ .
> (3) For a given average energy, the entropy is maximum to minimize failures in communication.

The third postulate actually assures that the maximum possible number of configurations ($`=2^S`$) are taken into account in the communication process. No attempt has been made to see if these postulates can be further minimized.

With these sensible postulates, we have the problem of maximizing $`S`$ with respect to $`p_i`$’s keeping $`E`$=constant and $`_ip_i=1`$. A straight forward variational calculation shows that $`p_i=\mathrm{exp}(\beta E_i)/Z`$ with $`Z=\mathrm{exp}(\beta E_i)`$ being the standard partition function. The parameter $`\beta `$ is to be chosen properly such that one gets back the average energy. The usual arguments of statistical mechanics can now be used to identify $`\beta `$ with the inverse temperature of the reservoir.

## V Summary

We have tried to show how the Kolmogorov approach to randomness may be fruitfully used to define entropy and also to formulate statistical mechanics. Once the equivalence with conventional approach is established, all calculations can then be done in the existing framework. What is gained is a conceptual framework which lends itself to exploitation in understanding basic issues of computations. This would not have been possible in the existing framework. This also opens up the possibility of replacing “engines” by “computers” in teaching of thermodynamics.

Acknowledgments

This is based on the C. K. Majumdar memorial talks given in Kolkata on 22nd and 23rd May 2003. I was fortunate enough to have a researcher like Prof. Chanchal Kumar Majumdar as a teacher in Science College. I thank the CKM Memorial Trust for organizing the memorial talk in Science College, Kolkata.

## Appendix A Toffoli gate

The truth table of the Toffoli gate is given below. With three inputs a,b,c, the output in c is the AND or NAND operation of a and b depending on c=0 or 1.

Fig. A1: Toffoli gate

| a | b | c | a | b | c |
| --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |

## Appendix B Proof of Shannon’s theorem

The statement of Shannon’s noiseless coding theorem is :

> If $`l`$ is the minimal average code length of an optimal code, then
>
> $$SlS+1$$
>
> where $`S=_jp_j\mathrm{log}_2p_j`$.

The adjective “noiseless” is meant to remind us that there is no error in communication. A more verbose statement would be

> If we use $`Nl`$ bits to represent strings of $`N`$ characters with Shannon entropy $`S`$, then a reliable compression scheme exists if $`l>S`$. Conversely, if $`l<S`$, no compression scheme is reliable.

The equivalence of the two statements can be seen by recognizing that $`S`$ need not be an integer but $`l`$ better be.

### B.1 Simple motivation

Let us first go through a heuristic argument to motivate Shannon’s coding theorem. Suppose a source is emitting signals $`\{𝖼_i\}`$ independently and identically distributed with two possible values $`𝖼_i=0`$ with probability $`p_1=p`$, and $`𝖼_i=1`$ with probability $`p_2=1p`$. For a long enough string $`𝒞𝖼_1𝖼_2𝖼_3𝖼_4\mathrm{}𝖼_N`$ the probability is

$`𝒫(𝒞)`$ $`=`$ $`p(𝖼_1)p(𝖼_2)p(𝖼_3)p(𝖼_4)\mathrm{}p(𝖼_N)`$ (10a)
$``$ $`p^{Np}(1p)^{N(1p)}`$ (10b)
$`=`$ $`2^{N[p\mathrm{log}_2p+(1p)\mathrm{log}_2(1p)]},`$ (10c)
because for large $`N`$ the number of expected $`0`$ is $`Np`$ and $`1`$ is $`N(1p)`$. This expression shows that the probability of a long string is determined by

$$S(\{p_j\})=[p\mathrm{log}_2p+(1p)\mathrm{log}_2(1p)],$$
(11)
the “entropy” for this particular problem. Note the subtle change from Eq. (10a) to Eq. (10b). This use of expectation values for large $`N`$ led to the result that most of the strings, may be called the “typical” strings, belong to a subset of $`2^{NS}`$ strings (out of total $`2^N`$ strings).

### B.2 What is “Typical”?

Let us define a typical string more precisely for any distribution. A string of $`N`$ symbols $`𝒞=𝖼_1𝖼_2𝖼_3𝖼_4\mathrm{}𝖼_N`$ will be called typical (or better $`ϵ`$-typical) if

$$2^{N(S+ϵ)}𝒫(𝒞)2^{N(Sϵ)},$$
(12)
for any given $`ϵ>0`$. Eq. (12) may also be rewritten as

$$ϵ\left[N^1\mathrm{log}_2𝒫(𝒞)\right]Sϵ$$
(13)
### B.3 How many typical strings?

Now, for random variables $`𝖼_i`$, $`X_i`$’s, defined by $`X_i=\mathrm{log}_2p(𝖼_i)`$, are also independent identically distributed random variables. It is then expected that $`\overline{X}=\frac{1}{N}_iX_i`$, the average value of $`X_i`$’s, averaged over the string for large $`N`$, should approach the ensemble average, namely, $`X=_jp_j\mathrm{log}_2p_j=S`$. This expectation comes from the law of large numbers that

$$\mathrm{Prob}\left[\left|N^1\underset{i}{}\mathrm{log}_2p(𝖼_i)S\right|<ϵ\right]\stackrel{N\mathrm{}}{}1,$$
(14)
for any $`ϵ>0`$. This means that given an $`ϵ`$ we may find a $`\delta >0`$ so that the above probability in Eq. 14 is greater than $`1\delta `$. Recognizing that

$$\underset{i}{}\mathrm{log}_2p(𝖼_i)=\mathrm{log}_2\underset{i}{}p(𝖼_i)=\mathrm{log}_2𝒫(𝒞),$$
(15)
Eq. (14) implies

$$\mathrm{Prob}\left[\left|N^1\mathrm{log}_2𝒫(𝒞)S\right|<ϵ\right]1\delta .$$
(16)
We conclude that the probability that a string is typical as defined in Eqs. (12) and (13) is $`1\delta `$.

Let us now try to estimate the number $`𝒩_{\mathrm{typ}}`$, the total number of typical strings. Let us use a subscript $`\mu `$ for the typical strings with $`\mu `$ going from $`1`$ to $`𝒩_{\mathrm{typ}}`$. The sum of probabilities $`𝒫_\mu `$’s of the typical strings has to be less than or equal to one, and using the definition of Eq. (12), we have one inequality

$$1\underset{\mu }{}𝒫_\mu \underset{\mu }{}2^{N(S+ϵ)}=𝒩_{\mathrm{typ}}2^{N(S+ϵ)}.$$
(17)
This gives $`𝒩_{\mathrm{typ}}2^{N(S+ϵ)}`$.

Let us now get a lower bound for $`𝒩_{\mathrm{typ}}`$. We have just established that the probability for a string to be typical is $`1\delta `$. Using the other limit from Eq. (12) we have

$$1\delta \underset{\mu }{}𝒫_\mu \underset{\mu }{}2^{N(Sϵ)}=𝒩_{\mathrm{typ}}2^{N(Sϵ)},$$
(18)
which gives $`𝒩_{\mathrm{typ}}(1\delta )2^{N(Sϵ)}`$. The final result is that the total number of typical strings satisfies $`2^{N(S+ϵ)}𝒩_{\mathrm{typ}}(1\delta )2^{N(Sϵ)}`$ where $`\delta >0`$ can be chosen small for large $`N`$. Hence, in the limit

$$𝒩_{\mathrm{typ}}2^{NS}.$$
(19)
### B.4 Coding scheme

Now let us choose a coding scheme that requires $`Nl`$ number of bits for the string of $`N`$ characters. Our aim is to convert a string to a bit string and decode it - the whole process has to be unique. Representing the coding and decoding by “operators” $`𝒞`$ and $`𝒟`$ respectively, and any string by $`𝖼|`$, what we want can be written in a familiar form

$`𝖼|𝒞|𝒟`$ $`=`$ $`𝖼|\mathrm{for}\mathrm{all}𝖼|,`$
$`\mathrm{𝚌𝚊𝚝}\mathrm{𝚖𝚢𝚏𝚒𝚕𝚎}|\mathrm{𝚐𝚣𝚒𝚙}|\mathrm{𝚐𝚞𝚗𝚣𝚒𝚙}`$ $`gives`$ $`\mathrm{𝚖𝚢𝚏𝚒𝚕𝚎}`$
where the last line is the equivalent “pipeline” in a UNIX or GNU/Linux system.

Let’s take $`l>S`$. We may choose an $`ϵ`$ such that $`l>S+ϵ`$. It is a trivial result that $`𝒩_{\mathrm{typ}}2^{N(S+ϵ)}<2^{Nl}`$. Here $`2^{Nl}`$ is the total number of possible bit strings. Hence all the typical strings can be encoded. Nontypical strings occur very rarely but still they may be encoded.

If $`l<S`$, then $`𝒩_{\mathrm{typ}}>2^{Nl}`$ and obviously all the typical strings cannot be encoded. Hence no coding is possible.

This completes the proof of the theorem.

## Appendix C Heat generated in a chip

As per a report of 1988, the energy dissipation per logic operation has gone down from $`10^3`$ joule in 1945 to $`10^{13}`$ joule in 1980’s. (Ref: R. W. Keyes, IBM J. Res. Devel. 32, 24 (1988) URL: http://www.research.ibm.com/journal/rd/441/keyes.pdf) For comparison, thermal energy $`k_BT`$ at room temperature is of the order of $`10^{20}`$ joule.

If one can pack $`10^{18}`$ logic gates in one cc operating at $`1`$ gigahertz with minimal dissipation of $`k_BT`$, it would release $`3`$ megawatts of energy. Can one cool that?

A more recent example. For a pentium 4 at 1.6GHz, if the cpu fan (that cools the CPU) is kept off, then during operations the cpu temperature may reach $`107C`$ (yes Celsius) as monitored by standard system softwares on an HCL made PC (used for preparation of this paper).


format: text

text:
# References and links

## 1 Introduction

Theoretical descriptions of photonic crystal fibers (PCFs) have traditionally been restricted to numerical evaluation of Maxwell’s equations. In the most general case, a plane wave expansion method with periodic boundary conditions is employed  while other methods, such as the multipole method , take advantage of the localized nature of the guided modes and to some extend the circular shape of the air-holes. The reason for the application of these methods is the relatively complex dielectric cross section of a PCF for which rotational symmetry is absent.

The aim of this work is to provide a set of numerically based empirical expressions describing the basic properties such as cutoff and mode-field radius of a PCF based on the fundamental geometrical parameters only.

## 2 Fiber geometry and numerical method

We consider the fiber structure first studied by Knight et al.  and restrict our study to fibers that consist of pure silica with a refractive index of 1.444. The air holes of diameter $`d`$ are arranged on a triangular grid with a pitch, $`\mathrm{\Lambda }`$. In the center an air hole is omitted creating a central high index defect serving as the fiber core. A schematic drawing of such a structure is shown in the inset of the right panel in Fig. 1.

Depending on the dimensions, the structure comprises both single- and multi-mode fibers with large mode area as well as nonlinear fibers. The results presented here cover relative air hole sizes, $`d/\mathrm{\Lambda }`$, from 0.2 to 0.9 and normalized wavelengths, $`\lambda /\mathrm{\Lambda }`$, from around 0.05 to 2. The modeling is based on the plane-wave expansion method with periodic boundary conditions . For the calculations of guided modes presented the size of the super cell was $`8\times 8`$ resolved by $`256\times 256`$ plane waves while for calculations on the cladding structure only, the super cell was reduced to a simple cell resolved by $`32\times 32`$ planes waves.

## 3 The $`V`$–parameter and the relative mode-field radius

When attempting to establish a simple formalism for the PCF it is natural to strive for a result similar to the $`V`$–parameter known from standard fibers . However, a simple translation is not straight forward since no wavelength-independent core- or cladding index can be defined. Recently, we instead proposed a formulation of the $`V`$–parameter for a PCF given by

$$V_{\mathrm{PCF}}=2\pi \frac{\mathrm{\Lambda }}{\lambda }\sqrt{n_{\mathrm{FM}}^2(\lambda )n_{\mathrm{FSM}}^2(\lambda )}$$
(1)
Although this expression has the same overall mathematical form as known from standard fibers, the unique nature of the PCF is taken into account. In Eq. (1), $`n_{\mathrm{FM}}(\lambda )`$ is the wavelength dependent effective index of the fundamental mode (FM) and $`n_{\mathrm{FSM}}(\lambda )`$ is the corresponding effective index of the first cladding mode in the infinite periodic cladding structure often denoted the fundamental space filling mode (FSM). For a more detailed discussion of this expression and its relation to previous work we refer to Ref.  and references therein. We have recently argued that the higher-order mode cut-off can be associated with a value of $`V_{\mathrm{PCF}}=\pi `$  and showed that this criterion is indeed identical to the single-mode boundary calculated from the multipole method . Recently the cut off results have also been confirmed experimentally . Further supporting the definition of $`V_{\mathrm{PCF}}`$ is the recent observation  that the relative equivalent mode field radius of the fundamental mode, $`w_{\mathrm{PCF}}/\mathrm{\Lambda }`$ as function of $`V_{\mathrm{PCF}}`$ fold over a single curve independent of $`d/\mathrm{\Lambda }`$. The mode field radius $`w_{\mathrm{PCF}}`$ is defined as $`A_{\mathrm{eff}}=\pi w_{\mathrm{PCF}}^2`$ and corresponds to the $`1/e^2`$ width of a Gaussian intensity distribution with the same effective area, $`A_{\mathrm{eff}}`$, as the fundamental mode itself .

In the left panel of Fig. 1, calculated curves of $`V_{\mathrm{PCF}}`$ as function of $`\mathrm{\Lambda }/\lambda `$ are shown for $`d/\mathrm{\Lambda }`$ ranging from 0.20 to 0.70 in steps of 0.05. In general, all curves are seen to approach constant levels dependent on $`d/\mathrm{\Lambda }`$. The horizontal dashed line indicates the single-mode boundary $`V_{\mathrm{PCF}}=\pi `$. In the right panel, $`w_{\mathrm{PCF}}/\mathrm{\Lambda }`$ is plotted as function of $`V_{\mathrm{PCF}}`$ for each of the 9 curves in the left panel and as seen all curves fold over a single curve. An empirical expression for $`w_{\mathrm{PCF}}/\mathrm{\Lambda }`$ can be found in Ref. . The mode is seen to expand rapidly for small values of $`V_{\mathrm{PCF}}`$ and the mode-field radius saturates toward a constant value when $`V_{\mathrm{PCF}}`$ becomes large. In fact, it turns out that $`w_{\mathrm{PCF}}/\mathrm{\Lambda }1.00`$ for $`V_{\mathrm{PCF}}=1`$ and $`w_{\mathrm{PCF}}/\mathrm{\Lambda }0.62`$ for $`V_{\mathrm{PCF}}=\pi `$. In the left panel of Fig. 2, curves corresponding to constant values of $`V_{\mathrm{PCF}}`$ are shown in a $`\lambda /\mathrm{\Lambda }`$ versus $`d/\mathrm{\Lambda }`$ plot. In the right panel, curves of constant $`w_{\mathrm{PCF}}/\mathrm{\Lambda }`$ is shown, also in a $`\lambda /\mathrm{\Lambda }`$ versus $`d/\mathrm{\Lambda }`$ plot. Since there is a unique relation between $`w_{\mathrm{PCF}}/\mathrm{\Lambda }`$ and $`V_{\mathrm{PCF}}`$  the curves naturally have the same shape.

When designing a PCF any combination of $`d`$ and $`\mathrm{\Lambda }`$ is in principle possible. However, in some cases the guiding will be weak causing the mode to expand beyond the core and into the cladding region  corresponding to a low value of $`V_{\mathrm{PCF}}`$. In the other extreme, the confinement will be too strong allowing for the guiding of higher-order modes . Since both situations are governed by $`V_{\mathrm{PCF}}`$ the design relevant region in a $`\lambda /\mathrm{\Lambda }`$ versus $`d/\mathrm{\Lambda }`$ plot can be defined. This is done in Fig. 3 where the low limit is chosen to be $`V_{\mathrm{PCF}}=1`$ where $`w_{\mathrm{PCF}}/\mathrm{\Lambda }1`$. How large a mode that can be tolerated is of course not unambiguous. However, for $`w_{\mathrm{PCF}}\mathrm{\Lambda }`$ leakage-loss typically becomes a potential problem in PCFs with a finite cladding structure. In non-linear PCFs it is for dispersion reasons often advantageous operating the PCF at $`V_{\mathrm{PCF}}1`$ and then a high number of air-hole rings is needed to achieve an acceptable level of leakage loss .

Finally, we note that the practical operational regime is also limited from the low wavelength side. In Ref.  a low-loss criterion was formulated in terms of the coupling length $`z_c=\lambda /[n_{\mathrm{FM}}(\lambda )n_{\mathrm{FSM}}(\lambda )]`$ between the FM and the FSM. In general scattering-loss due to longitudinal non-uniformities increases when $`z_c`$ increases and a PCF with a low $`z_c`$ will in general be more stable compared to one with a larger $`z_c`$. Using $`n_{\mathrm{FM}}+n_{\mathrm{FSM}}2n_{\mathrm{FM}}2n_{\mathrm{silica}}`$ we can rewrite Eq. (1) as

$$V_{\mathrm{PCF}}\frac{\mathrm{\Lambda }}{\lambda }\sqrt{\frac{\lambda }{z_c(\lambda )}}$$
(2)
from which it is seen that a high value of the $`V`$–parameter is preferred over a smaller value. In Fig. (3) it is thus preferable to stay close to the single-mode boundary ($`V_{\mathrm{PCF}}\pi `$) but in general there is a practical lower limit to the value of $`\lambda /\mathrm{\Lambda }`$ which can be realized because when $`\lambda /\mathrm{\Lambda }0.1`$ one generally has that $`z_c\lambda `$ .

## 4 $`V`$–parameter expression

Although the $`V`$–parameter offers a simple way to design a PCF, a limiting factor for using Eq. (1) is that a numerical method is still required for obtaining the effective indices. In analogy with expressions for standard fibers  it would therefore be convenient to have an alternative expression only dependent on the wavelength, $`\lambda `$, and the structural parameters $`d`$ and $`\mathrm{\Lambda }`$. In Fig. 4, we show $`V_{\mathrm{PCF}}`$ as function of $`\lambda /\mathrm{\Lambda }`$ (data are shown by open circles) for $`d/\mathrm{\Lambda }`$ ranging from 0.20 to 0.80 in steps of 0.05. Each data set in Fig. 4 is fitted to a function of the form

$$V_{\mathrm{PCF}}(\frac{\lambda }{\mathrm{\Lambda }},\frac{d}{\mathrm{\Lambda }})=\frac{𝒜\left(\frac{d}{\mathrm{\Lambda }}\right)}{\left(\frac{d}{\mathrm{\Lambda }}\right)\times \mathrm{exp}\left[𝒞\left(\frac{d}{\mathrm{\Lambda }}\right)\times \frac{\lambda }{\mathrm{\Lambda }}\right]+1}$$
(3a)
and the result is indicated by the full red lines. Eq. (3a) is not based on considerations of the physics of the V-parameter but merely obtained by trial and error in order to obtain the best representation of calculated data with the lowest possible number of free parameters. Prior to the fit, the data sets are truncated at $`V_{\mathrm{PCF}}=0.5`$ since $`w_{\mathrm{PCF}}2\mathrm{\Lambda }`$ in this region (see left panel in Fig. 1) and the data is thus not practically relevant. In Eq. (3a) the fitting parameters $`𝒜`$, $``$, and $`𝒞`$ depend on $`d/\mathrm{\Lambda }`$ only. In order to extract this dependency, suitable functions (again obtained by trial and error) are fitted to the data sets for $`𝒜`$, $``$, and $`𝒞`$. We find that the data are well described by the following expressions
$$𝒜\left(\frac{d}{\mathrm{\Lambda }}\right)=\frac{d}{\mathrm{\Lambda }}+0.457+\frac{3.405\times \frac{d}{\mathrm{\Lambda }}}{0.904\frac{d}{\mathrm{\Lambda }}}$$
(3b)
$$\left(\frac{d}{\mathrm{\Lambda }}\right)=0.200\times \frac{d}{\mathrm{\Lambda }}+0.100+0.027\times \left(1.045\frac{d}{\mathrm{\Lambda }}\right)^{2.8}$$
(3c)
$$𝒞\left(\frac{d}{\mathrm{\Lambda }}\right)=0.630\times \mathrm{exp}\left(\frac{0.755}{0.171+\frac{d}{\mathrm{\Lambda }}}\right)$$
(3d)
The above set of expressions, Eqs. (3), constitute our empirical expression for the $`V`$–parameter in a PCF with $`\lambda /\mathrm{\Lambda }`$ and $`d/\mathrm{\Lambda }`$ being the only input parameters. For $`\lambda /\mathrm{\Lambda }<2`$ and $`V_{\mathrm{PCF}}>0.5`$ the expression gives values of $`V_{\mathrm{PCF}}`$ which deviates less than $`3\%`$ from the correct values obtained from Eq. (1).

## 5 Endlessly single-mode criterion

The term endlessly single-mode (ESM) refers to PCFs which regardless of wavelength only support the two degenerate polarization states of the fundamental mode . In the framework of the $`V`$–parameter this corresponds to structures for which $`V_{\mathrm{PCF}}<\pi `$ for any $`\lambda /\mathrm{\Lambda }`$ . As seen in the left panel of Fig. 1 this corresponds to sufficiently small air holes. However, from the plot in Fig. 1 it is quite difficult to determine the exact $`d/\mathrm{\Lambda }`$ value for which $`V_{\mathrm{PCF}}=\pi `$ for $`\lambda `$ approaching 0. From Eq. (3) it is easily seen that the value may be obtained from

$$\underset{\lambda 0}{lim}V_{\mathrm{PCF}}(\frac{\lambda }{\mathrm{\Lambda }},\frac{d}{\mathrm{\Lambda }})=\frac{𝒜\left(\frac{d}{\mathrm{\Lambda }}\right)}{\left(\frac{d}{\mathrm{\Lambda }}\right)+1}=\pi .$$
(4)
Fig. 5 illustrates this equation graphically where we have extrapolated the data in Fig. 4 to $`\lambda =0`$. From the intersection of the full line with the dashed line we find that $`d/\mathrm{\Lambda }0.43`$ bounds the ESM regime. Solving Eq. (4) we get $`d/\mathrm{\Lambda }0.44`$ and the deviation from the numerically obtained value is within the accuracy of the empirical expression.

## 6 Conclusion

There are several issues to consider when designing a PCF. In this work we have addressed the single/multi-mode issue as well as those related to mode-field radius/field-confinement, and mode-spacing. We have shown how these properties can be quantified via the $`V`$–parameter. Based on extensive numerics we have established an empirical expression which facilitate an easy evaluation of the $`V`$-parameter with the normalized wavelength and hole-size as the only input parameters. We believe that this expression provides a major step away from the need of heavy numerical computations in design of solid core PCFs with triangular air-hole cladding.

## Acknowledgments

We thank J. R. Folkenberg for stimulating discussion and M. D. Nielsen acknowledges financial support by the Danish Academy of Technical Sciences.


text:
# Magnetotransport in Single Crystal Half-Heusler Compounds

## Abstract

We present the results of electrical resistivity and Hall effect measurements on single crystals of HfNiSn, TiPtSn, and TiNiSn. Semiconducting behavior is observed in each case, involving the transport of a small number of highly compensated carriers. Magnetization measurements suggest that impurities and site disorder create both localized magnetic moments and extended paramagnetic states, with the susceptibility of the latter increasing strongly with reduced temperature. The magnetoresistance is sublinear or linear in fields ranging from 0.01 - 9 Tesla at the lowest temperatures. As the temperature increases, the normal quadratic magnetoresistance is regained, initially at low fields, and at the highest temperatures extending over the complete range of fields. The origin of the vanishingly small field scale implied by these measurements remains unknown, presenting a challenge to existing classical and quantum mechanical theories of magnetoresistance.

One of the most exotic settings for small gap insulators is among materials made entirely of metals, i.e. intermetallic compounds. Nonetheless, it was demonstrated in the early 1990’s that a subset of the half-Heusler compounds, with the generic formula RNX (R,N are transition metal elements, and X is a main group element), display semiconducting transport while infrared absorption experiments found semiconducting gaps with magnitudes of $``$100 meV or less aliev1989 ; aliev1990 . In subsequent years, these materials were found to have a substantial thermopower aliev1990 ; cook1996 , and a number of different compositions were explored uher1999 ; hohl1998 ; mastronardi1999 ; tobola1998 ; kasaya1992  in the hopes of optimizing these characteristics. All of these experiments were carried out on polycrystalline samples, and since annealing dramatically affected their transport properties aliev1990 ; uher1999 , it was clear that the samples were unlikely to be either stoichiometric, or single phase. Understanding the intrinsic behaviors of these unusual materials has awaited the synthesis of single crystal samples, which we report here.

Many intermetallic compounds form in the Heusler structure RN2X, with four interpenetrating face centered cubic lattices, where the N elements lie at the center of the rock-salt cube formed by the R and X elements. The half-Heuslers are a variant on this structure, where one of the sublattices is entirely vacant, implying that now the N atoms ideally occupy every other rock-salt cube. This MgAgAs structure is found in intermetallic compounds with 16-20 electrons per formula unit z, but most often when z=18 as in the RNiSn (R=Ti, Zr, and Hf) dwight1974 . Of the known half-Heusler compounds hohl1999 , only a few are thought to be insulating in the absence of disorder: RNiSn (R= Ti, Zr, and Hf) and RNSn (R=Zr and Hf, N=Pd and Pt) aliev1989 , LnPdSb (Ln=Ho,Er, Dy) mastronardi1999 , LnPtSb (Ln=trivalent rare earth) kasaya1992 , CoTiSb and CoNbSn tobola1998 , and NbIrSn hohl1998 . Studies of half-Heusler systems in which the electron count is changed systematically pierre1994 ; tobola1996 ; tobola1998  reveal that insulating behavior is generally observed near z=18, while metallic and sometimes magnetically ordered systems are found at both higher and lower electron counts. We note that this result is based largely on resistance measurements carried out on polycrystalline samples, and that site disorder is potentially large in the half-Heusler structure, even for nominally stoichiometric compositions aliev1989 ; uher1999 . For these reasons, the exact range of intrinsic insulating behavior, is still experimentally uncertain. Electronic structure calculations ogut1995  support the view that the semiconducting behavior found in the RNiSn (R=Ti,Zr, Hf) is an intrinsic feature, finding indirect gaps between the $`\mathrm{\Gamma }`$ and X points in each compound. The gap is determined by the strength of the R-Sn pd hybridization, which leads to anticrossing of the extrema of the conduction and valence bands, which have primarily R dxy character. The anticrossing is further amplified through an indirect interaction of the R states mediated by low lying Ni states. Nonetheless, the indirect gaps in TiNiSn, ZrNiSn, and HfNiSn are expected to be nearly identical, $``$ 0.5 eV.

The purposes of this paper are two fold. First, we report the results of transport and magnetization experiments on single crystals of TiNiSn, HfNiSn, and TiPtSn. For comparision, similar experiments were carried out on polycrystalline samples as well. These measurements show that the semiconducting behavior found in polycrystalline samples is at least partly intrinsic, although electron microscopy evidence is presented which reveals substantial metallurgical phase separation in all polycrystalline samples. All of the samples, both single crystal and polycrystalline, are weakly magnetic, due to the presence of both extended and localized moment bearing defect states. The Hall constant is unusually small, suggesting a near balance of electrons and holes. While our original objective was to establish the RNiSn as intrinsic semiconductors by measuring single crystals instead of polycrystals, we found in addition that the magnetotransport is anomalous in this family of compounds. The second section of this paper is devoted to a description of the linear magnetoresistance found above a field scale which grows linearly with temperature, and which varies only moderately among our different samples.

Polycrystalline samples of HfNiSn were prepared by arc melting in a high purity Ar atmosphere, followed by high temperature vacuum annealing. An electron backscattering image of the as cast material is shown in Fig. 1a, revealing that most of the sample is near-stoichiometric HfNiSn, but that there are additional phases at the boundaries of the grains. Microprobe measurements find that these phases are roughly equal quantities of Hf5Sn4 and the Heusler compound HfNi2Sn, together making up about 4$`\%`$ of the total as cast sample volume. After annealing the as cast material in vacuum at 1000 C for 720 hours aliev1989 , the grain boundary phases are much reduced in volume (Fig. 1b), and we presume that the composition of the grains approaches the stoichiometric level. Annealing had very similar effects on both TiNiSn and ZrNiSn polycrystals, which were found to undergo even more extensive phase separation. We also attempted to introduce B,Ta,Lu,Co,Mn,U,and Ce into HfNiSn and ZrNiSn as dopants. In every case, the dopants were segregated in the grain boundary phases, with no measurable solubility in the HfNiSn and ZrNiSn grains. We note that earlier efforts to dope the RNiSn also employed some of these elements hohl1999 ; uher1999 ; slebarski1998 , and our results suggest that the primary effects of doping observed in these works likely result from modifications to the conducting properties of the grain boundary phases, and not from changes in the RNiSn matrix itself. We also experimented with shorter anneals at higher temperatures. Fig. 1c shows that a 72 hour anneal at 1300 C significantly decreases the volume of grain boundary phases, which is now largely Hf5Sn4, although higher levels of HfNi2Sn and significant Sn loss from the matrix are observed near the surface of the polycrystalline sample. Due in part to these concerns about sample homogeneity, single crystals of HfNiSn were prepared at the University of Amsterdam/Leiden University ALMOS facility using the tri-arc assisted Czolchralski method, while single crystals of TiNiSn and TiPtSn were synthesized at Ames Laboratory from a Sn flux canfield1992 . The crystal structures of all HfNiSn samples, both single crystal and polycrystal, were verified to be the MgAgAs type by powder x-ray diffraction.

We have studied these samples using both magnetization measurements, carried out using a Quantum Designs SQUID magnetometer, and electrical transport measurements, which employed both a Quantum Designs Physical Phenomena Measurement System and homebuilt helium cryostat systems. The resistivity and Hall effect measurements were performed at a frequency of 17 Hz, in the conventional four-probe and five probe configurations, respectively. Sweeps in positive and negative fields were combined to separate the mixed Hall signal and longitudinal magnetoresistance at each temperature. Special care was taken to avoid heating by the measuring current, especially at the lowest temperatures.

Sample homogeneity has a profound effect on the transport observed in the half-Heuslers. Fig. 2 depicts the temperature dependent resistivity for four different samples of HfNiSn: single crystal, as cast polycrystal, and polycrystal annealed for 720 hours at 1000C (optimally annealed), and 72 hours at 1300 C. The resistivity increases slowly with decreasing temperature in the as cast material and reaches a broad maximum near 120 K, before decreasing and displaying a superconducting transition near 3.8 K. The superconductivity is easily suppressed with modest fields, and since it is absent in the optimally annealed and single crystal samples we ascribe it to the grain boundary phases, or to trace amounts of elemental Sn. The resistivity of the optimally annealed polycrystalline sample reproduces the insulating behavior of the single crystal, although its resistivity is more than an order of magnitude smaller for the entire temperature range. The 72 hour/1300C anneal has an intermediate effect, marginally increasing the measured resistivity over that of the as-cast sample, while rendering it insulating down to the superconducting transition. We conclude from the data in Fig. 2 that the grain boundary phases are highly conducting relative to the matrix, but that once they are removed by annealing HfNiSn is intrinsically a semiconductor, as previously claimed on the basis of experimental evidence gathered from the polycrystalline samples aliev1989 .

Despite their intermetallic character, the single crystals of HfNiSn, TiNiSn, and TiPtSn all display semiconducting behavior, as predicted for filled d-band half-Heuslers ogut1995 . Fig. 3a shows the temperature dependences of the electrical resistivity of samples of all three materials, showing the behavior typical of n-type semiconductors. The activation plots of Fig. 3b are not linear over the entire range of temperatures investigated. In every case, the resistivity slowly approaches a constant value at the lowest temperatures, but in addition there are regions of distinctly different slopes, especially for TiNiSn. These results indicate the presence of narrow bands of impurity/defect states in the semiconducting gap, with excitation energies which are smaller than the semiconducting gap itself. The highest temperature transport gaps are very small: 26 meV for HfNiSn, 28 meV for TiPtSn, and 79 meV for TiNiSn. The estimates for the transport gaps in HfNiSn and TiNiSn are much smaller than the values previously reported for polycrystals aliev1989 , as well as being smaller than the indirect gap of 0.5 eV predicted by electronic structure calculations for TiNiSn and HfNiSn ogut1995 .

Hall effect measurements have been carried out on single crystals of HfNiSn, TiNiSn and TiPtSn, in order to estimate the number and type of carriers present. The data are presented in Fig. 4a. No Hall signal was detected in single crystal or polycrystalline HfNiSn in fields as large as 9 Tesla, and for temperatures between 1.2 K and 12 K. Our experimental accuracy consequently yields only an lower bound for a single band carrier concentration n of 5x1021 cm-3, which is more than one carrier per unit cell. The Hall constant in TiPtSn is just at the limits of our experimental resolution, and also indicates a large carrier concentration $``$ 1x1021cm3. In view of the semiconducting characters of single crystal HfNiSn and TiPtSn, we view these single band carrier concentrations as unreasonably high. We consider it more likely that both HfNiSn and TiPtSn are very close to perfect compensation, and perhaps may even be semimetals. In contrast, a large Hall voltage was detected in TiNiSn, linear in field and with a slope which indicates that the dominant carriers are electrons. The temperature dependence of the electron concentration n deduced from these measurements is plotted in Fig. 4b, showing a strong increase with reduced temperature, amounting to an increase by approximately one electron per 365 unit cells between 40 K and the approximately constant value of 1x1019 cm-3 found below 15 K. It is significant that the low temperature electron concentration in TiNiSn is approximately the same as the number of paramagnetic moments inferred from the magnetization measurements, which we discuss next.

All of the single crystal and polycrystalline samples we measured are weakly magnetic, despite the nominally nonmagnetic character expected for the filled-d shell half-Heusler compounds. The field dependence of the magnetization of polycrystalline HfNiSn, annealed for 720 hours at 1000 C, is presented in Fig. 5a, while similar data for single crystal TiNiSn appear in Fig. 5b. In both cases, the magnetization is strongly nonlinear, especially at low fields and low temperatures. As the temperature is raised, the magnetization is increasingly dominated by a diamagnetic contribution, linear in field, which is especially evident for the TiNiSn sample. The magnetization M divided by a constant measuring field of 1.5 T is plotted in Fig. 6 as a function of temperature for three different samples: polycrystalline HfNiSn, both as cast and annealed for 720 hours at 1000 C, as well as single crystal TiNiSn. Fig. 6 shows that the paramagnetic contribution to the magnetization is largest at low temperatures, but is superposed on a diamagnetic contribution. It is evident that the magnitudes of the paramagnetic and diamagnetic components, as well as their relative weights, vary considerably among the samples we investigated.

Figures 5 and 6 suggest that it may be possible to separate the two components of the magnetization by modelling the magnetization in each sample as M(H,T) = $`\chi _o`$H+$``$(H/T). The first term represents a field independent susceptibility, which we will show combines the normal diamagnetic susceptibility of the semiconducting host, with an additional Pauli paramagnetic susceptibility, which varies among samples. Given the small magnitude of the moments shown in Fig. 5, we think it unlikely that long range magnetic order is responsible for the nonlinear magnetization found at low temperatures. Instead, we suggest that the second term represents the scaling behavior of isolated and localized magnetic moments, where $``$ is consequently expected to be the Brillouin function.

The results of this modelling are shown in Fig. 7, which demonstrates that the magnetization sweeps taken in both samples for temperatures which range from 2 K - 20 K collapse onto scaling curves if a diamagnetic term is previously subtracted from the data at each temperature. As indicated, the scaled and corrected magnetizations for HfNiSN and TiNiSn are well described by J=1/2 Brillouin functions, yielding moment densities of 1.98x10-3$`\mu _B`$ per formula unit TiNiSn and 1.55x10-3$`\mu _B`$ and 0.144 $`\mu _B`$ per formula unit HfNiSn for the two annealed and polycrystalline HfNiSn samples investigated. We find that the diamagnetic susceptibilities $`\chi _o`$ of the three systems are also very different, as Fig. 6 suggests. These susceptibilities are plotted in Fig. 8, showing that $`\chi _o`$ is much larger for TiNiSn than for either HfNiSn sample, although $`\chi _o`$ varies by almost an order of magnitude between the two HfNiSn samples. While $`\chi _o`$ approaches a constant value at low temperature in one of the polycrystalline HfNiSn samples (filled circles), in each of the three samples, $`\chi _o`$ increases approximately linearly with temperature.

The pronounced temperature and sample dependences of $`\chi _o`$ which are demonstrated in Fig. 8 argue strongly for the presence of a paramagnetic contribution to the magnetization which is linear in field. The susceptibility of a semiconductor is approximated by the sum of the core susceptibilities of the constituent atoms: -4.8x10-5 emu/g for HfNiSn and -3.7x10-5 for TiNiSnselwood1956 , and is consequently independent of temperature and invariant among samples of the same nominal composition. The values we find for $`\chi _o`$ in HfNiSn and TiNiSn do not approach these limits on the temperature range of our experiment, suggesting the presence of an additional positive magnetization, linear in field and decreasing in magnitude with increasing temperature. The variation of $`\chi _o`$ between the two HfNiSn samples suggests that this inferred positive susceptibility has an extrinsic origin, consistent with the small magnitude of the local moments found in each sample, and with the variations in moment concentrations found among different samples.

We conclude that there are two magnetic entities present with different relative weights in each of our half-Heusler samples, superposed on the diamagnetic response of the semiconducting host. The first entities are localized magnetic moments, perhaps generated by the inevitable site disorder characteristic of the half-Heusler structure. Still, the level of this putative disorder can be quite low, corresponding to only one defect per 7000 unit cells in our least magnetic HfNiSn sample. Secondly, we propose that there are also extended and metallic states present which are responsible for the inferred paramagnetic susceptibility. In agreement with Hall effect measurements on TiNiSn, the number of these metallic states grows with decreasing temperature. It is interesting that the electron concentration in TiNiSn is similar to the concentration of localized magnetic moments, suggestive that both have the same origin, presumably defects or impurities. Further, the data suggest that the electron contributed by each impurity or defect in TiNiSn ultimately becomes delocalized as T$``$0, which is, intriguingly, just what is expected if the moment bearing impurities are compensated by the Kondo effect.

Perhaps the most striking property of the nonmetallic half-Heusler compounds is their magnetoresistance, which is linear or even sublinear in field at the lowest temperatures. The anomalous magnetoresistance has been observed in every half-Heusler compound we have measured, both single crystals and polycrystals, both as cast and annealed. This is demonstrated in Fig. 9 which presents the 2 K magnetoresistances of HfNiSn, TiPtSn, and TiNiSn single crystals, and HfNiSn polycrystal, both as cast and annealed for 720 hours at 1000C. The magnetoresistances of the single crystal samples are markedly sublinear, while those of the polycrystalline samples are more highly linear. In neither case is there any suggestion of a quadratic magnetoresistance, down to fields as small as 1000 Oe. We note that trace superconductivity in the polycrystalline samples prohibits measurements to fields less than $``$ 500 Oe. The magnitude of the magnetoresistance is rather modest, amounting to a few percent in each of the crystalline samples. It approaches 10$`\%`$ at 9 T in the as-cast polycrystalline sample, although annealing reduces the magnetoresistance to the level observed in the single crystals. This may result either from a compactification of the internal structure of the polycrystals, since annealing removes conducting grain boundaries, or from rendering the HfNiSn grains more nearly stoichiometric, as in the single crystal.

The low field magnetoresistance of all samples ultimately becomes quadratic in field if the temperature is increased sufficiently. The longitudinal magnetoresistance of single crystal HfNiSn is presented at several temperatures in Fig. 10, with an expanded low field region in the inset. At 2 K, the magnetoresistance is sublinear over our entire field range, and is never quadratic, even at the lowest fields. At 4 K, the magnetoresistance is linear over virtually the entire range of fields studied, with little trace of the upward curvature which emerges at the lowest fields at 6 K. Raising the temperature still furthur yields a range of fields for which quadratic magnetoresistance is found. This is demonstrated in Fig. 11, where the magnetoresistance of single crystal HfNiSn is plotted as a function of H2. At 30 K and above, the magnetoresistance is quadratic in field for the entire range of fields studied, 0.01 -9 T. As the temperature is lowered, clear departures from $`\mathrm{\Delta }\rho `$/$`\rho `$ $``$ H2 are observed, below fields H which become progressively smaller as the temperature is reduced. This analysis has been repeated on all of our samples, and the results are summarized in Fig. 12. It is evident that the range of fields H$``$H and temperatures for which $`\mathrm{\Delta }\rho `$/$`\rho `$ $``$ H2 varies considerably among the different samples. For instance, the magnetoresistance of the annealed sample of HfNiSn(open circles, Fig. 12) is quadratic in fields up to 9 T for all temperatures above 15 K, while clear departures are still evident at temperatures as large as 100 K for an as cast polycrystalline sample of HfNiSn(open squares, Fig. 12).

Fig. 12 may be viewed as an organizational scheme for our magnetoresistance observations, analagous to a phase diagram, where H(T) represents a crossover from a regime at low fields where the magnetoresistance is quadratic in field, to a regime at high fields where the magnetoresistance is linear or even sublinear in field. In agreement with the discussion of Fig. 9, the linear magnetoresistance is seen for the widest range of temperatures in the as cast polycrystalline samples, while annealing confines the linear magnetoresistance to the lowest temperatures and highest fields. H(T) for the single crystals is similar to that of the most homogeneous polycrystalline samples, which have been annealed for the longest times.

The observation of a linear or sublinear magnetoresistance is anomalous, as the magnetoresistance typically depends on the field magnitude, yielding a magnetoresistance which is even and usually quadratic in the applied field. Nonetheless, there are a few circumstances in which a linear magnetoresistance is expected. A linear magnetoresistance can occur in inhomogeneous materials, resulting from the accidental admixture of the Hall signalherring1960 . We rule out this possibility for the half-Heuslers, as we observe linear magnetoresistance in single crystals, and further since the Hall signal is immeasurably small, especially in HfNiSn and TiPtSn. Similarly, a variety of different mechanisms can lead to linear magnetoresistance in systems with large carrier concentrationsbudko1998 ; young2003 , but in most cases their application to the minimally magnetic and essentially semiconducting half-Heuslers seems tenuous. Finally, we note that there is no evidence for either magnetic or structural transitions, which might provide an internal symmetry breaking field, superseding the applied field.

Linear magnetoresistance is expected in metals with closed Fermi surface orbits at intermediate fields, in a crossover regime between the quadratic magnetoresistance expected at low fields, and saturation at high fields. The range of fields over which linear magnetoresistance can be observed is potentially quite extensive for materials with a high degree of compensation pippard1989 . However, this linear crossover regime emerges when the product of the cyclotron frequency $`\omega _c`$ and the scattering time $`\tau `$ exceeds one, $`\omega _c\tau `$1. For TiNiSn at 2 K, where n=1.3x1019 and $`\rho `$=18$`\mathrm{\Omega }`$-cm, $`\omega _c\tau `$=1 for an applied field of 3.7x105 Tesla. Indeed, this crossover field could be considerably larger if we consider that the Hall measurements provide only a lower bound on the total number of carriers, which may be electrons as well as holes. Conversely, if we assume that this crossover field is no more than 100 Oe, consistent with our lowest temperature magnetoresistance results on single crystal HfNiSn and TiPtSn, we would require a total carrier concentration of $``$3x1013cm-3. It is difficult to believe that the numbers of electrons and holes present in both our single crystal and polycrystalline samples are balanced at the level of one carrier per 108 unit cells, as the absence of a Hall signal suggests. We are forced to conclude that in each of our samples, linear or sublinear magnetoresistance is observed for a wide range of fields which are comfortably in the low field limit $`\omega _c\tau `$1.

Linear magnetoresistance is also predicted theoretically for a low density electron gas, in which only the lowest Landau level is occupied abrikosov1969 ; abrikosov1998 ; abrikosov2000 . The two requirements for realizing this quantum magnetoresistance are that H$``$($`\mathrm{}`$cn)2/3, and that T$``$eH$`\mathrm{}`$/mc. Consequently, the linear magnetoresistance should only be observed in TiNiSn at fields greater than 36 Tesla, and for temperatures T$``$1.35 (K/T)H. It is possible that the latter condition is satisfied in the half-Heusler compounds, since as Fig. 11 demonstrates, the linear magnetoresistance is only observed above a field H which increases linearly with temperature. In this view, the different slopes found in the plot of H(T) for the different systems (Fig. 11) could plausibly be the result of variations in magnitude of the effective mass between the least massive (m/m=0.09 in as cast HfNiSn 99106) and the heaviest (m/m=0.58 in single crystal TiPtSn). Nonetheless, our observation of linear magnetoresistance in TiNiSn in fields as small as 0.01 T, where the criterion H$``$($`\mathrm{}`$cn)2/3 is dramatically violated is problematic for the quantum magnetoresistance theory as well. One possibility is that only a tiny fraction of the carriers detected by the Hall effect in TiNiSn, one carrier in $``$ 2x105, actually participates in the quantum magnetoresistance. We note that a similar explanation has been proposed abrikosov1998  as an explanation for the linear magnetoresistance observed in doped silver chalcogenide compounds husmann2002 ; lee2002 ; xu1997 ; schnyders2000 . Here, spatial separation of conducting and insulating regions was invoked to achieve the needed reduction in effective carrier concentration, a scenario which is inapplicable to the single crystal half-Heuslers. The central dilemma lies with explaining the unexpected persistance of the linear and sublinear magnetoresistance to extremely low fields, particularly at low temperatures. If the linear magnetoresistance observed in the half-Heuslers derives from the scattering of fully quantum mechanical states, then our measurements suggest a less restrictive set of necessary conditions than has been theoretically proposed.

It is unclear whether the linear magnetoresistances found in the half-Heuslers and the silver chalcogenides arise from the same fundamental mechanism. Certainly there are general resemblences between the doped silver chalcogenides and the semiconducting half-Heuslers, as both systems are nonmagnetic semiconductors, with small or vanishing values of the Hall constant. We note that the single crystal half-Heuslers generally have larger resistivities, and as far as is known, electron concentrations which are similar to those in optimally doped Ag2-δTelee2002 . The progression of the magnetoresistance from sublinear, to linear, and ultimately to quadratic field dependencies is achieved by increasing temperature and consequently decreasing electron concentration in the half-Heuslers. In contrast, temperature has a very modest effect on the linear magnetoresistance found in the doped silver chalcogenidesxu1997 , although the same progression of field dependencies is achieved in this system by using high pressures to drive the Hall constant through zerolee2002 . A similar sensitivity to carrier density is apparently absent in the half-Heuslers, since the magnetoresistances of single crystal HfNiSn, TiPtSn, and TiNiSn are very similar in magnitude, despite their very different electron concentrations. Finally, we note that the magnetoresistances of the single crystal half-Heuslers are also much smaller than those of the silver chalcogenides, and the uniformly larger magnetoresistance found in as-cast polycrystalline half-Heusler samples may support the suggestion that compositional inhomogeneities, present only in the polycrystalline half-Heusler samples, are required to obtain large, linear magnetoresistancesabrikosov1998 ; lee2002 .

We have established here that single crystals of several half-Heusler compounds, selected to have a total of 18 valence electrons, are small gap insulators, in agreement with both electronic structure calculations and previous measurements on polycrystalline samples. Resistivity measurements show that HfNiSn, TiPtSn, and TiNiSn single crystals are all semiconducting, while magnetization measurements argue that both localized magnetic and extended states are introduced with impurities or site interchange disorder. Hall effect measurements indicate that the number of electrons and holes is closely balanced in HfNiSn and TiPtSn, although there is a pronounced excess of electrons in TiNiSn. Both the corresponding electron concentration and the inferred Pauli susceptibility in TiNiSn increase with decreasing temperature, which may signal the return via the Kondo effect of electrons to the Fermi surface which were formerly localized at high temperatures in magnetic impurity states.

Our results deepen the mystery surrounding the origin of linear magnetoresistance in materials with small carrier densities. Neither the classical nor quantum mechanical theories of the magnetoresistance can countenance the persistance of the linear magnetoresistance to fields as low as 0.01 T, given the mobility and carrier densities characteristic of both half-Heuslers and the doped silver chalcogenides. The observation of the linear magnetoresistance in single crystals of the half-Heuslers, which are presumed to be compositionally homogeneous on the shortest length scales, removes a degree of freedom present in the doped silver chalcogenides. Barring another mechanism which dramatically limits the number of electrons responsible for the linear magnetoresistance in the half-Heuslers, a new explanation for the origin of the miniscule field scale in these unusual materials must be sought.

We acknowledge stimulating discussions with C. M. Varma, as well as the assistance of S. Ramakrishnan in early stages of the sample synthesis. MCA is grateful to the Dutch NWO and FOM for partial support during a sabbatical visit to Leiden University, where this project was initiated. Work at the University of Michigan was performed under the auspices of the U. S. Department of Energy under grant DE-FG02-94ER45526. MCB acknowledges partial financial support from NHMFL-Los Alamos. EMS acknowledges partial financial support from CONACYT(Mexico) through Grant No. 39643-F. This manuscript has been authored by Iowa State University of Science and Technology under Contract No. W-7405-ENG-82 with the U. S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a nonexclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes.


text:
# Galois characterization of Endoscopy for rational Siegel modular forms

## 1 The Theorem

Let $`f`$ be a genus $`2`$ Siegel cuspidal Hecke eigenform of weight $`k>2`$ and $`_f`$ the number field generated by its eigenvalues. It is well known that if $`f`$ is not of Saito-Kurokawa type but it is “endoscopic” (i.e., it is in the image of the weak endoscopic lift) the compatible family of Galois representations $`\{\rho _{f,\lambda }\}`$ attached to $`f`$ (constructed by Taylor, Laumon and Weissauer for any Siegel cusp form) will be reducible over $`_f`$ , with two $`2`$-dimensional irreducible components.
In this note we will prove that the converse statement is true, for the case $`_f=`$. We will have to impose a local condition at $`3`$ and will assume that the determinants are minimally ramified. More precisely, the result is:

###### Theorem 1.1

Let $`f`$ be a genus $`2`$ Siegel cusp form of weight $`k>2`$ with $`_f=`$, such that the corresponding automorphic representation $`\pi _f`$ has multiplicity one and $`\pi _{f,3}`$, its local component at $`3`$, is unramified. Assume that the compatible family of Galois representations $`\{\rho _{f,\mathrm{}}\}`$ attached to $`f`$ reduces (over $``$) as follows:

$$\rho _{f,\mathrm{}}\sigma _{1,\mathrm{}}\sigma _{2,\mathrm{}}(1.1)$$

for every prime $`\mathrm{}`$, where $`\{\sigma _{1,\mathrm{}}\}`$ and $`\{\sigma _{2,\mathrm{}}\}`$ are compatible families of $`2`$-dimensional irreducible representations both with determinant $`\chi ^{2k3}`$.
Then, $`f`$ is endoscopic. More precisely, there exist two classical cuspidal modular forms $`f_1`$, $`f_2`$, of weights $`2`$ and $`2k2`$ (respectively) such that the family of representations $`\{\sigma _{1,\mathrm{}}\chi ^{2k}\}`$ is attached to $`f_1`$ and the family $`\{\sigma _{2,\mathrm{}}\}`$ is attached to $`f_2`$.

Remarks: 1- The irreducibility assumption of the $`2`$-dimensional components is equivalent to assume that $`f`$ is not of Saito-Kurokawa type.
2- Reducibility of the whole family $`\{\rho _{f,\mathrm{}}\}`$ as in the statement of the theorem is equivalent to a similar condition imposed only at a single prime $`\mathrm{}`$, provided that $`\mathrm{}>4k5`$ and $`\pi _{f,\mathrm{}}`$ is unramified. This follows from a result of “existence of a family” proved in \[D2\].

## 2 Proof

Irreducibility of the $`2`$-dimensional components implies that we are not in the Saito-Kurokawa case, and together with the multiplicity one assumption this implies (as proved by Weissauer) that the representations are pure, odd, and for every prime $`\mathrm{}`$ such that $`\pi _{f,\mathrm{}}`$ is unramified, the representations $`\sigma _{1,\mathrm{}}`$ and $`\sigma _{2,\mathrm{}}`$ are crystalline with Hodge-Tate weights $`\{k2,k1\}`$ and $`\{0,2k3\}`$, respectively.
Let us first show modularity of the family $`\{\sigma _{1,\mathrm{}}\chi ^{2k}\}`$. By assumption, $`\pi _{f,3}`$ is unramified, thus $`\sigma _{1,3}\chi ^{2k}`$ is a Barsotti-Tate representation, irreducible, odd, with rational coefficients, and unramified outside a finite set of primes. Then, applying a combination of modularity results of Diamond-Taylor-Wiles and Skinner-Wiles (as done in \[D1\] and \[D2\]) we conclude that $`\sigma _{1,3}\chi ^{2k}`$ is modular, and this gives modularity of the family $`\{\sigma _{1,\mathrm{}}\chi ^{2k}\}`$. The corresponding modular form $`f_1`$ must have weight $`2`$ because for almost every $`\mathrm{}`$ the representations in this family are Barsotti-Tate.
This argument “à la Wiles” can not be applied to $`\sigma _{2,3}`$ because, even if we again have Wiles’ starting point (namely, we know that residually $`\overline{\sigma }_{2,3}`$ is either modular or reducible), the prime $`3`$ is too small compared with the difference $`2k3`$ of the Hodge-Tate weights to make the strategy workable.
To show modularity of the family $`\{\sigma _{2,\mathrm{}}\}`$ we will explode the fact that (1.1) is telling us that the representations $`\sigma _{2,\mathrm{}}`$ can be obtained by “substracting” a modular representation from another modular representation.
A key ingredient is a result recently proved by Weselmann (yet unpublished, but see \[BWW\] and \[W\]), which states that $`\pi _f`$ has a weak lift to an automorphic representation $`\pi ^{}`$ of $`\mathrm{GL}(4,𝔸)`$, where $`𝔸`$ are the rational adeles. Thus, by Cebotarev, the family $`\{\rho _{f,\mathrm{}}\}`$ is also attached to $`\pi ^{}`$.
We want to apply a result of Jacquet and Shalika (which appears as theorem 3.3 in \[T2\]), in a similar way than what is done in \[T2\], section 533. We have from (1.1) the equality of $`L`$-functions:

$$L(\pi ^{},s)=L(\sigma _{2,\mathrm{}},s)L(f_1\chi ^{k2},s)$$

Observe that $`\pi ^{}`$ is the weak lift of $`\pi _f`$, but it is not necessarily cuspidal.
To conclude that $`\sigma _{2,\mathrm{}}`$ is modular, as in section 533 of \[T2\], we must find a prime $`\mathrm{}`$ such that $`L(\sigma _{2,\mathrm{}}^{}\sigma _{2,\mathrm{}},s)`$ has a simple pole at $`s=1`$, because in that case the result of Jacquet and Shalika implies $`\sigma _{2,\mathrm{}}\sigma _{\pi _i,\mathrm{}}`$, where $`\pi _i`$ is one of the cuspidal constituents of $`\pi ^{}`$. Then, it only remains to find a prime satisfying this condition.
Take $`\mathrm{}>4k5`$ such that the local components of $`\pi ^{}`$ and $`\pi _f`$ at $`\mathrm{}`$ are unramified. For such a prime $`\mathrm{}`$ the representation $`\sigma _{2,\mathrm{}}`$ is crystalline with Hodge-Tate weights $`\{0,2k3\}`$ and the main result of \[T1\] implies that there exists a totally real number field $`F`$ such that the restriction of $`\sigma _{2,\mathrm{}}`$ to the Galois group of $`F`$ is modular, i.e., it agrees with the Galois representation attached to a Hilbert modular form over $`F`$.
But, as explained in \[T2\], section 533, precisely from this potentially modular property (and the fact that it is preserved after solvable base change) one can deduce that $`L(\sigma _{2,\mathrm{}}^{}\sigma _{2,\mathrm{}},s)`$ does have a simple pole at $`s=1`$, as we wanted. This shows modularity of the family $`\{\sigma _{2,\mathrm{}}\}`$ and it is clear from its Hodge-Tate decomposition that it corresponds to a modular form of weight $`2k2`$. We conclude that the Siegel cusp form $`f`$ is endoscopic.

## 3 Bibliography

\[BWW\] Ballmann, J., Weissauer, R., Weselmann, U., Remarks on the Fundamental Lemma for stable twisted Endoscopy of Classical Groups, preprint (2002)
\[D1\] Dieulefait, L., Modularity of Abelian Surfaces with Quaternionic Multiplication, Math. Res. Letters 10 no. 2-3 (2003)
\[D2\] Dieulefait, L., Existence of families of Galois representations and new cases of the Fontaine-Mazur conjecture, preprint (2003)
available at http://www.arxiv.org/math.NT
\[T1\] Taylor, R., On the meromorphic continuation of degree two L-functions, preprint (2001)
available at http://abel.math.harvard.edu/$``$rtaylor/
\[T2\] Taylor, R., Galois Representations, proceedings of ICM, Beijing, August 2002
longer version available at http://abel.math.harvard.edu/$``$rtaylor/
\[W\] Weissauer, R., A remark on the existence of Whittaker models for $`L`$-packets of automorphic representations of $`\mathrm{GSp}(4)`$, preprint