text:
# Implementation of parallel algorithms for 2D vortex dynamics simulation in type-II superconductors

## I Introduction

The classical molecular dynamic (MD) simulation is a widely used computational method for studying the collective behaviour of interacting particles and appears in many diverse areas of science. The MD simulation involves numerically solving the classical Newton’s equation of motion for each particle starting from a set of initial conditions. The force on each particle in derived from the potential energy functional which contains the physics of the problem. Since the equation of motion of individual particle is solved, the MD simulation allows one to obtain details of the static and dynamical properties at the smallest length scale in the problem.

The computational complexity of the MD lies in two factors : the number of particles $`N`$, and the time scale of the phenomenon under simulation. A typical example is the melting of a simple cubic solid with dimension 50 lattice constants which requires 125,000 atoms simulation. Also, simulation of few pico-seconds of the real time dynamics would correspond to thousands of time steps which can be prohibitive even for large computers. Considerable research has therefore gone into optimizing algorithms for MD simulation depending upon the problem in hand. With development of parallel machines, various scalable algorithms for MD simulation has been given which can be used on a system with few processors to hundreds of processors. These algorithms use the message-passing model of programming for inter-processor communication. Another advantage of writing simulation code using message passing is due to availability of standard library which allows portability to various computing platforms.

In this report, we describe the implementation of two parallel MD algorithms for simulating 2D vortex dynamics in type-II superconductors. The algorithm used here have been previously developed and implemented by others for simulating short range MD simulation (see also Ref. for a review). To a large extent, this report is based on the work by Plimpton on short-range MD. The first algorithm uses the particle decomposition method wherein each processor is assigned a fixed number of particles. Each processor calculates the force on the same particles assigned to it irrespective of its spatial position. The second algorithm uses force decomposition method in which each processor calculates the sub-block of the force matrix. The parallelization is implemented using MPI and tested on a system with 4 processors. The purpose of this report is to present the simplicity of the algorithms in implementing and gain in run time compared to sequential algorithms on a single processor.

The report is presented as follows : in section II, the computational aspect of the problem is described. Section III explains the two algorithms in detail, whereas section IV compares the runtime for the two algorithms with vectorized algorithm.

## II Basic equation for vortex dynamics and its computational aspect

A vortex in the mixed phase of a bulk type-II superconductor is a line-like object which encompasses a quantum of magnetic flux ($`\frac{hc}{2e}`$ where $`h`$ is Planck constant, $`c`$ is the velocity of light, and $`e`$ charge of an electron) threaded by circulating super-current. The interaction between two vortices is electromagnetic and hence of long range nature. Though the vortex origin requires a quantum mechanical explanation, most of the physical properties (magnetisation, transport) of the mixed phase can be described by considering the vortices as classical interacting objects. In 2D, these vortices can be treated as point massless particles obeying the following overdamped equation of motion

$$\eta \frac{d\stackrel{}{r}_i}{dt}=\underset{ji}{}𝐅^{vv}(\stackrel{}{r}_i,\stackrel{}{r}_j)+\underset{j}{}𝐅^{vp}(\stackrel{}{r}_i,\stackrel{}{R}_j)+𝐅^{ext}$$
(1)
where $`\stackrel{}{r_i}`$ represents the co-ordinate of the $`i`$-th particle, and the first summation runs over all $`N1`$ particles. This term represents the repulsive force between two vortices and is given by the first-order Bessel function $`K_1(r)`$. At distances $`r1`$, the function decays rapidly as $`\frac{1}{r^{1/2}}\mathrm{exp}(r)`$. The second term represents the interaction between the vortex and the quenched disorder. The disorder co-ordinates $`\stackrel{}{R}`$ is distributed randomly in the simulation region, and the potential is attractive and short ranged. The last term is the force due to external condition that can include transport current. The above equation is a paradigm for driven interacting particles in presence of quenched disorder, and appears in other fields such charge-density wave (CDW), colloids, tribology.

Computationally, the maximum processor time in a single MD time step goes in calculating the two-body force represented by the first term. Even with overhead computational expenses, this could be as high as 95% (for instance, with 4800 vortices and 2000 point disorder, the first term accounts for 98% of the processor time). Therefore, much of the effort has been directed to optimize algorithms for calculating the two-body force. Since the second term is quenched and short ranged, it can be calculated efficiently by binning, and summing the forces over the closest bins. The third term is a one-body term and hence be efficiently vectorized and takes small fraction of the total computation time. Rest of the report hence deals with the computational aspect of the first term only.

It is useful to consider the positions of all particles as an $`N`$-dimensional vector $`𝐫=(\stackrel{}{r}_1,\stackrel{}{r}_2,\stackrel{}{r}_3,\mathrm{}\mathrm{}..\stackrel{}{r}_N)`$ where each of the $`\stackrel{}{r}_i`$ holds the $`d`$-dimensional co-ordinate of the $`i`$-th particle (henceforth, particle is assumed to imply vortex). Thus, for the 2D case $`\stackrel{}{r}_i=(x_i,y_i)`$. The force $`F_{ij}F(\stackrel{}{r}_i,\stackrel{}{r}_j)`$ between two particles at $`\stackrel{}{r}_i`$ and $`\stackrel{}{r}_j`$ can be thought as an element of a matrix of size $`N\times N`$. We denote such a force matrix by F. The total force on all $`N`$ particles can then be represented as a column vector of length $`N`$ such that the $`i`$-th element is given by $`\stackrel{}{f}_i=_{ij}F_{ij}`$. Symbolically, such a vector f can be written as

$$𝐟=𝐫𝐅𝐫$$
(2)
The MD simulation thus amounts to calculating $`𝐟`$ at each time step which is then used to update the vector $`𝐫`$.

The computational expense is reflected in the number of elements needed in the summation for $`\stackrel{}{f}_i`$. For long-range forces such as Coulomb force and gravitational force, each particle interacts with all $`(N1)`$ particles, thus requiring $`N1`$ elements of $`F_{ij}`$ in the summation for $`\stackrel{}{f}_i`$. Therefore, a direct calculation of such forces scales as $`N^2`$, and becomes prohibitively expensive even for moderate values of $`N`$. In the last decade, various approximate methods have been developed which allows considerable run time gain. They include particle-mesh algorithms which scale as $`f(M)N`$ where $`M`$ is the number of mesh points, hierarchical methods which goes as $`O(N\mathrm{log}N)`$, and fast multipole methods which scale as $`N`$. But most of these algorithms are difficult to implement and requires particular attention to data structure.

On the other hand, direct methods are specifically suitable for short-range forces in which case each particle interacts with few particles within a distance $`r_c`$. Typical examples are MD simulation employing Lennard-Jones potential and van-der Waals potential. In these simulations, a significant computational time is spend in searching for the particles within the cut-off distance $`r_c`$. There are two techniques usually employed for doing this. The first method constructs list of all atoms within a distance $`r_c+\delta `$ where $`\delta `$ is chosen to be small compared to $`r_c`$. The list is updated after few timesteps such that the total distance traveled by a particle between successive updates is less than $`\delta `$. The two-body force on a particle is found by summing over all particles within the list. The second method, known as link-cell method, employs binning of particles at every time step into cells of dimension $`r_c`$. Since this requires $`O(N)`$ operations, the overhead expenses more than compensates for the time required for searching particles within $`r_c`$ through the list of all $`N`$ particles. The fastest MD algorithms use both these techniques together.

For the interaction under consideration, the inter-particle force decays to a value $`10^8`$ at a distance $`r_c15`$ (in reduced units). This length scale is considerably larger (sometimes nearly half the system size) than usually employed in short-range MD, yet does not cover the whole system. Also, since the particle distribution is uniform, this leads to a significant fraction of total number of particles to be within the distance $`r_c`$ (for example, for 1200 particles in a square box of length 36, there are on an average 200 particles within a distance $`r_c`$). The construction of neighbour list is therefore of not much advantage and can occupy large memory. Also in the situation where particles are driven, the position changes randomly which would require frequent updating of the list. If $`r_c`$ is as large as half the length of the simulation box, binning of particles is not expected to give significant time gain (on the other hand, this is used for calculating the force due to disorder which is short ranged). The MD simulation presented here therefore does not employ both these techniques.

## III Parallel algorithms

In the last decade, with the arrival of multi-processor machines, much effort has been spend in constructing parallel MD algorithms. It is said that the MD computations are inherently parallel in the sense that force calculation and updates can be done simultaneously on all particles. The aim of parallelizing MD is to distribute the task of force calculation evenly among all processors. The various parallel algorithms are based on two basic methods. In the first class of methods, a pre-determined set of computation is assigned to each processor that remains fixed throughout the simulation time. One way of doing is to assign a group of particles to each processor, and at any time the processor computes the force for the particles assigned to it no matter where the particles are located in the simulation region. This is usually referred as atom decomposition (AD) or replicated-data method. Another possible way is to subscribe sub-blocks of the force matrix computation to each processor that has led to force-decomposition (FD) algorithms. Both these methods are analogous to Lagrangian gridding in computational fluid dynamics (CFD) where the grid cells (computational elements or processors) move along with the fluid (particles or atoms in MD). These two algorithms are discussed in detail below.

The second class of methods uses spatial decomposition (SD) wherein the simulation region is decomposed into cells and each cell is assigned to a processor. Each processor then computes the force on the particles within the cell region assigned to it. This is analogous to Eulerian gridding in CFD where the grid remains fixed and the fluid moves through it. In this report, we deal only with the implementation of atom decomposition and force-decomposition algorithms. Due to small number of processors available for computation, the spatial decomposition algorithm cannot be effectively compared with the others.

For the purpose of further discussions, we assume following symbols: the column vectors r, f and the matrix F assigned to a processor with rank $`k`$ is designated by the subscript $`k`$. The rank for the processors are indexed from 0 to $`P1`$ where $`P`$ is the total number of processors. Thus, $`𝐫_k`$ and $`𝐟_k`$ are the position vector and total force vector held in processor $`k`$, and $`𝐅_k`$ is the sub-block of the force matrix assigned to it. The number of particles (and hence the length of the vector $`𝐫_k`$ and $`𝐟_k`$) assigned to the $`k`$-th processor is represented by $`N_k`$. In all the cases considered here $`N_k=N/P`$. For simplicity, $`N`$ is chosen to be an integer multiple of $`P`$, and is not a constraint on the algorithm.

### A Atom-Decomposition algorithm

As mentioned earlier, in this method the computation is carried out by each of the $`P`$ processors for $`N_k(=N/P)`$ particles which are assigned to it at the start of the simulation. This amounts to assigning a sub-block of $`N_k`$ rows of the force matrix $`𝐅`$ to each processors. The $`k`$-th processor computes matrix elements of the sub-block $`𝐅_k`$. Let us assume that each processor has the updated co-ordinates of all particles initially assigned to it. To calculate the force for the next time step, the particles in $`k`$-th processor requires positions of all other particles held by the $`P1`$ processors. This implies that at each time step, each of the processor needs to communicate the co-ordinates of particles held by it to all other processors. This kind of collective communication can be implemented by calling all-to-all operation in MPI. An efficient algorithm to perform the same operation has been given by Fox et al. and is called an expand operation (see Appendix A for the details).

There are two versions of atom-decomposition method that is discussed in ref.. The A1 algorithm is a straightforward implementation of the above mentioned procedure. It does not use the skew-symmetric property of the force matrix $`𝐅`$, and hence the two-body force $`F_{ij}`$ is calculated twice (one by the processor holding $`\stackrel{}{r}_i`$ in the sub-vector, and the other holding $`\stackrel{}{r}_j`$). The A1 algorithm is outlined below :

1. Expand vector $`𝐫_k`$ and construct $`𝐫`$ in each processor.
2. Compute the sub-block $`𝐅_k`$ using $`𝐫_k`$ and $`𝐫`$, and sum the elements into $`𝐟_k`$ in each processor.
3. Update the sub-vector $`𝐫_k`$ in each processor using $`𝐟_k`$.

The communication cost of an algorithm is gauged by the number of messages (in MPI, a pair of MPI\_SEND and MPI\_RECV) and the volume of data exchanged. It would be fruitful to see both these factors for the above algorithm in each step. The first step expands the $`𝐫_k`$ in each processor to construct the full vector $`𝐫`$. This uses $`N_k`$ vector length for communication to $`P1`$ processors, and therefore scales as $`N_kP=N`$ (actually $`N_kPN_k`$). The second step computes the force on all the $`N_k`$ particles in $`𝐫_k`$. This operation scales as $`NN_k=\frac{N^2}{P}`$. And the last operation updates the vector $`𝐫_k`$ in each processor which also scales as $`N_k`$. Thus overall, the communication cost increases as $`N`$ and computation cost as $`\frac{N^2}{P}`$. Symbolically, the steps in the above algorithm can be represented as

$`𝐫`$ $`=`$ $`E_P[𝐫_k]`$ (3)
$`𝐟_k`$ $`=`$ $`𝐫_k𝐅𝐫`$ (4)
where $`𝐄_P`$ is an expand operation discussed in Appendix A. Note that $`𝐟_k`$ is of length $`N_k`$.

