text:
# First-order transition between a small-gap semiconductor and a ferromagnetic metal in the isoelectronic alloys FeSi1-xGex

## Abstract

The contrasting groundstates of isoelectronic and isostructural FeSi and FeGe can be explained within an extended local density approximation scheme (LDA+U) by an appropriate choice of the onsite Coulomb repulsion, $`U`$ on the Fe-sites. A minimal two-band model with interband interactions allows us to obtain a phase diagram for the alloys FeSi1-xGex. Treating the model in a mean field approximation, gives a first order transition between a small-gap semiconductor and a ferromagnetic metal as a function of magnetic field, temperature, and concentration, $`x`$. Unusually the transition from metal to insulator is driven by broadening, not narrowing, the bands and it is the metallic state that shows magnetic order.

The unusual magnetic susceptibility of FeSi has been a subject of interest for a long time. Jaccarino et al.  found a rapid crossover around room temperature from activated behavior at low temperature to an apparent localized Curie-Weiss form at high temperature. This has stimulated a number of proposed explanations. Among them are a form of Kondo insulating behavior in FeSi , although an underlying microscopic model has not been clarified, and almost ferromagnetic semiconductor model . The latter received support from the detailed LDA band structure calculation of Mattheiss and Hamann . They found a small gap semiconductor with formal neutral valences Fe0+, Si0+ on both elements. Later Anisimov et al.  extended these calculations to include the onsite Coulomb interaction, $`U`$, in a mean field approximation, the so-called LDA+U method , and found, for a reasonable choice of $`U`$, a ferromagnetic metallic phase very close by in energy. This led them to propose that a transition to this ferromagnetic state could be driven by applying a magnetic field ($`B`$) and that the unusual temperature ($`T`$) dependent susceptibility in FeSi reflected the proximity to a critical point of this transition at finite ($`B_c`$, $`T_c`$). However the predicted value of $`B_c`$ ($``$170T) is too large to be reached in the laboratory and the existence of the critical point remains untested experimentally. A non-trivial prediction was the fractional value of the saturation moment of the ferromagnetic phase at $`S=1/2`$ or 1 $`\mu _B`$/Fe. This is a consequence of the band structure and cannot be reconciled with a local model and a 3d8 configuration for Fe0+.

The magnetic properties of the isoelectronic and isostructural FeGe compound have aroused less interest. It is a magnetic metal with a long period spiral form which is simply a ferromagnet twisted by the Dzyaloshinskii-Moriya interaction that is a consequence of the absence of inversion symmetry at the Fe site in this cubic structure . Interestingly the saturation moment is the fractional $`S=1/2`$ value quoted above . In this letter we report LDA+U calculations (in TBLMTO calculation scheme ) for FeGe and the isoelectronic alloys FeSi1-xGex. Motivated by these results we use a simplified phenomenological model to explore the complete phase diagram of the isoelectronic alloys FeSi1-xGex with varying $`T`$ and $`B`$. Alloying FeSi with Ge allows one to tune the predicted semiconductor to ferromagnetic metal transition and its unusual critical point at ($`B_c`$, $`T_c`$), to experimentally convenient values.

Both FeSi and FeGe crystallize in the cubic B20 structure which can be viewed as highly distorted rocksalt with 4 FeSi formula units in the primitive cell. Each Fe site has 7 Si neighbors and point group symmetry, C3. The LDA band structure calculations of Mattheiss and Hamann  place the Fermi energy within a narrow manifold of 20 bands of predominantly Fe 3$`d`$ character lying within a larger hybridization gap with the Si ($`3p,3s`$) states. A fuller description of the band structure will be presented elsewhere . A nontrivial feature of their results is the presence of a small but complete band gap separating 16 filled valence bands from 4 empty conduction bands. The conduction bands have nonbonding character with respect to the Si atoms and are divided by a pseudogap into two lower lying quite narrow bands and two higher lying bands which are much wider. The results of our LDA band calculations for FeGe are similar but with an even smaller band gap and narrower overall bandwidths as expected from the larger lattice constant. The total density of states for both compounds is shown in Fig. 1.

Anisimov et al.  extended the LDA calculations for FeSi to incorporate the onsite Coulomb repulsion ($`U`$) on the Fe-sites in a mean field approximation scheme known as LDA+U . They found a local minimum in the total energy versus magnetization at a value $`1\mu _B`$/Fe which moved to lower energy with increasing $`U`$. In this magnetized state the lower pair of conduction bands are filled for the majority spin direction while the Fermi level of the minority spin electrons lies in the valence band complex leading to metallic behavior. The relative positions of the two minima corresponding to the small gap semiconductor and magnetized metal, depends on the choice of $`U`$ which is not known precisely.

We have used the TBLMTO scheme  to perform LDA+U calculations for FeGe. The narrower bandwidths and energy gap lead to a lower value for the critical $`U`$, where the two energy minima cross, in FeGe relative to FeSi. Thus it is possible to obtain within the LDA+U scheme for a common value of $`U`$, the correct groundstates for FeSi and FeGe  (see Fig. 2). There are two unusual aspects to this metal-insulator transition (MIT). It is the metallic state, rather than the insulating state, which is magnetically ordered. Secondly, the transition from insulating to metallic behavior is driven by narrowing, rather than increasing, the bandwidth. The inverted nature of the metal-insulator transition is a direct consequence of the fact that the MIT is driven by the paramagnet-ferromagnet transition.

FeSi and FeGe are the end members of the isoelectronic and isostructural alloys, FeSi1-xGex. We have extended the LDA+U calculations to the alloys  using experimental lattice parameters . The critical value $`x_c`$ of the first order transition is sensitive to the choice of $`U`$. For the value of $`U=3.7`$eV, illustrated in Fig. 2, $`x_c=0.4`$ in a good agreement with the experimental value $`x_c=0.3`$ .

To proceed further we introduce and solve (within a mean field approximation) a minimal phenomenological model for the isoelectronic alloys FeSi1-xGex. Motivated by the experimental fact that the ordered moment in FeGe is $`1\mu _B`$ per Fe atom  which implies a fractional magnetization with respect to the paramagnetic Fe $`3d^8`$ configuration, we are led to an itinerant model of magnetism. We consider the following model for the conduction and valence bands. The valence band, describing the upper part of the manifold of occupied Fe $`3d`$ bands, stretching below zero energy in Fig. 1, has a width $`2W`$ and contains one state per spin per Fe atom. The conduction band (of width $`W`$) contains $`1/2`$-state per spin per Fe atom and when multiplied by 4 (which is the number of Fe atoms per primitive cell), it corresponds to the two narrow conduction bands just above the Fermi level. Both the valence and conduction bands are assumed for simplicity to have a constant density of states $`N(\epsilon )=(2W)^1`$ per spin, with a $`𝐤`$-independent gap of $`2\mathrm{\Delta }`$. Taking 2 conduction electrons per Fe atom, leads to a fully occupied valence band and a semiconducting ground state in the noninteracting case.

We propose that three types of effective local interactions should control the physics: intraband repulsion $`\stackrel{~}{U}`$, interband repulsion $`V`$, and exchange coupling between the bands $`I`$. The interactions $`\stackrel{~}{U}`$, $`V`$, and $`I`$ are combinations of the matrix elements of the Coulomb interaction between the relevant Wannier orbitals and are taken as a phenomenological input to our theory. Furthermore, we assume that the primary effect of the $`\stackrel{~}{U}`$ term is to strongly renormalize the bandwidth $`W`$ with respect to estimates from the LDA calculations. In order to describe the experimental data, we have therefore decided to use a phenomenological bandwidth rather than the calculated $`W0.5`$ eV . Thus, in order not to double count its effects, the $`\stackrel{~}{U}`$ term is not included in our model Hamiltonian which reads

$`H={\displaystyle \underset{\lambda ,𝐤,\sigma }{}}(\epsilon _{\lambda 𝐤}\sigma \mu _BB)n_{\lambda 𝐤\sigma }{\displaystyle \frac{1}{2}}{\displaystyle \underset{𝐑}{}}\left(I\widehat{m}_𝐑^2+V\widehat{\rho }_𝐑^2\right),`$ (1)
where $`\lambda =1,+1`$ denotes the valence and conduction bands, respectively, and $`\epsilon _{\lambda 𝐤}`$ and $`n_{\lambda 𝐤\sigma }`$ is the band energy and number of electrons with momentum $`𝐤`$ and spin $`\sigma `$ in band $`\lambda `$. The operators $`\widehat{\rho }_𝐑=2+_{\lambda \sigma }\lambda n_{\lambda 𝐑\sigma }`$ and $`\widehat{m}_𝐑=_{\lambda \sigma }\sigma n_{\lambda 𝐑\sigma }`$ measure the local number of charge carriers and the local magnetization, respectively. The spin quantization axis has been chosen in the direction of the external magnetic field $`B`$. The Hamiltonian can be written also in an explicitly spin-rotation invariant form, which we do not specify here.

Below we describe the phase diagram of the FeSi1-xGex alloys by fixing the values of $`I`$, $`V`$, and $`\mathrm{\Delta }`$ irrespective of the Ge content $`x`$. Alloying changes the bandwidth $`W`$ which decreases with increasing $`x`$, in accordance with the LDA results. Treating the interaction terms in the mean field approximation allows to replace the operators $`\widehat{\rho }_𝐑`$ and $`\widehat{m}_𝐑`$ by the expectation values $`\rho `$ and $`m`$, respectively. The main technical difference of the present study with respect to Ref.  is that our model is not particle-hole symmetric, and therefore in addition to $`m`$ and $`\rho `$, the chemical potential $`\mu `$ has to be calculated self-consistently. Assuming finite values of $`m`$ and $`\rho `$, the single-particle energies in the lower and upper bands are $`\omega _{\lambda ,\sigma }=\epsilon \lambda V\rho \sigma (\mu _BB+Im)`$. The corresponding mean particle numbers are