The second algorithm, denoted by A2, uses Newton’s law to avoid double computing of the two-body force. Though this leads to extra communication between processors, this can still outperform the algorithm A1 even for moderate values of $`N`$ when number of processors $`P`$ is small. The A2 algorithm references the pair-wise interaction only once by using a modified force matrix $`G`$, which is defined as follows : $`G_{ij}=F_{ij}`$, except that $`G_{ij}=0`$ when $`i+j`$ is even for $`i>j`$, and also when $`i+j`$ is odd for $`i<j`$. This makes the matrix $`G`$ appear as a checkerboard (with the diagonal also set to zero) as shown in Fig.1. The difference between A1 and A2 is in the second step. The force between $`i`$-th and $`j`$-th particle is calculated, and summed into both $`i`$ and $`j`$ positions of the resulting force vector $`𝐟^{^{}}`$. For e.g., from Fig.1, at the end of the force calculation, the processor 0 and 1 will have following elements in the vector $`𝐟^{^{}}`$  Processor 0 $`F_{1,3}+F_{1,5}+F_{1,7}+F_{1,9}+F_{1,11}F_{2,1}`$ $`F_{2,1}+F_{2,4}+F_{2,6}+F_{2,8}+F_{2,10}+F_{2,12}F_{3,2}`$ $`F_{3,2}+F_{3,5}+F_{3,7}+F_{3,9}+F_{3,11}F_{1,3}`$ $`F_{2,4}`$ $`F_{1,5}F_{3,5}`$ $`F_{2,6}`$ $`F_{1,7}F_{3,7}`$ $`F_{2,8}`$ $`F_{1,9}F_{3,9}`$ $`F_{2,10}`$ $`F_{1,11}F_{3,11}`$ $`F_{2,12}`$   Processor 1 $`F_{4,1}F_{6,1}`$ $`F_{5,2}`$ $`F_{4,3}F_{6,3}`$ $`F_{4,1}+F_{4,3}+F_{4,6}+F_{4,8}+F_{4,10}+F_{4,12}F_{5,4}`$ $`F_{5,2}+F_{5,4}+F_{5,7}+F_{5,9}+F_{5,11}F_{6,5}`$ $`F_{6,1}+F_{6,3}+F_{6,5}+F_{6,8}+F_{6,10}+F_{6,12}F_{4,6}`$ $`F_{5,7}`$ $`F_{4,8}F_{6,8}`$ $`F_{5,9}`$ $`F_{4,10}F_{6,10}`$ $`F_{5,11}`$ $`F_{4,12}F_{6,12}`$

This means that the vector obtained as an output from the force calculation in each processor is again of length $`N`$ unlike A1 where it is of size $`N_k`$. The vector $`𝐟^{^{}}`$ is summed across all processors so that total force is obtained as the sub-vector $`𝐟_k`$ in each processor. This operation of summing is called fold and can be performed optimally by Fox’s algorithm (see Appendix B). The A2 algorithm can then be enumerated as follows :

1. Expand vector $`𝐫_k`$ and construct $`𝐫`$ in each processor.
2. Compute the sub-block of $`G`$ using $`𝐫_k`$ and $`𝐫`$, and obtain $`𝐟^{^{}}`$.
3. Fold vector $`𝐟^{^{}}`$ across all processors and obtain $`𝐟_k`$.
4. Update the sub-vector $`𝐫_k`$ in each processor using $`𝐟_k`$.

Note that there is an additional communication (in step 3) of order $`N`$ as compared to A1 at the expense of halving the force calculation. A gain in runtime is possible if the communication time is a small percentage of overall time which is not the case if $`P`$ is large. As pointed out by Plimpton, in that case A1 algorithm is faster than A2. But for the case where the force calculation is intensive and $`P`$ is small, A2 can outperform A1 which is indeed observed in our simulation. Symbolically, the A2 algorithm becomes

$`𝐫`$ $`=`$ $`E_P[𝐫_k]`$ (5)
$`𝐟^{^{}}`$ $`=`$ $`𝐫_k𝐆𝐫`$ (6)
$`𝐟_k`$ $`=`$ $`𝐑_P[𝐟^{^{}}]`$ (7)
where $`𝐑_P`$ is a fold operation discussed in Appendix B.

Both A1 and A2 algorithms has communication operations which scales as $`N`$. This for large values of $`N`$ can be prohibitive. The advantage with these algorithms is its simplicity, which allows parallelizing an existing vectorized code (and this was indeed the reason why parallelization was attempted in our simulation).

### B Force-Decomposition algorithm

The force-decomposition (FD) algorithm, which was first implemented by Hendrickson and Plimpton for short-range forces, was motivated by block-decomposition of matrix for solving linear algebra problems. An important aspect of this algorithm is that the communication between processors scales as $`N/\sqrt{P}`$ rather than $`N`$ for the atom-decomposition algorithm. For the FD algorithm the processors are assumed to be arranged in cartesian topology (see ref.). Also, we use the following notations : the cartesian co-ordinates of the processor is denoted by the subscripts $`(j,k)`$ ($`j`$ is a row index, and $`k`$ the column index) and runs from $`0`$ to $`\sqrt{P}1`$. Thus, $`𝐫_{j,k}`$ and $`𝐟_{j,k}`$ are the position and total force vectors held by the processor with co-ordinates $`(j,k)`$. We also use notation in which row (column) index in the subscript is absent which implies that the same vector is held by all processors in the given column (row) index. As an example, $`𝐫_{j,}`$ is held by all processors in the $`j`$-th row, and $`𝐫_{,k}`$ by all processors in the $`k`$-th column. This typically arises when a vector is expanded along a row or column of processors (see appendix A). Also, for simplicity we assume that $`P`$ is an even power of $`2`$, and $`N`$ is an multiple of $`P`$.

The block decomposition of the force matrix is performed not on $`𝐅`$ but on a new matrix $`𝐅^{^{}}`$ obtained by using vector $`𝐫`$ and permuted vector $`𝐫^{^{}}`$. The permuted vector $`𝐫^{^{}}`$ is formed by lining up $`𝐫_{j,k}`$ held by each processors column wise i.e., $`𝐫^{^{}}=(𝐫_{0,0},𝐫_{1,0},\mathrm{}\mathrm{}𝐫_{\sqrt{P}1,0},𝐫_{0,1},𝐫_{1,1},\mathrm{}.,𝐫_{\sqrt{P}1,1},\mathrm{}\mathrm{})`$. Note that the vector $`𝐫`$ is distributed as $`𝐫=(𝐫_{0,0},𝐫_{0,1},\mathrm{}\mathrm{}𝐫_{0,\sqrt{P}1},𝐫_{1,0},𝐫_{1,1},\mathrm{}\mathrm{}𝐫_{1,\sqrt{P}1},\mathrm{}\mathrm{})`$. Both these vectors are shown in Fig.2. The elements of the force matrix $`F_{ij}^{^{}}`$ is the force between particles at $`\stackrel{}{r}_i`$ and $`\stackrel{}{r}_j^{^{}}`$.

To calculate the elements of the sub-block $`𝐅_{j,k}^{^{}}`$, two sub-vectors of length $`N/\sqrt{P}`$ each from $`𝐫`$ and $`𝐫^{^{}}`$ are required. For a processor with cartesian co-ordinates $`(j,k)`$, these vectors are in fact obtained by expand operation across $`j`$-th row and $`k`$-th column. These vectors are represented as $`𝐫_{j,}`$ and $`𝐫_{,k}^{^{}}`$. As an example, from Fig.2, the vectors $`𝐫_{j,}`$ and $`𝐫_{,k}^{^{}}`$ are given below for all the 4 processors :

Processor 0 : $`𝐫_{0,}`$ = {1,2,3,4,5,6} and $`𝐫_{,0}`$ = {1,2,3,7,8,9}

Processor 1 : $`𝐫_{0,}`$ = {1,2,3,4,5,6} and $`𝐫_{,1}`$ = {4,5,6,10,11,12}

Processor 2 : $`𝐫_{1,}`$ = {7,8,9,10,11,12} and $`𝐫_{,0}`$ = {1,2,3,7,8,9}

Processor 3 : $`𝐫_{1,}`$ = {7,8,9,10,11,12} and $`𝐫_{,1}`$ = {4,5,6,10,11,12}

The force is then calculated between the elements of $`𝐫_{j,}`$ and $`𝐫_{,k}^{^{}}`$, and summed in a sub-vector $`𝐟_{j,k}^{^{}}`$ which is of length $`N/\sqrt{P}`$. The total force sub-vector $`𝐟_{j,k}`$ is obtained by a fold operation on $`𝐟_{j,k}^{^{}}`$ across the $`j`$-th row of processors. Note that the expand and fold operations are along a row or column requiring only $`\sqrt{P}`$ processors, unlike AD algorithm where all $`P`$ processors are involved. This leads to an overall communication cost which scales as $`N/\sqrt{P}`$ only unlike $`N`$ in AD algorithms. The algorithm is summarised in the following steps :

1. Expand vector $`𝐫_{j,k}`$ along $`j`$-th row, and construct $`𝐫_{j,}`$ in each processor.
2. Expand vector $`𝐫_{j,k}`$ along $`k`$-th column, and construct $`𝐫_{,k}^{^{}}`$ in each processor.
3. Compute the sub-block of $`𝐅_{j,k}^{^{}}`$ using $`𝐫_{j,}`$ and $`𝐫_{,k}^{^{}}`$, and obtain $`𝐟_{j,k}^{^{}}`$.
4. Fold vector $`𝐟_{j,k}^{^{}}`$ across $`j`$-th row of processors and obtain $`𝐟_{j,k}`$.
5. Update the sub-vector $`𝐫_{j,k}`$ in each processor using $`𝐟_{j,k}`$.

Symbolically, the first four steps of the above algorithm can be represented as

$`𝐫_{j,}`$ $`=`$ $`𝐄_{P_{,k}}[𝐫_{j,k}]`$ (8)
$`𝐫_{,k}^{^{}}`$ $`=`$ $`𝐄_{P_{j,}}[𝐫_{j,k}]`$ (9)
$`𝐟_{j,k}^{^{}}`$ $`=`$ $`𝐫_{j,}𝐅^{^{}}𝐫_{,k}^{^{}}`$ (10)
$`𝐟_{j,k}`$ $`=`$ $`𝐑_{P_{j,}}[𝐟_{j,k}^{^{}}]`$ (11)
Note that there are 3 communication processes, 2 expand, and 1 fold operation involved in this algorithm.

This algorithm does not make use of Newton’s law and is designated as F1 algorithm. Using Newton’s law leads to halving of the computation at the expense of increased inter-processor communication. Instead of using $`𝐅`$ for obtaining a permuted matrix, one can use the checkerboard matrix $`𝐆`$ described for A2 algorithm. Such a matrix is shown in Fig. 3 for $`P=4`$ and $`N=12`$. Using G modifies the F1 algorithm in step 3 and 4. In step 3, the elements of $`𝐆_{j,k}^{^{}}`$ are computed and accumulated in $`i^{th}`$ position of $`𝐟_{j,k}^{^{}}`$ and $`j^{th}`$ position of $`𝐟_{j,k}^{^{\prime \prime }}`$. For example, these vectors are given explicitly below for the two processors shown in Fig.3 :

Processor 0

$`𝐟_{0,0}^{^{}}`$

$`F_{1,3}+F_{1,7}+F_{1,9}`$

$`F_{2,1}+F_{2,8}`$

$`F_{3,2}+F_{3,7}+F_{3,9}`$

$`F_{4,1}+F_{4,3}+F_{4,8}`$

$`F_{5,2}+F_{5,7}+F_{5,9}`$

$`F_{6,1}+F_{6,3}+F_{6,8}`$

$`𝐟_{0,0}^{^{\prime \prime }}`$

$`F_{2,1}+F_{4,1}+F_{6,1}`$

$`F_{3,2}+F_{5,2}`$

$`F_{1,3}+F_{4,3}+F_{6,3}`$

$`F_{1,7}+F_{3,7}+F_{5,7}`$

$`F_{2,8}+F_{4,8}+F_{6,8}`$

$`F_{1,9}+F_{3,9}+F_{5,9}`$

Processor 1

$`𝐟_{0,1}^{^{}}`$

$`F_{1,5}+F_{1,11}`$

$`F_{2,4}+F_{2,6}+F_{2,10}+F_{2,12}`$

$`F_{3,5}+F_{3,11}`$

$`F_{4,6}+F_{4,10}+F_{4,12}`$

$`F_{5,4}+F_{5,11}`$

$`F_{6,5}+F_{6,10}+F_{6,12}`$

$`𝐟_{0,1}^{^{\prime \prime }}`$

$`F_{2,4}+F_{5,4}`$

$`F_{1,5}+F_{3,5}+F_{6,5}`$

$`F_{2,6}+F_{4,6}`$

$`F_{2,10}+F_{4,10}+F_{6,10}`$

$`F_{1,11}+F_{3,11}+F_{5,11}`$

$`F_{2,12}+F_{4,12}+F_{6,12}`$

The $`𝐟_{j,k}^{^{}}`$ is folded across the row of processors to obtain $`𝐟_{j,}^{^{}}`$, and $`𝐟_{j,k}^{^{\prime \prime }}`$ is folded across the column of processors to obtain $`𝐟_{,k}^{^{\prime \prime }}`$. The total force $`𝐟_{j,k}`$ is obtained by subtracting $`𝐟_{j,}^{^{}}`$ from $`𝐟_{,k}^{^{\prime \prime }}`$ element by element. In the above example, folding the vector $`𝐟_{0,0}^{^{}}`$ and $`𝐟_{0,0}^{^{}}`$ along the row gives for particle 1

$`\underset{𝐟_{0,0}^{^{}}}{\underset{}{F_{1,3}+F_{1,7}+F_{1,9}}}+\underset{𝐟_{0,1}^{^{}}}{\underset{}{F_{1,5}+F_{1,11}}}`$

whereas same operation on $`𝐟_{0,0}^{^{\prime \prime }}`$ and $`𝐟_{1,0}^{^{\prime \prime }}`$ along the column gives

$`\underset{𝐟_{0,0}^{^{\prime \prime }}}{\underset{}{F_{2,1}+F_{4,1}+F_{6,1}}}+\underset{𝐟_{1,0}^{^{\prime \prime }}}{\underset{}{F_{8,1}+F_{10,1}+F_{12,1}}}`$

The total force on particle 1 is obtained by subtracting the second sum from the first. This also brings out an important feature that all elements of the force matrix for an $`i`$-th particle is calculated by those processors which share the row and column with the processor to which $`i`$-th particle is assigned. The F2 algorithm can be enumerated as follows :

1. Expand vector $`𝐫_{j,k}`$ along $`j`$-th row, and construct $`𝐫_{j,}`$ in each processor.
2. Expand vector $`𝐫_{j,k}`$ along $`k`$-th column, and construct $`𝐫_{,k}^{^{}}`$ in each processor.
3. Compute the sub-block $`𝐆_{j,k}^{^{}}`$ and accumulate them in $`𝐟_{j,k}^{^{}}`$ and $`𝐟_{j,k}^{^{\prime \prime }}`$.
4. Fold vector $`𝐟_{j,k}^{^{}}`$ across $`j`$-th row of processors and and obtain $`𝐟_{j,}^{^{}}`$.
5. Fold vector $`𝐟_{j,k}^{^{\prime \prime }}`$ across $`k`$-th column of processors and obtain $`𝐟_{,k}^{^{\prime \prime }}`$.
6. Subtract $`𝐟_{,k}^{^{\prime \prime }}`$ from $`𝐟_{j,}^{^{}}`$, and obtain $`𝐟_{j,k}`$
7. Update the sub-vector $`𝐫_{j,k}`$ in each processor using $`𝐟_{j,k}`$.