$`n_{,\sigma }`$ $`=`$ $`(2W)^1{\displaystyle _{\mathrm{\Delta }2W}^\mathrm{\Delta }}{\displaystyle \frac{d\epsilon }{1+\mathrm{exp}(\omega _{,\sigma }\mu )/T}},`$ (2)
$`n_{+,\sigma }`$ $`=`$ $`(2W)^1{\displaystyle _\mathrm{\Delta }^{\mathrm{\Delta }+W}}{\displaystyle \frac{d\epsilon }{1+\mathrm{exp}(\omega _{+,\sigma }\mu )/T}}.`$ (3)
The equation for the total number of particles $`2=_{\lambda ,\sigma }n_{\lambda ,\sigma }`$ together with Eqs. (2,3) form a closed set of equations for $`\rho `$, $`m`$, and $`\mu `$, which have to be solved in general numerically.

At $`T=0`$, the model can be solved analytically. For sufficiently large bandwidth $`W`$, the following two phases compete: (i) semiconductor with $`\rho =0`$, $`m=0`$ and (ii) ferromagnetic metal with $`\rho =1`$, $`m=1`$. Their energies are $`E_{\mathrm{semi}}=2\mathrm{\Delta }2W`$ and $`E_{\mathrm{FM}}=\mathrm{\Delta }3W/2(I+V)/2\mu _BB`$, respectively. With changing bandwidth, at $`B=0`$ there is a level crossing between the semiconducting phase and the ferromagnetic metal at $`W=W_c(0)=I+V2\mathrm{\Delta }`$. For $`W>W_c(0)`$, the ferromagnetic phase is stable only in magnetic fields larger than a critical magnetic field $`\mu _BB_c(0)=(WW_c(0))/2`$.

We take $`\mathrm{\Delta }=20`$ meV in qualitative agreement with experiment and the effective interaction parameters $`I=80`$ meV and $`V=65`$ meV close to the values proposed in Ref. . The resulting phase diagram for $`B=0`$ shown in Fig. 4 implies that the phenomenological bandwidth of FeGe, $`W_{\mathrm{FeGe}}`$ is less than $`W_c(0)`$ ($`W_c(0)`$=105 meV). Note that the Curie temperatures predicted by our model for $`W<W_c(0)`$, $`T_c400`$ K, are in reasonable agreement with the experimentally observed transition temperature to a long-period spiral in FeGe, $`T_N280`$. The phenomenological bandwidth of FeSi, $`W_{\mathrm{FeSi}}`$,which is greater than $`W_c(0)`$, can be determined by fitting the spin susceptibility. For $`WW_c(0)`$, the spin susceptibility develops a strong peak around room temperature, confirming the interpretation of Anisimov et al. The peak position as a function of $`W`$ is shown in Fig. 4. Fitting the peak value of $`\chi `$ to $`27\mu _B^2/\mathrm{eV}`$ , we estimate $`W_{\mathrm{FeSi}}130`$ meV.

Nearly critical semiconducting alloys with $`W`$ slightly in excess of $`W_c(0)`$ should exhibit metamagnetic transitions to metallic phases at experimentally accessible magnetic fields. For instance in a sample with $`W=110`$ meV, the transition occurs at $`B_c(0)=43.1`$ T at $`T=0`$. The temperature evolution of the magnetization $`m`$ for such a sample for magnetic fields in the vicinity of the first-order transition is shown in the inset in Fig. 4. Note that at low temperatures the critical magnetic field lowers with increasing temperature. This follows simply from the larger electronic entropy of the metallic phase. At higher temperatures the phase boundary in our model bends towards smaller bandwidths $`W`$, in qualitative agreement with the higher susceptibility of small bandwidth systems to various forms of symmetry breaking transitions. The different low- and high-$`T`$ slopes of the phase boundary lead to a reentrant $`B=0`$ phase diagram and also to reentrant metamagnetic transitions in a narrow field range, as shown explicitly in the inset in Fig. 4 for $`B=25.9`$ T.

We should like to point out that not only the magnetic properties are anomalous at the metamagnetic transition. Since the transition is between a semiconductor and a ferromagnetic metal, large magnetoresistance is to be expected. As a result the critical endpoint of this metamagnetic transition should show particularily interesting magnetoresistance behavior at temperatures around room temperature.

In conclusion, we have calculated the complete phase diagram of the isoelectronic alloys FeSi1-xGex with varying $`T`$ and $`B`$. Our main results are summarized in a three-dimensional phase diagram, Fig. 5, which shows that, depending on $`x`$, $`T`$, and $`B`$, the alloy FeSi1-xGex can be a semiconductor or a ferromagnetic metal. The two phases are separated by a surface of first-order transitions which terminates at high temperatures in a line of critical points. Note, this phase diagram resembles that found by Pfleiderer et al  for isostructural MnSi under pressure and magnetic field but with the important difference that all phases of MnSi are metallic so that a semiconductor-metal transistion is not involved. We predict that, for intermediate values of the Ge content $`x`$, this transition can be realized as a metamagnetic transition at experimentally accessible magnetic fields. Large magnetoresistance is predicted at such a transition. Another possible way to realize the transition at experimentally accessible magnetic fields would be to apply pressure to FeGe.

VIA, VVM, AOS and RH thank the Center for Theoretical Studies, ETH Zurich and the Swiss National fond for support. Partial support by the Slovak Grant Agency VEGA under Grant No. 1/9177/02 and Russian Foundation For Basic Research grant RFFI-01-02-17063 is also acknowledged. We are especially grateful to Zachary Fisk for pointing out the experimental results on FeGe to us and for communicating his unpublished results on the FeSi1-xGex alloys.


format: text

text:
# Equitable coloring of 𝑘-uniform hypergraphs

## 1 Introduction

All hypergraphs considered here are finite. For standard terminology the reader is referred to . Let $`H`$ be a $`k`$-uniform hypergraph with $`n`$ vertices. A strong $`r`$-coloring is a partition of the vertices of $`H`$ into $`r`$ parts, such that each edge of $`H`$ intersects each part. (A weak $`r`$-coloring is a coloring where no edge is monochromatic.) A strong $`r`$-coloring is called equitable if the size of each part is $`n/r`$ or $`n/r`$. Let $`c(H)`$ denote the maximum possible number of parts in a strong coloring of $`H`$. Let $`ec(H)`$ denote the maximum possible number of parts in an equitable coloring of $`H`$. Trivially, $`1ec(H)c(H)k`$. In general, $`k`$ could be large and still $`ec(H)=c(H)=1`$, if we do not impose upper bounds on the maximum degree. Consider the complete $`k`$-uniform hypergraph on $`2k`$ vertices. Trivially, it has $`c(H)=1`$, and the maximum degree is less than $`4^k`$. In this paper we prove that $`c(H)`$ and $`ec(H)`$ are quite large if the maximum degree is bounded by a polynomial in $`k`$. In fact, we get the following tight result:

###### Theorem 1.1

Let $`a1`$. Let $`H`$ be a $`k`$-uniform hypergraph with maximum degree at most $`k^a`$. Then, $`ec(H)\frac{k}{a\mathrm{ln}k}(1o_k(1)).`$ The result is tight. For all $`a1`$, there exist $`k`$-uniform hypergraphs $`H`$ with maximum degree at most $`k^a`$ and $`c(H)\frac{k}{a\mathrm{ln}k}(1+o_k(1)).`$

The tightness is shown by a construction of a random hypergraph with appropriate parameters. Alon  has shown that there exist $`k`$-uniform hypergraphs with $`n`$ vertices and maximum degree at most $`k`$ that do not have a vertex cover of size less than $`(n\mathrm{ln}k/k)(1o_k(1))`$. In particular, no strong coloring (moreover an equitable one) could have more than $`(k/\mathrm{ln}k)(1+o_k(1))`$ parts. For completeness, we show a general construction valid for all $`a1`$ in Section 3. The proof of the main result appears in Section 2. The final section contains some concluding remarks.

## 2 Proof of the main result

In the proof of Theorem 1.1 we need to use the Lovász Local Lemma  in its strongest form, known as the nonsymmetric version. Here it is, following the notations in  (which also contains a simple proof of the lemma). Let $`A_1,\mathrm{},A_n`$ be events in an arbitrary probability space. A directed graph $`D=(V,E)`$ on the set of vertices $`V=[n]`$ is called a dependency digraph for the events $`A_1,\mathrm{},A_n`$ if for each $`i`$, $`i=1,\mathrm{},n`$, the event $`A_i`$ is mutually independent of all the events $`\{A_j:(i,j)E\}`$.

###### Lemma 2.1 (The Local Lemma, nonsymmetric version)

Let $`A_1,\mathrm{},A_n`$ be events in an arbitrary probability space and let $`D=(V,E)`$ be a corresponding dependency digraph. If $`x_1,\mathrm{},x_n`$ are real numbers such that $`0x_i<1`$ and $`\mathrm{Pr}[A_i]x_i_{(i,j)E}(1x_j)`$ for all $`i=1,\mathrm{},n`$, then, with positive probability no event $`A_i`$ holds.

If the maximum outdegree in $`D`$ is at most $`d1`$ and each $`A_i`$ has $`\mathrm{Pr}[A_i]p`$ then, by assigning $`x_i=1/(d+1)`$ we immediately get:

###### Corollary 2.2 (The Local Lemma, symmetric version)

If $`p(d+1)1/e`$ then with positive probability no event $`A_i`$ holds.

Proof of Theorem 1.1: Let $`a1`$ be any real number, and let $`ϵ>0`$ be small. Throughout the proof we assume $`k`$ is sufficiently large as a function of $`a`$ and $`ϵ`$. Let $`k`$ be sufficiently large such that there is an integer between $`\frac{k}{(1+ϵ^2/4)a\mathrm{ln}k}`$ and $`\frac{k}{(1+ϵ^2/8)a\mathrm{ln}k}`$. Thus, for some $`ϵ^2/8\gamma ϵ^2/4`$, the number $`t=\frac{k}{(1+\gamma )a\mathrm{ln}k}`$ is an integer. Now, let $`H=(V,E)`$ be a hypergraph with $`n`$ vertices and $`\mathrm{\Delta }(H)k^a`$. We will show that there exists an equitable coloring of $`H`$ with $`\frac{k}{(1+\gamma )a\mathrm{ln}k}\sqrt{\gamma }\frac{k}{a\mathrm{ln}k}>(1ϵ)\frac{k}{a\mathrm{ln}k}`$ colors.

Assume that we have the set of colors $`\{1,\mathrm{},t\}`$. It will be convenient to deal with the finite set of graphs having $`n<2k\mathrm{ln}k`$ separately. We begin with the general case.

### 2.1 The general case: $`n>2k\mathrm{ln}k`$

In the first phase of the proof we color most of the vertices (that is, we obtain a partial coloring) such that certain very specific properties hold. In the second phase we color the vertices that were not colored in the first phase and show that we can do it carefully enough and obtain a proper strong $`t`$-coloring. In the third phase we show how to modify our coloring and obtain an equitable coloring.

#### 2.1.1 First Phase

Our goal in this phase is to achieve a partial coloring with the following properties:

###### Lemma 2.3

There exists a partial coloring of $`H`$ with the colors $`\{1,\mathrm{},t\}`$ such that the following four conditions hold:

1. Every edge contains at least $`k\gamma /5`$ uncolored vertices.
2. Every edge has at most $`10/\gamma `$ colors that do not appear in its vertex set.
3. Put $`z=k^{1a\gamma /4}`$. For each $`vV`$, and for each sequence of $`z`$ distinct colors $`c_1,\mathrm{},c_z`$ and for each sequence of $`z`$ distinct edges containing $`v`$ denoted $`f_1,\mathrm{},f_z`$, at least one $`f_i`$ has an element colored $`c_i`$.
4. Every color appears in at least $`n\frac{(1+\gamma /4)a\mathrm{ln}k}{k}`$ vertices.

Proof: We let each vertex $`vV`$ choose a color from $`\{1,\mathrm{},t\}`$ randomly. The probability to choose color $`i`$ is $`p=\frac{(1+\gamma /2)a\mathrm{ln}k}{k}`$ for $`i=1,\mathrm{},t`$ and the probability of remaining uncolored is, therefore, $`q=1pt=\frac{\gamma }{2(1+\gamma )}`$. For an edge $`f`$, let $`A_f`$ denote the event that $`f`$ contains less than $`k\gamma /5`$ uncolored vertices. Let $`B_f`$ denote the event that $`f`$ has more than $`10/\gamma `$ colors missing from its vertex set. For a vertex $`v`$, let $`C_v`$ denote the event that there exist $`z`$ distinct edges $`f_1,\mathrm{},f_z`$ each $`f_i`$ contains $`v`$, and there exist $`z`$ distinct colors $`c_1,\mathrm{},c_z`$, such that $`c_i`$ is missing from $`f_i`$ for each $`i=1,\mathrm{},z`$. For a color $`c`$, let $`D_c`$ denote the event that the color $`c`$ appears in less than $`n\frac{(1+\gamma /4)a\mathrm{ln}k}{k}`$ vertices. We must show that with positive probability, none of the above $`2|E|+|V|+t`$ events hold. The following four claims provide upper bounds for the probabilities of the events $`A_f`$,$`B_f`$, $`C_v`$, $`D_c`$.

###### Claim 2.4

$`\mathrm{Pr}[A_f]<\frac{1}{k^{5a}}`$.

Proof: Let $`X_f`$ denote the random variable counting the uncolored elements of $`f`$. The expectation of $`X_f`$ is $`E[X_f]=kq`$. Since each vertex chooses its color independently we have by a common Chernoff inequality (cf. )

$$\mathrm{Pr}\left[A_f\right]=\mathrm{Pr}\left[X_f<\frac{k\gamma }{5}\right]\mathrm{Pr}\left[X_f<\frac{kq}{2}\right]=\mathrm{Pr}\left[X_f<\frac{E[X_f]}{2}\right]<$$

$$e^{2(E[X_f]/2)^2/k}=e^{k^2q^2/(2k)}=e^{kq^2/2}<<\frac{1}{k^{5a}}.$$

###### Claim 2.5

$`\mathrm{Pr}[B_f]<\frac{1}{k^{5a}}`$.

Proof: Fix $`s=10/\gamma `$ distinct colors. The probability that none of them appear in $`f`$ is precisely $`(1sp)^k`$. Now,

$$(1sp)^k=\left(1\frac{s(1+\frac{\gamma }{2})a\mathrm{ln}k}{k}\right)^k<\frac{1}{k^{as+as\gamma /2}}.$$

As there are $`\left(\genfrac{}{}{0pt}{}{t}{s}\right)<k^s`$ possible sets of $`s`$ distinct colors we get that

$$\mathrm{Pr}[B_f]<\left(\genfrac{}{}{0pt}{}{t}{s}\right)\frac{1}{k^{as+as\gamma /2}}<\frac{1}{k^{as\gamma /2}}\frac{1}{k^{5a}}.$$

###### Claim 2.6

$`\mathrm{Pr}[C_v]<\frac{1}{k^{5a}}`$.

Proof: If the degree of $`v`$ is less than $`z`$ there is nothing to prove. Otherwise, fix a set of $`z`$ distinct colors $`\{c_1,\mathrm{},c_z\}`$ and $`z`$ distinct edges containing $`v`$, denoted $`\{f_1,\mathrm{},f_z\}`$. We begin by computing the probability that for each $`i=1,\mathrm{},z`$, $`c_i`$ does not appear in an element of $`f_i`$. Denote this probability by $`\rho =\rho (v,f_1,\mathrm{},f_z,c_1,\mathrm{},c_z)`$ Let $`\stackrel{}{x}=(x_1,\mathrm{},x_z)`$ be a binary vector. Let $`N(\stackrel{}{x})`$ denote the subset of vertices that belong to the edges $`f_i`$, for each coordinate $`x_i`$ that is positive in $`\stackrel{}{x}`$, and that do not belong to the edge $`f_i`$ for each coordinate $`x_i`$ that is zero in $`\stackrel{}{x}`$. This partitions the vertex set into $`2^z`$ parts. Thus, if $`\stackrel{}{x}\stackrel{}{x^{}}`$ then $`N(\stackrel{}{x})N(\stackrel{}{x^{}})=\mathrm{}`$. Put $`n_\stackrel{}{x}=|N(\stackrel{}{x})|`$. Also notice that for each $`i=1,\mathrm{},z`$ we have $`(_{\stackrel{}{x}:x_i=1}n_\stackrel{}{x})=k`$. Let $`w_\stackrel{}{x}`$ denote the number of positive coordinates in $`\stackrel{}{x}`$. Clearly,

$$\rho =\underset{\stackrel{}{x}}{}(1w_\stackrel{}{x}p)^{n_\stackrel{}{x}}<\underset{\stackrel{}{x}}{}e^{pw_\stackrel{}{x}n_\stackrel{}{x}}=e^{pkz}=\frac{1}{k^{a(1+\gamma /2)z}}.$$

There are exactly $`t^z<(k/\mathrm{ln}k)^z`$ ordered sets of $`z`$ distinct colors. Thus, the probability that $`f_1,\mathrm{},f_z`$ each miss a distinct color is less than $`(k/\mathrm{ln}k)^z/k^{a(1+\gamma /2)z}`$. There are at most $`\left(\genfrac{}{}{0pt}{}{k^a}{z}\right)`$ distinct subsets of $`z`$ edges containing $`v`$. This, together with Stirling’s formula, gives

$$\mathrm{Pr}[C_v]<\left(\genfrac{}{}{0pt}{}{k^a}{z}\right)\frac{k^z}{\left(\mathrm{ln}k\right)^zk^{a\left(1+\gamma /2\right)z}}<\left(\frac{ek^a}{z}\frac{k}{k^{a\left(1+\gamma /2\right)}\mathrm{ln}k}\right)^z\left(\frac{e}{k^{a\gamma /4}\mathrm{ln}k}\right)^z<<\frac{1}{k^{5a}}.$$

###### Claim 2.7

$`\mathrm{Pr}[D_c]<\frac{1}{e^{n/k}}`$.

Proof: Let $`X_c`$ denote the number of vertices that received the color $`c`$. Clearly, $`E[X_c]=pn=n\frac{(1+\gamma /2)a\mathrm{ln}k}{k}`$. Put $`\beta =n\frac{a\gamma \mathrm{ln}k}{4k}`$. We shall use the Chernoff inequality (cf. )

$$\mathrm{Pr}[X_cpn<\beta ]<e^{\beta ^2/(2pn)}.$$

In our case

$$\mathrm{Pr}[D_c]=\mathrm{Pr}[X_cpn<\beta ]<e^{\beta ^2/(2pn)}=e^{\frac{na\mathrm{ln}k}{k}(\frac{\gamma ^2}{32(1+\gamma /2)})}<$$

$$e^{\frac{na\mathrm{ln}k}{k}(\frac{\gamma ^2}{33})}=\frac{1}{k^{(n/k)(\gamma ^2/33)}}<\frac{1}{e^{n/k}}.$$

We now construct a dependency graph for all the events of the form $`A_f,B_f,C_v,D_c`$ (we refer to the events as “type A”, “type B”, “type C”, and type “D” respectively). Consider an event $`A_f`$. Let $`E(f)`$ denote the set of edges of $`H`$ that are disjoint from $`f`$. Let $`V(f)`$ denote the set of vertices of $`H`$ that do not appear in any edge that intersects $`f`$. Clearly $`A_f`$ is mutually independent of all the $`2|E(f)|+|V(f)|`$ events of the form $`A_g`$, $`B_g`$ or $`C_v`$ which correspond to the elements of $`E(f)`$ and $`V(f)`$. Since there are at most $`k^{a+1}`$ edges intersecting $`f`$ and since there are at most $`k^{a+2}`$ vertices in these edges, the outdegree in the dependency graph from $`A_f`$ to other events of type $`A`$ is at most $`k^{a+1}`$. Similarly the outdegree in the dependency graph from $`A_f`$ to other events of type $`B`$ is at most $`k^{a+1}`$, and to events of type $`C`$ it is at most $`k^{a+2}`$. $`A_f`$ depends on all events of type $`D`$, so the outdegree is $`t`$. This explains the first line of Table 1 (the dependency table). The other elements in the table are figured out similarly. Note that events of type $`D`$ depend on all other events (the fourth line in Table 1).