Symbolically, the F2 algorithm has the following structure

$`𝐫_{j,}`$ $`=`$ $`𝐄_{P_{,k}}[𝐫_{j,k}]`$ (12)
$`𝐫_{,k}^{^{}}`$ $`=`$ $`𝐄_{P_{j,}}[𝐫_{j,k}]`$ (13)
$`𝐟_{j,k}^{^{}}`$ $`=`$ $`𝐫_{j,}𝐆^{^{}}𝐫_{,k}^{^{}}`$ (14)
$`𝐟_{j,}^{^{}}`$ $`=`$ $`𝐑_{P_{j,}}[𝐟_{j,k}^{^{}}]`$ (15)
$`𝐟_{,k}^{^{\prime \prime }}`$ $`=`$ $`𝐑_{P_{,k}}[𝐟_{j,k}^{^{\prime \prime }}]`$ (16)
$`𝐟_{j,k}`$ $`=`$ $`𝐟_{j,}^{^{}}𝐟_{,k}^{^{\prime \prime }}`$ (17)
The increased communication and computation is evident in step 5 and 6 at the expense of reduced force computation.

## IV Results

We have implemented all the four algorithms A1, A2, F1 and F2 on a 4 processor (each of 180MHz) SGI system. The first order differential equation (1) is solved using a fourth order predictor-corrector scheme. This requires evaluating the right hand side of Eq.(1) twice at each time step. All the calculation is done in double precision. Since the force between two particles is Bessel function of order 1 ($`K_1(r)`$), evaluating the function at each time step is expensive. We follow the usual practice of tabulating the function at regular interval over the full range. The force at any distance is then obtained by interpolating the values in the table. The program is written in Fortran 90 whereas the inter-processor communication is handled using MPI. For the AD algorithms, the default communicator world is used which does not specify any topology for the processors. For FD algorithms, the cartesian topology is imposed leading to a grid of $`2\times 2`$ processors. The number of particles tested ranged from 120 to 4800. The idea here is not to simulate large particles but to show the possibility of parallel computation and its advantage even on a small number of processors.

Fig. 4(a) shows the CPU time required for a single MD time step with increasing density of particles for different algorithms using all 4 processors. The time for A1 algorithm and F1 is nearly equal. Note that both these algorithms computes the inter-particle force twice. The number of communications for A1 is less than that for F1 at the expense of increased force computation. On the other hand, for A2 and F2 algorithms, the number of communications are same, and A2 outperforms F2 due to less computation required. Note that with increasing number of processors, F2 is expected to perform better  as communication cost for this algorithm goes as $`O(N/\sqrt{P})`$ rather than $`O(N)`$ for A2.

Though, the total number of processors available is too small to obtain the trends with varying number of processors, it would still be instructive to plot the CPU time as a function of $`P`$ for a system of 4800 particles and is shown in Fig.4(b). The dotted line represents the ideal speed up, which is obtained by assuming that the time required for a single processor is equally divided among all available processors.

## V Conclusions

This report shows that considerable gain in run time can be achieved on implementing parallel MD simulation even for a moderate number of processors. Though the algorithms that have been implemented here were used by others for short-range MD, present work shows that it can be used even for forces that are inter-mediate range with advantage over vectorized algorithms. As stressed in this report, the main advantage is its simplicity in implementing and requiring few modifications for an already vectorized simulation code for a sequential machine.

For this work, the emphasis is simply on the parallelization of the basic MD simulation. In the implementation reported here, a significant fraction of the computing time goes in searching for particles within the cut-off distance for the force. It is to be seen as to how the conventional methods of MD, which uses nearest neighbour tables and link-cell method would enhance the performance. As stressed before, the problem at hand is that of driven particles in presence of quenched random disorder. At depinning velocities when a fraction of the particles move, the neighbourhood of a particle changes rapidly with time. This would call for frequent updating of the nearest neighbour table. Also, maintaining such a table for long range force may affect the overall performance which need to be verified. Other approximate methods for long-range force  need to be explored though these algorithms are difficult to implement on distributed memory machines.

## Appendix A

The expand operation on vectors $`𝐱_k=\{x_i\}_{i=1}^{N_k}`$ (the rank of the processor is denoted by subscript $`k`$) held by $`P`$ processors results in a vector $`𝐲=\{y_i\}_{i=1}^N`$ in all processors such that $`𝐲=(𝐱_1,𝐱_2,𝐱_3,\mathrm{}..𝐱_P)`$. The length of the vector $`𝐲`$ in all the $`P`$ processors is $`N=N_kP`$. Thus, vector $`𝐲`$ is constructed by arranging vector $`𝐱`$ in ascending order of the rank of the processors. Symbolically, this operation can be represented as

$$𝐄_P[𝐱_k]=𝐲$$
(19)
where $`𝐱=\{x_i\}_{i=1}^{N_k}`$ and $`𝐲=\{y_i\}_{i=1}^{N_kP}`$. Thus after an expand operation, the output buffer in each processor has a vector of length which is $`P`$ times the length of the vector held by each processor.

For a 2D grid of processors, if $`(j,k)`$ is the cartesian co-ordinates, an expand operation across $`j`$-th row can be symbolically represented as

$$𝐄_{P_{,k}}[𝐱_{j,k}]=𝐲_{j,}$$
(20)
and that along the $`k`$-th column as

$$𝐄_{P_{j,}}[𝐱_{j,k}]=𝐲_{,k}$$
(21)
The expand operation along the row (column) returns a vector of length $`N_k`$ time the number of processors in a column (row).

Fox et al. has prescribed an elegant and simple method to perform this operation (also see ref.). In the first step, each processor allocates memory for the full vector $`𝐲`$, and the vector $`𝐱_k`$ is mapped to its position in $`𝐲`$. Thus, at the beginning of the expand, $`k`$-th processor has $`𝐲=(0,0,\mathrm{}.𝐱^k,\mathrm{}0)`$. In the first communication step, each processor partners with the neighbouring processor, and exchange non-zero sub-pieces. At the end of this step, $`𝐲=(0,0,\mathrm{}.𝐱^k,𝐱^{k+1}\mathrm{}0)`$ for the $`k`$-th and $`(k+1)`$-th processors. Every processor thus obtains a contiguous vector of length $`2N_k`$. In the next step, every processor partners with a processor that is two positions away, and exchanges the new piece (of length $`2N_k`$). This leads to $`𝐲=(0,0,\mathrm{}.𝐱^k,𝐱^{k+1},𝐱^{k+2},𝐱^{k+3}\mathrm{}.0)`$ in each of $`k,k+1,k+2,k+3`$ processors. This steps leads to each processor acquiring $`4N_k`$ contiguous vector length. This procedure is repeated till each processor communicates with a processor that is $`P/2`$ position away, and at the end of which the entire vector y is acquired by all the $`P`$ processors. Fig. A1 shows the procedure for $`P=4`$ and $`N_k=3`$.

For the expand operation given above, there are $`\mathrm{log}_2P`$ messages and $`N_kPN_k`$ length of vector exchanged. This is an optimal value. Allocation of $`N_kP`$ memory in each of the processing element can become prohibitive when $`N_k`$ and $`P`$ are large, though for most purpose this is never a real concern. Note that the number of processors involved in expand operation can be a sub-set of total number of available processors (see FD algorithms).

## Appendix B

The fold operation between $`P`$ processors is the inverse of expand. If each processor holds a vector $`𝐲=\{y_i\}_{i=1}^N`$ where $`N=N_kP`$, the fold operation between $`P`$ processors leads to $`k`$-th processor acquiring a vector $`𝐱=\{x_i\}_{i=1}^{N_k}`$. The vector $`𝐱`$ is constructed by summing up vector $`𝐲`$ across all $`P`$ processors and allocating the $`k`$-th segment of it. Thus, if $`𝐲^j=(𝐲_1^j,𝐲_2^j,𝐲_3^j,\mathrm{}..𝐲_P^j)`$ where $`𝐲_k^j`$ is the $`k`$-th segment of $`𝐲`$ (of length $`N_k`$) in $`j`$-th processor, after a fold operation the $`k`$-th processor receives $`𝐱_k=_{j=1}^P𝐲_k^j`$. Symbolically, we represent this operation as

$$𝐑_P[𝐲]=𝐱_k$$
(22)
where $`𝐲=\{y_i\}_{i=1}^N`$ and $`𝐱=\{x_i\}_{i=1}^{N/P}`$. Thus after a fold operation, the output buffer has a vector of length $`N/P`$ where $`N`$ is the vector length used for folding.

The expand algorithm by Fox et al. can be inverted to obtain a simple and optimal method to perform fold operation (also see ref.). In the first step, each processor pairs up with processor that is $`P/2`$ position away, and exchanges pieces of vector length $`N/2`$. The pieces that are received are the one that the processor must acquire as a final sum. Thus, processor 0 pairs up with $`P/2`$ and sends vector segment $`𝐲=\{y_i\}_{i=\frac{N}{2}+1}^N`$ and receives $`𝐲=\{y_i\}_{i=1}^{N/2}`$, whereas the $`P/2`$-th processor sends vector segment $`𝐲=\{y_i\}_{i=1}^{N/2}`$ and receives $`𝐲=\{y_i\}_{i=\frac{N}{2}+1}^N`$. In the next step, the processor pairs up with the processor at $`P/4`$ and exchanges $`N/4`$ length of the new vector $`𝐲`$, again noting that each processor in the pair receives that part which it requires in the summation. This procedure is done recursively, and in each step the vector length exchanged is halved. Fig. A2 shows the entire procedure for $`P=4`$ and $`N=12`$. This algorithm is again an optimal one requiring $`\mathrm{log}_2P`$ steps and requiring exchange of $`NN/P`$ length of vector.

## Figure Captions

* The checkerboard matrix used for computing in A2 algorithm.
* (a) The arrangement of processors and the vectors r and $`𝐫^{^{}}`$ for F1 and F2 algorithms. Note that the vector $`𝐫^{^{}}`$ is obtained by expanding first along column and then across the row, whereas the original vector r is generated by first expanding across a row and then along a column. The block-decomposition of the force matrix is shown in (b).
* The block-decomposition of the force matrix for F2 algorithm. Note the vector on the top $`𝐫^{^{}}`$ and compare it with that in Fig.1. The permuted vector leads to change in the checkerboard arrangement of the force matrix.
* (a) The CPU time taken for a single MD step by different algorithms for a 4 processor system.

(b) The CPU time taken for a single MD step by AD and FD algorithms with increasing number of processors in a simulation of 4800 particles . The dotted line is the ideal speed up and is the time for a single processor divided by the number of processors.

* The expand operation across 4 processors ranked 0 to 3 for a vector $`𝐱_k`$ with 3 elements. In the first step, each processor partners with nearest processor and exchanges sub-pieces. Thus 0 gives elements {1,2,3}, and receives {4,5,6} elements of 1. After this, both 0 and 1 has contiguous array of elements {1,2,3,4,5,6}. Similarly 2 and 3 has {7,8,9,10,11,12}. In the second step, the processor pairs with those situated 2 positions away and repeats the exchange of non-zero pieces thus generating the full vector. There are only $`\mathrm{log}_2P`$ steps.
* The fold operation is an inverse of expand. This is shown here for $`P=4`$ and $`𝐱_k`$ with 3 elements (total vector length $`N=12`$). In the first step, each processor pairs with the processor that is $`P/2`$ position away and sends $`N/2`$ sub-piece in which it is not a member. Thus, processor 0 gets the first half of 2 and sends it the second half. The pieces are added up and stored in the same vector (the stacking of the pieces sidewise in the figure implies addition). In the second step, the processor partners with those at position $`P/4`$ away, and receives the $`N/4`$ piece in which it is a member. Thus 0 processor receives the {1,2,3} of processor 1, and sends it the elements {4,5,6}. Note that the elements {1,2,3} is the sum of elements held by processor 2 and 4. The fold operation also requires only $`\mathrm{log}_2P`$ steps.


format: text

text:
# Bipolarons in the Extended Holstein Hubbard Model

\[

## Abstract

We numerically and analytically calculate the properties of the bipolaron in an extended Hubbard Holstein model, which has a longer range electron-phonon coupling like the Fröhlich model. In the strong coupling regime, the effective mass of the bipolaron in the extended model is much smaller than the Holstein bipolaron mass. In contrast to the Holstein bipolaron, the bipolaron in the extended model has a lower binding energy and remains bound with substantial binding energy even in the large-U limit. In comparison with the Holstein model where only a singlet bipolaron is bound, in the extended Holstein model a triplet bipolaron can also form a bound state. We discuss the possibility of phase separation in the case of finite electron doping.

\]

There is growing evidence that electron-phonon coupling plays an important role in determining exotic properties of novel materials such as colossal magnetoresistance  and high-$`T_c`$ compounds . Since electrons in these materials are strongly correlated, the interplay between an attractive electron phonon interaction and Coulomb repulsion may be important in determining physics at finite doping. In particular, when the electron-phonon interaction is local, as is the case in the Holstein model, finite Coulomb repulsion leads to the formation of an intra-site bipolaron , with an effective mass of the order of the polaron effective mass .

It has been recently discovered that a longer-range electron-phonon interaction leads to a decrease in the effective mass of a polaron in the strong-coupling regime . The lower mass can have important consequences, because lighter polarons and bipolarons are more likely to remain mobile, and less likely to trap on impurities or from mutual repulsion. Motivated by this discovery, we investigate a simplified version of the Fröhlich model in the case of two electrons,

$`H=`$ $``$ $`t{\displaystyle \underset{js}{}}(c_{j+1,s}^{}c_{j,s}+H.c.)`$ (1)
$``$ $`\omega g_0{\displaystyle \underset{jls}{}}f_l(j)c_{j,s}^{}c_{j,s}(a_l+a_l^{})`$ (2)
$`+`$ $`\omega {\displaystyle \underset{j}{}}a_j^{}a_j+U{\displaystyle \underset{j}{}}n_jn_j,`$ (3)
where $`c_{j,s}^{}`$ creates an electron of spin $`s`$ and $`a_j^{}`$ creates a phonon on site $`j`$. The second term represents the coupling of an electron on site $`j`$ with an ion on site $`l`$, where $`g_0`$ is the dimensionless electron-phonon coupling constant. While in general long range electron-phonon coupling $`f_l(j)`$ is considered , we further simplify this model by placing ions in the interstitial sites located between Wannier orbitals, as occurs in certain oxides , shown in Fig. (1a). In this case it is natural to investigate a simplified model, where an electron located on site $`j`$ couples only to its two neighboring ions, i.e. $`l=j\pm 1/2`$. We describe such coupling with $`f_{j\pm 1/2}(j)=1`$ and 0 otherwise, and refer to this model as the extended Holstein Hubbard model (EHHM). We can view the EHHM as the simplest model with longer range than a single site, and use it to explore the qualitative change in physics in the simplest possible setting. While it is clear that in comparison to the Fröhlich model, our simplified EHHM lacks long range tails in the electron phonon interaction, the physical properties that depend predominantly on the short range interaction should be similar. For example, calculating the polaron energy of the original Fröhlich model as defined in Refs. , one finds that 94% of the total polaron energy comes from the first two sites.

In the case when $`f_l(j)=\delta _{l,j}`$, the model in Eq. (1) maps onto a Holstein-Hubbard model (HHM) (see also Fig.(1b)). The last two terms in Eq. (1) represent the energy of the Einstein oscillator with frequency $`\omega `$ and the on-site Coulomb repulsion between two electrons. We consider the case where two electrons with opposite spins ($`S_z=0`$) couple to dispersionless optical phonons with polarization perpendicular to the chain.

In this Letter we use a recently developed, highly accurate numerical technique , combined with a strong coupling expansion to study the simplified EHHM. Our main goal is to calculate physical properties such as the binding energy, effective mass, isotope effect, and the phase diagram of the EHHM bipolaron and compare them to the Holstein bipolaron that has been thoroughly studied recently . Even though the two models appear very similar, we find profound differences between the physical properties of bipolarons within the EHHM and the HHM.

The numerical method that we use creates a systematically expandable variational space of phonon excitations in the vicinity of the two electrons . The variational method is defined on an infinite lattice and is not subject to finite-size effects. It allows the calculation of physical properties at any wavevector $`k`$. In the intermediate coupling regime where it is most accurate, it provides results that are variational in the thermodynamic limit and gives energies accurate to 14 digits for the polaron case and up to 7 digits for the bipolaron case.

To investigate the strong coupling regime of the EHHM, we use a Lang-Firsov  unitary transformation $`\stackrel{~}{H}=e^SHe^S`$, where $`S=g_0_{jls}f_l(j)n_{js}(a_la_l^{})`$. This incorporates the exact distortion and interaction energies for static electrons into $`H_0`$, and leads to a transformed Hamiltonian

$`\stackrel{~}{H}`$ $`=`$ $`H_0+T,`$ (4)
$`H_0`$ $`=`$ $`\omega {\displaystyle \underset{j}{}}a_j^{}a_j\omega g_0^2{\displaystyle \underset{ijl}{}}f_l(i)f_l(j)n_in_j+U{\displaystyle \underset{j}{}}n_jn_j,`$ (5)
$`T`$ $`=`$ $`te^{\stackrel{~}{g}^2}{\displaystyle \underset{js}{}}c_{j+1,s}^{}c_{j,s}e^{g_0_l\left(f_l(j+1)f_l(j)\right)a_l^{}}`$ (7)
$`e^{g_0_l\left(f_l(j+1)f_l(j)\right)a_l}+\mathrm{H}.\mathrm{c}.,`$
where $`n_j=n_j+n_j`$ and $`\stackrel{~}{g}^2=g_0^2_l[f_l(0)^2f_l(0)f_l(1)];`$ $`\stackrel{~}{g}=g_0`$ for the EHHM. The second term in $`H_0`$ gives the polaron energy, which in the EHHM case is $`ϵ_p=2\omega g_0^2`$, while for the HHM, $`ϵ_p=\omega g_0^2`$. This term also includes the interaction between electrons located on neighboring sites, a consequence of the non-local electron-phonon interaction. As noted by Alexandrov and Kornilovitch , in the strong coupling regime a Fröhlich polaron has a much smaller effective mass than a Holstein polaron with the same polaron energy $`ϵ_p`$. The reason for lower mass in the Fröhlich case (as well as EHHM) is that the effective electron-phonon coupling that renormalizes hopping $`\stackrel{~}{g}^2=\gamma ϵ_p/\omega `$ is smaller (in EHHM, $`\gamma =1/2`$) than in the case of the HHM with $`\gamma =1`$. In the strong coupling EHHM polaron, the phonon is displaced on two sites. It is identical on one of these sites in the initial and the final state after the electron hop, resulting in a smaller mass enhancement from phonon overlap.

In the anti-adiabatic limit where $`g_00`$ and $`\omega \mathrm{}`$ with $`\omega g_0^2`$ constant, the phonon interaction is instantaneous and our simplified EHHM model maps onto a generalized Hubbard model

$`H`$ $`=`$ $`t{\displaystyle \underset{js}{}}(c_{j+1,s}^{}c_{j,s}+H.c.)`$ (8)
$`+`$ $`\stackrel{~}{U}{\displaystyle \underset{j}{}}n_jn_j+V{\displaystyle \underset{j}{}}n_jn_{j+1},`$ (9)
with an effective Hubbard interaction $`\stackrel{~}{U}=U4\omega g_0^2`$ and $`V=2\omega g_0^2`$. In the case of two electrons an analytical solution can be found. As many as three bound states may exist: two singlets and a triplet. In the case when $`U=0`$ there is always at least one singlet bound state. A triplet bound state with an energy $`E=2\omega g_0^22t^2/\omega g_0^2`$ exists only when $`\omega g_0^2>t`$.

In the strong coupling limit, $`T`$ in Eq. (4) may be considered as a perturbation. In the case when $`U<2\omega g_0^2`$, the single site or S0 bipolaron, defined as $`\varphi _{S0}=c_0^{}c_0^{}|0`$, has the lowest energy to zeroth order. In this regime the binding energy is $`\mathrm{\Delta }=E_{bi}^{S0}2ϵ_p=U4\omega g_0^2`$, where $`E_{bi}^{S0}`$ denotes the S0 bipolaron energy and $`ϵ_p`$ is the energy of a polaron in zeroth order. In the opposite regime, when $`U>2\omega g_0^2`$, the inter-site or S1 bipolaron, $`\varphi _{S1}^{S=0,1}=\frac{1}{\sqrt{2}}(c_0^{}c_1^{}\pm c_0^{}c_1^{})|0`$, has the lowest energy. Its binding energy $`\mathrm{\Delta }=2\omega g_0^2`$ does not depend on $`U`$, which also leads to a degeneracy between the spin-singlet (S=0) and the spin-triplet (S=1) state. This simple analysis predicts that a EHHM bipolaron (EHB) remains bound in the strong coupling regime even in the limit when $`U\mathrm{}`$.

It is worth stressing that in the limit $`U\mathrm{}`$, singlet and triplet bipolarons become degenerate. We can therefore predict the existence of a singlet and a triplet bipolaron, where at finite $`U`$ the singlet bipolaron has lower energy. It is also obvious that the energy of the triplet bipolaron should not depend on $`U`$. In contrast to these predictions, a triplet Holstein bipolaron (HB) is never stable, and furthermore in the limit $`U\mathrm{}`$ no bound HB exists .

Next, we focus on the effective mass of the EHB in the strong coupling regime. First order perturbation theory does not lead to energy corrections for the S0 EHB. Second order perturbation theory gives

$$m_{S0}^{}{}_{}{}^{1}=4t^2e^{2g^2}\underset{n=0}{}\frac{(2g^2)^n}{n!}\frac{1}{ϵ_pU+n\omega },$$
(10)
where $`m^1d^2E(k)/dk^2`$. Equation (10) is only valid in the limit when $`1/\lambda 2t/ϵ_p0`$ and $`Uϵ_p`$. In the limit of large $`g`$ and $`U=0`$, $`m_{S0}^{}\mathrm{exp}(2ϵ_p/\omega )`$, which should be compared to the HB effective mass that scales as $`m_{S0}^{}\mathrm{exp}(4ϵ_p/\omega )`$ . In the strong coupling regime the EHB should be much lighter than the Holstein bipolaron. There is a particularly interesting EHB regime when $`U=ϵ_p`$. In this case the zero order energies of the $`\varphi _{S0}`$ and $`\varphi _{S1}^{S=0,1}`$ bipolarons are degenerate. Degenerate first order perturbation theory can be applied to the spin-singlet EHB in this case, which leads to a substantial decrease in the effective mass

$$m_{EHB}^{}(U=ϵ_p)=\frac{\sqrt{2}}{t}e^{ϵ_p/2\omega }.$$
(11)
The EHB in this regime consists of a superposition of $`\varphi _{S0}`$ and $`\varphi _{S1}^{S=0}`$, and moves through the lattice in a crab-like motion. Its binding energy is $`\mathrm{\Delta }=ϵ_p2\sqrt{2}t\mathrm{exp}(ϵ_p/2\omega )`$.

In the $`U\mathrm{}`$ limit we apply the second-order perturbation theory to the S1 bipolaron. We take into account processes where one of the electrons within the S1 bipolaron jumps to the left (right) and then the other follows. This leads to

$$m_{EHB}^{}(U=\mathrm{})=\frac{\lambda }{t}e^{ϵ_p/\omega }.$$
(12)
Strong coupling approach thus predicts nonmonotonous dependence of the effective EHB mass as a function of $`U`$ as can be seen from different exponents in Eqs. (10,11,12).

We next present numerical results. To achieve sufficient accuracy, we have used up to $`3\times 10^6`$ variational states. We use units where the bare hopping constant is $`t=1`$. The ground state energy of the EHB at $`\lambda =0.5`$, $`\omega =U=1`$, is E = -5.822621, which is accurate to the number of digits shown. (For the same parameters, $`U=0`$, the Holstein bipolaron energy is E = -5.4246528.) The accuracy of our plotted results in the thermodynamic limit is well within the line-thickness. In Fig. (2a) we present the inverse effective masses of the EHB and the HB at $`U=0`$ and of the EHB at $`U=ϵ_p`$. Our results for the bipolaron mass are in qualitative agreement with results for the polaron effective mass by Alexandrov and Kornilovitch . In the weak coupling regime we find the EHB slightly heavier than the HB, while in the strong coupling regime the opposite is true. Setting the Coulomb interaction to $`U=ϵ_p`$, the effective mass becomes even lighter, which is a consequence of the smaller exponent in Eq. (11). In the strong coupling regime ($`\lambda 1`$), we find good agreement with our strong coupling predictions in Eqs. (10,11), depicted by thin lines. While the absolute values may differ by up to a factor of 4 (in the case of $`U=ϵ_p`$), the strong coupling approach almost perfectly predicts the exponential dependence (seen as parallel straight lines in Fig. (2a)) of the effective masses on $`ϵ_p=2t\lambda `$.

To obtain better understanding of the effect of on-site Coulomb repulsion on the bipolaron effective mass in the strong coupling regime, we present in Fig. (2b) effective masses of the EHB and HB at fixed coupling strength $`\lambda =1.45`$ as a function of $`U`$. The most prominent finding is that the EHB is two orders of magnitude lighter than the HB when $`U=0`$. While the effective mass of the HB decreases monotonously with $`U`$, the EHB effective mass reaches a shallow minimum near $`U=ϵ_p`$ as predicted by the strong coupling approach. At larger $`U>ϵ_p`$ we observe a slight increase in the effective mass. In the same regime HB effective mass drops below EHB effective mass. This crossing coincides with a substantial decrease of the HB binding energy and consequently with separating of HB into two separate polarons. Numerical results for the EHB agree reasonably well with analytical predictions for small $`U`$, Eq. (10), and also in the limit of large $`U`$, Eq. (12).

To gain an insight into the symmetry of the bound EHB state, we have calculated the binding energy $`\mathrm{\Delta }^{(0,1)}=E_{bi}^{(0,1)}2E_{po}`$ where $`E_{bi}^{(0,1)}`$ are the ground state and the first excited energy of the EHHM or HHM for two electrons with opposite spins, $`S_z=0`$, and $`E_{po}`$ is the ground state energy of the corresponding model with one electron. In Fig. (3a) we present binding energies of the bipolaron ground and first excited states as a function of $`U`$. An important difference between the HHM and the EHHM is that in the former case a critical $`U_c`$ exists for any coupling strength $`\lambda `$ when the HB unbinds, while the EHB remains bound even in the limit $`U\mathrm{}`$ when $`\lambda >\lambda _c=0.76`$. At small $`U`$ excited states of both models correspond to bipolaronic singlets, spaced approximately $`\omega `$ above the ground state. Singlets can be recognized by the fact that their binding energies depend on $`U`$. As $`U`$ increases, the excited state of the HB unbinds while the excited state of the EHB undergoes a transition from a singlet to a triplet state which is also bound.

By solving $`\mathrm{\Delta }^{(0,1)}(\lambda ,U_c)=0`$ we arrive at the phase diagram $`(U_c,\lambda )`$ of the EHHM calculated at fixed $`\omega =1`$, presented in Fig. (3b). We indicate three different regimes. For small $`\lambda `$ and large $`U`$ no bound bipolarons exist. With increasing $`\lambda `$ there is a phase transition into a bound singlet bipolaron state. Increasing $`\lambda `$ even further, a triplet bipolaron becomes bound as well at $`\lambda =\lambda _c`$. For comparison we also include the phase boundary of the HHM (open circles). Note that only a singlet bipolaron exists in the HHM.

In Fig. (3c) we present a cross section through the phase diagram in Fig. (3b) at fixed $`U=5`$, and plot $`m_{}^{}{}_{}{}^{1}`$ and the isotope effect $`\alpha d\mathrm{ln}m_{bi}/d\mathrm{ln}M`$ vs. $`\lambda `$ (see also discussion of the isotope effect in Ref. ). The effective mass increases by approximately a factor of 2.5 from its noninteracting value in the regime where only a spin-singlet bipolaron exists (between the two vertical dashed lines). The increase of the effective mass is followed by an increase in the isotope effect. The binding energy (not plotted) reaches a value $`\mathrm{\Delta }0.5t`$ at $`\lambda =\lambda _c=0.76`$.