In order to apply Lemma 2.1 we need to assign a coefficient to each event in the dependency graph (the coefficients correspond to the $`x_i`$ in Lemma 2.1). To each event of type $`A`$, $`B`$ or $`C`$ we assign the coefficient $`3/k^{5a}`$. To each event of type $`D`$ we assign the coefficient $`1/e^{n/(2k)}`$. It remains to show that the conditions in Lemma 2.1 hold for each event. Consider events of type $`A`$. We must show that

$$\mathrm{Pr}[A_f]<\frac{3}{k^{5a}}\left(1\frac{3}{k^{5a}}\right)^{k^{a+1}}\left(1\frac{3}{k^{5a}}\right)^{k^{a+1}}\left(1\frac{3}{k^{5a}}\right)^{k^{a+2}}\left(1\frac{1}{e^{n/(2k)}}\right)^t.$$

Indeed, recall that $`n>2k\mathrm{ln}k`$ so $`(11/e^{n/(2k)})^{k1}>e^1`$. Since $`t<k1`$ we get, together with Claim 2.4,

$$\frac{3}{k^{5a}}\left(1\frac{3}{k^{5a}}\right)^{k^{a+1}}\left(1\frac{3}{k^{5a}}\right)^{k^{a+1}}\left(1\frac{3}{k^{5a}}\right)^{k^{a+2}}\left(1\frac{1}{e^{n/(2k)}}\right)^t>$$

$$\frac{3}{k^{5a}}\left(1\frac{3}{k^{5a}}\right)^{3k^{a+2}}e^1>\frac{3}{k^{5a}}0.99e^1>\frac{1}{k^{5a}}>\mathrm{Pr}[A_f].$$

The analogous inequalities hold for events of type $`B`$ and $`C`$ where we use Claim 2.5 and Claim 2.6 respectively. Finally, consider events of type $`D`$. We must show that

$$\mathrm{Pr}[D_c]<\frac{1}{e^{n/(2k)}}\left(1\frac{3}{k^{5a}}\right)^{2|E|+n}\left(1\frac{1}{e^{n/(2k)}}\right)^t.$$

In any $`k`$-uniform hypergraph, $`|E|n\mathrm{\Delta }/k`$. Thus, in our case, $`2|E|+n3k^{a1}n`$. Using again the fact that$`(11/e^{n/(2k)})^{k1}>e^1`$ we have, together with Claim 2.7,

$$\frac{1}{e^{n/(2k)}}\left(1\frac{3}{k^{5a}}\right)^{2|E|+n}\left(1\frac{1}{e^{n/(2k)}}\right)^t>$$

$$\frac{1}{e^{n/(2k)}}\left(1\frac{3}{k^{5a}}\right)^{3k^{a1}n}e^1>\frac{1}{e^{n/(2k)}}\left(1\frac{3}{k^{5a}}\right)^{(\frac{k^{5a}}{3}1)\frac{18n}{k^{4a+1}}}e^1>$$

$$\frac{1}{e^{n/(2k)}}e^{\frac{18n}{k^{4a+1}}1}>\frac{1}{e^{n/(2k)}}\frac{1}{e^{n/(2k)}}=\frac{1}{e^{n/k}}>\mathrm{Pr}[D_c].$$

According to Lemma 2.1, with positive probability, none of the events in the dependency graph hold. We have completed the proof of Lemma 2.3.

#### 2.1.2 Second Phase

Fix a partial coloring satisfying the four conditions in Lemma 2.3. For an edge $`f`$, let $`M(f)`$ denote the set of missing colors from $`f`$. By Lemma 2.3 we know that $`|M(f)|10/\gamma `$. For a vertex $`v`$, let $`S(v)=_{vf}M(f)`$. We claim that $`|S(v)|10/\gamma (z1)11z/\gamma `$. To see this, notice that if $`|S(v)|>10/\gamma (z1)`$ then there must be at least $`z`$ distinct edges containing $`v`$, say, $`f_1,\mathrm{},f_z`$ and $`z`$ distinct colors $`c_1,\mathrm{},c_z`$ such that $`c_i`$ does not appear in $`f_i`$ for $`i=1,\mathrm{},z`$. However, this is impossible by the third requirement in Lemma 2.3. In the second phase we only color the vertices that are uncolored after the first phase. Let $`v`$ be such a vertex. We let $`v`$ choose a random color from $`S(v)`$ with uniform distribution. The choices made by distinct vertices are independent (In case $`S(v)=\mathrm{}`$ we can assign an arbitrary color to $`v`$). Let $`fE`$ be any edge, and let $`cM(f)`$. Let $`A_{f,c}`$ denote the event that after the second phase, $`c`$ still does not appear as a color in a vertex of $`f`$. Our goal is to show that with positive probability, none of the events $`A_{f,c}`$ for $`fE`$ and $`cM(f)`$ hold. This will give a proper strong $`t`$-coloring of $`H`$ (although not necessarily an equitable one).

Let $`T(f)`$ be the subset of vertices of $`f`$ that are uncolored after the first phase. By Lemma 2.3 we have $`|T(f)|k\gamma /5`$. If $`cM(f)`$ we have that for each $`uT(f)`$, the color $`c`$ appears in $`S(u)`$. Hence,

$$\mathrm{Pr}[A_{f,c}]=\mathrm{\Pi }_{uT(f)}\left(1\frac{1}{|S(u)|}\right)\mathrm{\Pi }_{uT(f)}\left(1\frac{\gamma }{11z}\right)$$

$$\left(1\frac{\gamma }{11z}\right)^{k\gamma /5}<e^{\frac{k\gamma ^2}{55z}}<e^{k^{a\gamma /4}\frac{\gamma ^2}{110}}<<\frac{1}{k^{2a+2}}.$$

Since each event $`A_{f,c}`$ is mutually independent of all other events but those that correspond to edges that intersect $`f`$, we have that the dependency graph of the events has maximum outdegree at most $`10/\gamma k^{a+1}<k^{a+2}/e1`$. Since $`\frac{1}{k^{a+2}}((k^{a+2}/e1)+1)=1/e`$ we have, by Corollary 2.2, that with positive probability none of the events of the form $`A_{f,c}`$ hold. In particular, there exists a strong $`t`$-coloring of $`H`$.

#### 2.1.3 Third Phase

Assume the color classes of the strong $`t`$-coloring obtained after the second phase are $`V_1,\mathrm{},V_t`$ where $`|V_i||V_{i+1}|`$, $`i=1,\mathrm{},t1`$. By Lemma 2.3 we know that $`|V_i|n\frac{(1+\gamma /4)a\mathrm{ln}k}{k}`$, $`i=1,\mathrm{},t`$. Let $`s=\sqrt{\gamma }k/(a\mathrm{ln}k)`$ and let $`W=V_1\mathrm{}V_s`$. Clearly

$$n|W|=|VW|=|V_{s+1}\mathrm{}V_t|(ts)n\frac{(1+\frac{\gamma }{4})a\mathrm{ln}k}{k}=n\left(\frac{1+\frac{\gamma }{4}}{1+\gamma }\right)\frac{sn(1+\frac{\gamma }{4})a\mathrm{ln}k}{k}.$$

Hence,

$$|W|n\left(1\frac{1+\frac{\gamma }{4}}{1+\gamma }\right)+\frac{sn(1+\frac{\gamma }{4})a\mathrm{ln}k}{k}<\gamma n+\frac{sn(1+\frac{\gamma }{4})a\mathrm{ln}k}{k}.$$

In particular, $`|V_s||W|/s<\gamma n/s+n(1+\gamma /4)a\mathrm{ln}k/k`$. It follows that $`\left||V_i||V_j|\right|<\gamma n/s`$ for all $`s+1i<jt`$. Hence, it suffices to show that $`|W|(ts)\gamma n/s`$ since we can then transfer all the vertices in the color classes $`V_1,\mathrm{},V_s`$ to the color classes $`V_{s+1},\mathrm{},V_t`$ such that after the transfer, the $`ts`$ remaining classes form an equitable partition (the strong coloring stays proper, of course). Indeed,

$$|W|>sn\frac{a\mathrm{ln}k}{k}=s^2n\frac{a\mathrm{ln}k}{sk}n\gamma \frac{k^2}{a^2(\mathrm{ln}k)^2}\frac{a\mathrm{ln}k}{sk}=n\gamma \frac{k}{sa\mathrm{ln}k}>n\frac{t\gamma }{s}>(ts)\frac{n\gamma }{s}.$$

We have shown how to obtain an equitable coloring with $`ts=\frac{k}{(1+\gamma )a\mathrm{ln}k}\sqrt{\gamma }\frac{k}{a\mathrm{ln}k}>(1ϵ)\frac{k}{a\mathrm{ln}k}`$ colors.

### 2.2 The finite case: $`n<2k\mathrm{ln}k`$

As in the proof for the general case, let each vertex choose a color randomly and independently, each color with probability $`p`$ where $`p=\frac{(1+\gamma /2)a\mathrm{ln}k}{k}`$ for $`i=1,\mathrm{},t`$ and the probability of remaining uncolored is $`q=1pt=\frac{\gamma }{2(1+\gamma )}`$. As in the proof of Claim 2.4, the probability that an edge contains less than $`k\gamma /5`$ uncolored vertices is less than $`1/k^{5a}`$. There are $`|E|nk^a/k2k^a\mathrm{ln}k`$ edges. Hence, the expected number of edges with less than $`k\gamma /5`$ edges is less than $`1/k^3`$. Thus. With probability at least than $`11/k^3`$ all edges have at least $`k\gamma /5`$ uncolored vertices. As in the proof of Claim 2.7, the probability that a color appears in less than $`na\mathrm{ln}k(1+\gamma /4)/k`$ vertices is less than $`\frac{1}{k^{(n/k)(\gamma ^2/33)}}`$. Unlike Claim 2.7 we cannot bound this number from above by $`e^{n/k}`$; instead, since $`nk`$ (otherwise there are no edges at all), we can bound it with $`k^{\gamma ^2/33}`$. Since there are $`t<k`$ colors, the expected number of colors that appear in less than $`na\mathrm{ln}k(1+\gamma /4)/k`$ vertices is less than $`k^{1\gamma ^2/33}`$. Thus, with probability at least $`2/3`$ there are less than $`3k^{1\gamma ^2/33}`$ such colors. Finally, let $`X`$ count the number of pairs $`(e,c)`$ where $`eE`$ and $`c`$ is a color that is missing from $`e`$. Clearly,