To conclude, we have shown that a light EHB exists even in the strong coupling regime with an effective mass that can be a few orders of magnitude smaller than the HB effective mass at small $`U`$. At finite $`U=ϵ_p`$ a regime of extremely light EHB is found where bipolaron effective mass scales with the same exponent as the polaron effective mass. This mobile bipolaron arises as a superposition of a $`\varphi _{S0}`$ and a $`\varphi _{S1}`$ state and it moves through a lattice in a crab-like motion. As found in ref. , HB becomes very light with increasing $`U`$ close to the transition into two unbound polarons at $`U=U_c`$. Near this transition, its binding energy diminishes substantially and reaches $`\mathrm{\Delta }=0`$ at the transition point $`U_c`$. In contrast, EHB can have a small effective mass even in the regime where its binding energy is large ( in the strong coupling regime $`\mathrm{\Delta }`$ approaches $`\mathrm{\Delta }=ϵ_p`$). Furthermore, EHB remains bound in the limit when $`U\mathrm{}`$. As a consequence of a longer-range electron-phonon interaction, a bound spin-triplet bipolaron exists in the EHHM for $`\lambda >\lambda _c`$ The difference between the binding energies of the spin-singlet and the spin-triplet bipolaron is proportional to $`1/U`$. In the weak to intermediate coupling regime of the EHHM ($`\lambda <\lambda _c`$ and finite $`U`$) $`S=0`$ bipolarons exist with substantial binding energy close to $`\lambda \lambda _c`$, and an effective mass of the order of noninteracting electron mass.

The existence of a singlet and a triplet EHB state has important implications in the case of finite doping. As was established previously, there is no phase separation in the low-density limit of the HHM despite a substantially renormalized bandwidth . The reason is in part that a triplet bipolaron is always unstable. The lack of phase separation in the low-density limit and in the strong coupling regime has a simple intuitive explanation: a third particle, added to a bound singlet bipolaron, introduces a triplet component to the wavefunction. The opposite is true in the strong coupling limit of EHHM where singlet and triplet bipolarons coexist. In this case, the third added particle simply attaches to the existing singlet bipolaron and thus gains in the potential energy. We therefore expect that the EHHM phase separates in the case of finite doping for $`\lambda `$ sufficiently large. To stabilize a system of EHHM bipolarons against phase separation, a long-range Coulomb repulsion should be taken into account. This prediction is in agreement with recent findings by Alexandrov and Kabanov  that state, that there is no phase segregation in the Fröhlich model in the presence of long-range Coulomb interactions.

J.B. gratefully acknowledges the support of Los Alamos National Laboratory where part of this work has been performed, and financial support by the Slovene Ministry of Science, Education and Sport. This work was supported in part by the US DOE.


text:
# Energy Associated with a Charged Regular Black Hole

## 1 INTRODUCTION

A problem which still remains unsolved in general relativity is the energy-momentum localization.

Although an adequate coordinate-independent expression for energy and momentum density has not given yet, various energy-momentum complexes including those of Einstein -, Landau and Lifshitz , Papapetrou , Bergmann , Weinberg  and Møller  lead to acceptable results for many space-times. Cooperstock  gave his opinion that the energy and momentum are confined to the regions of non-vanishing energy-momentum tensor of the matter and all non-gravitational fields. Also, Chang, Nester and Chen  showed that the energy-momentum complexes are actually quasilocal and legitimate expressions for the energy-momentum. The above energy-momentum complexes, except that of Møller, need to carry out the calculations in “Cartesian coordinates”. The results obtained for some well-known space-times are encouraging -.

Aguirregabiria, Chamorro and Virbhadra  obtained that several energy-momentum complexes “coincide” for any metric of the Kerr-Schild class. In  Virbhadra established that several energy-momentum complexes (ELLPW) comply with the quasi-local mass definition of Penrose for a general non-static spherically symmetric metric of the Kerr-Schild class. He obtained the expression of the energy distribution for this general metric.

In this paper we first show that using an adequate coordinate transformation we can express the charged regular black hole (Ayón-Beato and Garcia, (ABG))  metric in Kerr-Schild Cartesian coordinates. Then we compute the energy distribution in this space-time using the energy expression given by Virbhadra . The result is the same as we obtained in the Einstein prescription  using the Schwarzschild Cartesian coordinates. We use the geometrized units $`(G=1,c=1)`$ and follow the convention that Latin indices run from $`0`$ to $`3`$.

## 2 ENERGY OF THE CHARGED REGULAR BLACK HOLE

A solution to the coupled system of the Einstein field and equations of the nonlinear electrodynamics was recently given by E. Ayón-Beato and A. Garcia (ABG) . This is a singularity-free black hole solution with mass $`M`$ and electric charge $`q`$. Also, the metric at large distances behaves as the Reissner-Nordström solution. The usual singularity of the RN solution, at $`r=0`$, has been smoothed out and now it simply corresponds to the origin of the spherical coordinates. This solution is given by the line element

$$ds^2=A(r)dt^2B(r)dr^2r^2(d\theta ^2+\mathrm{sin}^2\theta d\phi ^2),$$
(1)
where

$$A(r)=B^1(r)=1\frac{2M}{r}(1\mathrm{tanh}(\frac{q^2}{2Mr})).$$
(2)
If the electric charge vanishes we reach the Schwarzschild solution. At large distances (1) resembles to the Reissner-Nordström solution and can be written

$$A(r)=B^1(r)=1\frac{2M}{r}+\frac{q^2}{r^2}\frac{q^6}{12M^2r^4}+O(\frac{1}{r^6}).$$
(3)
The Kerr-Schild class space-times have the form

$$g_{ik}=\eta _{ik}Hl_il_k,$$
(4)
where $`\eta _{ik}=diag(1,1,1,1)`$ is the Minkowski metric. $`H`$ represents the scalar field and $`l_i`$ is a null, geodesic and shear free vector field in the Minkowski space-time. We also have

| $`\eta ^{ab}l_al_b=0,`$ |
| --- |
| $`\eta ^{ab}l_{i,a}l_b=0,`$ |
| $`(l_{a,b}+l_{b,a})l_{,c}^a\eta ^{bc}(l_{,a}^a)^2=0.`$ |

(5)
Aguirregabiria, Chamorro and Virbhadra  showed that for the space-times of the Kerr-Schild class the energy-momentum complexes of Einstein, Landau and Lifshitz, Papapetrou and Weinberg “coincide”.

We use the transformation

$$u=t+A^1(r)𝑑r$$
(6)
and we get

$$dt=duA^1(r)dr.$$
(7)
Also, we obtain

$$dt^2=du^2+A^2(r)dr^22A^1(r)drdu.$$
(8)
Using (8) the line element (1) becomes

$$ds^2=A(r)du^22dudrr^2(d\theta ^2+\mathrm{sin}^2\theta d\phi ^2),$$
(9)
that is the static case of the general non-static spherically symmetric space-time of the Kerr-Schild class used by Virbhadra  to calculate the energy distribution with the energy-momentum complexes of Einstein, Landau and Lifshitz, Papapetrou and Weinberg (ELLPW).

Now, with the transformations

| $`T=ur,`$ |
| --- |
| $`x=r\mathrm{sin}\theta \mathrm{cos}\phi ,`$ |
| $`y=r\mathrm{sin}\theta \mathrm{sin}\phi ,`$ |
| $`z=r\mathrm{cos}\theta ,`$ |

(10)
the metric given by (9) can be written

$$ds^2=dT^2dx^2dy^2dz^2(1A)\times [dT+\frac{xdx+ydy+zdz}{r}]^2.$$
(11)
For (11) we have $`H=1A`$ and $`l_i=(1,\frac{x}{r},\frac{y}{r},\frac{z}{r})`$. We evaluate the energy using the expression obtained by Virbhadra , (see Eq. (31) therein), in the case of a general non-static spherically symmetric space-time of the Kerr-Schild class, and which is the same in the (ELLPW) prescriptions. Our case is the static case, which is a special case of the metric considered by Virbhadra. We get

$$E(r)=\frac{r}{2}(1A(r)).$$
(12)
We obtain for the energy distribution of the ABG black hole

$$E(r)=M(1\mathrm{tanh}(\frac{q^2}{2Mr}))$$
(13)
and

$$E(r)=M\frac{q^2}{2r}+\frac{q^6}{24r^3M^2}\frac{q^{10}}{240M^4r^5}+O(\frac{1}{r^6}).$$
(14)
Also, for (14) we can write

$$E(r)=E_{RN}(r)+\frac{q^6}{24M^2r^3}\frac{q^{10}}{240M^4r^5}+O(\frac{1}{r^6}),$$
(15)
where the term $`E_{RN}(r)`$ represents the energy of the Reissner-Nordström solution that corresponds to the Penrose  quasi-local mass definition.

We define $`E^{^{}}=\frac{E(r)}{M}`$, $`Q=\frac{q}{M}`$ and $`R=\frac{r}{M}`$ and we have $`E^{^{}}=1\mathrm{tanh}(\frac{Q^2}{2R})`$. We plot the expression of $`E^{^{}}`$ in the Figure 1 ($`E^{^{}}`$ on Y-axis is plotted against $`R`$ on X-axis, for $`Q=0.1,\mathrm{},1`$).

## 3 DISCUSSION

Bondi  gave his opinion that a nonlocalizable form of energy is not admissible in relativity.

For the charged regular black hole solution given by Ayón-Beato and Garcia we make a coordinate transformation that allow us to evaluate the energy distribution using the expression of the energy obtained by Virbhadra  (see Eq. (31) therein), for a general non-static spherically symmetric space-time of the Kerr-Schild class. The new form of the (ABG) metric is a special static case of the metric considered by Virbhadra . The energy distribution depends on the mass $`M`$ of the black hole and electric charge $`q`$. Also, the result is the same as we obtained  in the Einstein prescription using the Schwarzschild Cartesian coordinates. Our result sustain the viewpoint of Virbhadra  that the Einstein energy-momentum complex is the most adequate to evaluate the energy distribution of a given space-time.

Acknowledgments

I am grateful to Professor K. S. Virbhadra for his helpful advice.


text:
# Some mapping theorems for extensional dimension

## 1 Introduction

All topological spaces are assumed to be separable metrizable, $`I=[0,1]`$. Recall that the covering dimension $`dimX`$ is the smallest number $`n`$ such that every open cover of $`X`$ admits an open refinement of order $`n+1`$. The cohomological dimension $`dim_GX`$ with respect to an abelian group $`G`$ is the smallest number $`n`$ such that $`\stackrel{ˇ}{H}^{n+1}(X,A;G)=0`$ for all closed subsets $`A`$ of $`X`$.

By a classical result of Alexandroff $`dim_{}X=dimX`$ for a finite dimensional $`X`$. Solving an outstanding problem in Dimension Theory Dranishnikov constructed in 1986 an infinite dimensional compactum (=compact metric space) of $`dim_{}=3`$. Many classical results for the covering and the cohomological dimensions shows a great deal of similarity between the theories. Here we mention just two such results.

###### Theorem 1.1

(Hurewicz ) Let $`f:XY`$ be a map of compacta. Then $`dimXdimY+dimf`$, where $`dimf=sup\{dimf^1(y):yY\}`$.

###### Theorem 1.2

(Skljarenko ) Let $`f:XY`$ be a map of compacta. Then $`dim_{}Xdim_{}Y+dim_{}f`$, where $`dim_{}f=sup\{dim_{}f^1(y):yY\}`$.

Despite such similarities the covering dimension was investigated using mostly set-theoretic methods and the cohomological dimension was investigated using mostly algebraic methods. In general the results for the cohomological dimension were proved with difficulty exceeding similar results for the covering dimension. The proofs of the theorems mentioned above are a good illustration of the differences in the approaches. The essentially different definitions of the dimensions seem to justify using different tools. However the following two theorems offer a common point of view on the theories.

###### Theorem 1.3

(Hurewicz-Wallman ) $`dimXn`$ if and only if any map $`f:AS^n`$ of a closed subset $`A`$ of $`X`$ into the $`n`$-dimensional sphere $`S^n`$ extends over $`X`$.

###### Theorem 1.4

(Cohen ) $`dim_GXn`$ if and only if any map $`f:AK(G,n)`$ of a closed subset $`A`$ of $`X`$ into an Eilenberg-MacLane complex of type $`(G,n)`$ extends over $`X`$.

Theorems 1.3 and 1.4 suggest that one may try to consider extension properties of maps into different CW-complexes hoping to create a theory encompassing both the covering and the cohomological dimension theories. Indeed, in the early 1990’s Dranishnikov laid down a foundation of such theory which he called “Extension Theory”. Extension Theory not only provided simpler proofs for many results in cohomological dimension theory, but it also gave an explanation of certain phenomena in cohomological dimension which are sometimes more general than expected, see  and .

Let us introduce the terminology. The extensional dimension of $`X`$ does not exceed a CW-complex $`K`$, written e-dim$`XK`$, if any map of a closed subset of $`X`$ into $`K`$ extends over $`X`$. Thus for the covering dimension dim$`Xn`$ if and only if e-dim$`XS^n`$ and for the cohomological dimension dim$`{}_{G}{}^{}Xn`$ if and only if e-dim$`XK(G,n)`$. Let $`f:XY`$ be a map. We will use the following notation:

e-dim$`fK`$ if e-dim$`f^1(y)K`$ for every $`yY`$;

e-dim$`Z`$e-dim$`f`$ if for every CW-complex $`K`$, e-dim$`fK`$ implies e-dim$`ZK`$;

e-dim$`X`$e-dim$`Y`$ if for every CW-complex $`K`$, e-dim$`YK`$ implies e-dim$`XK`$;

for CW-complexes $`K`$ and $`L`$, $`KL`$ if for every $`X`$, e-dim$`XK`$ implies e-dim$`XL`$.

This note is mainly devoted to an extensional dimension generalization of some results of Pasynkov  and Torunczyk  on the geometry of maps. For example, we obtain the following versions of Theorems 1.1 and 1.2. Note that Theorem 1.5 is an improvement of the results of  which provides the right estimates for cohomological dimension.

###### Theorem 1.5