$$E[X]=|E|t(1p)^k<2k^a\mathrm{ln}kkk^{a(1+\gamma /2)}=2k^{1a\gamma /2}\mathrm{ln}k<2k^{1\gamma /4}<\frac{k\gamma }{15}.$$

Hence, with probability at least $`2/3`$, $`X<k\gamma /5`$.

We have proved that with probability at least $`11/k^31/31/3>0`$ all the following occur simultaneously:

1. All edges have at least $`k\gamma /5`$ uncolored vertices.
2. At least $`t3k^{1\gamma ^2/33}`$ colors appear each in at least $`na\mathrm{ln}k(1+\gamma /4)/k`$ vertices.
3. The number of pairs $`(e,c)`$ of edges $`e`$ and colors $`c`$ such that $`c`$ is missing from $`e`$ is less than $`k\gamma /5`$.

Fix a partial coloring with all these properties. Trivially we can make it a proper strong coloring by assigning a color $`c`$ that is missing from an edge $`e`$ to one of the uncolored vertices of $`e`$, and we can do it greedily to all such $`(e,c)`$ pairs. We therefore obtain a proper strong $`t`$-coloring of $`H`$, where, in addition, at least $`t3k^{1\gamma ^2/33}`$ colors appear each in at least $`na\mathrm{ln}k(1+\gamma /4)/k`$ vertices. We can now use the same arguments as in the third phase of the general case and obtain an equitable coloring. The only difference is that instead of $`t`$ we only use $`tr`$ colors where $`r`$ is the number of color classes having less than $`na\mathrm{ln}k(1+\gamma /4)/k`$ vertices. Thus, $`trt3k^{1\gamma ^2/33}>t(1\gamma /33)`$, and it is easily seen that all computations in the third phase hold when replacing $`t`$ with $`t(1\gamma /33)`$.

## 3 A random hypergraph construction

Let $`a1`$ and let $`ϵ>0`$. Let $`n=k^{2a}`$. For simplicity we assume $`n`$ is an integer in order to ignore floors and ceilings. $`k`$ will be selected sufficiently large to justify this assumption and the assumptions that follow. Let $`m=(1ϵ)k^{3a1}`$ (again, assume $`m`$ is an integer). Consider the random $`k`$-uniform hypergraph on the vertex set $`[n]`$ with $`m`$ randomly selected edges $`f_1,\mathrm{},f_m`$. Each edge $`f_i`$ is chosen uniformly from all $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$ possible edges. The $`m`$ choices are independent (thus, the same edge can be selected more than once). The expected degree of a vertex $`v`$ (including multiplicities) is $`mk/n=(1ϵ)k^a`$. Notice that for $`k`$ sufficiently large we have, using a Chernoff inequality, that the degree of $`v`$ is greater than $`k^a`$ with probability less than $`1/(2k^{2a})=1/(2n)`$. Hence, with probability greater than $`0.5`$ the maximum degree is at most $`k^a`$. Put $`t=(12ϵ)na\mathrm{ln}k/k`$. Again, we assume $`t`$ is an integer. We show that with probability greater than $`0.5`$, no $`t`$-subset of vertices is a vertex cover. This proves the existence of hypergraphs $`H`$ with $`\mathrm{\Delta }(H)k^a`$ and $`c(H)(1+o_k(1))k/(a\mathrm{ln}k)`$.

Fix $`X[n]`$ with $`|X|=t`$. For each edge $`f_i`$ we have, assuming $`k`$ is sufficiently large,

$$\mathrm{Pr}[f_iX=\mathrm{}]=\frac{(nt)(nt1)\mathrm{}(ntk+1)}{n(n1)\mathrm{}(nk+1)}>\left(1\frac{t}{nk+1}\right)^k>\left(1\frac{t}{(1ϵ)n}\right)^k=$$

$$\left(1\frac{(12ϵ)a\mathrm{ln}k}{(1ϵ)k}\right)^k>\left(1\frac{(1ϵ)a\mathrm{ln}k}{k}\right)^k>\frac{1}{2}e^{(1ϵ)a\mathrm{ln}k}=\frac{1}{2k^{a(1ϵ)}}.$$

Since each edge is selected independently we have

$$\mathrm{Pr}[X\mathrm{is}\mathrm{a}\mathrm{vertex}\mathrm{cover}]<\left(1\frac{1}{2k^{a(1ϵ)}}\right)^m.$$

There are $`\left(\genfrac{}{}{0pt}{}{n}{t}\right)`$ possible choices for $`X`$. It suffices to show that

$$\left(\genfrac{}{}{0pt}{}{n}{t}\right)\left(1\frac{1}{k^{2a(1ϵ)}}\right)^m<\frac{1}{2}.$$

Indeed, for $`k`$ sufficiently large

$$\left(\genfrac{}{}{0pt}{}{n}{t}\right)\left(1\frac{1}{2k^{a(1ϵ)}}\right)^m<\left(\frac{en}{t}\right)^t\left(1\frac{1}{2k^{a(1ϵ)}}\right)^{(1ϵ)k^{3a1}}=$$

$$\left(\frac{ek}{(12ϵ)a\mathrm{ln}k}\right)^{(12ϵ)k^{2a1}\mathrm{ln}k}\left(1\frac{1}{2k^{a(1ϵ)}}\right)^{(1ϵ)k^{3a1}}=$$

$$\left(\left(\frac{ek}{(12ϵ)a\mathrm{ln}k}\right)^{(12ϵ)\mathrm{ln}k}\left(1\frac{1}{2k^{a(1ϵ)}}\right)^{(1ϵ)k^a}\right)^{k^{2a1}}<\left(e^{\mathrm{ln}^2k}e^{k^{aϵ}(1ϵ)/2}\right)^{k^{2a1}}<<\frac{1}{2}.$$

## 4 Concluding remarks

* In the proof of Theorem 1.1 we require that $`\mathrm{\Delta }(H)k^a`$ for some fixed $`a1`$. It is possible (although the computations get somewhat more complicated) to prove Theorem 1.1 when $`a`$ is not necessarily a constant but satisfies $`a=a(k)=o(k/\mathrm{ln}k)`$. In other words, $`\mathrm{\Delta }(H)`$ is allowed to be any subexponential function of $`k`$.
* The proof of Theorem 1.1 is not algorithmic. It is, however, possible to obtain a polynomial time (in the number of vertices of the hypergraph, and not in its uniformity) algorithm that yields an equitable partition with $`(1o_k(1))ck/(a\mathrm{ln}k)`$ parts where $`c`$ is a fixed small constant (depending only on $`a`$). This can be done by using the method of Beck for the two coloring of hypergraphs  and generalizing it to more colors. We also need to take care that the coloring obtained be equitable (Beck’s algorithm does not guarantee this). However, Beck’s algorithm can be modified so as to guarantee that all colors use roughly the same number of colors, and then we can use the approach from the third phase of our proof to show that by sacrificing only a small fraction of the colors we can make the partition equitable using the remaining colors. Notice that the third phase can easily be implemented in polynomial time.
* A special case of Theorem 1.1 yields an interesting result about graphs. Let $`G`$ be a $`k`$-regular graph. Then, $`G`$ has an equitable coloring with $`(1o_k(1))(k/\mathrm{ln}k)`$ colors such that each color class is a total dominating set (a total dominating set $`D`$ is a subset of the vertices that has the property that each vertex $`vG`$ has a neighbor in $`D`$). To see this, we can construct a hypergraph $`H`$ from the graph $`G`$ as follows. For each vertex $`vG`$ Let $`N(v)`$ denote the neighborhood of $`v`$. The vertices of $`H`$ are those of $`G`$ and the edges are all the sets $`N(v)`$. $`H`$ is $`k`$-uniform and $`\mathrm{\Delta }(H)=k`$. Theorem 1.1 applied to $`H`$ gives the desired result about $`G`$.


text:
# 1 Introduction.

## 1 Introduction.

This work does not depend on our previous poking at the Quantum Heisenberg system, , . We only learned from this previous study the surprisingly relevant relation between solutions of the heat equation and quantities in this model. There is the precise rigorous relation of Eq. (19) of ; and the numerical approximations of , which  makes feeble effort to justify. The key conjecture of this paper, as given in Section 3, is so inspired.

We work in $`d`$ dimensions, on a cubical periodic lattice, $`\mathrm{\Lambda }`$, of side $`L`$, so the total number of lattice sites is $`N=L^d`$. The Hilbert space, $``$, splits into sectors $`_i`$, $`i=0,\mathrm{},N`$, where in $`_i`$ there are $`i`$ spins up. The Hamiltonian, $`H`$, is given as

$$H=\underset{ij}{}(I_{ij}1)$$
(1.1)
$`I_{ij}`$ interchanges the spins of two neighboring sites $`i`$ and $`j`$ of the lattice $`\mathrm{\Lambda }`$. We will sometimes view $`H`$ as an operator on $``$, and sometimes as an element of the group algebra of the permutation group on the $`N`$ vertices of $`\mathrm{\Lambda }`$, allowing $`I_{ij}`$ to interchange vertices $`i`$ and $`j`$.

In what follows most of the development is not precise and rigorous, hand waving in nature. The conjectures are not precise either. We are far from a mathematically rigorous treatment. However, the independence of the arguments on precise details also means that a mathematically honest proof of the phase transition along these lines will not depend on obtaining proofs of the conjectures in a very circumscribed form. I.e., estimates of the flavor of our conjectures should work.

## 2 Strategy for Proving a Phase Transition.

In this Section all arguments are precise, and results proven or easy to prove. $`H`$ is taken as an operator on $``$. We let $`Tr(e^{\beta H})_{L,i}`$ be the trace of $`e^{\beta H}`$ restricted to $`_i`$, with $`L`$ the edge size (which we will vary). Let