(cf. Remark 2, Section 5) Let $`f:XY`$ be a map of compacta and let CW-complexes $`K`$ and $`L`$ be such that $`K`$ is countable, $`\mathrm{e}\mathrm{dim}fK`$ and $`\mathrm{e}\mathrm{dim}YL`$. Then $`X_{}=X\times I`$ can be decomposed into $`X_{}=AB`$ for subspaces $`A`$ and $`B`$ such that $`\mathrm{e}\mathrm{dim}AK`$ and $`\mathrm{e}\mathrm{dim}BL`$. As a result of such a decomposition $`\mathrm{e}\mathrm{dim}X_{}KL`$.

###### Theorem 1.6

Let $`f:XY`$ be a map of compacta with $`X`$ finite dimensional and let $`K`$ and $`L`$ be CW-complexes such that $`K`$ is countable, $`\mathrm{e}\mathrm{dim}fK`$ and $`\mathrm{e}\mathrm{dim}YL`$. Then $`\mathrm{e}\mathrm{dim}XKL`$.

Pasynkov  and Torunczyk  proved the following remarkable theorem.

###### Theorem 1.7

(Pasynkov-Torunczyk) Let $`f:XY`$ be a map of finite dimensional compacta $`X`$ and $`Y`$. Then the following conditions are equivalent:

(1) $`dimfn`$;

(2) there exists a $`\sigma `$-compact subset $`A`$ of $`X`$ such that $`dimAn1`$ and $`dimf|_{XA}0`$;

(3) almost every map $`g:XI^n`$ has the property that the map $`(f,g):XY\times I^n`$ is $`0`$-dimensional, where almost=all but a set of first category;

(3’) there exists a map $`g:XI^n`$ such that the map $`(f,g):XY\times I^n`$ is $`0`$-dimensional.

In this note we will prove two theorems generalizing Theorem 1.7.

###### Theorem 1.8

Let $`f:XY`$ be a map of compacta and let $`K`$ be a CW-complex. Consider the following properties:

(1) $`\mathrm{e}\mathrm{dim}f\mathrm{\Sigma }K`$;

(2) there exists a $`\sigma `$-compact subset $`A`$ of $`X`$ such that $`\mathrm{e}\mathrm{dim}AK`$ and $`dimf|_{XA}0`$;

(3) almost every map $`g:XI`$ is such that for the map $`(f,g):XY\times I`$, $`\mathrm{e}\mathrm{dim}(f,g)K`$;

(3’) there exists a map $`g:XI`$ such that for the map $`(f,g):XY\times I,\mathrm{e}\mathrm{dim}(f,g)K`$.

Then: (3)$``$(2)$``$(1), (3)$``$(3’)$``$(1) and if $`Y`$ is finite-dimensional and $`K`$ is countable then (1)$``$(3).

In particular all the properties are equivalent if $`Y`$ is finite dimensional and $`K`$ is countable.

Note that Theorem 1.7 can be derived from Theorem 1.8. Indeed, it is obvious for the properties (1) and (2) of Theorem 1.7. One can easily show by induction that the property (3) of Theorem 1.8 implies that the set of functions $`g`$ satisfying the property (3) of Theorem 1.7 for $`dimfn`$ is dense in $`C(X,I^n)`$. On the other hand this set is $`G_\delta `$ in $`C(X,I^n)`$ and hence (3) holds for $`dimfn`$. Clearly (3)$``$(3’)$``$(1) and Theorem 1.7 follows (see also Remark 1, Section 5).

It is unknown if the finite dimensional restriction on $`Y`$ is necessary in Theorems 1.7 and 1.8. Some versions of these theorems without this restriction were obtained in . The following theorem improves on these results.

###### Theorem 1.9

Let $`f:XY`$ be a map of compacta and let $`K`$ be a CW-complex. Define $`f_{}:X_{}=X\times IY`$ by $`f_{}(x,t)=f(x)`$. Consider the following properties:

(0) $`\mathrm{e}\mathrm{dim}fK`$;

(1) $`\mathrm{e}\mathrm{dim}f_{}\mathrm{\Sigma }K`$;

(2) there exists a $`\sigma `$-compact subset $`A`$ of $`X_{}`$ such that $`\mathrm{e}\mathrm{dim}AK`$ and $`dimf_{}|_{X_{}A}0`$;

(2’) a set $`A`$ satisfying (2) can be chosen such that $`A`$ splits into compacta $`A=_{i=1,\mathrm{}}A_i`$ such that each component of $`A_i`$ admits a $`0`$-dimensional map into a fiber of $`f`$.

(3) almost every map $`g_{}:X_{}I`$ is such that for the map $`(f_{},g_{}):X_{}Y\times I`$, $`\mathrm{e}\mathrm{dim}(f_{},g_{})K`$;

Then (0)$``$(3)$``$(2’)$``$(2)$``$(1).

Theorems 1.8 and 1.9 are proved in Section 4. Applications of Theorem 1.9 including the proofs of Theorems 1.5 and 1.6 are presented in Section 2. Section 3 is devoted to Krasinkiewicz maps which are essentially used in the proofs. In Section 5 we discuss some related results and problems.

Finally we wish to thank the referee for pointing out that Proposition 4.4 can also be derived from Lemma 2 of

## 2  Applications

We will use the following facts.

###### Theorem 2.1

() Let $`f:XY`$ be a light map of compacta. Then $`\mathrm{e}\mathrm{dim}X\mathrm{e}\mathrm{dim}Y`$.

In some cases we will need a stronger result than Theorem 2.1.

###### Definition 2.2

() A map $`f:XY`$ of metric spaces $`X`$ and $`Y`$ is said to be uniformly $`0`$-dimensional if there is a metric on $`X`$ such that for every $`ϵ>0`$ every point in $`f(X)`$ has a neighborhood $`V`$ in $`Y`$ such that $`f^1(V)`$ splits into a disjoint family of open sets of diam$`<ϵ`$.

Examples of uniformly $`0`$-dimensional maps are: a $`0`$-dimensional map of compacta, a $`0`$-dimensional perfect (=closed with compact fibers) map of metric spaces, a map of compacta restricted to the union of all trivial components of its fibers.

###### Theorem 2.3

() Let $`f:XY`$ be a uniformly $`0`$-dimensional map of metric spaces. Then $`\mathrm{e}\mathrm{dim}X\mathrm{e}\mathrm{dim}Y`$.

###### Theorem 2.4

() Let $`K`$ be a countable CW-complex and let $`A`$ be a subspace of a compactum $`X`$ such $`\mathrm{e}\mathrm{dim}AK`$. Then there is a completion $`A^{}X`$ of $`A`$ such that $`\mathrm{e}\mathrm{dim}A^{}K`$.

###### Theorem 2.5

(, see also Remark 2, Section 5) Let $`K`$ and $`L`$ be CW-complexes and let $`X=AB`$ be a decomposition of a separable metric space $`X`$ into subspaces $`A`$ and $`B`$ such that $`\mathrm{e}\mathrm{dim}AK`$ and $`\mathrm{e}\mathrm{dim}BL`$. Then $`\mathrm{e}\mathrm{dim}XKL`$.

###### Theorem 2.6

(,see also ) Let $`X=AB`$ be a decomposition of a separable metric space $`X`$. Then $`dim_{}Xdim_{}A+dim_{}B+1`$.

###### Theorem 2.7

() Let $`X`$ be a compactum and let $`K`$ be a simply connected CW-complex. Consider the following conditions:

(1) $`\mathrm{e}\mathrm{dim}XK`$;

(2) $`dim_{H_i(K)}Xi`$ for every $`i>1`$;

(3) $`dim_{\pi _i(K)}Xi`$ for every $`i>1`$.

Then (2) and (3) are equivalent and (1) implies both (2) and (3). If $`X`$ is finite dimensional then all the conditions are equivalent. In particular if $`X`$ is finite dimensional then $`dim_GXn`$, $`n>1`$ if and only if $`\mathrm{e}\mathrm{dim}XM(G,n)`$ where $`M(G,n)`$ is a Moore space of type $`(G,n)`$.

###### Theorem 2.8

() Assume that a compactum $`X`$ is expressed as the union $`X=AB`$. Then $`dim_{}Xdim_{}(A\times B)`$ if $`dim_{}X^2=2dim_{}X`$ and $`dim_{}Xdim_{}(A\times B)+1`$ if $`dim_{}X^22dim_{}X`$ (that is $`dim_{}X^2=2dim_{}X1`$).

###### Proposition 2.9

() Let $`K`$ be a CW-complex and let each component of a compactum $`X`$ be of $`\mathrm{e}\mathrm{dim}K`$. Then $`\mathrm{e}\mathrm{dim}XK`$.

The following two proposition can be easily derived from the proofs of Proposition 12,  and Lemma 2.11,  respectively.

###### Proposition 2.10

Let $`X`$ and $`Y`$ be compacta and let $`AX`$. Then there is a completion $`A^{}X`$ of $`A`$ such that $`dim_{}(A^{}\times Y)=dim_{}(A\times Y)`$.

###### Proposition 2.11

Let $`K`$ be a CW-complex such that $`\mathrm{e}\mathrm{dim}(X\times Y)K`$ where $`X`$ and $`Y`$ are non-trivial continua. Then $`K`$ is simply connected.

It was shown in  that for a map of compacta $`f:XY`$ and CW-complexes $`K`$ and $`L`$, $`X`$ can be decomposed into $`X=AB`$ such that e-dim$`AK`$ and $`\mathrm{e}\mathrm{dim}BL`$ provided e-dim$`fK`$, e-dim$`YL`$ and $`K`$ is countable. Theorem 1.5 improves this result.

Proof of Theorem 1.5. By Theorem 1.9 there is $`AX_{}`$ such that $`\mathrm{e}\mathrm{dim}AK`$ and $`dimf_{}|_B0`$ where $`B=X_{}A`$. By Theorem 2.4 there is a completion $`A^{}X_{}`$ of $`A`$ with e-dim$`A^{}K`$. $`B^{}=X_{}A^{}B`$ is $`\sigma `$-compact and hence by Theorem 2.1, e-dim$`B^{}L`$. By Theorem 2.5 $`\mathrm{e}\mathrm{dim}XKL`$. $`\mathrm{}`$

Note that applying Theorem 2.6 to the decomposition of $`X_{}`$ from Theorem 1.5 for $`dim_{}`$ it follows that $`dim_{}X+1=dim_{}X_{}=dim_{}(A^{}B^{})dim_{}A^{}+dim_{}B^{}+1`$ and we have obtained Theorem 1.2, see  for related results.

Dranishnikov and Dydak  proved that if for finite dimensional compacta $`X`$ and $`Y`$ and CW-complexes $`K`$ and $`L`$, $`\mathrm{e}\mathrm{dim}XK`$ and $`\mathrm{e}\mathrm{dim}YL`$ then $`\mathrm{e}\mathrm{dim}(X\times Y)KL`$. Theorem 1.6 is a mapping version of Dranishnikov-Dydak’s result.

Proof of Theorem 1.6. If $`K`$ is disconnected then $`\mathrm{e}\mathrm{dim}f=0`$ and if $`L`$ is disconnected then $`dimY=0`$. These cases can be treated in a way similar to the one in the proof of Theorem 5.6 of  to show that $`\mathrm{e}\mathrm{dim}XKL`$.

Assume that both $`K`$ and $`L`$ are connected. Then $`KL`$ is simply connected. By Theorem 1.5, $`\mathrm{e}\mathrm{dim}(X_{})KL`$, $`X_{}=X\times I`$ and since $`KL`$ is homotopy equivalent to $`\mathrm{\Sigma }(KL)`$, $`\mathrm{e}\mathrm{dim}(X_{})\mathrm{\Sigma }(KL)`$. Then by Theorem 2.7, $`dim_{H_{i+1}(\mathrm{\Sigma }(KL))}(X_{})=dim_{H_i(KL)}(X_{})=dim_{H_i(KL)}(X)+1i+1`$. Hence $`dim_{H_i(KL)}(X)i`$ and again by Theorem 2.7, $`\mathrm{e}\mathrm{dim}XKL`$. $`\mathrm{}`$
Note that if in the proof of Theorem 1.6 one uses Theorem 5.2 (see Section 5, Remark 2 of this note) instead of Theorem 1.5 then the restriction in Theorem 1.6 that $`K`$ is countable can be omitted.

The following theorem was announced by Dranishnikov in 1996. We will present a proof of this result based on Theorem 1.9.

###### Theorem 2.12

(Dranishnikov) Let $`f:XY`$ be a map of compacta. Then: $`dim_{}X`$$`\mathrm{sup}\{dim_{}`$ $`(f^1(y)\times Y):yY\}`$ if $`dim_{}X^2=2dim_{}X`$ and $`dim_{}X\mathrm{sup}\{dim_{}(f^1(y)\times Y):yY\}+1`$ otherwise.

Proof. Let $`n=`$sup$`\{dim_{}(f^1(y)\times Y):yY\}`$. Take a $`\sigma `$-compact $`AX_{}`$ satisfying (2’) of Theorem 1.9, that is $`A`$ splits into compacta $`A=A_i`$ such that each component of each $`A_j`$ admits a $`0`$-dimensional map to a fiber of $`f`$. Then each component of $`A_i\times Y`$ admits a $`0`$-dimensional map to $`f^1(y)\times Y`$ for some $`yY`$ and hence by Theorem 2.1 and Proposition 2.9 $`dim_{}(A\times Y)n`$ and by Proposition 2.10 there is a completion $`A^{}X_{}`$ of $`A`$ such that $`dim_{}(A^{}\times Y)n`$. Then $`B^{}=X_{}A^{}`$ is $`\sigma `$-compact and hence splits into compacta $`B^{}=B_j`$ admitting $`0`$-dimensional maps into $`Y`$. It follows that $`A^{}\times B_j`$ admits a $`0`$-dimensional perfect map to $`A^{}\times Y`$. Thus by Theorem 2.3 $`dim_{}(A^{}\times B_j)n`$ and hence $`dim_{}(A^{}\times B^{})n`$. By Theorem 2.8 $`dim_{}X_{}n+1`$ if $`dim_{}X_{}^2=2dim_{}X^{}`$ and $`dim_{}X_{}n+2`$ otherwise. Clearly $`dim_{}X_{}=dim_{}X+1`$ and $`dim_{}X_{}^2=dim_{}X^2+2`$ and the theorem follows. $`\mathrm{}`$