$$F_\beta (L,n)=\underset{i=0}{\overset{n}{}}Tr(e^{\beta H})_{L,i}.$$
(2.1)
We note

$$F_\beta (L,N)=Tr(e^{\beta H}).$$
(2.2)
Theorem. Let $`r<\frac{1}{2}`$ and $`\beta `$ be fixed. Then if

$$\frac{F_\beta (L,[rN])}{F_\beta (L,N)}>\gamma >0$$
(2.3)
for some $`\gamma `$ and all large enough $`L`$, there is spontaneous magnetization for such $`\beta `$. Here \[s\] is the largest integer in $`s`$, and $`N=L^d`$.

We have not used a standard definition of spontaneous magnetization. We consider the two-point correlation function:

$$\rho _L(i,j)=\frac{Tr(e^{\beta H}\sigma _{iz}\sigma _{jz})_L}{Tr(e^{\beta H})_L}$$
(2.4)
where the subscript, $`L`$, of course, indicates the edge size of $`\mathrm{\Lambda }`$. We argue for spontaneous magnetization by excluding the existence of a $`d(|ij|)`$ with

$$\underset{x\mathrm{}}{lim}d(x)=0$$
(2.5)
for which

$$|\rho _L(i,j)|<d(|ij|)$$
(2.6)
if

$$|ij|<\frac{L}{2}.$$
(2.7)
That is, we will show Eq. (2.3) implies there is no $`d(x)`$ satisfying Eq. (2.5) - (2.7). We take this as the definition of spontaneous magnetization. The limitation Eq. (2.7) is due to working in a periodic domain.

We assume, by contradiction, the existence of such a $`d`$ in the presence of Eq. (2.3) being satisfied. We let $`H^{}={\displaystyle \underset{i\mathrm{\Lambda }}{}}\sigma _{zi}`$ and consider

$$A_L(\delta )=\frac{Tr(e^{\beta H\delta H^{}})_L}{Tr(e^{\beta H})_L}.$$
(2.8)
One easily deduces the chain of inequalities

$$1+t\delta ^2\underset{i,j\mathrm{\Lambda }}{}d(|ij|)>A_L(\delta )>1+q\delta ^2N_L^2$$
(2.9)
with $`t,q>0`$, and in the limit $`\delta `$ goes to zero. The right inequality in (2.9) comes from (2.3) and (2.8). The left inequality in (2.9) comes from (2.8) and the definition of $`\rho _L(i,j)`$, expanding the exponent in $`H^{}`$ to second order. The inequalities are inconsistent from

$$\underset{i,j\mathrm{\Lambda }}{}d(|ij|)a(\epsilon )N+\epsilon N^2$$
(2.10)
for each $`\epsilon >0`$.

## 3 The Central Approximation

In this section we view $`H`$ as an element of the group algebra of the permutation group on the $`N`$ vertices of $`\mathrm{\Lambda }`$. Then

$$e^{\beta H}=\underset{\alpha }{}\stackrel{~}{C}_\alpha G_\alpha $$
(3.1)
where $`G_\alpha `$ is an element of the permutation group on $`N`$ letters. We also want the lattice Laplacian heat equation Greens function

$$g_\beta (i,j)=(e^{\beta \mathrm{\Delta }})_{ij}$$
(3.2)
where, naturally, periodic boundary conditions are imposed in our periodic lattice. We let $`G_\alpha `$ map the vertices as

$$G_\alpha :ii_\alpha ,i=1,\mathrm{},N$$
(3.3)
The approximation we now conjecture is

$$\stackrel{~}{C}_\alpha \begin{array}{c}\\ \beta \mathrm{}\end{array}\stackrel{~}{C}\underset{i=1}{\overset{N}{}}g_\beta (i,i_\alpha ).$$
(3.4)
But we are not going to be precise in what sense the right side approximates the left side (the type of convergence). We will in fact replace the left side by the right side in expressions we use from now on. What we desire in a rigorous form of (3.4) is a result that enables the remaining proof to proceed. We have ideas how to mathematically prove approximations similar to (3.4) and plan to work on them as the first step in rigorizing the present paper.

## 4 The Polymers

Each permutation group element, $`G`$, has associated to it in a 1-1 way a partition of the $`|\mathrm{\Lambda }|=N`$ vertices, within each subset of the partition being given a specific cyclic ordering. If $`S`$ is a subset of the partition with $`k`$ vertices, then $`S`$ may be given as

$$\{i,Gi,G^2i,\mathrm{},G^{k1}i\}=S$$
(4.1)
for any $`i`$ in $`S`$. $`S`$, of course, corresponds to a $`k`$-cycle of $`G`$. We label the vertices in $`S`$ by $`\alpha _1,\alpha _2,\mathrm{},\alpha _k`$ with $`G\alpha _i=\alpha _{i+1},i<k`$, $`G\alpha _k=\alpha _1`$. To this $`k`$-cycle $`S`$ it is natural from (3.4) to associate an “activity$`e_S`$ by

$$e_S=\left(\underset{i=1}{\overset{k1}{}}g_\beta (\alpha _i,\alpha _{i+1})\right)g_\beta (\alpha _1,\alpha _k).$$
(4.2)
We have constructed a “polymer” with vertices, $`\{\alpha _i\}`$, and activity, $`e_S`$. This we call a “$`k`$-polymer”.

We now consider the sum over all possible $`k`$-polymers through vertex $`i`$, each times its activity. This leads to a sum

$$\underset{\gamma _2,\gamma _3,\mathrm{},\gamma _k}{}g_\beta (i,\gamma _2)g_\beta (\gamma _2,\gamma _3)\mathrm{}g_\beta (\gamma _{k1},\gamma _k)g_\beta (i,\gamma _k)$$
(4.3)
where the vertices $`i,\gamma _2,\mathrm{},\gamma _k`$ are restricted to be distinct. We estimate the sum in (4.3) to be

$$\frac{1}{(\sqrt{\beta })^d}\frac{1}{(\sqrt{k})^d}.$$
(4.4)
We argue this by viewing the sum in (4.3) to be a random walk in $`d`$ dimensions, with $`k`$ steps, and step size $`\sqrt{\beta }`$. The random walk will then have travelled a mean-square distance $`\sqrt{\beta }\sqrt{k}`$ and thus in $`d`$-dimensions have probability as given in (4.4) to return to origin, $`i`$.

## 5 Statistical Mechanics of the Trace

For any element, $`G`$, of the permutation group we define $`m(G)`$ to be the number of cycles in $`G`$. Referring to equation (3.1) we find the expression for the trace, Tr$`(e^{\beta H})`$

$$\mathrm{Tr}(e^{\beta H})=\underset{\alpha }{}2^{m(G_\alpha )}\stackrel{~}{C}_\alpha .$$
(5.1)
The factor of 2 associated to each cycle is from the choice of spin up or down. Each vertex in a given cycle must have same value of spin. (We evaluate the trace in the product of spin up, spin down bases, as usual.)

We let $`G_\alpha `$ contain $`s_\alpha (n)`$ $`n`$-cycles. Thus one must have

$$\underset{n=1}{}s_\alpha (n)n=L^d.$$
(5.2)
We play a usual statistical mechanics game of approximating the sum in (5.1) by keeping only terms with fixed values of the $`s(n)`$; and then maximizing this subsum of (5.1) over choices of the $`s(n)`$. For a given $`s(n)`$ value we sum over the $`s(n)`$ choices of $`n`$-cycles using Boltzmann statistics

$$\frac{(L^d)^{s(n)}}{s(n)!}\left(\frac{1}{(\beta n)^{d/2}}\right)^{s(n)}\frac{1}{n^{s(n)}}.$$
(5.3)
The factorial arises from the Boltzmann statistics. The $`L^d`$ factors arise from the choice of $`i`$ in (4.3). The middle factors arise from (4.4) and the final factor accounts for the fact that any of the $`n`$ vertices in a polymer may be the first vertex $`i`$ in (4.3).

We write the subsum of (5.1) we’ve approximated and expressed by $`e^\mu `$ and in standard style approximate $`\mu `$ as follows (with $`s(n)`$ written as $`s`$)

$$\mu =\underset{n}{}\left[sd\mathrm{}n(L)(s\mathrm{}n(s)s)\left(\frac{sd}{2}\right)\mathrm{}n(\beta n)s\mathrm{}n(n)+s\mathrm{}n(2)\right].$$
(5.4)
We use a Lagrange multiplier $`\alpha `$ to conserve (5.2), and differentiate

$$\frac{d}{ds}(\mu +\alpha sn)=0.$$
(5.5)
Solving (5.5) and (5.2) together one gets

$$\underset{n}{}\frac{1}{n^{d/2}}e^{\alpha n}=\frac{1}{2}(\sqrt{\beta })^d$$
(5.6)
and

$$s(n)=2\left(\frac{L}{\sqrt{\beta }}\right)^d\frac{1}{n^{(1+d/2)}}e^{\alpha n}.$$
(5.7)
We now restrict the above approximation to the trace on $`_k`$. This involves considering sequences $`r_i(n)`$ satisfying

$$\underset{n}{}r_i(n)n=k$$
(5.8)
with $`r_i(n)`$ satisfying

$$r_i(n)s(n).$$
(5.9)
The $`i`$ labels such a sequence of $`r_i(n)`$.

Then

$$\mathrm{Tr}\left(e^{\beta H}\right)_k\underset{i}{}\underset{n=1}{}\left(\begin{array}{c}s(n)\\ r_i(n)\end{array}\right)e^\mu .$$
(5.10)
Basically we are selecting ways of choosing which cycles have spin up, and making sure for each such choice (5.8) holds, so there are total $`k`$ spins up.

We again approximate the sum in (5.10) by its biggest term, using a Lagrange multiplier to uphold (5.8). We let $`\tau `$ be the Lagrange multiplier. We get

$$r(n)=s(n)\frac{e^{\tau n}}{1+e^{\tau n}}$$
(5.11)
and

$$\underset{n}{}2\left(\frac{L}{\sqrt{\beta }}\right)^d\frac{1}{n^{d/2}}\left(\frac{e^{\tau n}}{1+e^{\tau n}}\right)=k.$$
(5.12)
## 6 The Picture

We consider three cases

Case 1 $`d=2`$.

Case 2 $`d=3`$, and $`\beta <<1`$.

Case 3 $`d=3`$, and $`\beta >>1`$.

In cases 1 and 2 one has the equation (5.6) satisfied with $`\alpha <0`$, $`s(n)`$ as given by (5.7). Equations (5.6) and (5.7) are satisfied using only “finite” $`k`$-cycles, there are no “infinite” $`k`$-cycles. There is not spontaneous magnetization.

In case 3, to satisfy (5.6) $`\alpha `$ must be greater than zero. For given such $`\beta `$, as $`L`$ gets large one has the following limiting situation:

$$\alpha =0+\epsilon .$$
(6.1)
That is, $`\alpha 0^+`$ as $`L\mathrm{}`$.

$$s(n)=2\left(\frac{L}{\sqrt{\beta }}\right)^3\frac{1}{n^{5/2}}$$
(6.2)
for “finite” $`n`$, and in addition a single “infinite” $`k`$-cycle with $`k`$ given by

$$k=N2N\frac{1}{\beta ^{3/2}}\frac{1}{n^{3/2}}.$$
(6.3)
This single “infinite” $`k`$-cycle is needed to complement in the sum of (5.6) the contributions of “finite” $`k`$-cycles.

It is perhaps easy for the reader to believe, and even deduce at the level of our calculations that the presence of the “infinite” $`k`$-cycle yields spontaneous magnetization. Alternatively we may use the arguement of Section 2, picking $`r`$ satisfying (for $`\beta >>1`$)

$$r>>\frac{1}{\beta ^{3/2}}\frac{1}{n^{3/2}}$$
(6.4)
We have attempted some improvements to the estimates used, particularly in Section 5, but the ones we have considered have not changed the flow of the argument and results in any meaningful way. We believe the picture we have presented herein is essentially correct, and that the key test and challenge to completing a rigorous presentation will be in proving a satisfactory form of (3.4), the central approximation. The remaining steps, not unremniscent of a Peierls’ argument, may be easier to substantiate.

Acknowledgement. I’d like to thank Joe Conlon for getting me started, Elliott Lieb for keeping me going, and Murph Goldberger for teaching me the “What else could it be” type of argument.

References

* \] P. Federbush, For the Quantum Heisenberg Ferromagnet, Some Conjectured Approximations, math-ph/0101017.
* \] P. Federbush, For the Quantum Heisenberg Ferromagnet, A Polymer Expansion and its High T Convergence, math-ph/0108002.


text:
# Lorentz Invariance Violation and the QED formation length

## 1 Introduction

A tiny Lorentz invariance violation (LIV) at high energies was suggested  as an explanation of two experimental astrophysical paradoxes - the observations of ultra high energy cosmic rays (UHECR) well beyond the theoretically expected Greisen-Zatzepin-Kuzmin (GZK) cutoff around $`6\times 10^{19}`$ eV  and the observations of 20 TeV gamma-rays from Mkn 501. UHECR should have been absorbed in photoproduction collisions with the microwave background and the 20 TeV $`\gamma `$–rays – on the extragalactic infrared/optical background . While some authors  consider the second puzzle not so dramatic and LIV hypothesis too premature, the number of showers above $`10^{20}`$ eV is already big enough to suggest the existence of a problem. As a solution of this problem LIV was first suggested about 30 years ago  and later in . In , , ,  the LIV hypothesis was suggested as a solution for both paradoxes.

In Ref.  the Lorentz invariance violation was formulated to correspond to an energy dependent photon group velocity

$$\frac{E}{k}=c[1\xi _\gamma \frac{E}{E_0}].$$

Here $`c`$ is the speed of light. This corresponds to a dispersion relation

$$c^2k^2E^2+\xi _\gamma \frac{E^3}{E_0}$$
(1)
with $`\xi _\gamma =\pm 1`$ and $`E_010^{19}`$ GeV.

Kifune  has used this formulation to investigate the consequences of LIV on collisions of high energy radiation with soft photons. The detection of TeV photons from point sources and protons above the GZK cutoff sets some constraints on $`\xi _\gamma ,\xi _e`$ and $`\xi _p`$, when photons, electrons and protons are allowed to have different degrees of the LIV. He also noted that the modified relation of energy and momentum can affect mildly the detection of high energy radiation. Observations of $`\gamma `$-rays are based on pair creation in the detector material (satellite experiments) or on the detection of Cherenkov light from air showers initiated by TeV photons in ground-based observations. There are also numerous experiments using electromagnetic cascading in emulsion chambers to detect high energy electrons and $`\gamma `$-rays.

The common wisdom is  that although LIV affects significantly the GZK and TeV-$`\gamma `$ thresholds the effect of the modified dispersion relation on other interactions of the relevant high-energy particles is negligible.

The aim of the present paper is to discuss the possibility that LIV deformed dispersion relations could change not only the thresholds of some reactions at extremely high energies, but will also strongly affect the electromagnetic cascade development in the atmosphere and detectors. The reason for this is that deformed dispersion relations affect the  *formation length* of bremsstrahlung and pair production and, hence, their cross sections.

## 2 Formation length and LI violation

The longitudinal momentum transfer between highly relativistic interacting particles (photons or electrons) and the target nuclei is small. Ter-Mikaelian  first realized that according to the uncertainty principle the interactions take place not at a single point but over a long distance (*formation length, coherence length*). The interactions cannot be localized within this length. In the classical electrodynamics *coherent length* is the distance over which constructive interference between radiated waves takes place. During the time the electron travels the formation length it and the radiated electromagnetic wave separate enough  to be considered independent particles. In bremsstrahlung this separation is at least a distance of the order of the emitted photon wavelength $`\lambda `$. In the case of pair production the formation length is the length over which the electron and the positron separate by a distance of about two electron Compton wavelengths $`2/m`$.

While the transverse momentum exchanged with the nucleus, $`q_{},`$ is of order $`mc`$, the longitudinal momentum transfer $`q_{}`$ is small. In bremsstrahlung

$$q_{}=p_ep_e^{}k/c,$$
(2)
where $`p_e`$ and $`p_e^{}`$ are the electron momenta before and after the interaction and $`k`$ is the photon energy. At high energy $`Em_ec^2`$ we can neglect emission angles and simplify to $`q_{}\frac{m^2c^3k}{2E(Ek)}`$. In pair production $`q_{}\frac{m^2c^3k}{2E(kE)}`$. For bremsstrahlung the formation length thus is:

$$l_0\frac{\mathrm{}}{q_{}}=\frac{2\mathrm{}E(Ek)}{m^2c^3k}.$$
(3)
The formation length increases rapidly with the energy of the primary particle and with its ratio to the energy of the emitted photon. For pair production $`Ek`$ in the numerator is replaced by $`kE`$.

The formation length is closely related to the interaction cross section. The amplitude of the radiation is proportional to $`l_0`$, and its intensity is proportional to $`l_0^2`$. If there is emission from an electron traversing a distance $`D`$, this is equivalent to $`\frac{D}{l_0}`$ independent emitters, giving a total radiation intensity proportional to $`l_0^2D/l_0l_{0.}`$ .

Because of the small value of $`q_{}`$ the formation length $`l_0`$ can have macroscopic dimensions even at moderate energies. For example, for a 25 GeV electron, emitting a 100 MeV photon, $`q_{}0.03`$ eV/c and $`l_010`$ $`\mu m.`$ For 109 GeV electron and 105 GeV bremsstrahlung photon $`q_{}1.45\times 10^8`$ eV/c and $`l_014`$ m.

The coherence over this very long length can be disrupted by other interactions reducing the effective formation length and hence the probability for radiation. For instance, because at high energies $`l_0`$ becomes much longer than the average distance between the atoms of the medium, the multiple scattering of the electron on the atoms within the formation length will change the electron path by reducing the electron longitudinal velocity and the emission will be suppressed. This is the physical mechanism of the Landau-Pomeranchuk-Migdal (LPM) effect (see  and references therein). Other factors that could reduce $`l_0`$ , and hence the probability for radiation or pair production are  photon interaction with the medium (dielectric suppression), external magnetic field (magnetic suppression), suppression of bremsstrahlung by pair production, and vice-versa.

In the case of bremsstrahlung the multiple scattering on the formation length (LPM effect) leads to an additional term in the expression for $`q_{}`$ which increases the longitudinal momentum transfer. In the small angle approximation

$$q_{}\frac{m^2c^3k}{2E(Ek)}+\frac{k\theta _{MS}^2}{2c},$$
(4)
where $`\theta _{MS}`$ is the electron multiple scattering angle in half the formation length . The increase of $`q_{}`$ reduces the formation length. The multiple scattering becomes significant when the second term in (4) is larger than the first.

LIV modified dispersion relation acts like the suppression factors above. Let us put, similarly to Eq. 1, the square of the modified momentum

$$q^2=p^2+\xi \frac{E^3}{E_0c^2}$$
(5)
Then Eq. 2 becomes ($`qp+\xi \frac{E^2}{2E_0c}`$)

$$q_{}\frac{m^2c^3k}{2E(Ek)}+\xi _e\frac{E^2}{2E_0c}\xi _e\frac{(Ek)^2}{2E_0c}\xi _\gamma \frac{k^2}{2E_0c}$$
(6)
for bremsstrahlung, and

$$q_{}\frac{m^2c^3k}{2E(kE)}+\xi _\gamma \frac{k^2}{2E_0c}$$
(7)
for pair production. In Eq. 7 LIV dispersion relation is used only for the particle with the highest energy - the photon.

The effect depends on the signs of the parameters $`\xi `$. If we take the electron and positron energies in Eq. 7 equal to $`\frac{k}{2}`$ ($`k`$ is the photon energy), then

$$q_{}^{\mathrm{min}}\frac{2m^2c^3}{k}+\xi _\gamma \frac{k^2}{2E_0c}$$