Note that it is unknown if the case $`dim_{}X=dim_{}A+dim_{}B+2`$ in Theorem 2.8 ever occurs. Eliminating this case would result in eliminating the case $`dim_{}X=\mathrm{sup}\{dim_{}(f^1(y)\times Y):yY\}+1`$ in Theorem 2.12.

Our next application is to prove in a slightly stronger form the generalized Hurewicz formula obtained by Dranishnikov, Repovš and Ščepin .

###### Theorem 2.13

(Dranishnikov-Repovš -Ščepin for a finite dimensional $`Y`$ ) Let $`f:XY`$ be a map of compacta such that $`X`$ is finite dimensional and $`Y`$ is full-valued and let a CW-complex $`K`$ be such that $`\mathrm{e}\mathrm{dim}(f^1(y)\times Y)K`$ for every $`yY`$. Then $`\mathrm{e}\mathrm{dim}XK`$.

Proof. By Proposition 2.9 and Theorem 2.1 the theorem holds if either $`Y`$ or $`f`$ is $`0`$-dimensional. If neither $`Y`$ nor $`f`$ is $`0`$-dimensional then by Proposition 2.11 we may assume that $`K`$ is simply connected. Fix $`i>1`$ and assume $`H=H_i(K)0`$. Let $`m=dim_{}Y`$, $`n=dim_Hf`$ and $`k=`$sup$`\{dim_H(f^1(y)\times Y):yY\}`$. By Theorem 2.7, $`ki`$. Since $`Y`$ is full-valued $`dim_HY=m`$ and $`k=n+m`$. By (2’) of Theorem 1.9, Theorem 2.1 and Proposition 2.9 there exists a $`\sigma `$-compact $`AX_{}`$ such that $`dim_H(A)n`$ and $`f_{}|_{X_{}A}`$ is $`0`$-dimensional. Let $`\sigma (H)`$ be the Bockstein basis for $`H`$ and let $`L=\{M(G,n):G\sigma (H)\}`$ where $`M(G,n)`$ is a Moore space of type $`(G,n)`$. Then $`L`$ is countable and by Bockstein theory and Theorem 2.7 e-dim $`AL`$. By Theorem 2.4 there is a completion $`A^{}X_{}`$ of $`A`$ such that $`\mathrm{e}\mathrm{dim}A^{}L`$. Then by Theorem 2.1, $`B^{}=X_{}A^{}`$ is of $`dim=dim_{}m`$.

Then by Theorem 2.5 $`\mathrm{e}\mathrm{dim}X_{}=\mathrm{e}\mathrm{dim}(A^{}B^{})LS^m=\mathrm{\Sigma }^{m+1}L=\{M(G,n+m+1):G\sigma (H)\}`$. Hence by Theorem 2.7 $`dim_HX_{}n+m+1`$. Then $`dim_HXn+m=k`$. Thus $`dim_{H_i(K)}Xi`$ and by Theorem 2.7 the theorem follows. $`\mathrm{}`$

Note that one can avoid the use of Olszewski’s completion theorem (Theorem 2.4) and Bockstein theory in the proof of Theorem 2.13 by using Theorem 5.1 instead of Theorem 2.5.

## 3 Krasinkiewicz maps

Krasinkiewicz  introduced and studied maps having the following remarkable property. We will call these maps Krasinkiewicz maps.

###### Definition 3.1

() A map $`f:XY`$ is said to be a Krasinkiewicz map if any continuum in $`X`$ either contains a component of a fiber of $`f`$ or is contained in a component of a fiber of $`f`$.

Krasinkiewicz  showed that for a compactum $`X`$ the Krasinkiewicz maps form a dense subset in $`C(X,I)`$. We improve this result by showing that almost every map in $`C(X,I)`$ is a Krasinkiewiz map.

First we present a short construction of Krasinkiewicz maps using a different approach based on . Namely, we will use the following proposition actually proved in .

###### Proposition 3.2

(, Proposition 2.2, Proof B) Let $`ZX`$ be a closed $`0`$-dimensional subset of a compactum $`X`$. Then for almost every map in $`C(X,I)`$, $`Z`$ is contained in the union of trivial components of the fibers of $`f`$.

We construct Krasinkiewicz maps as follows. Let $`X`$ be a compactum. Take a sequence of Cantor sets $`C_iI`$ and intervals $`[a_i,b_i]I`$, $`i=1,2,\mathrm{}`$ such that $`C_i(a_i,b_i)`$, $`[a_{i+1},b_{i+1}](C_1\mathrm{}C_i)=\mathrm{}`$ and each non-empty open interval in $`I`$ contains some $`C_i`$. Fix $`ϵ>0`$ and let $`fC(X,I)`$. Let $`\psi _0=f`$ and assume that we have constructed $`\psi _{i1}:XI`$. Let $`g_i:C_i2^X`$ be a map onto the hyperspace $`2^X`$ of all non-empty closed subsets of $`X`$ equipped with the Hausdorff topology. Define $`A_i=\{g_i(c)\psi _{i1}^1(c):cC_i\}`$. Then $`A_i`$ is closed in $`X`$. Let $`q_i:XX_i`$ be the quotient map to the space $`X_i`$ obtained from $`X`$ by identifying each component of $`A_i`$ with a singleton. Then $`\psi _{i1}`$ factors through $`\varphi _i:X_iI`$ and $`Z_i=q_i(A_i)`$ is $`0`$-dimensional. By Proposition 3.2 $`\varphi _i`$ can be $`ϵ/2^{i+1}`$-approximated by a map $`\varphi _i^{}:X_iI`$ such that $`Z_i`$ is contained in the union of trivial components of the fibers of $`\varphi _i^{}`$. Let $`\psi _i=\varphi _i^{}q_i:XI`$. Then $`\psi _i`$ is $`ϵ/2^{i+1}`$-close to $`\psi _{i1}`$ and it easy to see that we may assume that $`\psi _i(x)=\psi _{i1}(x)`$ if $`\psi _{i1}(x)I(a_i,b_i)`$. Then $`\psi =lim\psi _i`$ is $`ϵ`$-close to $`f=\psi _0`$ and one can easily observe that $`\psi `$ is a Krasinkiewicz map. Moreover, $`\psi `$ satisfies the following condition:

(\*) for every continuum $`FX`$ such that $`\psi (F)`$ is not a singleton there is a subset $`D\psi (F)`$ dense in $`\psi (F)`$ such that for every $`dD`$ ,$`\psi ^1(d)F`$ is the union of components of $`\psi ^1(d)`$.

###### Proposition 3.3

Let $`X`$ be a compactum. The set of maps in $`C(X,I)`$ satisfying the condition (\*) is a dense $`G_\delta `$-subset of $`C(X,I)`$.

Proof. Let $`H_{}=`$the set of maps in $`C(X,I)`$ satisfying (\*). We have already shown that $`H_{}`$ is dense in $`C(X,I)`$. For $`0p<q1`$ denote by $`H(p,q,n)`$ the set of functions $`fC(X,I)`$ such that there is a continuum $`FX`$ such that $`[p,q]f(F)`$ and for every $`d[p,q]`$ there is a component of the fiber $`f^1(d)`$ intersecting $`F`$ and containing a point $`x`$ such that dist$`(x,F)1/n`$. It is easy to check that $`H(p,q,n)`$ is closed in $`C(X,I)`$. Denote $`H=\{H(p,q,n):p,q`$ are rationals, $`0p<q1,n=1,2,..\}`$

Let us show that $`H_{}=C(X,I)H`$. It is clear that $`H_{}C(X,I)H`$. If $`\psi `$ does not satisfy (\*) then there are a continuum $`FX`$ and an interval $`[a,b]\psi (F)`$ such that for every $`d[a,b]`$ there is a component of $`\psi ^1(d)`$ intersecting both $`F`$ and $`XF`$. Let $`A_n=\{d[a,b]:`$ there are a component $`C`$ of $`\psi ^1(d)`$ and a point $`xC`$ such that $`CF\mathrm{}`$ and dist$`(x,F)1/n\}`$. Then $`A_n`$ is closed, $`[a,b]=A_n`$ and hence there are $`n`$ and a non-degenerate interval $`[p,q]`$ with rational endpoints such that $`[p,q]A_n`$. Then $`\psi H(p,q,n)`$ and we proved that $`H_{}=C(X,I)H`$. Thus $`H_{}`$ is $`G_\delta `$ in $`C(X,I)`$ and the proposition follows. $`\mathrm{}`$

Clearly each map satisfying (\*) is a Krasinkiewicz map and Proposition 3.3 implies:

###### Theorem 3.4

Let $`X`$ be a compactum. Almost every map in $`C(X,I)`$ is a Krasinkiewicz map.

###### Proposition 3.5

Let $`f:XY`$ be a Krasinkiewicz map of compacta $`X`$ and $`Y`$. Denote $`C(f)=`$the union of all non-trivial components of the fibers of $`f`$. Then there are compacta $`A_1,A_2,\mathrm{}X`$ such that $`C(f)=A_i`$ and each component of $`A_i`$ is contained in a fiber of $`f`$. In particular $`\mathrm{e}\mathrm{dim}C(f)\mathrm{e}\mathrm{dim}f`$.

Proof. Let $`C_n`$ = the union of all non-trivial components of $`f`$ of diam$`1/n`$. Clearly $`C_n`$ is closed and $`C(f)=_{n=1,\mathrm{}}C_n`$. Cover $`C_n`$ by finitely many closed subsets $`B_1^n,B_2^n,\mathrm{}C_n`$ of diam$`<1/n`$. Then a component of $`B_j^n`$ cannot contain a component of a fiber of $`f`$ and hence must be contained in a componet of a fiber of $`f`$. Enumerate $`\{B_j^n\}`$ as $`\{A_1,A_2,\mathrm{}\}`$ and we are done. $`\mathrm{}`$

A continuum $`X`$ is said to be hereditarily indecomposable if for every pair of intersecting subcontinua $`A,BX`$, either $`AB`$ or $`BA`$. A map $`f`$ is said to be a Bing map if each component of each fiber of $`f`$ is hereditarily indecomposable.

###### Theorem 3.6

() Let $`X`$ be a compactum. Almost every map in $`C(X,I)`$ is a Bing map.

By a Bing-Krasinkiewicz map we mean a map which is both Bing and Krasinkiewicz. By Theorems 3.4 and 3.6 for a compactum $`X`$ almost every map in $`C(X,I)`$ is Bing-Krasinkiewicz. It is easy to verify:

###### Proposition 3.7

Let $`f:XY`$ be a Bing-Krasinkiewicz map of compacta. Then for every map $`g:XZ`$ to a compactum $`Z`$ the map $`(f,g):XY\times Z`$ is also Bing-Krasinkiewicz.

## 4 Proofs of Theorems 1.8 and 1.9

We first present some facts used in the proofs.

###### Proposition 4.1

() Let $`Y`$ be a compactum. Then there is a $`\sigma `$-compact $`0`$-dimensional subset $`AY\times I`$ such that for the projection $`p:Y\times IY`$, $`dimp|_{(Y\times I)A}=0`$.

Such a subset $`A`$ is constructed as follows. Let $`C_1,C_2,\mathrm{}I`$ be a sequence of Cantor sets such that each non-empty open subset of $`I`$ contains some $`C_i`$. Let a map $`f_i:C_iY`$ be onto. Define $`A_i=\{(f_i(c),c):cC_i\}`$. Then $`dimA_i=0`$ and $`A=A_i`$ satisfies Proposition 4.1.

###### Proposition 4.2

Let $`X`$ be a compactum, let $`K`$ be a CW-complex and let a map $`f:XI`$ be of $`\mathrm{e}\mathrm{dim}K`$. Then $`\mathrm{e}\mathrm{dim}X\mathrm{\Sigma }K`$.

Proof. Let $`g:F\mathrm{\Sigma }K`$ be a map of a closed subset $`F`$ of $`X`$. Since $`\mathrm{e}\mathrm{dim}fK\mathrm{\Sigma }K`$, $`g`$ can be extended over a small neighbourhood of each fiber of $`f`$ and hence there is a partition $`0=t_1<t_2<\mathrm{}<t_k=1`$ of $`I`$ such that $`g`$ extends to $`g_i:F_i=Ff^1([t_i,t_{i+1}])\mathrm{\Sigma }K`$ for every $`i=1,k1`$. Since $`\mathrm{e}\mathrm{dim}fK`$, $`\mathrm{e}\mathrm{dim}(f^1(t)\times I)\mathrm{\Sigma }K`$ for every $`tI`$ and hence $`g_i|_{f^1(t_{i+1})}`$ and $`g_{i+1}|_{f^1(t_{i+1})}`$ are homotopic for every $`i=1,k2`$. It follows that there is a map $`g^{}:X\mathrm{\Sigma }K`$ which is homotopic on $`F_i`$ to $`g_i`$ for each $`i=1,k1`$ and hence $`g`$ can be extended over $`X`$. $`\mathrm{}`$

###### Theorem 4.3

() Let $`K`$ and $`L`$ be countable CW-complexes and let for a compactum $`X`$, $`\mathrm{e}\mathrm{dim}XKL`$. Then there is a $`\sigma `$-compact $`AX`$ such that $`\mathrm{e}\mathrm{dim}AK`$ and $`\mathrm{e}\mathrm{dim}(XA)L`$.

###### Proposition 4.4

Let $`f:XY`$ be a light map of finite dimensional compacta $`X`$ and $`Y`$. Then almost every map $`g:XI`$ has the property that each fiber of the map $`(f,g):XY\times I`$ contains at most $`dimY+1`$ points;

Proof. Let $`\delta >0`$ and consider the set $`𝒢`$ of maps $`g:XI`$ having the property that each fiber of $`(f,g)`$ contains at most $`k+1`$ points having pairwise distances $`\delta `$. Clearly $`𝒢`$ is an open subset of the mapping space $`C(X,I)`$. We will show that $`𝒢`$ is also dense proving the proposition.

Take a map $`g^{}:XI`$ and fix $`ϵ>0`$. Let $`\varphi _\alpha :YI`$ be a finite set of maps forming a partition of unity for $`Y`$ such that $`V_\alpha =`$supp$`\varphi _\alpha =\varphi _\alpha ^1(0,1]`$ is a cover of order $`k+1`$. Since $`dimf=0`$ we may assume that each $`f^1(V_\alpha )`$ splits into a finite family of disjoint open sets $`U_\alpha ^1,U_\alpha ^2,\mathrm{}`$ such that diam $`U_\alpha ^i\delta /3`$ and diam$`g^{}(U_\alpha ^i)ϵ/3`$ for every $`i`$. Let $`\psi _\alpha ^i:XI`$ be defined by $`\psi _\alpha ^i(x)=\varphi _\alpha (f(x))`$ if $`xU_\alpha ^i`$ and $`\psi _\alpha ^i(x)=0`$ if $`xXU_\alpha ^i`$. Then $`\psi _\alpha ^i`$ form a partition of unity for $`X`$. Choose real numbers $`0<b_\alpha ^i<1`$ such that dist$`(b_\alpha ^i,g^{}(U_\alpha ^i))<ϵ/6`$ and $`b_\alpha ^i`$ have the following general position property: for every $`l`$ any collection of $`l+1`$ points in $`R^l`$ with the coordinates formed from different elements $`b_\alpha ^i`$ is not contained in a hyperplane of $`R^l`$.

Define $`g:XI`$ by $`g(x)=\mathrm{\Sigma }_{\alpha ,i}\psi _\alpha ^i(x)b_\alpha ^i`$. Then $`|g(x)g^{}(x)|ϵ`$. We will show that $`g𝒢`$. Let $`aY`$, $`bI`$ and let $`x_1,x_2,\mathrm{}X`$ be such that dist$`(x_{j_1},x_{j_2})\delta ,j_1j_2`$ and $`(f,g)(x_j)=(a,b)`$. Let $`V_{\alpha _1},\mathrm{},V_{\alpha _l},lk+1`$ be the sets containing $`a`$. Then $`x_jU_{\alpha _t}^{i(j,t)}`$ and $`i(j_1,t)i(j_2,t)`$ if $`j_1j_2`$ for every $`t=1,l`$. Now $`g(x_j)=\mathrm{\Sigma }_{t=1,l}\psi _{\alpha _t}^{i(j,t)}(x_j)b_{\alpha _t}^{i(j,t)}=\mathrm{\Sigma }_{t=1,l}\varphi _{\alpha _t}(f(x_j))b_{\alpha _t}^{i(j,t)}=\mathrm{\Sigma }_t\varphi _{\alpha _t}(a)b_{\alpha _t}^{i(j,t)}=b`$. Then for every $`j`$, $`(b_{\alpha _1}^{i(j,1)},b_{\alpha _2}^{i(j,2)},\mathrm{},b_{\alpha _l}^{i(j,l)})`$ is a solution of the linear equation $`\mathrm{\Sigma }_t\varphi _{\alpha _t}(a)s_t=b`$ for the variables $`s_t`$. Since $`\mathrm{\Sigma }_t\varphi _{\alpha _t}(a)=1`$ there is at least one non-zero coefficient in the equation and according to our choice of $`b_\alpha ^i`$ there are at most $`l`$ solutions of this equation of the form $`(b_{\alpha _1}^{i(j,1)},b_{\alpha _2}^{i(j,2)},\mathrm{},b_{\alpha _l}^{i(j,l)})`$ and hence $`jlk+1`$. Thus we have proved that $`g𝒢`$ and the proposition follows. $`\mathrm{}`$
Proof of Theorem 1.8.
(1)$``$(3) Take a finite-to-one map $`\psi :CY`$ from a Cantor set $`C`$ onto $`Y`$ and let $`Z=\{(c,x)C\times X:\psi (c)=f(x)\}`$ be the pullback of $`\psi `$ and $`f`$ with the projections $`p_C:ZC`$ and $`p_X:ZX`$. Then $`\mathrm{e}\mathrm{dim}p_C=\mathrm{e}\mathrm{dim}f\mathrm{\Sigma }K`$ and by Proposition 2.9 $`\mathrm{e}\mathrm{dim}Z\mathrm{\Sigma }K`$. By Theorem 4.3 there are $`0`$-dimensional compact subsets $`A_1,A_2,\mathrm{}`$ of $`Z`$ such that $`\mathrm{e}\mathrm{dim}(ZA)K`$ where $`A=A_i`$. Then $`\mathrm{e}\mathrm{dim}(f^1(y)p_X(A))K`$ for every $`yY`$. Since $`\psi `$ is finite-to-one we have that $`f|_{p_X(A_i)}`$ is $`0`$-dimensional for every $`i`$. Hence by Proposition 4.4 almost every map $`g:XI`$ is such that $`(f,g)`$ is at most $`(dimY+1)`$-to-$`1`$ on $`p_X(A)`$. Let $`(y,t)Y\times I`$. Then $`(f,g)^1(y,t)(f^1(y)p_X(A))((f,g)^1(y,t)p_X(A))`$ and hence $`\mathrm{e}\mathrm{dim}(f,g)K`$. $`\mathrm{}`$
(3)$``$(2) By Theorems 3.4 and 3.6 there is a Bing-Krasinkiewcz map $`g:XI`$ such that $`\mathrm{e}\mathrm{dim}(f,g)K`$. By proposition 4.1 there is a $`\sigma `$-compact $`0`$-dimensional set $`SY\times I`$ such that $`dim((\{y\}\times I)S)=0`$ for every $`yY`$. Then by Proposition 2.9, $`A^{}=(f,g)^1(S)`$ is of $`\mathrm{e}\mathrm{dim}K`$. By Proposition 3.7 $`(f,g)`$ is Bing-Krasinkiewicz and by Proposition 3.5, $`A^{\prime \prime }=C((f,g))`$ is of $`\mathrm{e}\mathrm{dim}K`$. Then $`A=A^{}A^{\prime \prime }`$ is $`\sigma `$-compact and we show that $`f|_{XA}`$ is $`0`$-dimensional. Let $`h_m:XZ`$ and $`h_l:ZY\times I`$ be the monotone-light decomposition of $`(f,g)=h_lh_m`$ with $`h_m`$ monotone and $`h_l`$ light. Then for every $`yY`$, $`h_m|_{f^1(y)A^{\prime \prime }}`$ is a homeomorphism and $`h_m(f^1(y)A^{})h_l^1((\{y\}\times I)S)`$. Since $`h_l^1((\{y\}\times I)S)`$ is $`0`$-dimensional and $`h_m(f^1(y)A)h_l^1((\{y\}\times I)S)`$, $`f^1(y)A`$ is also $`0`$-dimensional and therefore $`dimf|_{XA}=0`$. $`\mathrm{}`$
(3)$``$(3’) is obvious. $`\mathrm{}`$
(3’)$``$(1) by Proposition 4.2. $`\mathrm{}`$
(2)$``$(1) by Theorem 2.5. $`\mathrm{}`$
Proof of Theorem 1.9.
(0)$``$(3) Let $`g_{}:X_{}I`$ be a Bing map. Then a fiber $`(f_{},g_{})^1(y,t)=g_{}^1(t)(f^1(y)\times I),yY,tI`$ contains no non-degenerate interval and hence the projection of $`(f_{},g_{})^1(y,t)`$ onto $`f^1(y)`$ is a $`0`$-dimensional map. Thus by Theorem 2.1 $`\mathrm{e}\mathrm{dim}(f_{},g_{})^1(y,t)\mathrm{e}\mathrm{dim}f^1(y)`$ and hence $`\mathrm{e}\mathrm{dim}(f_{},g_{})K`$. Note that by Theorem 3.6 almost every map is a Bing map and we are done. $`\mathrm{}`$
(3)$``$(2’) Replace $`X,f`$ and $`g`$ by $`X_{},f_{}`$ and $`g_{}`$ respectively and use the construction and notation of the proof (3)$``$(2) of Theorem 1.8. We only need to check that $`A`$ can be decomposed into a countable family of compacta whose components admit $`0`$-dimensional maps into the fibers of $`f`$. Each continuum contained in $`A^{}`$ is contained in a fiber of $`(f_{},g_{})`$. By Proposition 3.5 $`A^{\prime \prime }`$ can be decomposed into a countable family of compacta whose components are contained in the fibers of $`(f_{},g_{})`$. Each continuum in a fiber of $`(f_{},g_{})`$ is hereditarily indecomposible and hence its projection to the corresponding fiber of $`f`$ is a $`0`$-dimensional map. $`\mathrm{}`$
(2’)$``$(2) is obvious. $`\mathrm{}`$
(2)$``$(1) follows from Theorem 2.5. $`\mathrm{}`$

## 5 Remarks

Remark 1. The properties (1),(2) and (3) of Theorem 1.7 are equialent to:

(4) (cf. ) $`almost`$ $`every`$ $`map`$ $`g:XI^{n+1}`$ $`has`$ $`the`$ $`property`$ $`that`$ $`each`$ $`fiber`$ $`of`$ $`the`$ $`map`$ $`(f,g):XY\times I^{n+1}`$ $`contains`$ $`at`$ $`most`$ $`dimY+n+1`$ $`points`$.

Indeed, by Proposition 4.4 and Theorem 1.7 this property holds if $`dimfn`$. Assume that there is $`yY`$ such that $`dimf^1(y)n+1`$. Take disjoint closed subsets $`F_1,F_2,\mathrm{},F_kf^1(y)`$, $`k=dimY+n+2`$ such that $`dimF_in+1`$ and let $`g:XI^{n+1}`$ be such that $`g|_{F_i}`$ is essential for each $`i`$ (that is $`g|_{g^1(I^{n+1})F_i}`$ cannot be extended over $`F_i`$ as a map to $`I^{n+1}`$). Then any sufficiently close approximation of $`g`$ must be at least $`(dimY+n+2)`$-to-$`1`$ on $`f^1(y)`$ and this contradiction shows that (4) implies that $`dimfn`$.
Remark 2. The proof of Theorem 2.5 given in  applies to prove the following stronger result.

###### Theorem 5.1

Let $`K`$ and $`L`$ be CW-complexes and let a separable metric space $`X`$ be decomposed into subsets $`X=AB`$ such that $`\mathrm{e}\mathrm{dim}AK`$ and for every subset $`F`$ closed in $`X`$ and contained in $`B`$, $`\mathrm{e}\mathrm{dim}FL`$. Then $`\mathrm{e}\mathrm{dim}XKL`$.

Theorem 5.1 allows one to avoid the use of Olszewski’s completion theorem in Theorem 1.5 and to extend it to the following conclusion omitting the requirement that $`K`$ is countable.

###### Theorem 5.2

Let $`K`$ and $`L`$ be CW-complexes such that for a map of compacta $`f:XY`$, $`\mathrm{e}\mathrm{dim}fK`$ and $`\mathrm{e}\mathrm{dim}YL`$. Then $`\mathrm{e}\mathrm{dim}X_{}KL`$ where $`X_{}=X\times I`$.

E. Ščepin conjectured that $`\mathrm{e}\mathrm{dim}(X_1X_2)\mathrm{e}\mathrm{dim}(X_1X_2)`$. This would significantly improve Theorem 2.5. Let us state without a proof the following result related to Ščepin’s conjecture.

###### Theorem 5.3

Let $`X=X_1X_2`$ be a decomposition of a compactum $`X`$. Then $`\mathrm{e}\mathrm{dim}X\mathrm{e}\mathrm{dim}(\beta X_1\beta X_2)`$, where $`\beta X`$ is the Stone-Cech compactification of $`X`$.

Theorem 5.3 implies, for example, that dim$`Xdim(\beta X_1\times \beta X_2)+1`$. Note that Theorem 5.3 does not seem to be useful for infinite dimensional spaces, see .
Remark 3. It seems to be of interest to know some dimensional properties of $`B=X_{}A`$ in Theorem 1.9, especially, when $`K`$ is uncountable and it is unknown if $`A`$ has a completion of the same extensional dimension. In general, Theorem 2.1 does not hold for spaces which are not $`\sigma `$-compact and hence the $`0`$-dimensionality of $`f_{}|_B`$ does not give much information about $`B`$. In view of Theorem 2.3 one is tempted to replace the $`0`$-dimensionality by the uniform $`0`$-dimensionality.

Unfortunately Theorems 1.7, 1.8 and 1.9 do not hold if the $`0`$-dimensionality is replaced by the uniform $`0`$-dimensionality. Indeed, let $`p:I^nI`$, $`n2`$ be the projection $`p(x_1,\mathrm{},x_n)=x_n`$. Then for every $`\sigma `$-compact $`(n2)`$-dimensional subset $`A`$ of $`I^n`$ and every interval $`(a,b)`$ in $`I`$, $`p^1((a,b))A`$ is connected.

However one can observe that the following result is contained in the proof of Theorem 1.9.

###### Theorem 5.4

Let $`f:XY`$ be a map of compacta and let $`f_{}:X_{}=X\times IY`$ be defined by $`f_{}(x,t)=f(x)`$. Then for almost every map $`g_{}:X_{}=X\times II`$ there is a $`\sigma `$-compact $`AX_{}`$ such that $`A`$ splits into a countable family of compacta whose components admit $`0`$-dimensional maps into the fibers of $`f`$ and for $`B=X_{}A`$, $`f_{}|_B`$ is $`0`$-dimensional and $`(f_{},g_{})|_B`$ is uniformly $`0`$-dimensional.

In particular $`\mathrm{e}\mathrm{dim}A\mathrm{e}\mathrm{dim}f`$ and $`\mathrm{e}\mathrm{dim}B\mathrm{e}\mathrm{dim}\mathrm{\Sigma }Y`$.
Remark 4. Let us repeat that it is unknown if Theorems 1.7 and 1.8 hold without any dimensional restriction on $`Y`$. We end this note with posing the following problem.

###### Problem 5.5

(cf. Theorem 4.3) Let $`f:XY`$ be a map of compacta with $`Y`$ finite dimensional and let $`K`$ and $`L`$ be countable CW-complexes such that $`\mathrm{e}\mathrm{dim}fKL`$. Does there exist a $`\sigma `$-compact $`AX`$ such that $`\mathrm{e}\mathrm{dim}AK`$ and $`\mathrm{e}\mathrm{dim}f|_{XA}L`$ ?

Department of Mathematics
Ben Gurion University of the Negev
P.O.B. 653
Be’er Sheva 84105, ISRAEL
e-mail: mlevine@math.bgu.ac.il
Department of Mathematics
Texas Tech University
Lubbock, TX 79409-1042, USA
e-mail: wlewis@math.ttu.edu