When $`\xi _\gamma <0`$ $`q_{}^{\mathrm{min}}`$ becomes negative at the critical energy $`k_{cr}=[\frac{4(mc^2)^2E_0}{\xi _\gamma }]^{\frac{1}{3}}2.2`$x$`10^{13}`$ eV for $`\xi _\gamma =1`$.

Let us now calculate the *suppression factor S*, that measures the relative change of the interaction cross section and is defined as:

$$S=\frac{\frac{d\sigma }{dE}}{\frac{d\sigma }{dE_{BH}}}=\frac{l_f}{l_0}$$
(8)
where $`d\sigma /dE`$ is the differential cross section with suppression, $`d\sigma /dE_{BH}`$ is the Bethe-Heitler (BH) cross section, and $`l_f`$ is the formation length with suppression. This definition is convenient for estimation of suppression due to different factors because it is easy to estimate the change of the quantity $`q_{}`$ caused by these factors and, respectively $`l_f`$. For example, for strong suppression by multiple scattering, $`S_{LPM}=\sqrt{\frac{E_{LPM}k}{E(kE)}}`$ (the material dependent energy $`E_{LPM}`$ is defined in ). For $`EkEk/2`$ $`S_{LPM}2\sqrt{\frac{E_{LPM}}{k}\text{.}}`$

In case of pair production LIV gives a suppression factor

$$S_{LIV}=\frac{1}{1+\xi _\gamma \frac{k^3u(1u)}{E_0(mc^2)^2}}$$
(9)
(here $`u=E/k`$) and for $`EkEk/2`$

$$S_{LIV}\frac{1}{1+\xi _\gamma \frac{k^3}{4E_0(mc^2)^2}}$$
(10)
Neglecting $`1`$ in the denominator for strong suppression, Eq.10 becomes

$$S_{LIV}\frac{4E_0(mc^2)^2}{\xi _\gamma k^3}$$
(11)
Some numerical values for $`S_{LIV}`$ for pair production ($`E_0=10^{28}`$ eV , $`\xi _\gamma =1`$ ) are shown in table 1. For comparison LPM suppression factors for air ($`E_{LPM}`$=2.34$`\times `$108 GeV at sea level) and lead ($`E_{LPM}`$=4.3$`\times `$103 GeV) are also shown in the table (the values for $`E_{LPM}`$ are taken from ).

If $`\xi _\gamma =1`$

$$S_{LIV}=\frac{1}{1\frac{k^3}{4E_0(mc^2)^2}}$$

$`S_{LIV}`$ turns into enhancement, which becomes infinite for $`k=k_{thr}[4E_0(mc^2)^2]^{\frac{1}{3}}2.2\times 10^{13}`$ eV$`22`$ TeV, as shown in table 2.

This means that when $`\xi `$ is negative the formation length of the process (pair production in this case), respectively the cross section, increases. This sharp increase around $`k_{thr}`$ could in some cases be compensated by multiple scattering and other suppression factors.

The effects of LIV on bremsstrahlung are similar to those for pair production. If we neglect the last term in (6) (we suppose that LIV is negligible for low energy bremsstrahlung photons) the suppression factor becomes

$$S_{LIV}=\frac{1}{1+\xi _e\frac{2E^3(1u)}{E_0(mc^2)^2}}$$
(12)
or, for strong suppression,

$$S_{LIV}\frac{E_0(mc^2)^2}{2\xi _eE^3(1u)}$$
(13)
The corresponding LPM suppression factor (also for strong suppression) is

$$S_{LPM}=\sqrt{\frac{E_{LPM}}{E}\frac{u}{1u}}$$
(14)
Some numerical values for $`\xi =1`$ and $`u=0.001`$ are compared in table 3.

## 3 Discussion and conclusions

Using the concept of formation length we have shown that LIV parameters that are necessary for the explanation of the existence of UHECR and the non-absorption of 20 TeV $`\gamma `$-rays in a particular Lorentz invariance violation model will also strongly affect the bremsstrahlung and pair production cross sections. The general form of Planck scale motivated LIV dispersion relations is of the form

$$E^2p^2m^2\eta E^2(\frac{E}{E_0})^\alpha \eta p^2(\frac{E}{E_0})^\alpha ,$$

where $`\alpha `$ and $`\eta `$ are free parameters. We have only analyzed the case $`\alpha =1`$ and $`\eta =1`$.

To explain the experimental astrophysical paradoxes the positive values of $`\eta `$ should be excluded , which means that the parameter $`\xi `$ should be positive and the LIV would suppress pair production and bremsstrahlung above some critical energy $`k_{cr}`$. We obtain $`k_{cr}`$ values that are of the same order of magnitude as the critical energy $`E_c`$ defined in  (see also ). In the case of LIV $`E_c`$ is obtained from the condition for a minimum target photon energy for pair creation in a soft photon field. Above $`E_c`$ the target photon energy grows (for $`\xi >0`$) until the Universe becomes transparent to ultrahigh energy photons . This reflects the fact that () one can expect deviations from standard kinematics when the last two terms in the dispersion relation $`E^2p^2+m^2+\xi p^3/E_0`$ are of comparable magnitude. For $`\xi =1`$ the condition becomes $`p_{dev}(m^2E_0)^{\frac{1}{3}}10`$ TeV.

The suppression factor $`S`$ calculated above and shown for pair production in Table 1 is very strong and does not depend on the target material as in LPM. The suppression increases very fast with energy, proportionally to $`E^3`$ above 100 TeV. This will make photons and electrons very penetrating particles and will drastically suppress the electromagnetic shower development. For example, only about 20% of 100 TeV primary photons will interact in the atmosphere. For $`300÷400`$ TeV photons the atmosphere will be transparent. Such an effect must have already been observed in the numerous experiments in cosmic rays. The depth of maximum in electromagnetic showers $`X_{max}`$ is proportional to the product of the radiation length $`X_0`$ and the logarithm of the primary energy $`\mathrm{ln}E`$. In the case of LIV the radiation length $`X_0`$ above the critical energy becomes infinite, which changes drastically the behavior of electromagnetic and of hadronic air showers. This is especially true for giant air showers where the depth of maximum $`X_{max}`$ is generally determined by the electromagnetic cascades of primary energy exceeding 1017 eV. Thus LIV with the parameters discussed above would contradict to the results from giant air showers .

Coleman and Glashow  have suggested a different scheme for LIV in which the maximum attainable velocity $`c_a`$ of a particle is different from the photon velocity $`c`$. The relevant dispersion relations then has the form $`E_a^2=p^2c_a^2+m_a^2c_a^4`$. In this case our results will be applicable by substituting $`c^2c_a^2`$ for $`\xi \frac{E}{E_0}`$ in (1). Then the critical energy will be defined as $`k_{cr}=\frac{\sqrt{8}m_e}{c^2c_e^2^{1/2}}`$ . If the shower development is observed with no deviation from the standard cascade theory up to $`22`$ TeV, this will put the limits $`E_010^{28}`$ eV (Planck mass) or $`c^2c_e^21.5\times 10^{15}`$.

The observations of giant atmospheric showers created by particles with energies $``$ $`10^{20}`$ eV give, in principle, the possibility for a more precise test of LIV. For example, if the case $`\alpha =1`$ must be ruled out, one can move to the $`\alpha =2`$ case, i.e. quadratic suppression of $`E_0`$. The suppression factor for pair creation then becomes $`S_{LIV}\frac{4E_0^2(mc^2)^2}{\xi k^4}`$ and the drastic deformation of the shower development would be observed at energies $`10^{17}`$ eV. In the frame of Coleman and Glashow scheme this will put the limits $`c^2c_e^210^{23}`$. In this connection we would like to point out the interesting work  where new constraints on $`c_\gamma c_{\pi ^0}`$ ($`c_{\pi ^0}`$ is the maximal attainable speed of neutral pions) are obtained by comparing the experimentally measured position of the shower maximum $`X_{\mathrm{max}}`$ with calculations.

Our estimates are based on a quite general quantum-gravity induced modification of the dispersion relation between the energy and the momentum of a particle. We also supposed that the sign of the free parameter $`\xi `$ is fixed. As noted above, the positive sign of $`\xi `$ is required to solve the astrophysical paradoxes and is consistent with the constraints deduced from the analysis in . The future studies using the fruitful and physically very clear concept of the formation (coherent) length could include some additional phenomenological suggestions made in the literature. For example, it is possible to construct schemes in which the classical relation $`E^2=p^2+m^2`$ holds only on average, but in a given physical realization $`E^2=p^2+m^2+\mathrm{\Delta }`$, with $`\xi p^2(\frac{E}{E_0})^\alpha <\mathrm{\Delta }<\xi p^2(\frac{E}{E_0})^\alpha `$ . It is also possible that energy conservation (assumed in this work) may be valid only in a statistical sense (see the review  and references therein). If the LIV reflects some kind of special property of the space-time at Planck scales (or some other scale) the sign of $`\xi `$ may fluctuate on the length scales of the order of the Planck length. The negative sign of $`\xi `$ will, however, complicate the analysis. We showed above that for negative $`\xi `$ the formation length increases with energy, becoming infinite at the critical energy and negative above it. It is not obvious how to interpret the infinite, or negative, formation length in interactions with the field of a nucleus.

Finally, if the LIV is obtained as a result of spontaneous symmetry breaking in the context of an explicitly Lorentz invariant theory (see, e.g. ), it is possible that another scale (light mass scale $`m_l`$) enters the calculations. The correction term for the modified dispersion relation in this case is of the form (see (1)) $`\xi \frac{E^2V}{M_Pc^2}`$, where V is vev after the symmetry breaking and $`M_P`$ might be the Planck mass. In this case we could expect much smaller LIV depending on the value of $`m_l`$. For example, if $`V`$ is of the order of the other fundamental energy scale in nature, the electroweak scale $`m_{EW}10^3`$ GeV, then one can expect the deviation from the standard kinematics above $`p_{dev}50`$ TeV. The corresponding $`S_{LIV}`$ for pair production will be 0.51 for 100 TeV and 0.01 for 1000 TeV (instead of corresponding values $`10^2`$ and $`10^5`$ given in Table 1).

Acknowledgments. The work of TS is supported in part by the US Department of energy contract DE-FG02 91ER 40626.