---
abstract: |
    Let $X$ and $Y$ be finite simplicial sets (e.g. finite simplicial complexes), both equipped with a free simplicial action of a finite group $G$. Assuming that $Y$ is $d$-connected and $\dim X\le 2d$, for some $d\ge 1$, we provide an algorithm that computes the set of all equivariant homotopy classes of equivariant continuous maps $|X|\to|Y|$; the existence of such a map can be decided even for $\dim X\leq 2d+1$. For fixed $G$ and ${{d}}$, the algorithm runs in polynomial time. This yields the first algorithm for deciding topological embeddability of a $k$-dimensional finite simplicial complex into ${\mathbb R}^n$ under the condition $k\leq\frac 23 n-1$.

    More generally, we present an algorithm that, given a lifting-extension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the non-equivariant situation.
author:
- Martin Čadek
- Marek Krčál
- Lukáš Vokřínek
bibliography:
- 'Postnikov.bib'
title: 'Algorithmic solvability of the lifting-extension problem[^1]'
---

Introduction
============

Our original goal for this paper was to design an algorithm that decides existence of an equivariant map between given spaces under a certain “stability” assumption. To explain our solution however, it is more natural to deal with a more general lifting-extension problem. At the same time, lifting-extension problems play a fundamental role in algebraic topology since many problems can be expressed as their instances. We start by explaining our original problem and its concrete applications and then proceed to the main object of our study in this paper – the lifting-extension problem.

Equivariant maps {#equivariant-maps .unnumbered}
----------------

Consider the following algorithmic problem: given a finite group $G$ and two free $G$-spaces $X$ and $Y$, decide the existence of an equivariant map $f{\colon}X\to Y$.

In the particular case $G={{\mathbb Z}}_2$ and $Y=S^{n-1}$ equipped with the antipodal ${{\mathbb Z}}_2$-action, this problem has various applications in geometry and combinatorics.

Concretely, it is well-known that if a simplicial complex $K$ embeds into ${\mathbb R}^{{{n}}}$ then there exists a ${{\mathbb Z}}_2$-equivariant map $(K \times K) \smallsetminus \Delta_K \to S^{n-1}$; the converse holds in the so-called *metastable range* $\dim K \leq \tfrac{2}{3} {{n}}-1$ by [@Weber:PlongementsPolyedresDomaineMetastable-1967]. Algorithmic aspects of the problem of embeddability of $K$ into ${\mathbb R}^{{{n}}}$ were studied in [@MatousekTancerWagner:HardnessEmbeddings-2011] and the meta-stable range was essentially the only remaining case left open. Theorem \[t:emb-metast\] below shows that, for fixed $n$, it is solvable in polynomial time. Theorem \[t:emb-metast\] below shows that it is solvable.

Equivariant maps also provide interesting applications of topology to combinatorics. For example, the celebrated result of Lovász on Kneser’s conjecture states that for a graph $G$, the absence of a ${{\mathbb Z}}_2$-equivariant map $B(G) \to S^{n-1}$ imposes a lower bound $\chi(G) \geq n+2$ on the chromatic number of $G$, where $B(G)$ is a certain simplicial complex constructed from $G$, see [@Mat-top].

Building on the work of Brown [@Brown], that is not applicable for $Y=S^{{{n}}-1}$, we investigated in papers [@CKMSVW11; @polypost] the simpler, non-equivariant situation, where $X$ and $Y$ were topological spaces and we were interested in $[X,Y]$, the set of all homotopy classes of continuous maps $X\to Y$. Employing methods of *effective homology* developed by Sergeraert et al. (see e.g. [@SergerGenova]), we showed that for any fixed $d\ge 1$, $[X,Y]$ is polynomial-time computable if $Y$ is $d$-connected and $\dim X\le 2d$. In contrast, [@ext-hard] shows that the problem of computing $[X,Y]$ is \#P-hard when the dimension restriction on $X$ is dropped. More strikingly, a related problem of the existence of a continuous extension of a given map $A \to Y$, defined on a subspace $A$ of $X$, is *undecidable* as soon as $\dim X \geq 2d+2$.

Here we obtain an extension of the above computability result for free $G$-spaces and equivariant maps. The input $G$-spaces $X$ and $Y$ can be given as finite *simplicial sets* (generalizations of finite simplicial complexes, see [@Friedm08]), and the free action of $G$ is supposed to be simplicial. The simplicial sets and the $G$-actions on them are described by a finite table.

\[theorem:equivariant\] Let $G$ be a finite group. There is an algorithm that, given finite simplicial sets $X$ and $Y$ with free simplicial actions of $G$, such that $Y$ is $d$-connected, $d\geq 1$, and $\dim X\leq 2d+1$, decides the existence of a continuous equivariant map $X\to Y$.

If such a map exists and $\dim X\leq 2d$, then the set $[X,Y]$ of all equivariant homotopy classes of equivariant continuous maps can be equipped with the structure of a finitely generated abelian group, and the algorithm outputs the isomorphism type of this group.

For fixed $G$ and ${{d}}$, this algorithm runs in polynomial time.

Here the isomorphism type is output as an abstract abelian group given by a (finite) number of generators and relations. Furthermore, there is an algorithm that, given an equivariant simplicial map $\ell{\colon}X\to Y$, computes the element of this group that $\ell$ represents.

As a consequence, we also have an algorithm that, given two equivariant simplicial maps $X\to Y$, tests whether they are equivariantly homotopic under the above dimension restrictions on $X$. Building on the methods of the present paper, [@Filakovsky:suspension] removes the dimension restriction for the latter question: it provides a homotopy-testing algorithm assuming only that $Y$ is simply connected.

The lifting-extension problem {#the-lifting-extension-problem .unnumbered}
-----------------------------

We obtain Theorem \[theorem:equivariant\] by an inductive approach that works more generally and more naturally in the setting of the *(equivariant) lifting-extension problem*, summarized in the following diagram: $$\label{eq:basic_square}
\xy *!C\xybox{\xymatrix@C=40pt{
A \ar[r]^-{f} \ar@{ >->}[d]_-\iota & Y \ar@{->>}[d]^-\varphi \\
X  \ar[r]_-{g} \ar@{-->}[ru]^-{\ell
} & B
}}\endxy$$ The input objects for this problem are the solid part of the diagram and we require that:

1.  $A$, $X$, $Y$, $B$ are free $G$-spaces;

2.  $f{\colon}A\to Y$ and $g{\colon}X\to B$ are equivariant maps;

3.  $\iota{\colon}A{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{ >->}[r]^{} & {}}}}X$ is an equivariant inclusion map;

4.  $\varphi{\colon}Y{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{->>}[r]^{} & {}}}}B$ is an equivariant *fibration* (which we mark by the double-head arrow)[^2]; and

5.  the square commutes (i.e. $g\iota=\varphi f$).

The lifting-extension problem asks whether there exists a *diagonal* in the square, i.e. an (equivariant) map $\ell{\colon}X\to Y$, marked by the dashed arrow, that makes both triangles commute. We call such an $\ell$ a *solution* of the lifting-extension problem .

Moreover, if such an $\ell$ exists, we would like to compute the structure of the set $[X,Y]^A_B$ of all solutions, up to (equivariant) *fibrewise* homotopy *relative to $A$*.[^3] More concretely, in the cases covered by our algorithmic results, we will be able to equip $[X,Y]^A_B$ with a structure of an abelian group, and the algorithm computes the isomorphism type of this group.

The generalized lifting-extension problem {#the-generalized-lifting-extension-problem .unnumbered}
-----------------------------------------

Spaces appearing in a fibration $\varphi {\colon}Y{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{->>}[r]^{} & {}}}}B$ must typically be represented by infinite simplicial sets[^4], and their representation as inputs to an algorithm can be problematic. For this reason, we will consider a *generalized lifting-extension problem*, where, compared to the above, $\varphi{\colon}Y\to B$ can be an arbitrary equivariant map, *not* necessarily a fibration.

In this case, it makes no sense from the homotopy point of view to define a solution as a map $X\to Y$ making both triangles commutative. A homotopically correct way of defining a solution is to consider pairs $(\ell,h)$, where $\ell{\colon}X\to Y$ is a map for which the upper triangle commutes strictly and the lower one commutes up to the specified homotopy $h{\colon}[0,1]\times X\to B$ relative to $A$. We will not pursue this approach any further (in particular, we will not define the right notion of homotopy of such pairs) and choose an equivalent, technically less demanding alternative, which consists in replacing the map $\varphi$ by a homotopy equivalent fibration.

To this end, we factor $\varphi{\colon}Y\to B$ as a weak homotopy equivalence $j{\colon}Y{\xrightarrow{\sim}} Y'$ followed by a fibration $\varphi'{\colon}Y'{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{->>}[r]^{} & {}}}}B$ (in the simplicial setup, see Lemma \[l:fibrant\_replacement\]). We define a *solution* of the considered generalized lifting-extension problem to be a solution $\ell{\colon}X\to Y'$ of the lifting-extension problem $${\xy *!C\xybox{\xymatrix{
A \ar[r]^-{f} \ar@{ >->}[d] & Y \ar[r]^-j & Y' \ar@{->>}[d]^-{\varphi'} \\
X  \ar[rr]_-{g} \ar@{-->}[rru]^-\ell & & B
}}\endxy}$$ If $\varphi$ was a fibration to begin with, we naturally take $Y=Y'$ and $j={\mathop\mathrm{id}\nolimits}$, and then the two notions of a solution coincide. With some abuse of notation, we write $[X,Y]_B^A$ for the set $[X,Y']_B^A$ of all homotopy classes of solutions of the above lifting-extension problem.

We remark that $Y'$ is used merely as a theoretical tool – for actual computations, we use a different approximation of $Y$, namely a suitable finite stage of a Moore–Postnikov tower for $\varphi{\colon}Y\to B$; see Section \[s:main\_proofs\]. Moreover, $Y'$ is not determined uniquely, and thus neither are the solutions of the generalized lifting-extension problem. However, rather standard considerations show that the *existence* of a solution and the *isomorphism type* of $[X,Y']_B^A$ as an abelian group are independent of the choice of $Y'$.

Examples of lifting-extension problems {#examples-of-lifting-extension-problems .unnumbered}
--------------------------------------

In order to understand the meaning of the (generalized) lifting-extension problem, it is instructive to consider some special cases.

1.  (Classification of extensions.) First, let us consider $G=\{e\}$ trivial (thus, the equivariance conditions are vacuous) and $B$ a point (which makes the lower triangle in the lifting-extension problem superfluous). Then we have an *extension problem*, asking for the existence of a map $\ell{\colon}X\to Y$ extending a given $f{\colon}A\to Y$. Moreover, $[X,Y]$ is the set of appropriate homotopy classes of such extensions.[^5] We remind that this problem is undecidable when $\dim X$ is not bounded, according to [@ext-hard].

2.  (Equivariant maps.) Here $G$ is nontrivial, $A=\emptyset$, and $B=EG$, a contractible free $G$-space (it is unique up to equivariant homotopy equivalence). For every free $G$-space $Z$, there is an equivariant map $c_Z{\colon}Z\to EG$, unique up to equivariant homotopy. If we set $g=c_X$ and $\varphi=c_Y$ in the generalized lifting-extension problem, then it can be proved that $[X,Y]_{EG}^\emptyset$ is in a bijective correspondence with all equivariant maps $X\to Y$ up to equivariant homotopy. This is how we obtain Theorem \[theorem:equivariant\].[^6]

3.  (Extending sections in a vector bundle.) Let $G=\{e\}$, and let $\varphi{\colon}Y\to B$ be the inclusion ${BSO}({{n}}-k){\rightarrow}{BSO}({{n}})$, where $BSO({{n}})$ is the classifying space of the special orthogonal group $SO({{n}})$. Then the commutative square in the generalized lifting-extension problem is essentially an oriented vector bundle of dimension ${{n}}$ over $X$ together with $k$ linearly independent vector fields over $A$. The existence of a solution is then equivalent to the existence of linearly independent continuations of these vector fields to the whole of $X$. We remark that in order to apply our theorem to this situation, a finite simplicial model of the classifying space $BSO({{n}})$ would have to be constructed. As far as we know, this has not been carried out yet.

    We briefly remark that for non-oriented bundles, it is possible to pass to certain two-fold “orientation” coverings and reduce the problem to the one for oriented bundles but with a further ${\mathbb Z}_2$-equivariance constraint.

The main theorem {#the-main-theorem .unnumbered}
----------------

Now we are ready to state the main result of this paper.

\[thm:main\_theorem\] Let $G$ be a finite group and let an instance of the generalized lifting-extension problem be input as follows: $A$, $X$, $Y$, $B$ are finite simplicial sets with free simplicial actions of $G$, $A$ is an (equivariant) simplicial subset of $X$, and $f$, $g$, $\varphi$ are equivariant simplicial maps. Furthermore, both $B$ and $Y$ are supposed to be $1$-connected, and the *homotopy fibre*[^7] of $\varphi{\colon}Y\to B$ is supposed to be $d$-connected for some $d\geq 1$.

There is an algorithm that, for $\dim X\leq 2d+1$, decides the existence of a solution. Moreover, if $\dim X\leq 2d$ and a solution exists, then the set $[X,Y]_B^A$ can be equipped with the structure of an abelian group, and the algorithm computes its isomorphism type. The running time of this algorithm is polynomial when $G$ and ${{d}}$ are fixed.

As in Theorem \[theorem:equivariant\], the isomorphism type means an abstract abelian group (given by generators and relations) isomorphic to $[X,Y]^A_B$. Given an arbitrary diagonal $\ell{\colon}X\to Y$ in the considered square, one can compute the element of this group that the solution $j\ell{\colon}X\to Y'$ represents.

Constructing the abelian group structure on $[X,Y]_B^A$ will be one of our main objectives. In the case of all *continuous* maps $X\to Y$ up to homotopy, with no equivariance condition imposed, as in [@CKMSVW11], the abelian group structure on $[X,Y]$ is canonical. In contrast, in the setting of the lifting-extension problem, the structure is canonical only up to a choice of a zero element; in other words, $[X,Y]_B^A$ really has an “affine” nature (in very much the same way as an affine space is naturally a vector space up to a choice of its origin).

This non-canonicality of zero is one of the phenomena making the equivariant problem (and the lifting-extension problem) substantially different from the non-equivariant case treated in [@CKMSVW11]. We will have to devote much effort to dealing with the choice of zero, and working with “zero sections” in the considered fibrations.

Embeddability and equivariant maps {#embeddability-and-equivariant-maps .unnumbered}
----------------------------------

Theorem \[theorem:equivariant\] has the following consequence for embeddability of simplicial complexes:

\[t:emb-metast\] Let $n$ be a fixed integer. Let $n$ be an integer. There is an algorithm that, given a finite simplicial complex $K$ of dimension $k \leq \frac23 n-1$, decides the existence of an embedding of $K$ into ${\mathbb R}^n$ in polynomial time.

The algorithmic problem of testing embeddability of a given $k$-dimensional simplicial complex into ${\mathbb R}^n$, which is a natural generalization of graph planarity, was studied in [@MatousekTancerWagner:HardnessEmbeddings-2011]. Theorem \[t:emb-metast\] clarifies the decidability of this problem for $k\le \frac23 n-1$; this is the so-called *metastable range* of dimensions, which was left open in [@MatousekTancerWagner:HardnessEmbeddings-2011]. Briefly, in the metastable range, the classical theorem of Weber (see [@Weber:PlongementsPolyedresDomaineMetastable-1967]) asserts that embeddability is equivalent to the existence of a ${{\mathbb Z}}_2$-equivariant map $(K\times K)\smallsetminus \Delta_K \to S^{{{n}}-1}$ whose domain is equivariantly homotopy equivalent to a finite simplicial complex[^8] with a free simplicial action of ${{\mathbb Z}}_2$. Thus, Theorem \[t:emb-metast\] follows immediately from Theorem \[theorem:equivariant\]; we refer to [@MatousekTancerWagner:HardnessEmbeddings-2011] for details.

Polynomial running times {#polynomial-running-times .unnumbered}
------------------------

We remark that for fixed $G$ and ${{d}}$, the algorithms of Theorems \[theorem:equivariant\] and \[thm:main\_theorem\] run in polynomial time. The algorithm of Theorem \[t:emb-metast\] also runs in polynomial time when the dimension $n$ is fixed. These claims are proved in an extended version of this paper, [@aslep-long].

Outline of the proof {#outline-of-the-proof .unnumbered}
--------------------

In the rest of this section we sketch the main ideas and tools needed for the algorithm of Theorem \[thm:main\_theorem\]. Even though the computation is very similar in its nature to that of [@CKMSVW11], there are several new ingredients which we had to develop in order to make the computation possible. We will briefly describe these after the outline of the proof.

Our first tool is a Moore–Postnikov tower ${{P_{{n}}}}$ for $\varphi {\colon}Y{\rightarrow}B$ within the framework of (equivariant) effective algebraic topology (essentially, this means that all objects are representable in a computer); it is enough to construct the first $\dim X$ stages. It can be shown that $[X,Y]^A_B\cong[X,{{P_{{n}}}}]^A_B$ for ${{n}}\geq \dim X$ and so it suffices to compute inductively $[X,{{P_{{n}}}}]^A_B$ from $[X,{{P_{{{n}}-1}}}]^A_B$ for ${{n}}\leq \dim X$. This is the kind of problems considered in obstruction theory. Namely, there is a natural map $[X,{{P_{{n}}}}]^A_B\to[X,{{P_{{{n}}-1}}}]^A_B$ and it is possible to describe all preimages of any given homotopy class $[\ell] \in [X,{{P_{{{n}}-1}}}]^A_B$ using, in addition, an inductive computation of $[{\Delta^{1}}\times X,{{P_{{{n}}-1}}}]^{(\partial{\Delta^{1}}\times X)\cup({\Delta^{1}}\times A)}_B$. In general however, $[X,{{P_{{{n}}-1}}}]^A_B$ is infinite and it is thus impossible to compute $[X,{{P_{{n}}}}]^A_B$ as a union of preimages of all possible homotopy classes $[\ell]$ (on the other hand, if these sets are finite, the above description provides an algorithm, probably not very efficient, see [@Brown]).

For this reason, we use in the paper to a great advantage our second tool, an abelian group structure on the set $[X,{{P_{{n}}}}]^A_B$ of homotopy classes of diagonals, which only exists on a “stable” part ${{n}}\leq 2{{d}}$ and, of course, only if this set is non-empty. It comes from an “up to homotopy” (fibrewise) abelian group structure on Moore–Postnikov stages (of a certain pullback of $Y'{\rightarrow}B$) which we construct algorithmically – this is the heart of the present paper. We remark that the abelian group structure on $[X,{{P_{{n}}}}]^A_B$ was already observed in [@McClendon]; however, this paper did not deal with algorithmic aspects.

In the stable part of the Moore–Postnikov tower, the natural map $[X,{{P_{{n}}}}]^A_B\to[X,{{P_{{{n}}-1}}}]^A_B$ is a group homomorphism and the above mentioned computation of the preimages of a given homotopy class $[\ell]$ may be reduced to a *finite* set of generators of the image; the computation is conveniently summarized in a long exact sequence . This finishes the rough description of our inductive computation.

New tools {#new-tools .unnumbered}
---------

In the process of building the Moore–Postnikov tower and also later, it is important to work with infinite simplicial sets, such as the Moore–Postnikov stages $P_n$, in an algorithmic way. This is handled by the so-called *equivariant* effective algebraic topology and effective homological algebra. The relevant non-equivariant results are described in [@SergerGenova; @polypost]. In many cases, only minor and/or straightforward modifications are needed. One exception is the equivariant effective homology of Moore–Postnikov stages, for which we rely on a separate paper [@Vokrinek].

Compared to our previous work [@CKMSVW11], the main new ingredient is the weakening of the [H-]{}space structure that exists on Moore–Postnikov stages. This is needed in order to carry out the whole computation algorithmically. Accordingly, the construction of this structure is much more abstract. In [@CKMSVW11] we had $B=*$ and Postnikov stages carried a unique basepoint. In the case of nontrivial $B$, the basepoints are replaced by sections and Moore–Postnikov stages may not admit a section at all – this is related to the possibility of $[X,Y]^A_B$ being empty. Even if a section exists, it might be non-unique and consequently, the addition on ${{P_{{n}}}}$ will not preserve it in general. This is the origin of the above weakening. A further complication emerging from the non-uniqueness of the section is that it might happen that in the stage ${{P_{{{n}}-1}}}$ we choose a section which does not lift to ${{P_{{n}}}}$. In that case, we need to change the section of ${{P_{{{n}}-1}}}$ and compute everything again from scratch.

Plan of the paper {#plan-of-the-paper .unnumbered}
-----------------

In the second section, we give an overview of equivariant effective homological algebra that we use in the rest of the paper. The third section is devoted to the algorithmic construction of an equivariant Moore–Postnikov tower. The proofs of Theorems \[theorem:equivariant\] and \[thm:main\_theorem\], without their polynomial time claims, are given in the following section, although proofs of its two important ingredients are postponed to Sections $5$ and $6$. In the fifth section, we construct a certain weakening of an (equivariant and fibrewise) [H-]{}space structure on stable stages of Moore–Postnikov towers with sections. In the sixth section, we show how this structure enables one to endow the sets of homotopy classes with addition in an algorithmic way. Finally, we derive an exact sequence relating $[X,{{P_{{n}}}}]^A_B$ to $[X,{{P_{{{n}}-1}}}]^A_B$ and thus enabling an inductive computation. In the seventh section, we provide proofs that we feel would not fit the previous sections. In the last section, we prove polynomial bounds for the running time of our algorithms.

Equivariant effective homological algebra {#sec:equi_eff_hlgy_alg}
=========================================

Basic setup
-----------

For a simplicial set, the face operators are denoted by $d_{{i}}$, and the degeneracy operators by $s_{{i}}$. The standard ${{m}}$-simplex ${\Delta^{{{m}}}}$ is a simplicial set with a unique non-generate ${{m}}$-simplex and no relations among its faces. The simplicial subset generated by the ${{i}}$-th face of ${\Delta^{{{m}}}}$ will be denoted by ${d}_{{i}}{\Delta^{{{m}}}}$. The boundary $\partial{\Delta^{{{m}}}}$ is the union of all the faces and the ${{i}}$-th horn ${\mbox{$\xy
<0pt,-\the\fontdimen22\textfont2>;p+<.1em,0em>:
{\ar@{-}(0,0.1);(3,7)},
{\ar@{-}(3,7);(6,0.1)},
{\ar@{-}(3.2,7);(6.2,0.1)},
{\ar@{-}(3.4,7);(6.4,0.1)}
\endxy\;\!{}^{{{m}}}_{{{i}}}$}}$ is generated by all faces ${d}_{{j}}{\Delta^{{{m}}}}$, ${{j}}\neq{{i}}$. Finally, we denote the vertices of ${\Delta^{{{m}}}}$ by $0,\ldots,{{m}}$.

Sergeraert et al. (see [@SergerGenova]) have developed an “effective version” of homological algebra, in which a central notion is an object (simplicial set or chain complex) with effective homology. Here we will discuss analogous notions in the equivariant setting, as well as some other extensions. For a key result, we rely on a separate paper [@Vokrinek] which shows, roughly speaking, that if the considered action is free, equivariant effective homology can be obtained from non-equivariant one.

We begin with a description of the basic computational objects, sometimes called *locally effective* objects. The underlying idea is that in every definition one replaces sets by computable sets and mappings by computable mappings. A *computable set* is a set whose elements have a finite encoding by bit strings, so that they can be represented in a computer, and an algorithm is available that, given a bit string, decides whether it represents an element of the set.[^9] On the other hand, it may happen that no “global” information about the set is available; e.g.  it is algorithmically undecidable in general whether a given computable set is nonempty. A *mapping* between computable sets is *computable* if there is an algorithm computing its values.

We will need two particular cases of this principle – simplicial sets and chain complexes.

Simplicial sets {#simplicial-sets .unnumbered}
---------------

A *locally effective simplicial set* is a simplicial set $X$ whose simplices have a specified finite encoding and whose face and degeneracy operators are specified by algorithms. Our simplicial sets will be equipped with a simplicial *action* of a finite group $G$ that is also computed by an algorithm (whose input is an element of $G$ and a simplex of $X$). We will assume that this action is *free* and that a distinguished set of representatives of orbits is specified – we will call such $X$ *cellular*. In the locally effective context, we require that there is an algorithm that expresses each simplex $x\in X$ (in a unique way) as $x=ay$ where $a\in G$ and $y\in X$ is a distinguished simplex.

We will not put any further restrictions on the representation of simplicial sets in a computer – the above algorithms will be sufficient. On the other hand, it is important that such representations exist. We will describe one possibility for finite simplicial sets and complexes.

Let $X$ be a finite simplicial set with a free action of $G$. Let us choose arbitrarily one simplex from each orbit of the non-degenerate simplices; these simplices together with all of their degeneracies are the distinguished ones. Then every simplex $x\in X$ can be represented uniquely as $x=as_Iy$, where $a\in G$, $s_I$ is an iterated degeneracy operator (i.e. a composition $s_{{{i}}_{{m}}}\cdots s_{{{i}}_1}$ with ${{i}}_1<\cdots<{{i}}_{{m}}$), and $y$ is a non-degenerate distinguished simplex. With this representation, it is possible to compute the action of $G$ and the degeneracy operators easily, while face operators are computed using the relations among the face and degeneracy operators and a table of faces of non-degenerate distinguished simplices. This table is finite and it can be provided on the input.

A special case is that of a finite simplicial complex. Here, one can prescribe a simplex (degenerate or not) uniquely by a finite sequence of its vertices.

Chain complexes {#chain-complexes .unnumbered}
---------------

For our computations, we will work with nonnegatively graded chain complexes $C_\ast$ of abelian groups on which $G$ acts by chain maps; denoting by ${{{\mathbb Z}G}}$ the integral group ring of $G$, one might equivalently say that $C_*$ is a chain complex of ${{{\mathbb Z}G}}$-modules. We will adopt this terminology from now on. We will also assume that these chain complexes are *cellular*, i.e. equipped with a distinguished ${{{\mathbb Z}G}}$-basis; this means that for each ${{n}}\geq 0$ there is a collection of distinguished elements of $C_{{n}}$ such that the elements of the form $ay$, with $a\in G$ and $y$ distinguished, are all distinct and form a ${{\mathbb Z}}$-basis of $C_{{n}}$.

In the locally effective version, we assume that the elements of the chain complex have a finite encoding, and there is an algorithm expressing arbitrary elements as (unique) ${{{\mathbb Z}G}}$-linear combinations of the elements of the distinguished bases. We require that the operations of zero, addition, inverse, multiplication by elements of ${{{\mathbb Z}G}}$, and differentials are computable.[^10]

A basic example on which these assumptions are modelled is that of the normalized chain complex $C_*X$ of a simplicial set $X$. For each ${{n}}\geq 0$, a ${{\mathbb Z}}$-basis of $C_{{n}}X$ is given by the set of nondegenerate ${{n}}$-dimensional simplices of $X$. If $X$ is equipped with a free simplicial action of $G$, then this induces an action of $G$ on $C_*X$ by chain maps, and a ${{{\mathbb Z}G}}$-basis for each $C_{{n}}X$ is given by a collection of nondegenerate distinguished ${{n}}$-dimensional simplices of $X$, one from each $G$-orbit.

If $X$ is locally effective as defined above, then so is $C_*X$ (for evaluating the differential, we observe that a simplex $x$ is degenerate if and only if $x=s_{{i}}d_{{i}}x$ for some ${{i}}$, and this can be checked algorithmically).

\[con:G\_action\_loc\_eff\] We fix a finite group $G$. All simplicial sets are locally effective, equipped with a free action of $G$ and cellular in the locally effective sense. All chain complexes are non-negatively graded locally effective chain complexes of free ${{{\mathbb Z}G}}$-modules that are moreover cellular in the locally effective sense.

All simplicial maps, chain maps, chain homotopies, etc. are equivariant and computable.

Later, Convention \[con:fibrewise\] will introduce additional standing assumptions.

An *effective* chain complex is a (locally effective) chain complex equipped with an algorithm that generates a list of elements of the distinguished basis in any given dimension (in particular, the distinguished bases are finite in each dimension).

For example, if a simplicial set $X$ admits an algorithm generating a (finite) list of its non-degenerate distinguished simplices in any given dimension (we call it *effective* in Section \[sec:polynomiality\]), then its normalized chain complex $C_*X$ is effective.

Reductions, strong equivalences
-------------------------------

\[s:effReduction\]

We recall that a *reduction* (also called *contraction* or *strong deformation retraction*) $C_*{\xRightarrow{\ \ }}C'_*$ between two chain complexes is a triple $(\alpha,\beta,\eta)$ such that $\alpha{\colon}C_*{\rightarrow}C'_*$ and $\beta{\colon}C'_*{\rightarrow}C_*$ are equivariant chain maps with $\alpha\beta={\mathop\mathrm{id}\nolimits}$ and $\eta$ is an equivariant chain homotopy on $C_*$ with $\partial\eta+\eta\partial={\mathop\mathrm{id}\nolimits}-\beta\alpha$; moreover, we require that $\eta\beta=0$, $\alpha\eta=0$ and $\eta\eta=0$. The following diagram illustrates this definition:

$$(\alpha,\beta,\eta){\colon}C_*{\xRightarrow{\ \ }}C'_*\quad\equiv\quad\xymatrix@C=30pt{
C_* \ar@(ul,dl)[]_{\eta} \ar@/^/[r]^\alpha & C'_* \ar@/^/[l]^{\beta}
}$$

Reductions are used to solve homological problems in $C_*$ by translating them to $C_*'$ and vice versa, see [@SergerGenova]; a particular example is seen at the end of the proof of Lemma \[l:lift\_ext\_one\_stage\]. While for this principle to work, chain homotopy equivalences would be enough, they are not sufficient for the so-called perturbation lemmas (we will introduce them later), where the real strength of reductions lies.

For the following definition, we consider pairs $(C_*,D_*)$, where $C_*$ is a chain complex and $D_*$ is a subcomplex of $C_*$. Such pairs are always understood in the *cellular* sense; i.e.  the distinguished basis of each $D_{{n}}$ is a subset of the distinguished basis of $C_{{n}}$.

A *reduction* $(C_*,D_*){\xRightarrow{\ \ }}(C'_*,D'_*)$ *of (cellular) pairs* is a reduction $C_*{\xRightarrow{\ \ }}C'_*$ that restricts to a reduction $D_*{\xRightarrow{\ \ }}D'_*$, i.e. such that $\alpha(D_*)\subseteq D'_*$, $\beta(D'_*)\subseteq D_*$, and $\eta(D_*)\subseteq D_*$.

From this reduction, we get an induced reduction $C_*/D_*{\xRightarrow{\ \ }}C'_*/D'_*$ of the quotients.

We will need to work with a notion more general than reductions, namely strong equivalences. A *strong equivalence* $C_*{\xLeftrightarrow{\ \ \ }}C'_*$ is a pair of reductions $C_*{\xLeftarrow{\ \ }}\widehat C_*{\xRightarrow{\ \ }}C'_*$, where $\widehat C_*$ is some chain complex. Similarly, a strong equivalence $(C_*,D_*){\xLeftrightarrow{\ \ \ }}(C'_*,D'_*)$ is a pair of reductions $(C_*,D_*){\xLeftarrow{\ \ }}(\widehat C_*,\widehat D_*){\xRightarrow{\ \ }}(C'_*,D'_*)$. Strong equivalences can be (algorithmically) composed: if $C_*{\xLeftrightarrow{\ \ \ }}C'_*$ and $C'_*{\xLeftrightarrow{\ \ \ }}C''_*$, then one obtains $C_*{\xLeftrightarrow{\ \ \ }}C''_*$ (see e.g. [@polypost Lemma 2.7]).

Let $C_*$ be a chain complex. We say that $C_*$ is equipped with *effective homology* if there is specified a strong equivalence $C_*{\xLeftrightarrow{\ \ \ }}C_*^{\mathrm{ef}}$ of $C_*$ with some effective chain complex $C_*^{\mathrm{ef}}$. Effective homology for pairs $(C_*,D_*)$ of chain complexes is introduced similarly using strong equivalences of pairs. A simplicial set $X$ is equipped with *effective homology* if $C_*X$ is. Finally, a pair $(X,A)$ of simplicial sets is equipped with *effective homology* if $(C_*X,C_*A)$ is.[^11]

In what follows, we will only assume $(X,A)$, $Y$, $B$ to be equipped with effective homology. Consequently, it can be seen that Theorems \[theorem:equivariant\] and \[thm:main\_theorem\] also hold under these weaker assumptions. The dimension restriction on $X$ can be weakened to: the equivariant cohomology groups of $(X,A)$, defined in Section \[sec:equiv\_cohomology\], vanish above dimension $2{{d}}$.[^12]

The following theorem shows that, in order to equip a chain complex with effective homology, it suffices to have it equipped with effective homology in the non-equivariant sense.

\[t:vokrinek\] Let $C_*$ be a chain complex (of free ${{{\mathbb Z}G}}$-modules). Suppose that as a chain complex of abelian groups $C_*$ can be equipped with effective homology (i.e. in the non-equivariant sense). Then it is possible to equip $C_*$ with effective homology in the equivariant sense. This procedure is algorithmic.

The original strong equivalence $C_*{\xLeftrightarrow{\ \ \ }}C_*^{\mathrm{ef}}$ gets replaced by an equivariant one $C_*{\xLeftrightarrow{\ \ \ }}BC_*^{\mathrm{ef}}$, where $BC_*^{\mathrm{ef}}$ is a bar construction of some sort; see [@Vokrinek] for details.

Thus, although non-equivariant effective homology is not the same as equivariant effective homology, it is possible to construct one from the other. In this paper, effective homology will be always understood in the equivariant sense.

We recall that the *Eilenberg–Zilber reduction* is a particular reduction $C_*(X\times Y){\xRightarrow{\ \ }}C_*X\otimes C_*Y$; see e.g. [@EML54; @polypost; @SergerGenova]. It is known to be functorial (see e.g. [@EML54 Theorem 2.1a]), and hence it is equivariant. We extend it to pairs.

\[prop:relative\_product\] If pairs $(X,A)$ and $(Y,B)$ of simplicial sets are equipped with effective homology, then it is also possible to equip the pair $$(X,A)\times(Y,B){\stackrel{\mathrm{def}}{=}}\big(X\times Y,(A\times Y)\cup(X\times B)\big)$$ with effective homology.

The Eilenberg–Zilber reduction $C_*(X\times Y){\xRightarrow{\ \ }}C_*X\otimes C_*Y$ is functorial, which implies that it restricts to a reduction $$C_*\big((A\times Y)\cup(X\times B)\big){\xRightarrow{\ \ }}(C_*A\otimes C_*Y)+(C_*X\otimes C_*B){\stackrel{\mathrm{def}}{=}}D_*.$$ The strong equivalences $C_*X{\xLeftrightarrow{\ \ \ }}C_*^{\mathrm{ef}}X$ and $C_*Y{\xLeftrightarrow{\ \ \ }}C_*^{\mathrm{ef}}Y$ induce a strong equivalence (by [@SergerGenova Proposition 61], whose construction is functorial, and hence applicable to the equivariant setting) $$C_*X\otimes C_*Y{\xLeftrightarrow{\ \ \ }}C_*^{\mathrm{ef}}X\otimes C_*^{\mathrm{ef}}Y$$ that, again, restricts to a strong equivalence of the subcomplex $D_*$ above with its obvious effective version $D_*^{\mathrm{ef}}$. The composition of these two strong equivalences finally yields a strong equivalence $C_*((X,A)\times(Y,B)){\xLeftrightarrow{\ \ \ }}(C_*^{\mathrm{ef}}X\otimes C_*^{\mathrm{ef}}Y,D_*^{\mathrm{ef}})$.

Important tools allowing us to work efficiently with reductions are two *perturbation lemmas*. Given a reduction $C_*{\xRightarrow{\ \ }}C'_*$, they provide a way of obtaining a new reduction, in which the differentials of the complexes $C_*$, $C'_*$ are perturbed. Again, we will need versions for pairs.

Let $C_*$ be a chain complex with a differential $\partial$. A collection of morphisms $\delta{\colon}C_{{n}}\to C_{{{n}}-1}$ is called a *perturbation* of the differential $\partial$ if the sum $\partial+\delta$ is also a differential.

Since there will be many differentials around, we will emphasize them in the notation.

\[p:epl\] Let $(\alpha,\beta,\eta){\colon}(C_*,D_*,\partial){\xRightarrow{\ \ }}(C'_*,D'_*,\partial')$ be a reduction and let $\delta'$ be a perturbation of the differential $\partial'$ on $C'_*$ satisfying $\delta'(D_*')\subseteq D_*'$. Then $(\alpha,\beta,\eta)$ also constitutes a reduction $(C_*,D_*, \partial+\beta\delta'\alpha){\xRightarrow{\ \ }}(C'_*,D'_*, \partial'+\delta')$.

\[p:bpl\] Let $(\alpha,\beta,\eta){\colon}(C_*,D_*,\partial){\xRightarrow{\ \ }}(C'_*,D'_*,\partial')$ be a reduction and let $\delta$ be a perturbation of the differential $\partial$ on $C_*$ satisfying $\delta(D_*)\subseteq D_*$. Assume that for every $c\in C_*$ there is a $\nu\in\mathbb N$ such that $(\eta\delta)^{\nu}(c)=0$. Then it is possible to compute a perturbation $\delta'$ of the differential $\partial'$ on $C'_*$ that preserves $D_*'$ and a reduction $(\alpha',\beta',\eta'){\colon}(C_*,D_*,\partial+\delta){\xRightarrow{\ \ }}(C'_*,D'_*, \partial'+\delta')$.

The absolute versions (i.e. versions where all considered subcomplexes are zero) of the perturbation lemmas are due to [@Shih]. There are explicit formulas provided there for $\delta'$ etc. (see also [@SergerGenova]), which show that the resulting reductions are equivariant (since all the involved maps are equivariant). Similarly, these formulas show that in the presence of subcomplexes $D_*$ and $D_*'$, these are preserved by all the maps in the new reductions (since all the involved maps preserve them).

The following proposition is used for the construction of the Moore–Postnikov tower in Section \[sec:Moore\_Postnikov\]. Here $Z_{{{n}}+1}(C_*)$ denotes the group of all cycles in $C_{{{n}}+1}$.

\[prop:projectivity\] Let $C_*$ be an effective chain complex such that $H_{{i}}(C_*)=0$ for ${{i}}\le{{n}}$. Then there is a (computable) retraction $C_{{{n}}+1}{\rightarrow}Z_{{{n}}+1}(C_*)$, i.e.  a homomorphism that restricts to the identity on $Z_{{{n}}+1}(C_*)$.

We construct a contraction[^13] $\sigma$ of $C_*$ by induction on the dimension, and use it for splitting $Z_{{{n}}+1}(C_*)$ off $C_{{{n}}+1}$. It suffices to define $\sigma$ on the distinguished bases. Since every basis element $x\in C_0$ is a cycle, it must be a boundary. We compute some $y\in C_1$ for which $x=\partial y$, and we set $\sigma(x)=y$; since $G$ is finite, we may treat $\partial{\colon}C_1{\rightarrow}C_0$ as a ${\mathbb Z}$-linear map between finitely generated free ${\mathbb Z}$-modules and solve for $y$ using Smith normal form.

Now assume that $\sigma$ has been constructed up to dimension ${{i}}-1$ in such a way that $\partial\sigma+\sigma\partial={\mathop\mathrm{id}\nolimits}$, and we want to define $\sigma(x)$ for a basis element $x\in C_{{i}}$. Since $x-\sigma(\partial x)$ is a cycle, we can compute some $y$ with $x-\sigma(\partial x)=\partial y$, and set $\sigma(x)=y$.

This finishes the inductive construction of $\sigma$. The desired retraction $C_{{{n}}+1}{\rightarrow}Z_{{{n}}+1}(C_*)$ is given by ${\mathop\mathrm{id}\nolimits}-\sigma\partial$.

Eilenberg–MacLane spaces and fibrations
---------------------------------------

\[sec:equiv\_cohomology\]

For an abelian group $\pi$, the simplicial abelian group $K(\pi,{{n}}+1)_{{m}}=Z^{{{n}}+1}({\Delta^{{{m}}}},\pi)$ of normalized cocycles and the simplicial abelian group $E(\pi,{{n}})_{{m}}=C^{{{n}}}({\Delta^{{{m}}}},\pi)$ of normalized cochains are standard models for the Eilenberg–MacLane space and its path space. The coboundary operator $\delta{\colon}E(\pi,{{n}})\to K(\pi,{{n}}+1)$ is a fibration with fibre $K(\pi,{{n}})$.

The Eilenberg–MacLane spaces are useful for their relation to cohomology. Here we only summarize the relevant results, details may be found in [@May:SimplicialObjects-1992 Section 24] or [@polypost Section 3.7] (both in the non-equivariant setup though).

When $\pi$ is a ${{{\mathbb Z}G}}$-module, there is an induced action of $G$ on both $K(\pi,{{n}})$ and $E(\pi,{{n}})$. We note that, in contrast to our general assumption, this action is *not free* and consequently, these spaces may not possess effective homology. This will not matter since they will not enter our constructions on their own but as certain principal twisted cartesian products, see [@May:SimplicialObjects-1992] for the definition. Firstly, $K(\pi,{{n}})$ possesses non-equivariant effective homology by [@polypost Theorem 3.16]. The principal twisted cartesian product $P = Q \times_\tau K(\pi,{{n}})$ has a free $G$-action whenever $Q$ does and [@Filakovsky Corollary 12] constructs the non-equivariant effective homology of $P$ from that of $Q$ and $K(\pi,{{n}})$. Theorem \[t:vokrinek\] then provides (equivariant) effective homology for $P$.

It is easy to see that the addition in the simplicial abelian groups $K(\pi,{{n}})$, $E(\pi,{{n}})$ and the homomorphism $\delta$ between them are equivariant. Moreover, for every simplicial set $X$, there is a natural isomorphism $${\mathop\mathrm{map}\nolimits}(X,E(\pi,{{n}}))\cong C^{{n}}(X;\pi)^G$$ between equivariant simplicial maps and equivariant cochains, that sends $f{\colon}X{\rightarrow}E(\pi,{{n}})$ to $f^*({\mathop\mathrm{ev}\nolimits})$, where ${\mathop\mathrm{ev}\nolimits}\in C^{{n}}(E(\pi,{{n}});\pi)^G$ is the canonical cochain that assigns to each ${{n}}$-simplex of $E(\pi,{{n}})_{{n}}$, i.e. an ${{n}}$-cochain on ${\Delta^{{{n}}}}$, its value on the unique non-degenerate ${{n}}$-simplex of ${\Delta^{{{n}}}}$.

The set ${\mathop\mathrm{map}\nolimits}(X,K(\pi,{{n}}))$ is naturally an abelian group, with addition inhereted from that on $K(\pi,{{n}})$, and the above isomorphism is and isomorphism of groups.

When $X$ is finite, this isomorphism is computable (objects on both sides are given by a finite amount of data). When $X$ is merely locally effective, then an algorithm that computes a simplicial map $X{\rightarrow}E(\pi,{{n}})$ can be converted into an algorithm that evaluates the corresponding cochain in $C^{{n}}(X;\pi)^G$, and vice versa.

The above isomorphism restricts to an isomorphism $${\mathop\mathrm{map}\nolimits}(X,K(\pi,{{n}}))\cong Z^{{n}}(X;\pi)^G.$$ We will denote the cohomology groups of $C^*(X;\pi)^G$ by $H^*_G(X;\pi)$.[^14] We have an induced isomorphism $$[X,K(\pi,{{n}})]\cong H^n_G(X;\pi)$$ between homotopy classes of equivariant maps and these cohomology groups. By the naturality of these isomorphisms, the maps which are zero on $A$ correspond precisely to relative cocycles and consequently $$[(X,A),(K(\pi,{{n}}),0)]\cong H^n_G(X,A;\pi).$$

Constructing diagonals for Eilenberg–MacLane fibrations
-------------------------------------------------------

When solving the generalized lifting-extension problem, we will replace $\varphi{\colon}Y\to B$ by a fibration built inductively from Eilenberg–MacLane fibrations $\delta{\colon}E(\pi,{{n}})\to K(\pi,{{n}}+1)$. The following lemma will serve as an inductive step in the computation of $[X,Y]^A_B$. It also demonstrates how effective homology of pairs enters the game.

\[l:lift\_ext\_one\_stage\] There is an algorithm that, given a commutative square $$\xymatrix@C=30pt{
A \ar[r]^-c \ar@{ >->}[d] & E(\pi,{{n}}) \ar@{->>}[d]^\delta \\
X  \ar[r]_-z \ar@{-->}[ru] & K(\pi,{{n}}+1)
}$$ where the pair $(X,A)$ is equipped with effective homology, decides whether a diagonal exists. If it does, it computes one.

If $H^{{{n}}+1}_G(X,A;\pi)=0$, then a diagonal exists for every $c$ and $z$.

Let us remark that although our main result, Theorem \[thm:main\_theorem\], assumes $X$ finite, we will need to use the lemma for infinite simplicial sets $X$, and then the effective homology assumption for $(X,A)$ is important.

Thinking of $c$ as a cochain in $C^{{n}}(A;\pi)^G$, we extend it to a cochain on $X$ by mapping all ${{n}}$-simplices not in $A$ to zero. This prescribes a map $\widetilde c \colon X{\rightarrow}E(\pi,{{n}})$ that is a solution of the lifting-extension problem from the statement for $z$ replaced by $\delta\widetilde c$. Since the lifting-extension problems and their solutions are additive, one may subtract this solution from the previous problem and obtain an equivalent lifting-extension problem $$\xymatrix@C=30pt{
A \ar[r]^-{0} \ar@{ >->}[d] & E(\pi,{{n}}) \ar@{->>}[d]^\delta \\
X  \ar[r]_-{z-\delta\widetilde c} \ar@{-->}[ru]^-{c_0} & K(\pi,{{n}}+1)
}$$ A solution of this problem is an (equivariant) relative cochain $c_0$ whose coboundary is $z_0=z-\delta\widetilde c$ (this $c_0$ yields a solution $\widetilde c+c_0$ of the original problem). If $C_*(X,A)$ is effective, then such a $c_0$ is computable whenever it exists (and it always exists in the case $H^{{{n}}+1}_G(X,A;\pi)=0$).

However, $C_*(X,A)$ itself is not effective in general, it is only strongly equivalent to an effective complex. Thus, we need to check that the computability of a preimage under $\delta$ is preserved under reductions in both directions. Let $(\alpha,\beta,\eta){\colon}C_*{\xRightarrow{\ \ }}C'_*$ be a reduction. First, let us suppose that $z_0'{\colon}C'_*{\rightarrow}\pi$ is a cocycle with $z_0'\alpha=\delta c_0$. Then $$z_0'=z_0'\alpha\beta=(\delta c_0)\beta=\delta(c_0\beta),$$ and we may set $c_0'=c_0\beta$. Next, suppose that $z_0{\colon}C_*{\rightarrow}\pi$ is a cocycle with $z_0\beta=\delta c_0'$. Then $$z_0=z_0(\partial\eta+\eta\partial+\beta\alpha)=z_0\eta\partial+\delta c_0'\alpha=\delta(z_0\eta+c_0'\alpha),$$ and we may set $c_0=z_0\eta+c_0'\alpha$.

Constructing a Moore–Postnikov tower {#sec:Moore_Postnikov}
====================================

We remind that we defined $Y'$ by factoring $\varphi$ as a composition $Y{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{ >->}[r]^{} & {}}}}Y'{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{->>}[r]^{\varphi'} & {}}}}B$ of a weak homotopy equivalence followed by a fibration; such a factorization exists by Lemma \[l:fibrant\_replacement\]. Using this approximation, $[X,Y]^A_B$ was defined as the set of homotopy classes $[X,Y']^A_B$. In order to compute this set, we approximate $Y'$ by the Moore–Postnikov tower of $Y$ over $B$. Then the computation will proceed by induction over the stages of this tower, as will be explained in Section \[s:main\_proofs\]. For now, we will give a definition of an equivariant Moore–Postnikov tower of a simplicial map $\varphi{\colon}Y\to B$ and review some of the statements of the last section in the context of this tower. The actual construction of the tower, when both simplicial sets $Y$ and $B$ are equipped with effective homology, will be carried out later in Section \[sec:MP\_tower\_proof\].

Definition
----------

Let $\varphi{\colon}Y\to B$ be a map. A (simplicial) *Moore–Postnikov tower* for $\varphi$ is a commutative diagram $$\xymatrix{
& & {} \ar@{.}[d] \\
& & {{P_{{n}}}}\ar[d]^-{{{p_{{n}}}}} \\
& & {{P_{{{n}}-1}}}\ar@{.}[d] \\
Y \ar[uurr]^-{{{\varphi_{{n}}}}} \ar[urr]_-{\varphi_{{{n}}-1}} \ar[rr]_-{\varphi_1} \ar[drr]_-{{\settowidth{\hlp}{$\scriptstyle\varphi_0$}\makebox[\hlp][r]{${\scriptstyle\varphi={}}{\scriptstyle\varphi_0}$}}}
& & P_{1} \ar[d]^-{p_1} \\
& & {\settowidth{\hlp}{$P_{0}$}\makebox[\hlp][l]{${P_{0}}{{}=B}$}}
}$$ satisfying the following conditions:

1.  \[MP1\] The induced map ${{\varphi_{{{n}}*}}}{\colon}\pi_{{i}}(Y)\to \pi_{{{i}}}({{P_{{n}}}})$ is an isomorphism for $0\leq{{i}}\leq{{n}}$ and an epimorphism for ${{i}}={{n}}+1$.

2.  \[MP2\] The map ${{P_{{n}}}}\to B$ induces an isomorphism $\pi_{{i}}({{P_{{n}}}})\to\pi_{{i}}(B)$ for ${{i}}\ge{{n}}+2$ and a monomorphism for ${{i}}={{n}}+1$.

3.  \[MP3\] The map ${{p_{{n}}}}{\colon}{{P_{{n}}}}\to{{P_{{{n}}-1}}}$ is a Kan fibration induced by a map $${{k_{{n}}'}}{\colon}{{P_{{{n}}-1}}}\to K({{\pi_{{n}}}},{{n}}+1)$$ for some ${{{\mathbb Z}G}}$-module ${{\pi_{{n}}}}$, i.e. there exists a pullback square $$\xymatrix@C=30pt{
    {{P_{{n}}}}{{\save []+<{15pt},-{15pt}>="a";[]+<{15pt},0pt>;"a"**{}?({.5});"a"**\dir{-};[]+<0pt,-{15pt}>;"a"**{}?({.5});"a"**\dir{-}\restore}}\ar[r] \ar[d]_-{{p_{{n}}}}& E({{\pi_{{n}}}},{{n}}) \ar[d]^{\delta} \\
    {{P_{{{n}}-1}}}\ar[r]_-{{k_{{n}}'}}& K({{\pi_{{n}}}},{{n}}+1)
    }$$ identifying ${{P_{{n}}}}$ with the pullback ${{P_{{{n}}-1}}}\times_{K({{\pi_{{n}}}},{{n}}+1)}E({{\pi_{{n}}}},{{n}})$. Alternatively, one may identify ${{P_{{n}}}}$ as the principal twisted cartesian product ${{P_{{n}}}}\times_\tau K({{\pi_{{n}}}},{{n}})$ – this will be used to equip ${{P_{{n}}}}$ with effective homology.

We remark that the axioms imply ${{\pi_{{n}}}}\cong{{\pi_{{n}}}}F$, where $F$ is the homotopy fibre of $Y{\rightarrow}B$, i.e. the fibre of $Y'\to B$.

\[t:MP\_tower\] [There is an algorithm that, given a map $\varphi{\colon}Y\to B$ between simply connected simplicial sets with effective homology and an integer ${{n}}$, constructs the first ${{n}}$ stages of a Moore–Postnikov tower for $\varphi$. The stages $P_{{i}}$ are constructed as simplicial sets with effective homology, and $\varphi_{{i}}$, ${{k_{{i}}'}}$, $p_{{i}}$ as computable maps.]{}

The proof of the theorem is postponed to Section \[sec:MP\_tower\_proof\]. From the tower, we obtain a new lifting-extension problem with ${{f_{{n}}}}={{\varphi_{{n}}}}f$: $$\xymatrix@C=40pt{
A \ar[r]^-{{{f_{{n}}}}} \ar@{ >->}[d] & {{P_{{n}}}}\ar@{->>}[d]^-{{{\psi_{{n}}}}} \\
X  \ar[r]_-g \ar@{-->}[ru] & B
}$$ The following theorem explains the role of the Moore–Postnikov tower in our algorithm.

\[t:n\_equivalence\] [There exists a map ${{\varphi_{{n}}'}}{\colon}Y'\to{{P_{{n}}}}$ inducing a bijection ${{\varphi_{{{n}}*}'}}{\colon}[X,Y']^A_B\to [X,{{P_{{n}}}}]^A_B$ for every ${{n}}$-dimensional simplicial set $X$ with a free action of $G$.]{}

The theorem should be known but we could not find an equivariant fibrewise version anywhere. For this reason, we include a proof in Section \[sec:n\_equivalence\_proof\].

From the point of view of Theorem \[thm:main\_theorem\], we have reduced the computation of $[X,Y]^A_B=[X,Y']^A_B$ to that of $[X,{{P_{{n}}}}]^A_B$, where ${{n}}=\dim X$. Before going into details of this computation, we present a couple of results that are directly related to the Moore–Postnikov tower. They will be essential tools in the proof of Theorem \[thm:main\_theorem\].

Inductive construction of diagonals
-----------------------------------

We will slightly reformulate Lemma \[l:lift\_ext\_one\_stage\] in terms of the Moore–Postnikov tower.

\[prop:lift\_ext\_one\_stage\] There is an algorithm that, given a diagram $$\xymatrix@C=40pt{
A \ar[r]^-f \ar@{ >->}[d] & {{P_{{n}}}}\ar@{->>}[d]^-{{{p_{{n}}}}} \\
X  \ar[r]_-g \ar@{-->}[ru] & {{P_{{{n}}-1}}}}$$ where the pair $(X,A)$ is equipped with effective homology, decides whether a diagonal exists. If it does, it computes one.

When $H^{{{n}}+1}_G(X,A;{{\pi_{{n}}}})=0$, a diagonal exists for every $f$ and $g$.

We will use property (3) of Moore–Postnikov towers, which expresses ${{p_{{n}}}}$ as a pullback: $$\xymatrix@C=30pt{
A \ar[r]^-f \ar@{ >->}[d] & {{P_{{n}}}}{{\save []+<{15pt},-{15pt}>="a";[]+<{15pt},0pt>;"a"**{}?({.5});"a"**\dir{-};[]+<0pt,-{15pt}>;"a"**{}?({.5});"a"**\dir{-}\restore}}\ar[r] \ar[d]_-{{{p_{{n}}}}} & E({{\pi_{{n}}}},{{n}}) \ar@{->>}[d]^\delta \\
X  \ar[r]_-g \ar@{-->}[ru]^{\ell} & {{P_{{{n}}-1}}}\ar[r]_-{{{k_{{n}}'}}} & K({{\pi_{{n}}}},{{n}}+1)
}$$ Thus, diagonals $\ell$ are exactly of the form $(g,c){\colon}X{\rightarrow}{{P_{{{n}}-1}}}\times_{K({{\pi_{{n}}}},{{n}}+1)}E({{\pi_{{n}}}},{{n}})$, where $c{\colon}X\to E({{\pi_{{n}}}},{{n}})$ is an arbitrary diagonal in the composite square and thus computable by Lemma \[l:lift\_ext\_one\_stage\].

We obtain two important consequences as special cases. The first one is an algorithmic version of lifting homotopies across ${{P_{{n}}}}{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{->>}[r]^{} & {}}}}{{P_{{m}}}}$.

\[prop:homotopy\_lifting\] Given a diagram $$\xymatrix{
({{{i}}}\times X)\cup({\Delta^{1}}\times A) \ar[r] \ar@{ >->}[d]_-\sim & {{P_{{n}}}}\ar@{->>}[d] \\
{\Delta^{1}}\times X  \ar[r] \ar@{-->}[ru] & P_{{m}}}$$ where ${{i}}\in\{0,1\}$ and $(X,A)$ is equipped with effective homology, it is possible to compute a diagonal. In other words, one may lift homotopies in Moore–Postnikov towers algorithmically.

It is possible to equip $({\Delta^{1}}\times X,
({{{i}}}\times X)\cup({\Delta^{1}}\times A))$ with effective homology by Proposition \[prop:relative\_product\]. Moreover, this pair has zero cohomology since there exists a (continuous) equivariant deformation of ${\Delta^{1}}\times X$ onto the considered subspace. Thus a diagonal can be constructed by a successive use of Proposition \[prop:lift\_ext\_one\_stage\].

The second result concerns algorithmic concatenation of homotopies. Let ${\mbox{$\xy
<0pt,-\the\fontdimen22\textfont2>;p+<.1em,0em>:
{\ar@{-}(0,0.1);(3,7)},
{\ar@{-}(3,7);(6,0.1)},
{\ar@{-}(3.2,7);(6.2,0.1)},
{\ar@{-}(3.4,7);(6.4,0.1)}
\endxy\;\!{}^{2}_{1}$}}$ denote the first horn in the standard $2$-simplex ${\Delta^{2}}$, i.e. the simplicial subset of the standard simplex ${\Delta^{2}}$ spanned by the faces ${d}_2{\Delta^{2}}$ and ${d}_0{\Delta^{2}}$. Given two homotopies $h_2,h_0{\colon}{\Delta^{1}}\times X\to Y$ that are compatible, in the sense that $h_2$ is a homotopy from $\ell_0$ to $\ell_1$ and $h_0$ is a homotopy from $\ell_1$ to $\ell_2$, one may prescribe a map ${\mbox{$\xy
<0pt,-\the\fontdimen22\textfont2>;p+<.1em,0em>:
{\ar@{-}(0,0.1);(3,7)},
{\ar@{-}(3,7);(6,0.1)},
{\ar@{-}(3.2,7);(6.2,0.1)},
{\ar@{-}(3.4,7);(6.4,0.1)}
\endxy\;\!{}^{2}_{1}$}}\times X\to Y$ as $h_2$ on ${d}_2{\Delta^{2}}\times X$ and as $h_0$ on ${d}_0{\Delta^{2}}\times X$. If this map has an extension $H{\colon}{\Delta^{2}}\times X\to Y$, then the restriction of $H$ to ${d}_1{\Delta^{2}}\times X$ gives a homotopy from $\ell_0$ to $\ell_2$, which can be thought of as a *concatenation* of $h_2$ and $h_0$. We will need the following effective, relative and fibrewise version; the proof is entirely analogous to that of the previous proposition and we omit it.

\[prop:homotopy\_concatenation\] Given a diagram $$\xymatrix{
({\mbox{$\xy
<0pt,-\the\fontdimen22\textfont2>;p+<.1em,0em>:
{\ar@{-}(0,0.1);(3,7)},
{\ar@{-}(3,7);(6,0.1)},
{\ar@{-}(3.2,7);(6.2,0.1)},
{\ar@{-}(3.4,7);(6.4,0.1)}
\endxy\;\!{}^{2}_{1}$}}\times X)\cup({\Delta^{2}}\times A) \ar[r] \ar@{ >->}[d]_-\sim & {{P_{{n}}}}\ar@{->>}[d] \\
{\Delta^{2}}\times X  \ar[r] \ar@{-->}[ru] & P_{{m}}}$$ where $(X,A)$ is equuipped with effective homology, it is possible to compute a diagonal. In other words, one may concatenate homotopies in Moore–Postnikov towers algorithmically.

Computing homotopy classes of maps {#s:main_proofs}
==================================

In this section, we prove Theorems \[theorem:equivariant\] and \[thm:main\_theorem\]. First, we will explain our computational model for abelian groups, since these are one of our main computational objects and also form the output of our algorithms.

There are two levels of these computational models: *semi-effective* and *fully effective* abelian groups. They are roughly analogous to locally effective chain complexes and effective ones. There is, however, one significant difference: while an element of a chain complex is assumed to have a unique computer representation, a single element of a semi-effective abelian group may have many different representatives. We can perform the group operations in terms of the representatives, but in general, we cannot decide whether two representatives represent the same group element. This setting is natural when working with elements of $[X,{{P_{{n}}}}]^A_B$, i.e. with homotopy classes of diagonals. The representatives are simplicial maps $X\to{{P_{{n}}}}$, and at first, we will not be able to decide whether given two such maps are homotopic.

Given a semi-effective abelian group, it is not possible to compute its isomorphism type (even when it is finitely generated); for this we need additional information, summarized in the notion of a fully effective abelian group. A semi-effective abelian group can be made fully effective provided that it is a part of a suitable exact sequence, additionally provided with set-theoretic sections; this is described in Section \[s:abelops\].

This suggests a computation of $[X,{{P_{{n}}}}]^A_B$ in two steps. First, we will endow it with a structure of a semi-effective abelian group, whose addition comes from the weak [H-]{}space structure on ${{P_{{n}}}}$ constructed in Section \[sec:H\_space\_constr\]. Next, we will promote it to a fully effective abelian group by relating it to $[X,{{P_{{{n}}-1}}}]^A_B$ through a long exact sequence.

We note that the long proofs of Theorems \[t:semi\_eff\] and \[thm:exact\_sequence\] are postponed to later sections. This enables us to complete the proof of the main Theorem \[thm:main\_theorem\] in the present section.

Operations with abelian groups
------------------------------

\[s:abelops\]

This subsection is a short summary of a detailed discussion found in [@CKMSVW11].

In our setting, an abelian group $A$ is represented by a set ${\mathcal A}$, whose elements are called *representatives*; we also assume that the representatives can be stored in a computer.[^15] For $\alpha\in{\mathcal A}$, let $[\alpha]$ denote the element of $A$ represented by $\alpha$. The representation is generally non-unique; we may have $[\alpha]=[\beta]$ for $\alpha\ne\beta$.

We call $A$ represented in this way *semi-effective*, if algorithms for the following three tasks are available: provide an element $o\in{\mathcal A}$ with $[o]=0$ (the neutral element); given $\alpha{{},\,}\beta\in{\mathcal A}$, compute $\gamma\in{\mathcal A}$ with $[\gamma]=[\alpha]+[\beta]$; given $\alpha\in{\mathcal A}$, compute $\beta \in{\mathcal A}$ with $[\beta]=-[\alpha]$.

For semi-effective abelian groups $A$, $B$, with sets ${\mathcal A}$, ${\mathcal B}$ of representatives, respectively, we call a mapping $f{\colon}A\to B$ *computable* if there is a computable mapping $\varphi{\colon}{\mathcal A}\to{\mathcal B}$ such that $f([\alpha])=[\varphi(\alpha)]$ for all $\alpha\in {\mathcal A}$.

We call a semi-effective abelian group $A$ *fully effective* if there is given an isomorphism $A\cong{\mathbb Z}/q_1\oplus\cdots\oplus{\mathbb Z}/q_r$, computable together with its inverse. In detail, this consists of

-   a finite list of generators $a_1,\ldots,a_r$ of $A$ (given by representatives) and their orders $q_1,\ldots,q_r\in\{2,3,\ldots\}\cup\{0\}$ (where $q_{{i}}=0$ gives ${\mathbb Z}/q_{{i}}={\mathbb Z}$),

-   an algorithm that, given $\alpha\in{\mathcal A}$, computes integers $z_1,\ldots,z_r$ so that $[\alpha]=\sum_{i=1}^rz_i a_i$; each coefficient $z_i$ is unique within ${\mathbb Z}/q_i$.

The proofs of the following lemmas are not difficult; they are given in [@CKMSVW11].

\[l:ker\_coker\] Let $f{\colon}A\to B$ be a computable homomorphism of fully effective abelian groups. Then both $\ker(f)$ and ${\mathop\mathrm{coker}\nolimits}(f)$ can be represented as fully effective abelian groups.

\[l:ses\] Let $A$, $B$, $C$ be abelian groups, with $A$, $C$ fully effective and $B$ semi-effective, and let $$\xymatrix{0 \ar[r]& A \ar[r]^{f} & B \ar[r]^{g} & C \ar[r]&0}$$ be a short exact sequence with $f$, $g$ computable. Assume, moreover, that the following computable maps are given:

-   $r{\colon}{\mathop\mathrm{im}\nolimits}f\to A$ such that $f(r(b))=b$ for every $b\in{\mathop\mathrm{im}\nolimits}f$,

-   $\sigma\colon {\mathcal C}\to {\mathcal B}$ (where ${\mathcal B}$, ${\mathcal C}$ are the sets of representatives for $B$, $C$, respectively) that behaves like a set-theoretic section for $g$, i.e. such that $g([\sigma(\gamma)])=[\gamma]$ for all $\gamma \in {\mathcal C}$.

Then we can obtain a fully effective representation of $B$.

We remark that we *do not* require $[\sigma(\gamma)]$ to depend only on $[\gamma]$ – it might well depend on the representative $\gamma$.

Semi-effectivity of $\boldsymbol{[X,{{P_{{n}}}}]^A_B}$ for pointed stable stages $\boldsymbol{{{P_{{n}}}}}$
-----------------------------------------------------------------------------------------------------------

\[s:semi\_eff\_str\] We call a Moore–Postnikov stage ${{P_{{n}}}}$ *stable* if ${{n}}\leq 2{{d}}$, where ${{d}}$ is the connectivity of the homotopy fibre of $\varphi{\colon}Y\to B$ as in the introduction. The significance of this restriction lies in the existence of an abelian group structure on $[X,{{P_{{n}}}}]^A_B$. The construction of this structure is (together with the construction of the Moore–Postnikov tower) the technically most demanding part of the paper and we postpone it to later sections. For its existence, we will have to assume further that ${{P_{{n}}}}$ is *pointed* (i.e. provided with a section); this equips $[X,{{P_{{n}}}}]^A_B$ with a particular choice of zero. In detail, a lifting-extension problem *for a pointed fibration* is a lifting-extension problem $$\xymatrix@C=40pt{
A \ar[r]^-{{f_{{n}}}}\ar@{ >->}[d]_-\iota & {{P_{{n}}}}\ar@{->>}[d]_-{{\psi_{{n}}}}\\
X  \ar[r]_-{g} \ar@{-->}[ru]^-{\ell} & B \ar@{-->}@/_10pt/[u]_-o
}$$ where ${{f_{{n}}}}=f{{\varphi_{{n}}}}$ as before, in which a section $o{\colon}B\to{{P_{{n}}}}$ is given, referred to as the *zero section*, such that ${{f_{{n}}}}=og\iota$, i.e. such that ${{f_{{n}}}}$ takes values on this zero section. In this case, ${{f_{{n}}}}$ is uniquely determined from the rest of the data and we may thus specify such a lifting-extension problem equivalently by a pair $(X,A)$ of simplicial sets over $B$ and a pointed fibration ${{\psi_{{n}}}}{\colon}{{P_{{n}}}}\to B$. In this case, a solution is a map $\ell{\colon}X\to{{P_{{n}}}}$ over $B$ that sends $A$ to the zero section. In particular, $\ell=og$ (the zero map) is a solution, and we use it as a basepoint in $[X,{{P_{{n}}}}]^A_B$, making it into a pointed set.

\[t:semi\_eff\] [Suppose that ${{n}}\leq 2{{d}}$, that ${{P_{{n}}}}\to B$ is given a zero section ${{o}}$, that ${{f_{{n}}}}$ takes values on this zero section, and that $(X,A)$ is equipped with effective homology. Then the (pointed) set $[X,{{P_{{n}}}}]^A_B$ admits a structure of a semi-effective abelian group, whose elements are represented by algorithms that compute diagonals $X\to {{P_{{n}}}}$.]{}

The proof of the theorem occupies a significant part of the paper. First, we construct a “weak [H-]{}space structure” on ${{P_{{n}}}}$ in Section \[s:weak\_H\_spaces\] and then show how this structure gives rise to addition on the homotopy classes of diagonals in Section \[sec:weak\_H\_space\].

A special case of a pointed stable Moore–Postnikov stage is ${{L_{{n}}}}=B\times K({{\pi_{{n}}}},{{n}})$ (it is the first non-trivial stage with the corresponding Postnikov invariant ${{k_{{n}}'}}$ zero). It is equipped with the zero section $b\to(b,0)$, which we denote by $0$. The weak [H-]{}space structure on ${{L_{{n}}}}$ is very simple to describe: for two elements $z=(b,z')$ and $w=(b,w')$ of ${{L_{{n}}}}$ lying over the same $b\in B$, we define $z+w{\stackrel{\mathrm{def}}{=}}(b,z'+w')$. This addition makes ${{L_{{n}}}}$ even into a fibrewise simplicial abelian group. In this case, we get immediately a stronger result.

\[l:fully\_eff\_cohlgy\] Let $(X,A)$ be equipped with effective homology. Then it is possible to equip $[X,{{L_{{n}}}}]^A_B$ with a structure of a fully effective abelian group; the elements are represented by algorithms that compute (equivariant and fibrewise) simplicial maps $X\to{{L_{{n}}}}$ that map $A$ to the zero section.

We start with isomorphisms $$[X,{{L_{{n}}}}]^A_B\cong[(X,A),(K(\pi,{{n}}),0)]\cong H^{{n}}_G(X,A;\pi)\cong H^{{n}}_G(X,A;\pi)^{\mathrm{ef}}$$ where the group on the right is the cohomology group of the complex of equivariant cochains $C_*^{\mathrm{ef}}(X,A)\to\pi$ on the effective chain complex of $(X,A)$ and the last isomorphism comes from effective homology of $(X,A)$.

It is possible to represent elements of these groups by algorithms that compute the respective (equivariant) simplicial maps or equivariant cocycles – since it is possible to transform one such representing algorithm into another, this follows from the above isomorphisms and the case of $H^{{n}}_G(X,A;\pi)^{\mathrm{ef}}$, where any cocycle is computable. Thus, the set of homotopy classes can be computed as the cohomology group of $$C^*_{\mathrm{ef}}(X,A;\pi)^G=\operatorname{Hom}_{{{\mathbb Z}G}}(C_*^{\mathrm{ef}}(X,A),\pi)$$ using a Smith normal form algorithm – it is a cochain complex of finitely generated abelian groups. The algorithm also gives the required generators. Any homotopy class is expressed as a combination of the chosen generators by translating to the right-hand side of the above isomorphism and using the output of the Smith normal form algorithm.

An exact sequence relating consecutive pointed stable stages
------------------------------------------------------------

\[sec:exact\_sequence\]

To promote the semi-effective structure on $[X,{{P_{{n}}}}]^A_B$ to a fully effective one, we will apply Lemma \[l:ses\] to a certain exact sequence relating two consecutive stable stages of the Moore–Postnikov tower. Thus, again, we assume that ${{n}}\leq 2{{d}}$, that ${{P_{{n}}}}\to B$ has a zero section ${{o}}$, and that ${{f_{{n}}}}$ takes values on this zero section. Defining the zero section of ${{P_{{{n}}-1}}}$ to be $B{\xrightarrow{{{o}}}}{{P_{{n}}}}{\xrightarrow{{{p_{{n}}}}}}{{P_{{{n}}-1}}}$, and denoting it for simplicity also by ${{o}}$, these assumptions will apply also to ${{P_{{{n}}-1}}}$.

The description of ${{P_{{n}}}}$ in the definition of a Moore–Postnikov tower as a pullback is classical and is also useful for the actual construction of the tower. For the upcoming computations, it has a major disadvantage, though – the spaces appearing in the pullback square are not spaces over $B$. This is easily corrected by replacing the Eilenberg–MacLane space by the product ${{K_{{{n}}+1}}}=B\times K({{\pi_{{n}}}},{{n}}+1)$ and the “path space” by ${{E_{{n}}}}=B\times E({{\pi_{{n}}}},{{n}})$. Denoting by ${{k_{{n}}}}$ the fibrewise Postnikov invariant, i.e. the map whose first component is the projection ${{\psi_{{{n}}-1}}}{\colon}{{P_{{{n}}-1}}}\to B$ and the second component is the original (non-fibrewise) Postnikov invariant ${{k_{{n}}'}}$, we obtain another pullback square $$\xymatrix@C=40pt{
{{P_{{n}}}}{{\save []+<{15pt},-{15pt}>="a";[]+<{15pt},0pt>;"a"**{}?({.5});"a"**\dir{-};[]+<0pt,-{15pt}>;"a"**{}?({.5});"a"**\dir{-}\restore}}\ar[r]^-{{{q_{{n}}}}} \ar[d]_-{{{p_{{n}}}}} & E_{{n}}\ar[d]^-\delta \\
{{P_{{{n}}-1}}}\ar[r]_-{{k_{{n}}}}& K_{{{n}}+1}
}$$

Let ${\mathop\mathrm{fib}\nolimits}_{{o}}{{p_{{n}}}}$ denote the *(fibrewise) fibre* of ${{p_{{n}}}}$ over ${{o}}$, i.e. the subset of ${{P_{{n}}}}$ lying over the zero section of ${{P_{{{n}}-1}}}$. We will need that ${\mathop\mathrm{fib}\nolimits}_{{o}}{{p_{{n}}}}$ is isomorphic to ${{L_{{n}}}}=B\times K({{\pi_{{n}}}},{{n}})$. For the description of this isomorphism, it is useful to recall that ${{p_{{n}}}}$ is a principal fibration. Thinking of ${{P_{{n}}}}$ as a subset of ${{P_{{{n}}-1}}}\times{{E_{{n}}}}$, $z\in{{L_{{n}}}}$ acts on $(x,c)\in{{P_{{n}}}}$ by $(x,c)+z{\stackrel{\mathrm{def}}{=}}(x,c+z)$ where the sum $c+z$ is taken within the fibrewise simplicial group ${{E_{{n}}}}$. Then the isomorphism ${{L_{{n}}}}\to {\mathop\mathrm{fib}\nolimits}_{{o}}{{p_{{n}}}}$ is the restriction of the map ${{j}}{\colon}{{L_{{n}}}}\to{{P_{{n}}}}$, $z\mapsto{{o}}+z$.

Giving both ${{K_{{{n}}+1}}}$ and ${{L_{{n}}}}$ the zero section $b\mapsto(b,0)$, the previous subsection endows both $[X,{{L_{{n}}}}]^A_B$ and $[X,{{K_{{{n}}+1}}}]^A_B$ with a structure of a fully effective abelian group.

\[thm:exact\_sequence\] [ Suppose that ${{n}}\leq 2{{d}}$ and that ${{P_{{n}}}}$ is equipped with a zero section ${{o}}$ on which ${{f_{{n}}}}$ takes values. Then there is an exact sequence of semi-effective abelian groups and computable homomorphisms.]{}

The exactness itself ought to be well known and is nearly [@Crabb_James Proposition II.2.7].

The proof is postponed to Section \[sec:leftover\_proofs\]; until then, we only describe the maps in this sequence – these will be important in the proceeding. The middle homomorphisms are induced by the maps ${{j}}{\colon}{{L_{{n}}}}{\rightarrow}{{P_{{n}}}}$ and ${{p_{{n}}}}{\colon}{{P_{{n}}}}{\rightarrow}{{P_{{{n}}-1}}}$. The last homomorphism ${{k_{{{n}}*}}}$ sends $[\ell]\in[X,{{P_{{{n}}-1}}}]^A_B$ to $[{{k_{{n}}}}\ell-{{{{k_{{n}}}}{{o}}}}]\in[X,{{K_{{{n}}+1}}}]^A_B$. We remark that without subtracting ${{{{k_{{n}}}}{{o}}}}$, the result would not be an element of $[X,{{K_{{{n}}+1}}}]^A_B$, since ${{k_{{n}}}}\ell$ is in general not zero on $A$.

It remains to describe the connecting homomorphism $\partial$. Starting with a homotopy $h:{\Delta^{1}}\times X{\rightarrow}{{P_{{{n}}-1}}}$, we lift it to a homotopy $\widetilde h:{\Delta^{1}}\times X{\rightarrow}{{P_{{n}}}}$ in such a way that $({0}\times X)\cup({\Delta^{1}}\times A)$ is mapped to the zero section. This can be computed using Proposition \[prop:homotopy\_lifting\]. The restriction of $\widetilde h$ to ${1}\times X$ then represents $\partial[h]$.

Proof of Theorem \[thm:main\_theorem\] for pointed fibrations
-------------------------------------------------------------

\[sec:description\]

In addition to the assumptions of Theorem \[thm:main\_theorem\], we assume that ${{P_{{n}}}}\to B$ admits a zero section ${{o}}$ on which ${{f_{{n}}}}$ takes values.

Let us review the reductions made so far. By Theorem \[t:n\_equivalence\], it is enough to compute $[X,{{P_{{n}}}}]^A_B$ for ${{n}}=\dim X\leq 2{{d}}$. By Theorem \[t:semi\_eff\], it is a semi-effective abelian group. According to Theorem \[thm:exact\_sequence\], this group fits into an exact sequence with all the remaining terms fully effective either by Lemma \[l:fully\_eff\_cohlgy\] or by induction, since they concern diagonals into ${{P_{{{n}}-1}}}$. By Lemma \[l:ker\_coker\], the resulting short exact sequence $$\xymatrix{
0 \ar[r] & {\mathop\mathrm{coker}\nolimits}\partial \ar[r]_-{{{j_*}}} & [X,{{P_{{n}}}}]^A_B \ar[r]_-{{{p_{{{n}}*}}}} \POS[l]+R*{\vphantom{|}}="a";[]+L*{\vphantom{|}} \ar@<-5pt>@/_2pt/"a"_-r & \ker{{k_{{{n}}*}}}\ar[r] \POS[l]+R*{\vphantom{|}}="a";[]+L*{\vphantom{|}} \ar@<-5pt>@/_2pt/"a"_-\sigma & 0.
}$$ has both ${\mathop\mathrm{coker}\nolimits}\partial$ and $\ker{{k_{{{n}}*}}}$ also fully effective. In order to apply Lemma \[l:ses\], it thus suffices to construct the indicated set-theoretic sections $r$ and $\sigma$.

In the following, we will denote, for every space over $B$, the unique (fibrewise) map that takes values on the zero section by $o$ and call it the *zero map*. In particular, the zero of $[X,{{P_{{n}}}}]^A_B$ is the homotopy class of the zero map $o={{o}}g$.

Computing sections {#computing-sections .unnumbered}
------------------

The section $\sigma$ is defined on the level of representatives (on which it depends) by mapping a partial diagonal $\ell{\colon}X{\rightarrow}{{P_{{{n}}-1}}}$ to an arbitrary lift $\widetilde\ell{\colon}X{\rightarrow}{{P_{{n}}}}$ of $\ell$, zero on $A$. The computation of $\widetilde\ell$ is taken care of by Proposition \[prop:lift\_ext\_one\_stage\]; a lift exists by $\ker{{k_{{{n}}*}}}={\mathop\mathrm{im}\nolimits}{{p_{{{n}}*}}}$.

For the construction of the partial inverse $r$ on ${\mathop\mathrm{im}\nolimits}{{j_*}}=\ker{{p_{{{n}}*}}}$, let $\ell{\colon}X{\rightarrow}{{P_{{n}}}}$ be a diagonal such that its composition with ${{p_{{n}}}}{\colon}{{P_{{n}}}}{\rightarrow}{{P_{{{n}}-1}}}$ is homotopic to ${{o}}$. First suppose that we have computed such a nullhomotopy $h_{{{n}}-1}$, i.e. a homotopy from the zero diagonal ${{o}}$ to ${{p_{{n}}}}\ell$. Using Proposition \[prop:homotopy\_lifting\], we lift it along ${{p_{{n}}}}$ to a homotopy from some $\ell'$ to $\ell$. Since ${{p_{{n}}}}\ell'={{o}}$, the diagonal $\ell'$ in fact lands in ${\mathop\mathrm{fib}\nolimits}_{{o}}{{p_{{n}}}}\cong{{L_{{n}}}}$ and we may set $r([\ell])=[\ell']$.

Computing nullhomotopy {#computing-nullhomotopy .unnumbered}
----------------------

Thus, it remains to compute the nullhomotopy $h_{{{n}}-1}$ by induction on the height of the Moore–Postnikov tower. Let $\ell_{{i}}$ denote the projection of $\ell$ onto the ${{i}}$-th stage $P_{{i}}$ of the Moore–Postnikov tower. Suppose that we have computed a nullhomotopy $h_{{{i}}-1}$ of $\ell_{{{i}}-1}$ and lift it by Proposition \[prop:homotopy\_lifting\] to a homotopy $\widetilde h_{{{i}}-1}{\colon}\ell'_{{i}}\sim\ell_{{i}}$ from some map $\ell'_{{i}}$, whose image necessarily lies in ${\mathop\mathrm{fib}\nolimits}_{{o}}p_i$.

Since Proposition \[prop:homotopy\_concatenation\] provides algorithmic means for concatenating homotopies, it remains to construct a nullhomotopy $h'_{{i}}$ of $\ell'_{{i}}$. Consider the connecting homomorphism in for stages $P_{{{i}}-1}$ and $P_{{i}}$, i.e. $$\partial{\colon}[{\Delta^{1}}\times X,P_{{{i}}-1}]^{(\partial{\Delta^{1}}\times X)\cup({\Delta^{1}}\times A)}_B{\longrightarrow}[X,{{L_{{i}}}}]_B^A.$$ From the exactness of and from $\ell'_{{i}}\sim\ell_{{i}}\sim o$, it follows that $[\ell'_{{i}}]$ lies in the image of $\partial$. By computing generators of the domain of $\partial$ and their images, we obtain some $h_{{{i}}-1}^2$ with $\partial[h_{{{i}}-1}^2]=[\ell'_{{i}}]$.

We claim that $h'_{{i}}$ can then be computed as a diagonal in the following lifting-extension problem with the top map zero on $(0\times X)\cup({\Delta^{1}}\times A)$ and equal to $\ell'_{{i}}$ on $1\times X$: $$\xymatrix{
(\partial{\Delta^{1}}\times X)\cup({\Delta^{1}}\times A) \ar[r] \ar[d] & P_{{i}}\ar[d] \\
{\Delta^{1}}\times X \ar[r]_-{h_{{{i}}-1}^2} \ar@{-->}[ru]_-{h'_{{i}}} & P_{{{i}}-1}
}$$ Once we show the existence of such a lift, Proposition \[prop:lift\_ext\_one\_stage\] provides an algorithm for its computation and the proof is finished.

The existence of $\boldsymbol{h_{{i}}'}$ {#the-existence-of-boldsymbolh_i .unnumbered}
----------------------------------------

Let $\widetilde h_{{{i}}-1}^2$ be an arbitrary lift of $h_{{{i}}-1}^2$ that is zero on $(0\times X)\cup({\Delta^{1}}\times A)$. It ends at a diagonal $\ell''_{{i}}{\colon}X\to P_{{i}}$, which is homotopic in ${{L_{{i}}}}$ to $\ell'_{{i}}$, by the definition of the connecting homomorphism and by $\partial[h_{{{i}}-1}^2]=[\ell'_{{i}}]$. Let $h_{{i}}^0$ be this homotopy, say from $\ell''_{{i}}$ to $\ell'_{{i}}$. The homotopy $h_{{i}}'$ is obtained as a concatenation of $\widetilde h_{{{i}}-1}^2$ and $h_{{i}}^0$, using Proposition \[prop:homotopy\_concatenation\].

![image](lift)

It remains to specify the bottom map in the corresponding lifting-extension problem. Our choice is illustrated in the above picture (for $(X,A)=(*,\emptyset)$) – the projection of the hatched triangle is a degeneracy of $h_{{{i}}-1}^2$, namely the composition[^16] $${\Delta^{2}}\times X{\xrightarrow{s^1\times{\mathop\mathrm{id}\nolimits}}}{\Delta^{1}}\times X{\xrightarrow{h_{{{i}}-1}^2}}P_{{{i}}-1}.$$ This implies easily that $h_{{i}}'$ is indeed a lift of $h_{{{i}}-1}^2$.

Proof of Theorem \[thm:main\_theorem\]
--------------------------------------

\[s:main\_proof\]

Again, we need to compute $[X,{{P_{{n}}}}]^A_B$ for ${{n}}=\dim X\leq 2{{d}}$. This time however, we do not assume the existence of a zero section ${{o}}$. The proof is naturally split into two parts that also form an actual algorithm: finding an element of $[X,{{P_{{n}}}}]^A_B$ if it exists at all and computing this set when an element of it is specified. The second step is simpler since it reduces quickly to the previously considered pointed case.

Non-empty case {#non-empty-case .unnumbered}
--------------

First suppose that we have computed a diagonal $\ell_0{\colon}X\to{{P_{{n}}}}$. Consider the following lifting-extension problem, where ${{\widetilde\psi_{{n}}}}$ is obtained as a pullback of ${{\psi_{{n}}}}$ along $g$ (as in the square on the right). $$\xymatrix@C=30pt{
A \ar[r]^-{(\iota,{{f_{{n}}}})} \ar@{ >->}[d]_-\iota & X\times_B{{P_{{n}}}}\ar@{->>}[d]^-{{{\widetilde\psi_{{n}}}}} & & X\times_B{{P_{{n}}}}{{\save []+<{15pt},-{15pt}>="a";[]+<{15pt},0pt>;"a"**{}?({.5});"a"**\dir{-};[]+<0pt,-{15pt}>;"a"**{}?({.5});"a"**\dir{-}\restore}}\ar@{->>}[d]_-{{{\widetilde\psi_{{n}}}}} \ar[r] & {{P_{{n}}}}\ar@{->>}[d]^-{{{\psi_{{n}}}}} \\
X \ar[r]_-{\mathop\mathrm{id}\nolimits}\ar@{-->}[ru] & X & & X \ar[r]_-g & B
}$$ Its diagonals are of the form $({\mathop\mathrm{id}\nolimits},\ell)$ with $\ell{\colon}X\to{{P_{{n}}}}$ an arbitrary diagonal in the original problem and thus these problems are equivalent, $[X,{{P_{{n}}}}]_B^A\cong[X,X\times_B{{P_{{n}}}}]_X^A$.

Since the bottom map in the new problem is the identity, its solutions are *sections* of ${{\widetilde\psi_{{n}}}}{\colon}X\times_B{{P_{{n}}}}{\rightarrow}X$ that extend a given partial section $(\iota,{{f_{{n}}}})$ defined on $A$. The solution $({\mathop\mathrm{id}\nolimits},\ell_0)$, whose existence we assume, provides ${{\widetilde\psi_{{n}}}}$ with a zero section on which $(\iota,{{f_{{n}}}})$ takes values.

In order to employ the results of Section \[sec:description\], we need to show that ${{\widetilde\psi_{{n}}}}{\colon}X\times_B{{P_{{n}}}}\to X$ is a stage of a Moore–Postnikov tower composed of simplicial sets with effective homology. This follows from the argument of the proof of Theorem \[t:MP\_tower\], since $X\times_B{{P_{{n}}}}$ is obtained as an iterated pullback of Eilenberg–MacLane fibrations in exactly the same way as ${{P_{{n}}}}$. Thus, we obtain a fully effective abelian group structure on $[X,{{P_{{n}}}}]_B^A$ whose zero is $[\ell_0]$.

Finding an element {#finding-an-element .unnumbered}
------------------

It remains to decide whether a diagonal $\ell_0$ exists at all and, if this is the case, find one. This is also done by induction. Therefore, we assume that a diagonal $X\to{{P_{{{n}}-1}}}$ has been computed. By Section \[sec:description\], we are able to compute $[X,{{P_{{{n}}-1}}}]^A_B$ and we would like to decide whether there exists a partial diagonal $\ell{\colon}X\to{{P_{{{n}}-1}}}$ that admits a lift further to ${{P_{{n}}}}$, as indicated in the square on the left. $$\xymatrix@C=40pt{
A \ar[r]^-{{{f_{{n}}}}} \ar@{ >->}[d] & {{P_{{n}}}}{{\save []+<{15pt},-{15pt}>="a";[]+<{15pt},0pt>;"a"**{}?({.5});"a"**\dir{-};[]+<0pt,-{15pt}>;"a"**{}?({.5});"a"**\dir{-}\restore}}\ar[r]^-{{{q_{{n}}}}} \ar[d]_-{{p_{{n}}}}& {{E_{{n}}}}\ar[d]^\delta \\
X \ar@{-->}[ru] \ar[r]_-\ell & {{P_{{{n}}-1}}}\ar[r]_-{{k_{{n}}}}& {{K_{{{n}}+1}}}}$$ This lift exists precisely when there exists a diagonal in the composite square $$\xymatrix@C=40pt{
A \ar[r]^-{{{q_{{n}}}}{{f_{{n}}}}} \ar@{ >->}[d] & {{E_{{n}}}}\ar[d]^{\delta} \\
X \ar@{-->}[ru] \ar[r]_-{{{k_{{n}}}}\ell} & {{K_{{{n}}+1}}}}$$ Let $\widetilde c{\colon}X{\rightarrow}{{E_{{n}}}}$ be any extension of ${{q_{{n}}}}{{f_{{n}}}}$. According to the proof of Lemma \[l:lift\_ext\_one\_stage\], a diagonal exists if and only if the class $$[{{k_{{n}}}}\ell-\delta\widetilde c]\in[X,{{K_{{{n}}+1}}}]_B^A\cong H^{{{n}}+1}_G(X,A;{{\pi_{{n}}}})$$ is zero. By Theorem \[thm:exact\_sequence\], the induced map $${{k_{{{n}}*}}}{\colon}[X,{{P_{{{n}}-1}}}]^A_B{\rightarrow}[X,{{K_{{{n}}+1}}}]^A_B,\ [\ell]\mapsto [{{k_{{n}}}}\ell-{{{{k_{{n}}}}{{o}}}}]$$ is a group homomorphism. Clearly $[{{k_{{n}}}}\ell-\delta\widetilde c]$ is zero if and only if $[{{k_{{n}}}}\ell-{{{{k_{{n}}}}{{o}}}}]=[\delta\widetilde c-{{{{k_{{n}}}}{{o}}}}]$. Therefore, a diagonal $\ell$ liftable to ${{P_{{n}}}}$ exists if and only if the image of ${{k_{{{n}}*}}}$ contains $[\delta\widetilde c-{{{{k_{{n}}}}{{o}}}}]\in[X,{{K_{{{n}}+1}}}]^A_B$, a class independent of $\ell$. We are able to determine this image completely from our knowledge of (generators of) $[X,{{P_{{{n}}-1}}}]^A_B$. Moreover, if $[\delta\widetilde c-{{{{k_{{n}}}}{{o}}}}]$ lies in this image, we are able to compute an $\ell$ with $[{{k_{{n}}}}\ell-{{{{k_{{n}}}}{{o}}}}]=[\delta\widetilde c-{{{{k_{{n}}}}{{o}}}}]$ and use it for the construction of a diagonal: Let ${{k_{{n}}}}\ell-\delta\widetilde c=\delta c_0$, where $c_0$ is zero on $A$. The corresponding diagonal is then given by $(\ell,\widetilde c+c_0){\colon}X\to{{P_{{n}}}}\subseteq{{P_{{{n}}-1}}}\times{{E_{{n}}}}$.

Existence {#existence .unnumbered}
---------

When ${{n}}=2{{d}}+1$, Lemma \[l:lift\_ext\_one\_stage\] guarantees the existence of a diagonal $X\to{{P_{{n}}}}$ for *any* partial diagonal $X\to{{P_{{{n}}-1}}}$. Thus, it is enough to decide whether the stable $[X,{{P_{{{n}}-1}}}]^A_B$ is non-empty.

Proof of Theorem \[theorem:equivariant\]
----------------------------------------

We describe how the set of equivariant homotopy classes of maps $[X,Y]$ between two simplicial sets can be computed as a particular stable instance of the lifting-extension problem, namely $[X,Y]^\emptyset_{EG}$, so that Theorem \[thm:main\_theorem\] applies.

This instance is obtained by setting $B=EG$ where $EG$ is a non-commutative version of $E(\pi,0)$. It has as ${{n}}$-simplices sequences $(a_0,\ldots,a_{{n}})$ of elements $a_{{i}}\in G$, and its face and degeneracy operators are the maps $$\begin{aligned}
d_{{i}}(a_0,\ldots,a_{{n}}) & =(a_0,\ldots,a_{{{i}}-1},a_{{{i}}+1},\ldots,a_{{n}}) \\
s_{{i}}(a_0,\ldots,a_{{n}}) & =(a_0,\ldots,a_{{{i}}-1},a_{{i}},a_{{i}},a_{{{i}}+1},\ldots,a_{{n}}).\end{aligned}$$ There is an obvious diagonal action of $G$ which is clearly free.

As every $k$-simplex of $EG$ is uniquely determined by its (ordered) collection of vertices, it is clear that a simplicial map $g{\colon}X{\rightarrow}EG$ is uniquely determined by the mapping $g_0{\colon}X_0{\rightarrow}G$ of vertices and $g$ is equivariant if and only if $g_0$ is. A particular choice of a map $X\to EG$ is thus uniquely specified by sending the distinguished vertices of $X$ to $(e)$; it is clearly computable. Moreover, any two equivariant maps $X\to EG$ are (uniquely) equivariantly homotopic (vertices of ${\Delta^{1}}\times X$ are those of ${0}\times X$ and ${1}\times X$).

Factoring $Y\to EG$ as $Y{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{ >->}[r]^{\sim} & {}}}}Y'{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{->>}[r]^{} & {}}}}EG$ using Lemma \[l:fibrant\_replacement\], the geometric realization of $Y'$ equivariantly deforms onto that of $Y$. This shows that the first map in $$[X,Y]{\xrightarrow{\cong}}[X,Y']{\leftarrow}[X,Y']^\emptyset_{EG}$$ is a bijection and it remains to study the second map. As observed above, for every simplicial map $X\to Y'$, the lower triangle in $$\xymatrix@C=40pt{
\emptyset \ar[r] \ar[d] & Y' \ar@{->>}[d] \\
X \ar[r] \ar@{-->}[ur]^-\ell & EG
}$$ commutes up to homotopy. Since $Y'{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{->>}[r]^{} & {}}}}EG$ is a fibration, one may replace $\ell$ by a homotopic map for which it commutes strictly, showing surjectivity of $[X,Y']^\emptyset_{EG}\to[X,Y']$. The injectivity is implied by uniqueness of homotopies – every homotopy of maps $X\to Y'$ that are diagonals is automatically vertical.

It remains to show how to identify a given equivariant map $\ell{\colon}X\to Y$ as an element of the computed group $[X,{{P_{{n}}}}]^\emptyset_{EG}$. By its fully effective abelian group structure, it is enough to find the corresponding diagonal $X\to{{P_{{n}}}}$. As above, compute a homotopy $h$ from $\varphi\ell$ to $g{\colon}X\to EG$; then, using Proposition \[prop:homotopy\_lifting\], compute a lift of $h$ that fits into $$\xymatrix{
{0}\times X \ar[r]^-{\ell} \ar@{ >->}[d] & Y \ar[r]^-{{{\varphi_{{n}}}}} & {{P_{{n}}}}\ar@{->>}[d] \\
{\Delta^{1}}\times X \ar[rr]_-h \ar@{-->}[rru]^{\widetilde h} & & EG
}$$ The restriction of $\widetilde h$ to ${1}\times X$ is the required diagonal $X\to{{P_{{n}}}}$.

Weak [H-]{}spaces {#s:weak_H_spaces}
=================

In this section, we construct a weak fibrewise [H-]{}space structure on stable Moore–Postnikov stages with sections. This will culminate in the proof of Theorem \[t:semi\_eff\].

First, we explain a simple approach to constructing a *strict* fibrewise [H-]{}space structure, which we cannot make algorithmic, though. However, it introduces the ideas employed in the actual proof of Theorem \[t:semi\_eff\], and it also shows why a weakening of the [H-]{}space structure is needed.

We start with additional running assumptions.

\[con:fibrewise\] In addition to Convention \[con:G\_action\_loc\_eff\], all simplicial sets will be equipped with a map to $B$ and all maps, homotopies, etc. will be fibrewise, i.e. they will commute with the specified maps to $B$. In the case of homotopies, this means that they remain in one fibre the whole time or in other words that they are vertical.

Fibrewise [H-]{}spaces
----------------------

Let $\psi{\colon}P{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{->>}[r]^{} & {}}}}B$ be a given fibration with a section $o{\colon}B{\rightarrow}P$. We remind that the pullback $P\times_BP$ consists of pairs $(x,y)$ with $\psi(x)=\psi(y)$. Associating to $(x,y)$ this common value makes $P\times_BP$ into a space over $B$. We remind that a (fibrewise) *[H-]{}space structure* on $\varphi$ is a fibrewise map $${\mathop\mathrm{add}\nolimits}{\colon}P\times_BP{\rightarrow}P,$$ where we write ${\mathop\mathrm{add}\nolimits}(x,y)=x+y,$ that satisfies a single condition – the zero section $o$ should act as a zero for this addition, i.e. for $x\in P$ lying over $b=\psi(x)$ we have $o(b)+x=x=x+o(b)$. In the proceeding, we will abuse the notation slightly and write $o$ for any value of $o$, so that we rewrite the zero axiom as $o+x=x=x+o$. After all, there is a single value of $o$ for which this makes sense. It will be convenient to organize this structure into a commutative diagram $$\xymatrix@C=40pt{
P\vee_BP \ar[rd]^-\nabla \ar[d]_\vartheta \\
P\times_BP \ar[r]_-{\mathop\mathrm{add}\nolimits}& P
}$$ with $P\vee_BP$ the fibrewise wedge sum, $P\vee_BP=(B\times_BP)\cup(P\times_BB)$ (where $B\subseteq P$ is the image of the zero section), and with $\nabla$ denoting the fold map given by $(o,x)\mapsto x$ and $(x,o)\mapsto x$. As explained, all maps are fibrewise over $B$. Under this agreement, the above diagram is a *definition* of a (fibrewise) [H-]{}space structure.

We say that the [H-]{}space structure is *homotopy associative* if there exists a homotopy $(x+y)+z\sim x+(y+z)$ (i.e. formally a homotopy of maps $P\times_BP\times_BP\to P$) that is constant when restricted to $x=y=z=o$. *Homotopy commutativity* is defined similarly. Finally, it has a (right) *homotopy inverse* if there exists a map ${\mathop\mathrm{inv}\nolimits}{\colon}P\to P$, denoted $x\mapsto -x$, such that $-o=o$ and such that there exists a homotopy $x+(-x)\sim o$, constant when restricted to $x=o$.

We have already met an example of an [H-]{}space, namely ${{L_{{n}}}}=B\times K({{\pi_{{n}}}},{{n}})$ with the addition $(b,z)+(b,w)=(b,z+w)$. Not only it plays an important role in inductive considerations, it is also the most trivial case of an [H-]{}space structure on pointed stable Moore–Postnikov stages. In general, we have the following crucial theorem. The proof can be found in Section \[sec:existence\_of\_H\_space\_structures\_proof\].

\[t:existence\_of\_H\_space\_structures\] [Let $\varphi{\colon}Y\to B$ be a map whose homotopy fibre is $d$-connected, and let $n\leq 2d$. Then there exists a fibrewise [H-]{}space structure on the Moore–Postnikov stage ${{P_{{n}}}}$. Any such structure is homotopy associative, homotopy commutative and has a homotopy inverse.]{}

The importance of this result does not lie in the existence of an [H-]{}space structure but in its properties. After all, we will need to construct this structure and in this respect, the above existential result is not sufficient.

[H-]{}space structures on pullbacks
-----------------------------------

\[sec:non\_constr\_H\_space\]

We describe a general method for introducing [H-]{}space structures on pullbacks since ${{P_{{n}}}}$ is defined in this way. Let us start with a general description of our situation. We are given a pullback square $$\xymatrix@C=40pt{
P \ar[r] \ar[d] {{\save []+<{15pt},-{15pt}>="a";[]+<{15pt},0pt>;"a"**{}?({.5});"a"**\dir{-};[]+<0pt,-{15pt}>;"a"**{}?({.5});"a"**\dir{-}\restore}}& R \ar@{->>}[d]^-\psi \\
Q \ar[r]_-\chi & S
}$$ with $\psi$ a fibration. We assume that all of $Q$, $R$ and $S$ are fibrewise [H-]{}spaces over $B$, and that $R$ and $S$ are strictly associative and with a strict inverse. If both $\psi$ and $\chi$ preserved the addition strictly we could define addition on $P\subseteq Q\times R$ componentwise. In our situation, though, $\chi$ preserves the addition only up to homotopy and accordingly, the addition on $P$ will have to be perturbed to $$\label{eq:addition_on_pullback}
(x,y)+(x',y')=(x+x',y+y'+M(x,x')).$$ There are two conditions that need to be satisfied in order for this formula to be correct: $\psi M(x,x')=\chi(x+x')-(\chi(x)+\chi(x'))$ (so that the result lies in the pullback) and $M(x,o)=o=M(o,x)$ (to get an [H-]{}space). Both are summed up in the following lifting-extension problem $$\xymatrix@C=30pt{
P\vee_BP \ar[r]^-o \ar[d]_-\vartheta & R \ar@{->>}[d]^-\psi \\
P\times_BP \ar[r]_-m \ar@{-->}[ru]^-M & S
}$$ with $m(x,x')=\chi(x+x')-(\chi(x)+\chi(x'))$. In our situation, $\psi$ is $\delta{\colon}{{E_{{n}}}}\to{{K_{{{n}}+1}}}$. Thus, Lemma \[l:lift\_ext\_one\_stage\] would give us a solution if the pair $(P\times_BP,P\vee_BP)$ had effective homology.

However, we have not been able to prove this, and consequently, we cannot construct the addition on the pullback. In the computational world, we are thus forced to replace this pair by a certain homotopy version $(P{\mathbin{\widehat\times}}_BP,P{\mathbin{\widehat\vee}}_BP)$ of it that admits effective homology. This transition corresponds, as explained later, to the passage from [H-]{}spaces to a weakened notion, where the zero section serves as a zero for the addition only up to homotopy.

After this rather lengthy introduction, the plan for the rest of the section is to introduce weak [H-]{}spaces and then to describe the inductive construction of the weak [H-]{}space structure on pointed stable stages of Moore–Postnikov towers. We believe that to understand the weak version, it helps a lot to have in mind the above formula for addition on $P$.

Assuming that a right inverse exists in $Q$, $R$ and $S$, a right inverse in $P$ is given by the formula $$\label{eq:inverse_on_pullback}
-(x,y)=(-x,-y-M(x,-x)).$$

Weak [H-]{}spaces {#weak-h-spaces}
-----------------

\[s:hocolim\]

We will need a weak version of an [H-]{}space. Roughly speaking this is defined to be a fibrewise addition $x+y$ together with left zero and right zero homotopies $\lambda{\colon}x\sim o+x$ and $\rho{\colon}x\sim x+o$ that become homotopic as homotopies $o\sim o+o$. In simplicial sets a homotopy between homotopies can be defined in various ways. Here we will interpret it as a map $\eta{\colon}{\Delta^{2}}\times B{\rightarrow}P$ that is a constant homotopy on ${d}_2{\Delta^{2}}\times B$ and restricts to the two unit homotopies on ${d}_1{\Delta^{2}}\times B$ and ${d}_0{\Delta^{2}}\times B$, respectively. $$\xymatrix{
& o+o \POS[];[d]**{}?(.6)*{//{\scriptstyle\eta}//} \\
o \ar[rr]_{s_0o} \ar[ru]^{\lambda(o)} & & o \ar[lu]_{\rho(o)}
}$$

We will organize this data into a map ${\mathop\mathrm{add}\nolimits}{\colon}P{\mathbin{\widehat\times}}_BP\to P$ with similar properties to the strict [H-]{}space structure. The space $P{\mathbin{\widehat\times}}_BP$ will be a special case of the following construction which works for any commutative square (of spaces over $B$) $${\mathcal S}={}\quad{\xy *!C\xybox{\xymatrix{
Z \ar[r]^-{u_0} \ar[d]_-{u_1} & Z_0 \ar[d]^-{v_0} \\
Z_1 \ar[r]_-{v_1} & Z_2
}}\endxy}$$ that we denote for simplicity by ${\mathcal S}$. We define $$|{\mathcal S}|=\big({\Delta^{2}}\times Z\big)\cup\big({d}_1{\Delta^{2}}\times Z_0\big)\cup\big({d}_0{\Delta^{2}}\times Z_1\big)\cup\big(2\times Z_2\big)$$ together with the subspace $${d}_2|{\mathcal S}|=\big({d}_2{\Delta^{2}}\times Z\big)\cup\big(0\times Z_0\big)\cup\big(1\times Z_1\big),$$ where we assume for simplicity that all the maps in ${\mathcal S}$ are inclusions; otherwise, the union has to be replaced by a certain (obvious) colimit. In this case, $|{\mathcal S}|$ is naturally a subspace of ${\Delta^{2}}\times Z_2$ and as such admits an obvious map to ${\Delta^{2}}\times B$ whose fibres are equal to those of $Z$, $Z_0$, $Z_1$ or $Z_2$ (over $B$), depending on the point of ${\Delta^{2}}$. In the picture below, $B=\{*\}$ and $|{\mathcal S}|$ is thus depicted as a space over ${\Delta^{2}}$; here, $Z_2$ is a $3$-simplex, $Z_0$ and $Z_1$ its edges and $Z$ their common vertex.

![image](hocolim)

The construction $|{\mathcal S}|$ is a small model of a homotopy colimit of the square ${\mathcal S}$ with ${d}_2|{\mathcal S}|$ the corresponding small model for a homotopy pushout of $Z_0$ and $Z_1$ along $Z$.

The construction $|{\mathcal S}|$ possesses the following universal property: to give a map $f{\colon}|{\mathcal S}|{\rightarrow}Y$ is the same as to give maps $f_{{i}}{\colon}Z_{{i}}{\rightarrow}Y$ (for ${{i}}=0{{},\,}1{{},\,}2$), homotopies $h_{{i}}{\colon}f_{{i}}\sim f_2v_{{i}}$ (for ${{i}}=0{{},\,}1$) and a “second order homotopy” $H{\colon}{\Delta^{2}}\times Z{\rightarrow}Y$ whose restriction to ${d}_{{i}}{\Delta^{2}}\times Z$ equals $h_{{i}}u_{{i}}$ (for ${{i}}=0{{},\,}1$). Similarly, a map ${d}_2|{\mathcal S}|{\rightarrow}Y$ is specified by $f_0{\colon}Z_0\to Y$ and $f_1{\colon}Z_1\to Y$ as above and a homotopy ${d}_2{\Delta^{2}}\times Z$ from $f_0u_0$ to $f_1u_1$.

In order to apply this definition to weak [H-]{}spaces, we consider the square $${\mathcal S}_P={}\qquad{\xy *!C\xybox{\xymatrix{
B\times_BB \ar@{ >->}[r] & {\settowidth{\hlp}{$B\times_BP$}\makebox[\hlp][l]{${B\times_BP}{{}{\stackrel{\mathrm{def}}{=}}P_\mathrm{right}}$}} \ar@{ >->}[d] \\
{\settowidth{\hlp}{$P\times_BB$}\makebox[\hlp][r]{${P_\mathrm{left}{\stackrel{\mathrm{def}}{=}}{}}{P\times_BB}$}} \ar@{ >->}[r] \POS[]*+!!<0pt,\the\fontdimen22\textfont2>{\phantom{P\times_BB}}="a";[u]\ar@{ >->}"a" & P\times_BP
}}\endxy}$$ (the subspaces consist of pairs where one of the two components, or both, lie on the zero section). We will denote $B\times_BB$ for simplicity by $B$, to which it is canonically isomorphic.

Let $P\to B$ be a Kan fibration. We define simplicial sets $$P{\mathbin{\widehat\vee}}_BP\stackrel{\mathrm{def}}{=}{d}_2|{\mathcal S}_P|,\qquad P{\mathbin{\widehat\times}}_BP\stackrel{\mathrm{def}}{=}|{\mathcal S}_P|.$$ We denote the inclusion by $\vartheta{\colon}P{\mathbin{\widehat\vee}}_BP\to P{\mathbin{\widehat\times}}_BP$.

Furthermore, we define a “fold map” ${\mathop{\widehat\nabla}}{\colon}P{\mathbin{\widehat\vee}}_BP{\rightarrow}P$, prescribed as the identity map on $0\times P_\mathrm{right}$ and $1\times P_\mathrm{left}$ and as the constant homotopy at $o$ on ${d}_2{\Delta^{2}}\times B$.

We remark that $P{\mathbin{\widehat\vee}}_BP$ and $P{\mathbin{\widehat\times}}_BP$ are weakly homotopy equivalent to $P\vee_BP$ and $P\times_BP$, respectively; this is proved in Lemma \[l:whe\_weak\_strict\]. Now, we are ready to define weak [H-]{}spaces.

A *weak [H-]{}space structure* on $P$ is a (fibrewise) map ${\mathop\mathrm{add}\nolimits}{\colon}P{\mathbin{\widehat\times}}_BP\to P$ that fits into a commutative diagram $$\xymatrix@C=40pt{
P{\mathbin{\widehat\vee}}_BP \ar[rd]^-{\mathop{\widehat\nabla}}\ar[d]_\vartheta \\
P{\mathbin{\widehat\times}}_BP \ar[r]_-{\mathop\mathrm{add}\nolimits}& P
}$$ We denote the part of ${\mathop\mathrm{add}\nolimits}$ corresponding to $2\times(P\times_BP)$ by $x+y={\mathop\mathrm{add}\nolimits}(2,x,y)$, the part corresponding to ${d}_1{\Delta^{2}}\times P_\mathrm{right}$, i.e. the left zero homotopy, by $\lambda$, and the part corresponding to ${d}_0{\Delta^{2}}\times P_\mathrm{left}$, i.e. the right zero homotopy, by $\rho$.

Finally, we define a “diagonal” ${\mathop{\widehat\Delta}}{\colon}P{\rightarrow}P{\mathbin{\widehat\times}}_BP$ by $x\mapsto(2,x,x)$. All these associations are natural, making $P{\mathbin{\widehat\times}}_BP$ etc. into functors and ${\mathop{\widehat\nabla}}$ etc. into natural transformations.

\[p:effective\_homotopy\_colimits\] [Assume that all the spaces in the square ${\mathcal S}$ have effective homology. Then so does the pair $(|{\mathcal S}|,{d}_2|{\mathcal S}|)$.]{}

The proof is given in Section \[sec:effective\_homotopy\_colimits\]. The following special case will be crucial in constructing a weak [H-]{}space structure on stable stages of Moore–Postnikov towers with sections.

\[c:weak\_H\_space\_eff\_hlgy\] [Let ${{P_{{n}}}}$ be a Moore–Postnikov stage of a map $\varphi{\colon}Y\to B$ between simplicial sets with effective homology. Then it is possible to equip the pair $({{P_{{n}}}}{\mathbin{\widehat\times}}_B{{P_{{n}}}},{{P_{{n}}}}{\mathbin{\widehat\vee}}_B{{P_{{n}}}})$ with effective homology.]{}

As in Section \[s:main\_proof\], it is possible to equip ${{P_{{n}}}}\times_B{{P_{{n}}}}$ with effective homology as a pullback of a Moore–Postnikov stage. Thus, the result follows from the previous proposition.

Alternatively, we may compute ${{P_{{n}}}}\times_B{{P_{{n}}}}$ as a stage of the Moore–Postnikov tower for $Y'\times_BY'{\rightarrow}B$ (at the same time as we build the tower for $Y{\rightarrow}B$) with all the Eilenberg–MacLane spaces and Postnikov classes “squared”.

The following proposition will be used in Section \[sec:H\_space\_constr\] as a certificate for the existence of a weak [H-]{}space structure on ${{P_{{n}}}}$; namely, it will guarantee that all relevant obstructions vanish.

\[prop:weak\_H\_space\_connect\]

If the homotopy fibre of $\varphi{\colon}Y{\rightarrow}B$ is ${{d}}$-connected, then for any Moore–Postnikov stage ${{P_{{n}}}}$ the pair $({{P_{{n}}}}{\mathbin{\widehat\times}}_B{{P_{{n}}}},{{P_{{n}}}}{\mathbin{\widehat\vee}}_B{{P_{{n}}}})$ is $(2{{d}}+1)$-connected.

In particular, the cohomology groups $H^*_G({{P_{{n}}}}{\mathbin{\widehat\times}}_B{{P_{{n}}}},{{P_{{n}}}}{\mathbin{\widehat\vee}}_B{{P_{{n}}}};\pi)$ of this pair vanish up to dimension $2{{d}}+1$.

The proof can be found in Section \[sec:leftover\_proofs\].

Constructing weak [H-]{}spaces
------------------------------

\[sec:H\_space\_constr\]

Prime examples of weak [H-]{}spaces are the strict ones, and in particular every fibrewise simplicial group is a weak [H-]{}space. In the proceeding, we will make use of the trivial bundles ${{K_{{{n}}+1}}}=B\times K({{\pi_{{n}}}},{{n}}+1)$ and ${{E_{{n}}}}=B\times E({{\pi_{{n}}}},{{n}})$. Since ${{K_{{{n}}+1}}}$ is a fibrewise simplicial group, we have a whole family of weak [H-]{}space structures on ${{K_{{{n}}+1}}}$, one for each choice of a zero section $o{\colon}B{\rightarrow}{{K_{{{n}}+1}}}$. Namely, we define addition $z+_{o}w=z-o+w$ (the inverse then becomes $-_oz=-z+2o$). A similar formula defines an [H-]{}space structure on ${{E_{{n}}}}$ for every choice of its zero section. Unless stated otherwise, we use the real zero section $0$.

We are now ready to prove the following crucial proposition.

\[prop:weak\_H\_space\_structure\] If ${{n}}\leq 2{{d}}$ and ${{P_{{n}}}}$ is given a zero section ${{o}}$, it is possible to construct a structure of a weak [H-]{}space on ${{P_{{n}}}}$ with a strict right inverse.

Let ${{P_{{{n}}-1}}}$ be a Moore–Postnikov stage and ${{k_{{n}}}}{\colon}{{P_{{{n}}-1}}}{\rightarrow}{{K_{{{n}}+1}}}$ the respective (fibrewise) Postnikov invariant. There is a pullback square $$\label{eq:consecutive_stages}
\xy *!C\xybox{\xymatrix@C=40pt{
{{P_{{n}}}}\ar[r]^{{{q_{{n}}}}} \ar[d]_{{{p_{{n}}}}} {{\save []+<{15pt},-{15pt}>="a";[]+<{15pt},0pt>;"a"**{}?({.5});"a"**\dir{-};[]+<0pt,-{15pt}>;"a"**{}?({.5});"a"**\dir{-}\restore}}& {{E_{{n}}}}\ar[d]^\delta \\
{{P_{{{n}}-1}}}\ar[r]^{{k_{{n}}}}& {{K_{{{n}}+1}}}}}\endxy$$ of spaces over $B$. We denote the images of the zero section ${{o}}{\colon}B\to{{P_{{n}}}}$ by ${{o}}={{p_{{n}}}}{{o}}$ in ${{P_{{{n}}-1}}}$ and ${{q_{{n}}}}{{o}}$ in ${{E_{{n}}}}$ and use these sections as basepoints in the fibres over $B$. In this way ${{K_{{{n}}+1}}}$ is equipped with two sections, the zero section $0$ and the composition ${{{{k_{{n}}}}{{o}}}}$. We will see that the fact that these do not coincide in general causes some technical problems.

Assume inductively that there is given a structure of a weak [H-]{}space on ${{P_{{{n}}-1}}}$. $$\xymatrix@C=40pt{
{{P_{{{n}}-1}}}{\mathbin{\widehat\vee}}_B{{P_{{{n}}-1}}}\ar[rd]^-{\mathop{\widehat\nabla}}\ar[d]_\vartheta \\
{{P_{{{n}}-1}}}{\mathbin{\widehat\times}}_B{{P_{{{n}}-1}}}\ar[r]_-{\mathop\mathrm{add}\nolimits}& {{P_{{{n}}-1}}}}$$ We form the “non-additivity” map $m{\colon}{{P_{{{n}}-1}}}{\mathbin{\widehat\times}}_B {{P_{{{n}}-1}}}{\rightarrow}{{K_{{{n}}+1}}}$ as the difference of the following two compositions $$\xymatrix@=15pt{
& {{P_{{{n}}-1}}}{\mathbin{\widehat\times}}_B{{P_{{{n}}-1}}}\ar[ld]_{{\mathop\mathrm{add}\nolimits}} \ar[rd]^{{{k_{{n}}}}{\mathbin{\widehat\times}}{{k_{{n}}}}} & \\
{{P_{{{n}}-1}}}\ar[rd]_{{k_{{n}}}}& - & {\settowidth{\hlp}{${{K_{{{n}}+1}}}$}\makebox[\hlp][l]{${{{K_{{{n}}+1}}}}{{}{\mathbin{\widehat\times}}_B{{K_{{{n}}+1}}}}$}} \ar[ld]^{{\mathop\mathrm{add}\nolimits}_{{{{{k_{{n}}}}{{o}}}}}} \\
& {{K_{{{n}}+1}}}}$$ where ${\mathop\mathrm{add}\nolimits}_{{{{{k_{{n}}}}{{o}}}}}$ is the [H-]{}space structure on ${{K_{{{n}}+1}}}$ whose zero section is ${{{{k_{{n}}}}{{o}}}}$. We remind that it is given by $z+_{{{{{k_{{n}}}}{{o}}}}}w=z-{{{{k_{{n}}}}{{o}}}}+w$.

We will now construct a weak [H-]{}space structure on ${{P_{{n}}}}={{P_{{{n}}-1}}}\times_{{K_{{{n}}+1}}}{{E_{{n}}}}$ under our stability assumption ${{n}}\leq 2{{d}}$. The zero of this structure will be ${{o}}$. We compute a diagonal in $$\label{eq:lift_homotopy_additivity}
\xy *!C\xybox{\xymatrix@C=30pt{
{{P_{{{n}}-1}}}{\mathbin{\widehat\vee}}_B{{P_{{{n}}-1}}}\ar[r]^-0 \ar[d]_-\vartheta & {{E_{{n}}}}\ar[d]^-\delta \\
{{P_{{{n}}-1}}}{\mathbin{\widehat\times}}_B{{P_{{{n}}-1}}}\ar[r]_-m \ar@{-->}[ru]^-M & {{K_{{{n}}+1}}}}}\endxy$$ by Lemma \[l:lift\_ext\_one\_stage\], whose hypotheses are satisfied according to Corollary \[c:weak\_H\_space\_eff\_hlgy\] and Proposition \[prop:weak\_H\_space\_connect\]. The existence of $M$ says roughly that ${{k_{{n}}}}$ is additive up to homotopy. We define $$\mathop{{\mathop\mathrm{add}\nolimits}}{\colon}{{P_{{n}}}}{\mathbin{\widehat\times}}_B{{P_{{n}}}}{\longrightarrow}{{P_{{n}}}}={{P_{{{n}}-1}}}\times_{{K_{{{n}}+1}}}{{E_{{n}}}}$$ by its two components. The first is uniquely specified by the requirement that ${{p_{{n}}}}{\colon}{{P_{{n}}}}{\rightarrow}{{P_{{{n}}-1}}}$ is a homomorphism, i.e. by the commutativity of the square $$\xymatrix@C=30pt{
{{P_{{n}}}}{\mathbin{\widehat\times}}_B{{P_{{n}}}}\ar[r]^-{\mathop\mathrm{add}\nolimits}\ar[d]_-{{{p_{{n}}}}{\mathbin{\widehat\times}}{{p_{{n}}}}} & {{P_{{n}}}}\ar[d]^-{{{p_{{n}}}}} \\
{{P_{{{n}}-1}}}{\mathbin{\widehat\times}}_B{{P_{{{n}}-1}}}\ar[r]_-{\mathop\mathrm{add}\nolimits}& {{P_{{{n}}-1}}}}$$ The second component ${{q_{{n}}}}\mathop{{\mathop\mathrm{add}\nolimits}}$ is given as a sum $$\xymatrix@=15pt{
& {{P_{{n}}}}{\mathbin{\widehat\times}}_B{{P_{{n}}}}\ar[ld]_{{{q_{{n}}}}{\mathbin{\widehat\times}}{{q_{{n}}}}} \ar[rd]^{{{p_{{n}}}}{\mathbin{\widehat\times}}{{p_{{n}}}}} & \\
{\settowidth{\hlp}{${{E_{{n}}}}$}\makebox[\hlp][r]{${{{E_{{n}}}}{\mathbin{\widehat\times}}_B{}}{{{E_{{n}}}}}$}} \ar[rd]_{{\mathop\mathrm{add}\nolimits}_{{{q_{{n}}}}{{o}}}} & + & {\settowidth{\hlp}{${{P_{{{n}}-1}}}$}\makebox[\hlp][l]{${{{P_{{{n}}-1}}}}{{}{\mathbin{\widehat\times}}_B{{P_{{{n}}-1}}}}$}} \ar[ld]^M \\
& {{E_{{n}}}}\\
}$$ The last two diagrams are a “weak” version of the formula . A simple diagram chase shows that the two components are compatible and satisfy the condition of a weak [H-]{}space; details can be found in Lemma \[lem:calculations\].

We will also need a right inverse, which we denote by $\mathop{{\mathop\mathrm{inv}\nolimits}}{\colon}{{P_{{n}}}}{\rightarrow}{{P_{{n}}}}$, $x\mapsto -x$. We assume that ${\mathop\mathrm{inv}\nolimits}$ is constructed on ${{P_{{{n}}-1}}}$ in such a way that $x+(-x)={{o}}$. Then we define a right inverse on ${{P_{{n}}}}$ by the formula $$-(x,c)=(-x,-c+2{{q_{{n}}}}{{o}}-M(2,x,-x)).$$ Again, ${\mathop\mathrm{inv}\nolimits}$ is well defined and a right inverse for ${\mathop\mathrm{add}\nolimits}$; details can be found in Lemma \[lem:calculations\].

Structures induced by weak [H-]{}spaces {#sec:weak_H_space}
=======================================

In the case of a strict [H-]{}space $P\to B$, it is easy to define addition on $[X,P]^A_B$: simply put $[\ell_0]+[\ell_1]=[\ell_0+\ell_1]$. In particular, this defines addition on $[X,{{L_{{n}}}}]^A_B$ which, under the identification of $[X,{{L_{{n}}}}]^A_B$ with $H^{{n}}_G(X,A;{{\pi_{{n}}}})$, corresponds to the addition in the cohomology group.

It is technically much harder to equip $[X,P]^A_B$ with addition when the [H-]{}space structure on $P$ is weak. In this case, $\ell_0+\ell_1$ is not zero on $A$ and thus does not represent an element of $[X,P]^A_B$. This problem is solved in Section \[sec:strictness\]. Next, we will discuss the appropriate notion of a map between weak [H-]{}spaces and show how they induce group homomorphisms on homotopy classes. Finally, we will derive the exact sequence relating diagonals into two subsequent pointed stable stages of a Moore–Postnikov tower.

Strictification and addition of homotopy classes
------------------------------------------------

\[sec:strictness\]

The point of this subsection is to describe a perturbation of a weak [H-]{}space structure to one for which the zero is strict. We will then apply this to the construction of addition on $[X,{{P_{{n}}}}]^A_B$. Assume thus that we have a weak [H-]{}space structure $$\xymatrix@C=40pt{
P{\mathbin{\widehat\vee}}_BP \ar[d]_-\vartheta \ar[rd]^-{{\mathop{\widehat\nabla}}} \\
P{\mathbin{\widehat\times}}_BP \ar[r]_-{\mathop\mathrm{add}\nolimits}& P
}$$ Form the following lifting-extension problem where the top map is ${\mathop\mathrm{add}\nolimits}$ on $P{\mathbin{\widehat\times}}_BP$ and $\nabla{\mathop\mathrm{pr}\nolimits}_2$ on ${d}_2{\Delta^{2}}\times(P\vee_BP)$. Lemma \[l:whe\_weak\_strict\] shows that the map on the left is a weak homotopy equivalence and thus a diagonal exists (but in general not as a computable map). $$\xymatrix@C=50pt{
(P{\mathbin{\widehat\times}}_BP)\cup\big({d}_2{\Delta^{2}}\times(P\vee_BP)\big) \ar@{ >->}[d]_-\sim \ar[r]^-{[{\mathop\mathrm{add}\nolimits},\nabla{\mathop\mathrm{pr}\nolimits}_2]} & P \ar@{->>}[d] \\
{\Delta^{2}}\times(P\times_BP) \ar[r]  \ar@{-->}[ur] & B
}$$ The restriction of the diagonal to $0\times(P\times_BP)$ is then an [H-]{}space structure which we denote ${\mathop\mathrm{add'}\nolimits}$ with the corresponding addition ${\mathbin{+'}}$. The restriction to ${d}_1{\Delta^{2}}\times(P\times_BP)$ is a homotopy $x_0{\mathbin{+'}}x_1\sim x_0+x_1$.

Let $\varphi{\colon}P\to B$ be a weak [H-]{}space with addition ${\mathop\mathrm{add}\nolimits}$. Let ${\mathop\mathrm{add'}\nolimits}$ be its perturbation to a strict [H-]{}space structure as above. We define the addition in $[X,P]^A_B$ by $[\ell_0]+[\ell_1]=[\ell_0{\mathbin{+'}}\ell_1]$. Below, we prove that it is independent of the choice of a perturbation.

Composing the above homotopy with $\ell_0$ and $\ell_1$, we obtain $\ell_0{\mathbin{+'}}\ell_1\sim\ell_0+\ell_1$ whose restriction to $A$ is the left zero homotopy $\lambda(o){\colon}o=o{\mathbin{+'}}o\sim o+o$; again, we will be using $o$ to denote the unique map with values on the zero section. We will use this observation as a basis for the computation of the homotopy class of $\ell_0{\mathbin{+'}}\ell_1$, since we do not see a way of computing ${\mathop\mathrm{add'}\nolimits}$ directly – it seems to require certain pairs to have effective homology and we think that this might not be the case in general.

Restricting to the case $P={{P_{{n}}}}$ of Moore–Postnikov stages, the addition in $[X,{{P_{{n}}}}]^A_B$ is computed in the following algorithmic way. Let $\ell_0,\ell_1{\colon}X\to{{P_{{n}}}}$ and consider $\ell_0+\ell_1$ which is not zero on $A$ but rather takes values $o+o$. Extend the left zero homotopy $\lambda(o){\colon}o\sim o+o$ on $A$ to a homotopy $\sigma{\colon}\ell\sim\ell_0+\ell_1$ on $X$. It is quite easy to see that the resulting map $\ell$ is unique up to homotopy relative to $A$.[^17] Since $\ell_0{\mathbin{+'}}\ell_1$ is also obtained in this way, this procedure gives correctly $[\ell]=[\ell_0]+[\ell_1]\in[X,{{P_{{n}}}}]^A_B$. From the algorithmic point of view, this is well behaved – if $(X,A)$ is equipped with effective homology, we may extend homotopies by Proposition \[prop:homotopy\_lifting\]. This proves the first half of the following proposition.

\[prop:addition\_on\_homotopy\_classes\] If $(X,A)$ is equipped with effective homology and ${{P_{{n}}}}{\rightarrow}B$ is given a weak fibrewise [H-]{}space structure with zero section ${{o}}$, then there exists an algorithm that computes, for any two maps $\ell_0{{},\,}\ell_1{\colon}X{\rightarrow}{{P_{{n}}}}$, zero on $A$, a representative of $[\ell_0]+[\ell_1]$. If the weak [H-]{}space structure has a strict right inverse, then the computable $o+(-\ell)$ is a representative of $-[\ell]$.

The formula $\ell\mapsto{{o}}+(-\ell)$ prescribes a mapping $[X,{{P_{{n}}}}]^A_B{\rightarrow}[X,{{P_{{n}}}}]^A_B$ since ${{o}}+(-{{o}})={{o}}$. It is slightly more complicated to show that it is an inverse for our perturbed version of the addition. To this end, we have to exhibit a homotopy $${{o}}\sim\ell+({{o}}+(-\ell))$$ that on $A$ agrees with the left zero homotopy $\lambda({{o}})$. We start with the left zero homotopy $\lambda(-\ell){\colon}-\ell\sim{{o}}+(-\ell)$ and add $\ell$ to it on the left to obtain $\ell+\lambda(-\ell){\colon}{{o}}\sim\ell+({{o}}+(-\ell))$. By Lemma \[lem:commuting\_left\_zero\_homotopies\], its restriction ${{o}}+\lambda(-{{o}})$ to $A$ is homotopic to the left zero homotopy $\lambda({{o}}+(-{{o}}))=\lambda({{o}})$. Extending this second order homotopy from $A$ to $X$, we obtain a new homotopy ${{o}}\sim \ell+({{o}}+(-\ell))$ that agrees with the left zero homotopy on $A$ as desired.

\[lem:commuting\_left\_zero\_homotopies\] The homotopies $\lambda({{o}}+x),{{o}}+\lambda(x){\colon}{{o}}+x\sim {{o}}+({{o}}+x)$ are homotopic relative to $\partial{\Delta^{1}}\times{{P_{{n}}}}$.

We concatenate the two homotopies from the statement with the left zero homotopy $\lambda(x){\colon}x\sim {{o}}+x$. It is then enough to show that the two concatenations are homotopic. The homotopy between them is simply ${\Delta^{1}}\times{\Delta^{1}}\times{{P_{{n}}}}{\rightarrow}{{P_{{n}}}}$, $(s,t,x)\mapsto\lambda(s,\lambda(t,x))$.

This is a corollary of a collection of results obtained so far.

By Proposition \[prop:weak\_H\_space\_structure\], it is possible to construct on ${{P_{{n}}}}$ the structure of a weak [H-]{}space. By results of this subsection, it is possible to strictify this structure which makes ${{P_{{n}}}}$ into an [H-]{}space. According to Theorem \[t:existence\_of\_H\_space\_structures\], it is homotopy associative, homotopy commutative and with a right homotopy inverse; consequently, $[X,{{P_{{n}}}}]^A_B$ is an abelian group. By Proposition \[prop:addition\_on\_homotopy\_classes\], it is possible to compute the addition and the inverse in this group on the level of representatives, making it finally into a semi-effective abelian group.

[H-]{}maps
----------

\[sec:H-maps\] In this subsection, we assume that $\psi{\colon}P\to Q$ is a map between two weak [H-]{}spaces, that preserves the zero section, i.e. $\psi(o)=o$.[^18]

We say that $\psi$ is a *homomorphism*, if it preserves the whole structure strictly, i.e. when $$\xymatrix@C=30pt{
P{\mathbin{\widehat\times}}_BP \ar[r]^-{\mathop\mathrm{add}\nolimits}\ar[d]_-{\psi{\mathbin{\widehat\times}}\psi} & P \ar[d]^-\psi \\
Q{\mathbin{\widehat\times}}_BQ \ar[r]_-{\mathop\mathrm{add}\nolimits}& Q
}$$ commutes. This notion is too strict for our purposes, but still useful.

We say that $\psi$ is an *[H-]{}map* if there is specified a homotopy $$\alpha{\colon}\psi(x+y)\sim\psi(x)+\psi(y)$$ together with a second order homotopy $$\label{eq:second_order_homotopy}
{\xy *!C\xybox{\xymatrix{
\psi(o+o) \ar[rr]^-\alpha & & \psi(o)+\psi(o) \\
& \psi(o) \ar[lu]^-{\psi\lambda(o)} \ar[ru]_-{\lambda(o)} \POS[];[u]**{}?(.6)*{/////}
}}\endxy}$$ where $\lambda$ stands for the left zero homotopies. In this situation, the induced map $\psi_*{\colon}[X,P]^A_B{\rightarrow}[X,Q]^A_B$ is a group homomorphism for every pair $(X,A)$ over $B$. This is because the composition of homotopies $$\xymatrix{
\psi(x{\mathbin{+'}}y) \ar[r]^-{\psi\sigma} & \psi(x+y) \ar[r]^-\alpha & \psi(x)+\psi(y) & \psi(x){\mathbin{+'}}\psi(y) \ar[l]_-\sigma,
}$$ with $\sigma$ denoting the homotopies from the strictifications, restricts to $A$ to a homotopy that is homotopic to a constant homotopy via the above second order homotopy. Using the homotopy extension property, $\psi(x{\mathbin{+'}}y)\sim \psi(x){\mathbin{+'}}\psi(y)$ by a homotopy relative to $A$.

There is an obvious variation with $\alpha$ pointing the other way, i.e. $\alpha^{-1}{\colon}\psi(x)+\psi(y)\sim\psi(x+y)$. In the case that $Q\to B$ is a Kan fibration, this notion is equivalent to the previous one.

Proof of Theorem \[thm:exact\_sequence\]
----------------------------------------

First, we restate the theorem.

To start with, we have a fibration sequence of spaces over $B$ with sections, $$({{L_{{n}}}},0){\xrightarrow{\ {{j}}\ }}({{P_{{n}}}},{{o}}){\xrightarrow{\ {{p_{{n}}}}\ }}({{P_{{{n}}-1}}},{{o}}){\xrightarrow{\ {{k_{{n}}}}\ }}({{K_{{{n}}+1}}},{{{{k_{{n}}}}{{o}}}})$$ where the last two maps are those from the diagram  and ${{L_{{n}}}}=B\times K({{\pi_{{n}}}},{{n}})$ is identified with the (fibrewise) fibre of ${{p_{{n}}}}$, $${{j}}{\colon}{{L_{{n}}}}{\xrightarrow{\ \cong\ }}{\mathop\mathrm{fib}\nolimits}_{{o}}{{p_{{n}}}}\subseteq{{P_{{n}}}},\ z\mapsto{{o}}+z.$$ There is an isomorphism $({{K_{{{n}}+1}}},{{{{k_{{n}}}}{{o}}}})\cong({{K_{{{n}}+1}}},0)$ of fibrewise simplicial groups, given by $z\mapsto z-{{{{k_{{n}}}}{{o}}}}$.

This fibration sequence induces, for each pair $(X,A)$ over $B$, an exact sequence of pointed sets of homotopy classes of maps over $B$, $$[X,{{L_{{n}}}}]^A_B{\rightarrow}[X,{{P_{{n}}}}]^A_B{\rightarrow}[X,{{P_{{{n}}-1}}}]^A_B{\rightarrow}[X,{{K_{{{n}}+1}}}]^{A,{{{{k_{{n}}}}{{o}}}}}_B\cong[X,{{K_{{{n}}+1}}}]^A_B,$$ where the decoration “${{{{k_{{n}}}}{{o}}}}$” in $[X,{{K_{{{n}}+1}}}]^{A,{{{{k_{{n}}}}{{o}}}}}_B$ is used to distinguish it from $[X,{{K_{{{n}}+1}}}]^A_B$, where the zero section $0$ is used instead of ${{{{k_{{n}}}}{{o}}}}$. The base points of all terms are given by maps taking values on the respective zero sections.

It is possible to extend the sequence to the left by $[{\Delta^{1}}\times X,P]^{(\partial{\Delta^{1}}\times X)\cup({\Delta^{1}}\times A)}_B$ where ${\Delta^{1}}\times X$ is thought of as an object over $B$ via ${\Delta^{1}}\times X{\xrightarrow{{\mathop\mathrm{pr}\nolimits}}}X{\rightarrow}B$. First, we describe $$[{\Delta^{1}}\times X,{{P_{{{n}}-1}}}]^{(\partial{\Delta^{1}}\times X)\cup({\Delta^{1}}\times A)}_B{\rightarrow}[X,{{L_{{n}}}}]^A_B.$$ Let $h{\colon}{\Delta^{1}}\times X{\rightarrow}{{P_{{{n}}-1}}}$ be zero on the prescribed subspace. We choose a lift $\widetilde h$ of the homotopy $h$ along ${{p_{{n}}}}{\colon}{{P_{{n}}}}{\rightarrow}{{P_{{{n}}-1}}}$ which starts at the zero map and is zero on $A$ for the whole time (this can be carried out in an algorithmic way by Proposition \[prop:homotopy\_lifting\]). Restricting to the end of the homotopy prescribes a map $\widetilde h_\mathrm{end}{\colon}X{\rightarrow}{{P_{{n}}}}$ that lies over the zero section and may thus be viewed as a map $X{\rightarrow}{{L_{{n}}}}$.

The homotopy $\widetilde h$ shows that $\widetilde h_\mathrm{end}$, thought of as a map $X{\rightarrow}{{P_{{n}}}}$, is in fact nullhomotopic. The exactness is also easy – a nullhomotopy of $\ell{\colon}X{\rightarrow}{{L_{{n}}}}$ in ${{P_{{n}}}}$ projects down to ${{P_{{{n}}-1}}}$ to a map ${\Delta^{1}}\times X{\rightarrow}{{P_{{{n}}-1}}}$ that is zero on $(\partial{\Delta^{1}}\times X)\cup({\Delta^{1}}\times A)$. To summarize, what we have so far is an exact sequence of pointed sets $$[{\Delta^{1}}\times X,{{P_{{{n}}-1}}}]^{(\partial{\Delta^{1}}\times X)\cup({\Delta^{1}}\times A)}_B{\rightarrow}[X,{{L_{{n}}}}]^A_B{\rightarrow}[X,{{P_{{n}}}}]^A_B{\rightarrow}[X,{{P_{{{n}}-1}}}]^A_B{\rightarrow}[X,{{K_{{{n}}+1}}}]^A_B.$$

Our next aim will be to show that the maps in this sequence are homomorphisms of groups with respect to the group structures described in Section \[sec:strictness\]. According to Section \[sec:H-maps\] in order to show that ${{j_*}}$, ${{p_{{{n}}*}}}$ and ${{k_{{{n}}*}}}$ are homomorphisms of groups it is enough to exhibit, in each case, an additivity homotopy $\alpha$ together with a second order homotopy as in – in our case, the second order homotopy will always be degenerate.

The simplest case is ${{p_{{n}}}}{\colon}{{P_{{n}}}}\to{{P_{{{n}}-1}}}$, which is a homomorphism, so that $\alpha$ may be taken constant.

For ${{j}}{\colon}{{L_{{n}}}}{\rightarrow}{{P_{{n}}}}$, the additivity homotopy is simply the left zero homotopy since, according to the definition of addition on ${{P_{{n}}}}$, we have $${{o}}+z+w\sim{{o}}+({{o}}+z+w)=({{o}}+z)+({{o}}+w).$$

For ${{k_{{n}}}}{\colon}{{P_{{{n}}-1}}}{\rightarrow}{{K_{{{n}}+1}}}$, start with the map $M$ from the diagram  of Section \[sec:H\_space\_constr\] and restrict it to the part over ${d}_1{\Delta^{2}}$ to obtain $$({d}_1{\Delta^{2}}\times({{P_{{{n}}-1}}})_\mathrm{right})\cup(2\times({{P_{{{n}}-1}}}\times_B{{P_{{{n}}-1}}})){\xrightarrow{\ M'\ }}{{E_{{n}}}}.$$ Next, extend it to ${d}_1{\Delta^{2}}\times({{P_{{{n}}-1}}}\times_B{{P_{{{n}}-1}}})$ arbitrarily so that $0\times({{P_{{{n}}-1}}}\times_B{{P_{{{n}}-1}}})$ gets mapped to $0$. Then the additivity homotopy $\alpha^{-1}{\colon}{{k_{{n}}}}x+_{{{{{k_{{n}}}}{{o}}}}}{{k_{{n}}}}y\sim{{k_{{n}}}}(x+y)$ is given by $(t,x,y)\mapsto\delta M'(t,x,y)+{{k_{{n}}}}x+_{{{{{k_{{n}}}}{{o}}}}}{{k_{{n}}}}y$.

It remains to treat the connecting homomorphism $\partial$. If $h_0,h_1{\colon}{\Delta^{1}}\times X{\rightarrow}{{P_{{{n}}-1}}}$ represent two elements of the domain, then the lift of $h_0{\mathbin{+'}}h_1$ may be chosen to be the sum $\widetilde h_0{\mathbin{+'}}\widetilde h_1$ of the two lifts. Its restriction to the end of the homotopy is the sum of the two restrictions, $(\widetilde h_0{\mathbin{+'}}\widetilde h_1)_\mathrm{end}=(\widetilde h_0)_\mathrm{end}{\mathbin{+'}}(\widetilde h_1)_\mathrm{end}$.

Leftover proofs {#sec:leftover_proofs}
===============

The purpose of this section is to prove statements that were used in the main part but whose proofs would disturb the flow of the paper.

\[sec:MP\_tower\_proof\]

The proof will be presented in two parts. First, we describe the construction of the objects and then we will prove that they really constitute a Moore–Postnikov tower.

The construction itself follows ideas by E. H. Brown for non-equivariant simplicial sets in [@Brown] and by C. A. Robinson for topological spaces with free actions of a group in [@Robinson].

We described the construction in the non-equivariant non-fibrewise case $G=1$ and $B=*$ in detail in [@polypost]. Here, we will give a brief overview with the emphasis on the necessary changes for $G$ and $B$ non-trivial.

Construction {#construction .unnumbered}
------------

The first step of the construction is easy. Put $P_0=B$ and $\varphi_0=\varphi$. To proceed by induction, suppose that we have constructed ${{P_{{{n}}-1}}}$ and a map $\varphi_{{{n}}-1}{\colon}Y\to {{P_{{{n}}-1}}}$ with properties \[MP1\] and \[MP2\] from the definition of the Moore–Postnikov tower. Moreover, assume that ${{P_{{{n}}-1}}}$ is equipped with effective homology.

Viewing ${\mathop\mathrm{cone}\nolimits}\varphi_{({{n}}-1)*}$ as a perturbation of $C_*{{P_{{{n}}-1}}}\oplus C_*Y$, we obtain from strong equivalences $C_*{{P_{{{n}}-1}}}{\xLeftrightarrow{\ \ \ }}C_*^{\mathrm{ef}}{{P_{{{n}}-1}}}$ and $C_*Y{\xLeftrightarrow{\ \ \ }}C_*^{\mathrm{ef}}Y$ a strong equivalence ${\mathop\mathrm{cone}\nolimits}\varphi_{({{n}}-1)*}{\xLeftrightarrow{\ \ \ }}C_*^{\mathrm{ef}}$ with $C_*^{\mathrm{ef}}$ effective (for details, see [@polypost Proposition 3.8]). Let us consider the composition $$C_{{{n}}+1}^{\mathrm{ef}}{\rightarrow}Z_{{{n}}+1}(C_*^{\mathrm{ef}}){\rightarrow}H_{{{n}}+1}(C_*^{\mathrm{ef}}){\stackrel{\mathrm{def}}{=}}{{\pi_{{n}}}},$$ where the first map is an (equivariant) retraction of $Z_{{{n}}+1}(C_*^{\mathrm{ef}})\subseteq C_{{{n}}+1}^{\mathrm{ef}}$, computed by the algorithm of Proposition \[prop:projectivity\]. The second map is simply the projection onto the homology group. The homology group itself is computed from $C_*^{\mathrm{ef}}$ – by forgetting the action of $G$, it is a chain complex of finitely generated abelian groups and Smith normal form is available. The $G$-action on ${{\pi_{{n}}}}$ is easily computed from the $G$-action on $C_*^{\mathrm{ef}}$. Composing with the chain map ${\mathop\mathrm{cone}\nolimits}\varphi_{({{n}}-1)*}{\rightarrow}C_*^{\mathrm{ef}}$ coming from the strong equivalence, we obtain $$\kappa+\lambda{\colon}C_{{{n}}+1}{{P_{{{n}}-1}}}\oplus C_{{n}}Y=\big({\mathop\mathrm{cone}\nolimits}\varphi_{({{n}}-1)*}\big)_{{{n}}+1}{\rightarrow}C_{{{n}}+1}^{\mathrm{ef}}{\rightarrow}{{\pi_{{n}}}}$$ whose components are denoted $\kappa$ and $\lambda$. They correspond, respectively, to maps $${{k_{{n}}'}}{\colon}{{P_{{{n}}-1}}}{\rightarrow}K({{\pi_{{n}}}},{{n}}+1),\ l_{{n}}{\colon}Y{\rightarrow}E({{\pi_{{n}}}},{{n}})$$ that fit into a square $$\label{eq:postnikov_square}
{\xy *!C\xybox{\xymatrix{
Y \ar[r]^-{l_{{n}}} \ar[d]_-{\varphi_{{{n}}-1}} & E({{\pi_{{n}}}},{{n}}) \ar[d]^-\delta \\
{{P_{{{n}}-1}}}\ar[r]_-{{{k_{{n}}'}}} & K({{\pi_{{n}}}},{{n}}+1)
}}\endxy}$$ which commutes by the argument of [@polypost Section 4.3].

Now we can take ${{P_{{n}}}}={{P_{{{n}}-1}}}\times_{K({{\pi_{{n}}}},{{n}}+1)}E({{\pi_{{n}}}},{{n}})$ to be the pullback as in part \[MP3\] of the definition of the tower. By the commutativity of the square , we obtain a map ${{\varphi_{{n}}}}=(\varphi_{{{n}}-1},l_{{n}}){\colon}Y{\rightarrow}{{P_{{n}}}}$ as in $$\xymatrix@=10pt{
Y \ar@/^10pt/[drrr]^{l_{{n}}} \ar@/_10pt/[dddr]_{\varphi_{{{n}}-1}} \ar@{-->}[dr]^-{{{\varphi_{{n}}}}} \\
& {{P_{{n}}}}\ar[rr] \ar[dd]^{{{p_{{n}}}}} & & E({{\pi_{{n}}}},{{n}}) \ar[dd]^{\delta} \\
\\
& {{P_{{{n}}-1}}}\ar[rr]_-{{{k_{{n}}'}}} & & K({{\pi_{{n}}}},{{n}}+1)
}$$ which we will prove to satisfiy the remaining conditions for the ${{n}}$-th stage of a Moore–Postnikov tower.

First, however, we will equip ${{P_{{n}}}}$ with effective homology. To this end, observe that ${{P_{{n}}}}$ is isomorphic to the twisted cartesian product ${{P_{{{n}}-1}}}\times_{\tau}K({{\pi_{{n}}}},{{n}})$, see [@May:SimplicialObjects-1992 Proposition 18.7]. Since ${{P_{{{n}}-1}}}$ is equipped with effective homology by induction, and $K({{\pi_{{n}}}},{{n}})$ admits effective homology non-equivariantly by [@polypost Theorem 3.16], it follows from [@Filakovsky Corollary 12] (or [@polypost Proposition 3.10]) that ${{P_{{n}}}}$ can also be equipped with effective homology non-equivariantly. Since the $G$-action on ${{P_{{n}}}}$ is clearly free (any fixed point would get mapped by ${{\psi_{{n}}}}$ to a fixed point in $B$), Theorem \[t:vokrinek\] provides (equivariant) effective homology for ${{P_{{n}}}}$ (distinguished simplices of ${{P_{{n}}}}$ are pairs with the component in ${{P_{{{n}}-1}}}$ distinguished).

Correctness {#correctness .unnumbered}
-----------

From the exact sequence of homotopy groups associated with the fibration sequence $${{P_{{n}}}}{\rightarrow}{{P_{{{n}}-1}}}{\rightarrow}K({{\pi_{{n}}}},{{n}}+1)$$ and the properties \[MP1\] and \[MP2\] for ${{P_{{{n}}-1}}}$, we easily get that ${{P_{{n}}}}$ satisfies the condition \[MP2\] and that ${{\varphi_{{{n}}*}}}{\colon}\pi_{{i}}(Y)\to\pi_{{i}}({{P_{{n}}}})$ is an isomorphism for $0\le{{i}}\le{{n}}-1$.

The rest of the proof is derived, as in [@polypost Section 4.3], from the morphism of long exact sequences of homotopy groups $$\xymatrix@R=15pt@C=10pt{
& \pi_{{{n}}+1}(Y)\ar[r] \ar[d]^{{{\varphi_{{{n}}*}}}}& \pi_{{{n}}+1}({\mathop\mathrm{cyl}\nolimits}\varphi_{{{n}}-1})\ar[r] \ar[d]^{\cong} & \pi_{{{n}}+1}({\mathop\mathrm{cyl}\nolimits}\varphi_{{{n}}-1},Y) \ar[d]^{\cong} \ar[r] & {{\pi_{{n}}}}(Y) \ar[d]^{{{\varphi_{{{n}}*}}}} \ar[r] & {{\pi_{{n}}}}({\mathop\mathrm{cyl}\nolimits}\varphi_{{{n}}-1}) \ar[d]^{\cong} \ar[r] & 0 \\
0 \ar[r] & \pi_{{{n}}+1}({{P_{{n}}}})\ar[r] & \pi_{{{n}}+1}({\mathop\mathrm{cyl}\nolimits}{{p_{{n}}}}) \ar[r] & \pi_{{{n}}+1}({\mathop\mathrm{cyl}\nolimits}{{p_{{n}}}},{{P_{{n}}}}) \ar[r] & {{\pi_{{n}}}}({{P_{{n}}}}) \ar[r] & {{\pi_{{n}}}}({\mathop\mathrm{cyl}\nolimits}{{p_{{n}}}})
}$$ associated with pairs $({\mathop\mathrm{cyl}\nolimits}\varphi_{{{n}}-1},Y)$ and $({\mathop\mathrm{cyl}\nolimits}{{p_{{n}}}},{{P_{{n}}}})$. The arrow in the middle is an isomorphism by [@polypost Lemma 4.5], while the remaining two isomorphisms are consequences of the fact that both cylinders deform onto the same base ${{P_{{{n}}-1}}}$. The zero on the left follows from the fact that the fibre of ${{p_{{n}}}}$ is $K({{\pi_{{n}}}},{{n}})$ and the zero on the right comes from the condition \[MP1\] for ${{P_{{{n}}-1}}}$. By the five lemma, ${{\varphi_{{{n}}*}}}$ is an isomorphism on ${{\pi_{{n}}}}$ and an epimorphism on $\pi_{{{n}}+1}$ which completes the proof of condition \[MP1\].

For the next proof, we will use the following observation.

\[l:fibrant\_replacement\] Every map $\psi{\colon}Q\to P$ can be factored as $\psi{\colon}Q{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{ >->}[r]^{j} & {}}}}Q'{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{->>}[r]^{\psi'} & {}}}}P$, where $j$ is a weak homotopy equivalence and $\psi'$ is a Kan fibration.

By a *weak homotopy equivalence*, we will understand a map whose geometric realization is a $G$-homotopy equivalence.

This is the small object argument (see e.g. [@Hirschhorn Section 10.5] or [@DwyerSpalinski Section 7.12]) applied to the collection ${\mathcal J}$ of “$G$-free horn inclusions” $G\times{\mbox{$\xy
<0pt,-\the\fontdimen22\textfont2>;p+<.1em,0em>:
{\ar@{-}(0,0.1);(3,7)},
{\ar@{-}(3,7);(6,0.1)},
{\ar@{-}(3.2,7);(6.2,0.1)},
{\ar@{-}(3.4,7);(6.4,0.1)}
\endxy\;\!{}^{{{n}}}_{{{i}}}$}}\to G\times{\Delta^{{{n}}}}$, ${{n}}\geq1$, $0\leq{{i}}\leq{{n}}$. Using the terminology of [@Hirschhorn], the ${\mathcal J}$-injectives are exactly those maps that have non-equivariantly the right lifting property with respect to ${\mbox{$\xy
<0pt,-\the\fontdimen22\textfont2>;p+<.1em,0em>:
{\ar@{-}(0,0.1);(3,7)},
{\ar@{-}(3,7);(6,0.1)},
{\ar@{-}(3.2,7);(6.2,0.1)},
{\ar@{-}(3.4,7);(6.4,0.1)}
\endxy\;\!{}^{{{n}}}_{{{i}}}$}}\to {\Delta^{{{n}}}}$ (this follows from the equivalence from the next proof), i.e. Kan fibrations. The geometric realization of every relative ${\mathcal J}$-cell complex is a $G$-homotopy equivalence since the geometric realization of $G\times{\Delta^{{{n}}}}$ clearly deforms onto that of $G\times{\mbox{$\xy
<0pt,-\the\fontdimen22\textfont2>;p+<.1em,0em>:
{\ar@{-}(0,0.1);(3,7)},
{\ar@{-}(3,7);(6,0.1)},
{\ar@{-}(3.2,7);(6.2,0.1)},
{\ar@{-}(3.4,7);(6.4,0.1)}
\endxy\;\!{}^{{{n}}}_{{{i}}}$}}$.

\[sec:n\_equivalence\_proof\]

By construction, ${{\varphi_{{n}}}}{\colon}Y\to {{P_{{n}}}}$ is an $({{n}}+1)$-equivalence. By the proof of Lemma \[l:fibrant\_replacement\], we may assume $Y\to Y'$ to be a relative ${\mathcal J}$-cell complex. We will show that ${{\varphi_{{n}}}}$ factors through $Y'$. Given that this is true for ${{P_{{{n}}-1}}}$, we form the square $$\xymatrix@C=40pt{
Y \ar[r]^-{{{\varphi_{{n}}}}} \ar@{ >->}[d]_-\sim & {{P_{{n}}}}\ar@{->>}[d]^{{p_{{n}}}}\\
Y' \ar[r]_-{\varphi_{{{n}}-1}'} \ar@{-->}[ur]^-{{{\varphi_{{n}}'}}} & {{P_{{{n}}-1}}}}$$ in which a diagonal exists by the fact that $Y\to Y'$ is a relative ${\mathcal J}$-cell complex and such maps have the left lifting property with respect to Kan fibrations.

The map ${{\varphi_{{n}}'}}$ is also an $({{n}}+1)$-equivalence. We will prove more generally that $$\psi_*{\colon}[X,Q]^A_B\to[X,P]^A_B$$ is an isomorphism for any $({{n}}+1)$-equivalence $\psi{\colon}Q\to P$.

The basic idea is that $X$ is built from $A$ by consecutively attaching “cells with a free action of $G$”, namely $X=\cup X_{{i}}$ and in each step $X_{{i}}=X_{{{i}}-1}\cup_{G\times\partial{\Delta^{{{m}}_{{i}}}}}G\times{\Delta^{{{m}}_{{i}}}}$ with ${{m}}_{{i}}\leq{{n}}$.[^19]

First, we prove that $\psi_*$ is surjective under the assumption that $\psi$ is an ${{n}}$-equivalence. For convenience, we replace $\psi$ by a $G$-homotopy equivalent Kan fibration using Lemma \[l:fibrant\_replacement\]. Suppose that $\psi_*$ is surjective with $X$ replaced by $X_{{{i}}-1}$ and we prove the same for $X_{{i}}$. This is clearly implied by the solvability of the following lifting-extension problem $$\xymatrix@C=40pt{
X_{{{i}}-1} \ar[r] \ar@{ >->}[d] & Q \ar@{->>}[d]^-\psi \\
X_{{i}}\ar[r]_-{\ell} \ar@{-->}[ru] & P
}$$ (to find a preimage of $[\ell]$ at the bottom, we find the top map by the inductive hypothesis; if the lift exists, it gives a preimage of $[\ell]$ as required). As $X_{{i}}$ is obtained from $X_{{{i}}-1}$ by attaching a single cell, the problem is equivalent to $$\label{eq:horn-injectivity}
\xy *!C\xybox{\xymatrix@C=30pt{
G\times\partial{\Delta^{{{m}}_{{i}}}} \ar[r] \ar@{ >->}[d] & Q \ar@{->>}[d]^-\psi \ar@{}[drrr]|-{\parbox{\widthof{that is further}}{that is further equivalent to}} & & & \partial{\Delta^{{{m}}_{{i}}}} \ar[r] \ar@{ >->}[d] & Q \ar@{->>}[d]^-\psi \\
G\times{\Delta^{{{m}}_{{i}}}} \ar[r] \ar@{-->}[ru] & P & & & {\Delta^{{{m}}_{{i}}}} \ar[r] \ar@{-->}[ru] & P
}}\endxy$$ where the problem on the right is obtained from the left by restricting to $e\times{\Delta^{{{m}}_{{i}}}}$ and is non-equivariant. Its solution is guaranteed by $\psi$ being an ${{m}}_{{i}}$-equivalence.

To prove the injectivity of $\psi_*$, we put back the assumption of $\psi$ being an $({{n}}+1)$-equivalence. We study the preimages of $[\ell]\in[X,P]^A_B$ under $\psi_*$; these clearly form $[X,Q]^A_P$. By the surjectivity part, this set is non-empty. By pulling back along $\ell$, we thus obtain a fibration $\ell^*Q\to X$ with a section $X\to\ell^*Q$ which is an ${{n}}$-equivalence.[^20] Thus, $$[X,Q]^A_P\cong[X,\ell^*Q]^A_X{\xleftarrow{\ \cong\ }}[X,X]^A_X=*$$ by the surjectivity part (any surjection from a one-element set is a bijection).

Next, we need the following lemma.

\[l:whe\_weak\_strict\] The natural maps $P{\mathbin{\widehat\vee}}_BP{\rightarrow}P\vee_BP$ and $P{\mathbin{\widehat\times}}_BP{\rightarrow}P\times_BP$ are weak homotopy equivalences.

The inclusion $(P{\mathbin{\widehat\times}}_BP)\cup\big({d}_2{\Delta^{2}}\times(P\vee_BP)\big){\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{ >->}[r]^{} & {}}}}{\Delta^{2}}\times(P\times_BP)$ is a weak homotopy equivalence.

The space $P{\mathbin{\widehat\vee}}_BP$ is naturally a subspace of ${d}_2{\Delta^{2}}\times(P\vee_BP)$ and it is enough to show that it is in fact a deformation retract. A continuous deformation is obtained from a deformation of ${d}_2{\Delta^{2}}\times P_\mathrm{right}$ onto $(0\times P_\mathrm{right})\cup({d}_2{\Delta^{2}}\times B)$ and a symmetric deformation of ${d}_2{\Delta^{2}}\times P_\mathrm{left}$ onto $(1\times P_\mathrm{left})\cup({d}_2{\Delta^{2}}\times B)$.

To prove the remaining claims, consider the deformation of ${\Delta^{2}}\times(P\times_BP)$ onto $2\times(P\times_BP)$, given by deforming ${\Delta^{2}}$ linearly onto $2$ and by a constant homotopy on the second component $P\times_BP$. By an easy inspection, it restricts to a deformation of $P{\mathbin{\widehat\times}}_BP$ onto $2\times(P\times_BP)$, giving the second claim.

Since both ${\Delta^{2}}\times(P\times_BP)$, $P{\mathbin{\widehat\times}}_BP$ deform onto the same $2\times(P\times_BP)$, it is enough for the last claim to find a deformation of $$(P{\mathbin{\widehat\times}}_BP)\cup\big({d}_2{\Delta^{2}}\times(P\vee_BP)\big)$$ onto $P{\mathbin{\widehat\times}}_BP$. This is provided by the deformation of ${d}_2{\Delta^{2}}\times(P\vee_BP)$ onto $P{\mathbin{\widehat\vee}}_BP$ (the intersection of the two spaces in the union above) from the first paragraph.

Now we are ready to prove the following proposition.

By the first part of the previous lemma, we may replace the pair in the statement by $({{P_{{n}}}}\times_B{{P_{{n}}}},{{P_{{n}}}}\vee_B{{P_{{n}}}})$.

First, we recall that ${{P_{{n}}}}{\rightarrow}B$ is a minimal fibration (each $\delta{\colon}E(\pi_{{i}},{{i}}){\rightarrow}K(\pi_{{i}},{{i}}+1)$ is one and the class of minimal fibrations is closed under pullbacks and compositions, see [@May:SimplicialObjects-1992]). It is well known that over each simplex $\sigma{\colon}{\Delta^{{{i}}}}{\rightarrow}B$ any minimal fibration is trivial and it is easy to modify this to an isomorphism $\sigma^*{{P_{{n}}}}\cong{\Delta^{{{i}}}}\times F$ of fibrations with sections[^21]. Here, $F$ denotes the fibre of ${{P_{{n}}}}{\rightarrow}B$ and is ${{d}}$-connected by the assumptions. Consequently, ${{P_{{n}}}}\vee_B{{P_{{n}}}}$ is a fibre bundle with fibre $F\vee F$. Thus, we have a map of fibre sequences $$\xymatrix{
F\vee F \ar[r] \ar[d] & {{P_{{n}}}}\vee_B{{P_{{n}}}}\ar[r] \ar[d] & B \ar@{=}[d] \\
F\times F \ar[r] & {{P_{{n}}}}\times_B{{P_{{n}}}}\ar[r] & B
}$$ The left map is $(2{{d}}+1)$-connected. By the five lemma applied to the long exact sequences of homotopy groups, the middle map ${{P_{{n}}}}\vee_B{{P_{{n}}}}{\rightarrow}{{P_{{n}}}}\times_B{{P_{{n}}}}$ is also $(2{{d}}+1)$-connected.

To show that the equivariant cohomology group vanishes, we will make use of a contraction of $C_*({{P_{{n}}}}{\mathbin{\widehat\times}}_B{{P_{{n}}}})$ onto $C_*({{P_{{n}}}}{\mathbin{\widehat\vee}}_B{{P_{{n}}}})$ in dimensions $\leq2{{d}}+1$; its existence follows from the proof of Proposition \[prop:projectivity\]. By the additivity of $\operatorname{Hom}_{{{{\mathbb Z}G}}}(-,\pi)$, there is an induced contraction of $C^*_G({{P_{{n}}}}{\mathbin{\widehat\times}}_B{{P_{{n}}}};\pi)$ onto $C^*_G({{P_{{n}}}}{\mathbin{\widehat\vee}}_B{{P_{{n}}}};\pi)$ and thus the relative cochain complex is acyclic.

\[sec:existence\_of\_H\_space\_structures\_proof\]

By the previous proposition, the left vertical map in $$\xymatrix@C=40pt{
{{P_{{n}}}}\vee_B{{P_{{n}}}}\ar[r]^-\nabla \ar@{ >->}[d]_\vartheta & {{P_{{n}}}}\ar@{->>}[d]^-{{{\psi_{{n}}}}} \\
{{P_{{n}}}}\times_B{{P_{{n}}}}\ar[r] \ar@{-->}[ru]_-{\mathop\mathrm{add}\nolimits}& B
}$$ is $(2{{d}}+1)$-connected. Since the homotopy groups of the fibre of ${{\psi_{{n}}}}$ are concentrated in dimensions ${{d}}\leq{{i}}\leq{{n}}$, the relevant obstructions (they can be extracted from the proof of Proposition \[prop:lift\_ext\_one\_stage\]) for the existence of the diagonal lie in $$H^{{{i}}+1}_G({{P_{{n}}}}\times_B{{P_{{n}}}},{{P_{{n}}}}\vee_B{{P_{{n}}}})=0$$ (since $i+1\leq{{n}}+1\leq 2{{d}}+1$). The diagonal is unique up to homotopy by the very same computation. Thus, in particular, replacing ${\mathop\mathrm{add}\nolimits}$ by the opposite addition ${\mathop\mathrm{add}\nolimits}^{\mathrm{op}}{\colon}(x,y)\mapsto y+x$ yields a homotopic map, proving homotopy commutativity. Similarly, homotopy associativity follows from the uniqueness of a diagonal in $$\xymatrix@C=40pt{
(B\times_B{{P_{{n}}}}\times_B{{P_{{n}}}})\cup({{P_{{n}}}}\times_B{{P_{{n}}}}\times_BB) \ar[r] \ar@{ >->}[d] & {{P_{{n}}}}\ar@{->>}[d]^-{{{\psi_{{n}}}}} \\
{{P_{{n}}}}\times_B{{P_{{n}}}}\times_B{{P_{{n}}}}\ar[r] \ar@{-->}[ru] & B
}$$ (the pair on the left is again $(2{{d}}+1)$-connected) with two diagonals specified by mapping $(x,y,z)$ to $(x+y)+z$ and $x+(y+z)$.

The existence of a homotopy inverse is a fibrewise and equivariant version of [@Stasheff Theorem 3.4]; the proof applies without any complications when the action of $G$ is free. We will not provide more details since we construct the inverse directly in Section \[sec:H\_space\_constr\].

For the next proof, we will use a general lemma about filtered chain complexes. Let $C_*$ be a chain complex equipped with a filtration $$0 = F_{-1}C_* \subseteq F_0C_* \subseteq F_1C_* \subseteq \cdots$$ such that $C_* = \bigcup_i F_iC_* $. As usual, we assume that each $F_iC_*$ is a cellular subcomplex, i.e. generated by a subset of the given basis of $C_*$. We assume that this filtration is *locally finite*, i.e. for each $n$, we have $C_n = F_iC_n$ for some $i \geq 0$. For the relative version, let $D_*$ be a (cellular) subcomplex of $C_*$ and define $F_iD_* = D_* \cap F_iC_*$.

\[l:filt\] Under the above assumptions, if each filtration quotient $G_iC_* = F_iC_*/F_{i-1}C_*$ has effective homology then so does $C_*$. More generally, if each $(G_iC_*,G_iD_*)$ has effective homology then so does $(C_*,D_*)$.

We define $G_* = \bigoplus_{i \geq 0} G_iC_*$, the associated graded chain complex. Then $C_*$ is obtained from $G_*$ via a perturbation that decreases the filtration degree $i$. Taking a direct sum of the given strong equivalences $G_iC_* {\xLeftarrow{\ \ }}\widehat G_iC_* {\xRightarrow{\ \ }}G_i^{\mathrm{ef}}C_*$, we obtain a strong equivalence $G_* {\xLeftarrow{\ \ }}\widehat G_* {\xRightarrow{\ \ }}G_*^{\mathrm{ef}}$ with all the involved chain complexes equipped with a “filtration” degree. Since the perturbation on $G_*$ decreases this degree, while the homotopy operator preserves it, we may apply the perturbation lemmas, Propositions \[p:epl\] and \[p:bpl\], to obtain a strong equivalence $C_* {\xLeftarrow{\ \ }}\widehat C_* {\xRightarrow{\ \ }}C_*^{\mathrm{ef}}$.

\[sec:effective\_homotopy\_colimits\]

We continue the notation of Section \[s:hocolim\].

We apply Lemma \[l:filt\] to the natural filtration $F_iC_*|{\mathcal S}| = C_*{\mathop\mathrm{sk}\nolimits}_i|{\mathcal S}|$, where ${\mathop\mathrm{sk}\nolimits}_i|{\mathcal S}|$ is the preimage of the $i$-skeleton ${\mathop\mathrm{sk}\nolimits}_i{\Delta^{2}}$ under the natural projection $|{\mathcal S}| \to {\Delta^{2}}$. The Eilenberg–Zilber reduction applies to the quotient $$C_*{\mathop\mathrm{sk}\nolimits}_2|{\mathcal S}|/C_*{\mathop\mathrm{sk}\nolimits}_1|{\mathcal S}| \cong C_*({\Delta^{2}} \times Z, \partial{\Delta^{2}} \times Z) {\xRightarrow{\ \ }}C_*({\Delta^{2}},\partial{\Delta^{2}}) \otimes C_*Z \cong s^2C_*Z$$ where $s$ denotes the suspension. The effective homology of $Z$ provides a further strong equivalence with $s^2C_*^{\mathrm{ef}}Z$. Similarly, $C_*{\mathop\mathrm{sk}\nolimits}_1|{\mathcal S}|/C_*{\mathop\mathrm{sk}\nolimits}_0|{\mathcal S}|$ is isomorphic to $$C_*(({d}_2{\Delta^{2}},\partial{d}_2{\Delta^{2}}) \times Z) \oplus C_*(({d}_1{\Delta^{2}},\partial{d}_1{\Delta^{2}}) \times Z_0) \oplus C_*(({d}_0{\Delta^{2}},\partial{d}_0{\Delta^{2}}) \times Z_1)$$ and thus strongly equivalent to $sC_*^{\mathrm{ef}}Z \oplus sC_*^{\mathrm{ef}}Z_0 \oplus sC_*^{\mathrm{ef}}Z_1$. Finally, $C_*{\mathop\mathrm{sk}\nolimits}_0|{\mathcal S}|$ is strongly equivalent to $C_*^{\mathrm{ef}}Z_0 \oplus C_*^{\mathrm{ef}}Z_1 \oplus C_*^{\mathrm{ef}}Z_2$.

The subcomplexes corresponding to ${d}_2|{\mathcal S}|$ are formed by some of the direct summands above and are thus preserved by all the involved strong equivalences. This finishes the verification of the assumptions of Lemma \[l:filt\].

\[lem:calculations\] The two components ${{q_{{n}}}}\mathop{{\mathop\mathrm{add}\nolimits}}$ and ${{p_{{n}}}}\mathop{{\mathop\mathrm{add}\nolimits}}$ defined in Section \[sec:H\_space\_constr\] determine a map $\mathop{{\mathop\mathrm{add}\nolimits}}{\colon}{{P_{{n}}}}{\mathbin{\widehat\times}}_B{{P_{{n}}}}{\rightarrow}{{P_{{n}}}}$ and this map is a weak [H-]{}space structure.

The two components ${{q_{{n}}}}\mathop{{\mathop\mathrm{inv}\nolimits}}$ and ${{p_{{n}}}}\mathop{{\mathop\mathrm{inv}\nolimits}}$ defined in Section \[sec:H\_space\_constr\] determine a map $\mathop{{\mathop\mathrm{inv}\nolimits}}{\colon}{{P_{{n}}}}{\rightarrow}{{P_{{n}}}}$ and this map is a right inverse for ${\mathop\mathrm{add}\nolimits}$.

The compatibility for ${\mathop\mathrm{add}\nolimits}$: $$\begin{aligned}
\delta{{q_{{n}}}}\mathop{{\mathop\mathrm{add}\nolimits}} & =\delta\big(\mathop{{\mathop\mathrm{add}\nolimits}_{{{q_{{n}}}}{{o}}}}({{q_{{n}}}}{\mathbin{\widehat\times}}{{q_{{n}}}})+M({{p_{{n}}}}{\mathbin{\widehat\times}}{{p_{{n}}}})\big)=\mathop{{\mathop\mathrm{add}\nolimits}_{{{{{k_{{n}}}}{{o}}}}}}(\delta{\mathbin{\widehat\times}}\delta)({{q_{{n}}}}{\mathbin{\widehat\times}}{{q_{{n}}}})+m({{p_{{n}}}}{\mathbin{\widehat\times}}{{p_{{n}}}}) \\
& =\mathop{{\mathop\mathrm{add}\nolimits}_{{{{{k_{{n}}}}{{o}}}}}}({{k_{{n}}}}{\mathbin{\widehat\times}}{{k_{{n}}}})({{p_{{n}}}}{\mathbin{\widehat\times}}{{p_{{n}}}})+\big({{k_{{n}}}}\mathop{{\mathop\mathrm{add}\nolimits}}-\mathop{{\mathop\mathrm{add}\nolimits}_{{{{{k_{{n}}}}{{o}}}}}}({{k_{{n}}}}{\mathbin{\widehat\times}}{{k_{{n}}}})\big)({{p_{{n}}}}{\mathbin{\widehat\times}}{{p_{{n}}}}) \\
& ={{k_{{n}}}}\mathop{{\mathop\mathrm{add}\nolimits}}({{p_{{n}}}}{\mathbin{\widehat\times}}{{p_{{n}}}})={{k_{{n}}}}{{p_{{n}}}}\mathop{{\mathop\mathrm{add}\nolimits}}\end{aligned}$$ The weak [H-]{}space condition $\mathop{{\mathop\mathrm{add}\nolimits}}\vartheta={\mathop{\widehat\nabla}}$ on ${{P_{{n}}}}$ verified for its two components: $$\begin{aligned}
{{p_{{n}}}}\mathop{{\mathop\mathrm{add}\nolimits}}\vartheta & =\mathop{{\mathop\mathrm{add}\nolimits}}({{p_{{n}}}}{\mathbin{\widehat\times}}{{p_{{n}}}})\vartheta=\mathop{{\mathop\mathrm{add}\nolimits}}\vartheta({{p_{{n}}}}{\mathbin{\widehat\vee}}{{p_{{n}}}})={\mathop{\widehat\nabla}}({{p_{{n}}}}{\mathbin{\widehat\vee}}{{p_{{n}}}})={{p_{{n}}}}{\mathop{\widehat\nabla}}\\
{{q_{{n}}}}\mathop{{\mathop\mathrm{add}\nolimits}}\vartheta & =\big(\mathop{{\mathop\mathrm{add}\nolimits}_{{{q_{{n}}}}{{o}}}}({{q_{{n}}}}{\mathbin{\widehat\times}}{{q_{{n}}}})+M({{p_{{n}}}}{\mathbin{\widehat\times}}{{p_{{n}}}})\big)\vartheta=\mathop{{\mathop\mathrm{add}\nolimits}_{{{q_{{n}}}}{{o}}}}\vartheta({{q_{{n}}}}{\mathbin{\widehat\vee}}{{q_{{n}}}})+\underbrace{M\vartheta}_0({{p_{{n}}}}{\mathbin{\widehat\vee}}{{p_{{n}}}}) \\
& ={\mathop{\widehat\nabla}}({{q_{{n}}}}{\mathbin{\widehat\vee}}{{q_{{n}}}})={{q_{{n}}}}{\mathop{\widehat\nabla}}\end{aligned}$$ The compatibility for ${\mathop\mathrm{inv}\nolimits}$: $$\begin{aligned}
\delta(-c+2{{q_{{n}}}}{{o}}&-M(2,x,-x))=-\delta c+2\delta{{q_{{n}}}}{{o}}-m(2,x,-x) \\
& =-{{k_{{n}}}}x+2{{{{k_{{n}}}}{{o}}}}-({{k_{{n}}}}(\underbrace{x+(-x)}_{{{o}}})-{{k_{{n}}}}x+{{{{k_{{n}}}}{{o}}}}-{{k_{{n}}}}(-x))={{k_{{n}}}}(-x)\end{aligned}$$ The condition $\mathop{{\mathop\mathrm{add}\nolimits}}({\mathop\mathrm{id}\nolimits}{\mathbin{\widehat\times}}\mathop{{\mathop\mathrm{inv}\nolimits}}){\mathop{\widehat\Delta}}={{o}}$ of being a right inverse: $$\begin{aligned}
(x,c)+(-(x,c)) & =(x,c)+(-x,-c+2{{q_{{n}}}}{{o}}-M(2,x,-x)) \\
& =(x+(-x),c-{{q_{{n}}}}{{o}}+(-c+2{{q_{{n}}}}{{o}}-M(2,x,-x))+M(2,x,-x)) \\
& =({{o}},{{q_{{n}}}}{{o}})={{o}}\qedhere\end{aligned}$$

Polynomiality {#sec:polynomiality}
=============

Basic notions {#basic-notions .unnumbered}
-------------

The algorithm of Theorem \[thm:main\_theorem\] was described for a single generalized lifting-extension problem. To prove that its running time is polynomial, we will have to deal with the class of all generalized lifting-extension problems and also certain related classes, e.g. the class of Moore-Postnikov stages. We will base our analysis on the notion of a locally polynomial-time simplicial set, described in [@polypost]. Here, we will call it a polynomial-time family of simplicial sets.

Since we assume ${{d}}$ to be fixed and our algorithms only access information up to dimension $2{{d}}+2$, we make the following standing assumption.

In this section, when speaking about the running time of algorithms, it is understood that inputs are limited to dimension at most $2{{d}}+2$.

A *family of (locally effective) simplicial sets* is a collection $(X(p))_{p\in{\mathsfsl{P}}}$ of simplicial sets, such that the elements of the *parameter set* ${\mathsfsl{P}}$ have a representation in a computer, simplices of each $X(p)$ also have a representation in a computer and such that there are provided algorithms, all taking as inputs pairs $(p,x)$ with $p\in{\mathsfsl{P}}$, and performing the following tasks:

1.  decide whether $x$ is a simplex of the simplicial set $X(p)$,

2.  compute all faces of $x$,

3.  compute all degeneracies of $x$,

4.  compute the action of each $a\in G$ on $x$,

5.  compute the expression of $x$ as $x=ay$ with $a\in G$ and $y$ distinguished.

We say that this family is *polynomial-time* if all these algorithms have their running time bounded by $g({\mathop\mathrm{size}\nolimits}(p)+{\mathop\mathrm{size}\nolimits}(x))$, where $g$ is some polynomial function and ${\mathop\mathrm{size}\nolimits}(p)$, ${\mathop\mathrm{size}\nolimits}(x)$ are the encoding sizes of $p$ and $x$ (we remind the assumption $\dim x\leq 2{{d}}+2$).

A *family of effective simplicial sets* possesses, in addition, an algorithm that, given $p\in{\mathsfsl{P}}$, outputs the list of all non-degenerate distinguished simplices of $X(p)$.

In Section \[sec:equi\_eff\_hlgy\_alg\], we described a way of encoding finite simplicial sets. Such encodings comprise the parameter set ${\mathsfsl{SSet}}$; it then supports an obvious polynomial-time family of effective simplicial sets.

The notion of a family can be similarly defined for pairs of (effective) simplicial sets, (effective) chain complexes, strong equivalences, simplicial sets with effective homology etc. Each such class ${\mathcal C}$ is described by a collection of algorithms that are required to specify its object. Families of objects of ${\mathcal C}$ are then obvious parametrized versions of such collections of algorithms; we will denote them as ${\mathsfsl{P}}{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{~>}[r]^{} & {}}}}{\mathcal C}$.

Since for each class ${\mathcal C}$ the number of the required algorithms is finite, we may consider the parameter set ${\mathsfsl{Alg}}({\mathcal C})$, whose elements are such collections of algorithms (non-parametrized, i.e. describing a single object). Further, we denote by ${\mathsfsl{Alg}}_g({\mathcal C})$ the collections of algorithms that run in time bounded by the polynomial $g$. When membership algorithms are present, as in the case of simplicial sets, ${\mathsfsl{Alg}}({\mathcal C})$ supports an obvious family ${\mathsfsl{Alg}}({\mathcal C}){\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{~>}[r]^{} & {}}}}{\mathcal C}$ that assigns to each collection of algorithms the object they represent (the parametrized version of each algorithm simply runs the appropriate algorithm contained in the parameter). It restricts to a polynomial-time family parametrized by ${\mathsfsl{Alg}}_g({\mathcal C})$. We will use this observation as a motivation for the following.

In constructing new families of objects, it is important that these are polynomial-time whenever the old ones are. We will encapsulate this situation in the notion of a polynomial-time construction. A *construction* $F{\colon}{\mathcal C}\to{\mathcal D}$ is simply a mapping; we use a different name to emphasize that it operates on the level of objects (i.e. mathematical structures of some sort). In general, we will not require it to be single-valued, having in mind an example of associating to an equation its solution – no solution needs exist and if it does, there might be many.

Assuming the presence of membership algorithms in the class ${\mathcal C}$, we say that the construction $F$ is *computable*, if the collection ${\mathsfsl{Alg}}({\mathcal C}){\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{~>}[r]^{} & {}}}}{\mathcal C}\to{\mathcal D}$ is made into a family. It is said to be *polynomial-time* if, in addition, this family restricts to a polynomial-time family ${\mathsfsl{Alg}}_g({\mathcal C}){\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{~>}[r]^{} & {}}}}{\mathcal D}$ for each polynomial $g$. Thus, computability is an extra structure on a construction, given by a collection of algorithms required to set up a family in ${\mathcal D}$; these algorithms may use as subroutines the algorithms that specify objects of ${\mathcal C}$. We remark that this description does not depend on the presence of membership algorithms and we may thus define polynomial-time constructions between general classes.

The use of algorithms from the class ${\mathcal C}$ to set up those for ${\mathcal D}$ is a typical situation – for a pair of simplicial sets $X$, $Y$, we may form their product $X\times Y$; then the ${{i}}$-th face $d_{{i}}(x,y)=(d_{{i}}x,d_{{i}}y)$ may be computed from the respective faces in $X$ and $Y$. Since this computation is clearly polynomial-time, we have a polynomial-time construction $$\xymatrix{
\{\text{pairs of locally effective simplicial sets}\} \ar[r] & \{\text{locally effective simplicial sets}\}.
}$$

The usefullness of polynomial-time constructions $F{\colon}{\mathcal C}\to{\mathcal D}$ lies in the following simple observation: when a polynomial-time family $C\colon{\mathsfsl{P}}{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{~>}[r]^{} & {}}}}{\mathcal C}$ is given, the composition with $F$ yields a collection ${\mathsfsl{P}}{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{~>}[r]^{C} & {}}}}{\mathcal C}{\xrightarrow{F}}{\mathcal D}$ which gets a structure of a polynomial-time family from that of $F$ and $C$, i.e. $F$ “preserves” polynomial-time families. The dual situation is called a reparametrization: when $\Phi{\colon}{\mathsfsl{Q}}\to{\mathsfsl{P}}$ is a polynomial-time function and ${\mathsfsl{P}}$ supports a polynomial-time family $C{\colon}{\mathsfsl{P}}{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{~>}[r]^{} & {}}}}{\mathcal C}$ then ${\mathsfsl{Q}}{\xrightarrow{\Phi}}{\mathsfsl{P}}{\mathbin{\:\!\!\xymatrix@1@C=15pt{{}\ar@{~>}[r]^{C} & {}}}}{\mathcal C}$ is another polynomial-time family.

At the same time, the polynomiality of a construction does not depend on the actual encodings but only on the classes involved. The main result of this section is the following.

\[thm:main\_poly\] For each fixed ${{d}}\geq 1$, the algorithm of Theorem \[thm:main\_theorem\] describes a polynomial-time construction $$\xymatrix@R=15pt{
\left\{\parbox{\widthof{\upshape ${{d}}$-stable generalized lifting-extension problems}}{\upshape ${{d}}$-stable generalized lifting-extension problems composed of effective simplicial sets}\right\} \ar[r] & *+!!<-\the\hlp,\the\fontdimen22\textfont2>{\left\{\parbox{\widthof{\upshape abelian groups}}{\upshape fully effective abelian groups}\right\}\cup\{\emptyset\},} \\
{} \POS*!<0pt,-13pt>\xybox{\xymatrix@=15pt{
\scriptstyle A \ar[r] \ar@{ >->}[d] & \scriptstyle Y \ar[d] \\
\scriptstyle X \ar[r] & \scriptstyle B
}} \ar@{|->}[r] & [X,Y]^A_B,
}$$ where the ${{d}}$-stability of a generalized lifting-extension problem means that $\dim X\leq 2{{d}}$, both $B$ and $Y$ are $1$-connected and the homotopy fibre of $\varphi{\colon}Y\to B$ is ${{d}}$-connected.

From the definition, we are required to set up a polynomial-time family indexed by ${\mathsfsl{Alg}}({\mathcal C})$ where ${\mathcal C}$ is the class of generalized lifting-extension problems in question. We will make use of restricted parameter sets ${\mathsfsl{Map}}$ and ${{\mathsfsl{Pair}}}$ that describe $\varphi$ and $(X,A)$ respectively.

The whole computation is summarized in the following chains of computable functions between parameter sets that describe various partial stages of the computation; we will explain all the involved parameter sets later. The functions $$\xymatrix@R=2pt{
{\settowidth{\hlp}{${\mathsfsl{EMPS}_{0}}$}\makebox[\hlp][r]{${{\mathsfsl{Map}}={}}{{\mathsfsl{EMPS}_{0}}}$}} \ar@{.>}[rr] \POS[];[rr]**\dir{}?<>(.33)**\dir{-}*\dir{>},[];[rr];**\dir{}?<>(.33)**\dir{-} & & {\mathsfsl{EMPS}_{{{n}}}} & {\mathsfsl{Map}}\times_{\mathsfsl{SSet}}{\mathsfsl{MPS}_{{{n}}}} \ar[r] & {\mathsfsl{MPS}_{{{n}}}},
}$$ for ${{n}}=\dim X$, describe the computation of the Moore–Postnikov system over $B$ and its pullback to $X$, $$\xymatrix@R=2pt{
{{\mathsfsl{Pair}}}\times_{\mathsfsl{SSet}}{\ifthenelse{\equal{{{m}}-1}{}}{\mathsfsl{HMPS}_{{{n}}}}{\mathsfsl{HMPS}_{{{n}},{{m}}-1}}} \ar[r] & {\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{PMPS}_{{{n}}}}{\mathsfsl{PMPS}_{{{n}},{{m}}}}}\cup\{\bot\} & {\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{PMPS}_{{{n}}}}{\mathsfsl{PMPS}_{{{n}},{{m}}}}} \ar[r] & {\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{HMPS}_{{{n}}}}{\mathsfsl{HMPS}_{{{n}},{{m}}}}},
}$$ for ${{m}}\leq{{n}}$, describe the computation of the weak [H-]{}space structure on the stable part of the pullback (when it admits a section at all) and $$\xymatrix@R=2pt{
\Gamma_{{{n}}}{\colon}{{\mathsfsl{Pair}}}\times_{\mathsfsl{SSet}}{\ifthenelse{\equal{{{n}}}{}}{\mathsfsl{HMPS}_{{{n}}}}{\mathsfsl{HMPS}_{{{n}},{{n}}}}} \ar@{~>}[r] & \{\text{fully effective abelian groups}\}
}$$ describes a polynomial-time family, given by the homotopy classes of sections of the final ${{n}}$-th stage that are zero on $A$.

Moore–Postnikov systems {#moorepostnikov-systems .unnumbered}
-----------------------

The elements of the parameter set ${\mathsfsl{EMPS}_{{{n}}}}$ encode “extended” Moore–Postnikov systems and are composed of the following data

1.  finite $1$-connected simplicial sets $Y$, $B$;

2.  finitely generated abelian groups $\pi_1,\ldots,\pi_{{n}}$;

3.  effective Postnikov invariants ${{\kappa_1^{\mathrm{ef}}}},\ldots,{{\kappa_{{n}}^{\mathrm{ef}}}}$ (to be explained below);

4.  a simplicial map $\varphi_{{n}}{\colon}Y\to P_{{n}}$;

where we set, by induction, $P_0=B$ and $P_{{i}}=P_{{{i}}-1}\times_{K(\pi_{{i}},{{i}}+1)}E(\pi_{{i}},{{i}})$, a pullback taken with respect to the Postnikov invariant ${{k_{{i}}'}}{\colon}P_{{{i}}-1}\to K(\pi_{{i}},{{i}}+1)$ that corresponds to the equivariant cocycle $$\xymatrix{
C_{{{i}}+1}P_{{{i}}-1} \ar[r] & C_{{{i}}+1}^{\mathrm{ef}}P_{{{i}}-1} \ar[r]^-{{{\kappa_{{i}}^{\mathrm{ef}}}}} & \pi_{{i}}}$$ with the first map the canonical map coming from the effective homology of $P_{{{i}}-1}$. Thus, ${{\kappa_{{i}}^{\mathrm{ef}}}}$ is required to be an equivariant cocycle as indicated.[^22]

The above simplicial sets provide a number of families $$\xymatrix{
B,P_1,\ldots,P_{{n}},Y{\colon}{\mathsfsl{EMPS}_{{{n}}}} \ar@{~>}[r] & \left\{\parbox{\widthof{simplicial sets equipped}}{simplicial sets equipped with effective homology}\right\}
}$$ and also a number of families of simplicial maps $p_{{i}}$, ${{k_{{i}}'}}$, $\varphi_{{i}}$ etc. between these. They are polynomial-time essentially by the results of [@polypost] – there is only one significant difference, namely the (equivariant) polynomial-time homology of Moore–Postnikov stages. For that we need the following observation: the functor $B$ of Theorem \[t:vokrinek\] is a polynomial-time construction defined on $$\left\{\parbox{\widthof{strong equivalences $C{\xLeftrightarrow{\ \ \ }}C^{\mathrm{ef}}$ with $C$ locally}}{strong equivalences $C{\xLeftrightarrow{\ \ \ }}C^{\mathrm{ef}}$ with $C$ locally effective over ${{{\mathbb Z}G}}$, $C^{\mathrm{ef}}$ effective over ${\mathbb Z}$}\right\}$$ and taking values in a similar collection with everything ${{{\mathbb Z}G}}$-linear. Its polynomiality is guaranteed by the explicit nature of this functor, see [@Vokrinek].

Polynomiality of functions ${\mathsfsl{EMPS}_{{{i}}-1}}\to{\mathsfsl{EMPS}_{{{i}}}}$ is proved in the same way as in [@polypost] with the exception of the use of Proposition \[prop:projectivity\] that describes a polynomial-time construction $$\xymatrix@R=2pt{
\left\{\parbox{\widthof{$n$-connected effective}}{$n$-connected effective chain complexes}\right\} \ar[r] & \left\{\parbox{\widthof{homomorphisms of effective}}{homomorphisms of effective abelian groups}\right\}, \\
C \ar@{|->}[r] & (C_{n+1}\to Z(C_{n+1})).
}$$

Parameters for a Moore–Postnikov system are comprised of the same data with the exception of $Y$ and $\varphi_{{n}}$; we denote their collection by ${\mathsfsl{MPS}_{{{n}}}}$. The parameters for the pullback $g^*S$ of a Moore–Postnikov system $S$ of $\varphi{\colon}Y\to B$ along $g{\colon}X\to B$ are: the base is $X$, the homotopy groups remain the same and the Postnikov invariants are pulled back along $X\times_BP_{{i}}\to P_{{i}}$. Thus, the pullback function ${\mathsfsl{Map}}\times_{\mathsfsl{SSet}}{\mathsfsl{EMPS}_{{{n}}}}\to{\mathsfsl{MPS}_{{{n}}}}$, $(g,S)\mapsto g^*S$ is polynomial-time (it is defined whenever the target of $g$ agrees with the base of $S$).

Stable Moore–Postnikov systems {#stable-moorepostnikov-systems .unnumbered}
------------------------------

For the subsequent developement, the most important ingredient is Lemma \[l:lift\_ext\_one\_stage\]. It is easy to see that it is a polynomial-time construction $$\xymatrix{
\left\{\parbox{\widthof{$(X,A)$ equipped with effective homology, $\pi$ fully}}{$(X,A)$ equipped with effective homology, $\pi$ fully effective abelian group, $z{\colon}X\to K(\pi,{{n}}+1)$, $c{\colon}A\to E(\pi,{{n}})$ computable such that $\delta c=z|_A$}\right\} \ar[r] & \left\{\parbox{\widthof{$X\to E(\pi,{{n}})$}}{$X\to E(\pi,{{n}})$ computable}\right\}\cup\{\bot\}.
}$$ It will be useful to split this construction into two steps: finding an “effective” cochain $c_0^{\mathrm{ef}}{\colon}C_{{n}}^{\mathrm{ef}}(X,A)\to\pi$ and computing from it the solution $\widetilde c+c_0$. The advantage of this splitting lies in the possibility of storing the effective cochain as a parameter.

We enhance the parameter set ${\mathsfsl{MPS}_{{{n}}}}$ to ${\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{PMPS}_{{{n}}}}{\mathsfsl{PMPS}_{{{n}},{{m}}}}}$ by including the parameter

1.  a simplicial map ${{o}}{\colon}B\to P_{{m}}$;

and to ${\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{HMPS}_{{{n}}}}{\mathsfsl{HMPS}_{{{n}},{{m}}}}}$ by including in addition the parameters

1.  equivariant effective cochains $M_{{i}}^{\mathrm{ef}}{\colon}C_{{i}}^{\mathrm{ef}}(P_{{{i}}-1}{\mathbin{\widehat\times}}_B P_{{{i}}-1},P_{{{i}}-1}{\mathbin{\widehat\vee}}_B P_{{{i}}-1})\to\pi_{{i}}$, $1\leq{{i}}\leq{{m}}$;

which give the zero section and the addition in the Moore–Postnikov stages; for the latter, we use the observation above.

There are polynomial-time functions $$\xymatrix{
{\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{PMPS}_{{{n}}}}{\mathsfsl{PMPS}_{{{n}},{{m}}}}} \ar[r] & {\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{HMPS}_{{{n}}}}{\mathsfsl{HMPS}_{{{n}},{{m}}}}}
}$$ which compute inductively the equivariant cochains $M_{{i}}$, $1\leq{{i}}\leq{{m}}$, using Lemma \[l:lift\_ext\_one\_stage\].

Computing diagonals {#computing-diagonals .unnumbered}
-------------------

We describe a number of polynomial-time families supported by ${\ifthenelse{\equal{}{}}{\mathsfsl{HMPS}_{}}{\mathsfsl{HMPS}_{,}}}$ and its relatives. We restrict our attention to the pullback Moore–Postnikov system $\widetilde S$ over $X$ whose stages will be denoted ${{\widetilde P_{{n}}}}$. The use of ${\mathop\mathrm{add}\nolimits}_{{m}}$ and Proposition \[prop:homotopy\_lifting\] gives a polynomial-time family $$\xymatrix@R=3pt{
\Gamma_{{{n}},{{m}}}{\colon}{{\mathsfsl{Pair}}}\times_{\mathsfsl{SSet}}{\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{HMPS}_{{{n}}}}{\mathsfsl{HMPS}_{{{n}},{{m}}}}} \ar@{~>}[r] & \{\text{semi-effective abelian groups}\} \\
((X,A),\widetilde S) \ar@{|->}[r] & [X,\widetilde P_{{m}}]^A_X
}$$ (defined whenever the bigger space $X$ of the pair $(X,A)$ agrees with the base of $\widetilde S$) which is then extended to a polynomial-time family of exact sequences from Theorem \[thm:exact\_sequence\]. More precicesly, it is a family of exact sequences $A\to B{\xrightarrow{f}}C{\xrightarrow{g}}D\to E$ of semi-effective abelian groups together with computable sections of the middle homomorphisms $f$, $g$ (as in Lemma \[l:ses\]); we will call them semi-effective exact sequences for short. We assume, by induction, that $\Gamma_{{{n}},{{m}}-1}$ has been already promoted to a polynomial-time family of fully effective abelian groups. The “five lemma” for fully effective structures (Lemmas \[l:ker\_coker\] and \[l:ses\]) provides a polynomial-time construction $$\xymatrix{
\left\{\parbox{\widthof{semi-effective exact sequences}}{semi-effective exact sequences $A\to B\to C\to D\to E$ with $A$, $B$, $D$, $E$ fully effective}\right\} \ar[r] & \{\text{fully effective abelian groups}\}
}$$ sending each exact sequence to its middle term $C$. Thus, $\Gamma_{{{n}},{{m}}}$ is enhanced to a polynomial-time family of fully effective abelian groups.

Computing zero sections {#computing-zero-sections .unnumbered}
-----------------------

It remains to analyze the function $$\xymatrix{
{{\mathsfsl{Pair}}}\times_{\mathsfsl{SSet}}{\ifthenelse{\equal{{{m}}-1}{}}{\mathsfsl{HMPS}_{{{n}}}}{\mathsfsl{HMPS}_{{{n}},{{m}}-1}}} \ar[r] & {\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{PMPS}_{{{n}}}}{\mathsfsl{PMPS}_{{{n}},{{m}}}}}\cup\{\bot\}.
}$$ By the above, we obtain a polynomial-time family of homorphisms $$\xymatrix{
{{k_{{{m}}*}}}{\colon}[X,\widetilde P_{{{m}}-1}]^A_X \ar[r] & H^{{{m}}+1}_G(X,A;\pi_{{m}})
}$$ of fully effective abelian groups, parametrized by ${{\mathsfsl{Pair}}}\times_{\mathsfsl{SSet}}{\ifthenelse{\equal{{{m}}-1}{}}{\mathsfsl{HMPS}_{{{n}}}}{\mathsfsl{HMPS}_{{{n}},{{m}}-1}}}$, and consequently a family of generators of the image of ${{k_{{{m}}*}}}$. We need to compute a preimage of $[\delta\widetilde c-{{k_{{m}}{{o_{{{m}}-1}}}}}]$, then transform it into a section of $\widetilde P_{{{m}}-1}\to X$ and thus enhance $\widetilde S\in{\ifthenelse{\equal{{{m}}-1}{}}{\mathsfsl{HMPS}_{{{n}}}}{\mathsfsl{HMPS}_{{{n}},{{m}}-1}}}$ to an element of ${\ifthenelse{\equal{{{m}}}{}}{\mathsfsl{PMPS}_{{{n}}}}{\mathsfsl{PMPS}_{{{n}},{{m}}}}}$, all in polynomial time. For this purpose, we employ a polynomial-time construction $$\xymatrix{
\left\{(A,a_1,\ldots,a_{{m}},b)\ \left|\ \parbox{\widthof{$A$ a fully effective abelian}}{$A$ a fully effective abelian group, $a_1,\ldots,a_{{m}},b\in A$}\right.\right\} \ar[r] & \{\text{lists of integers}\}\cup\{\bot\},
}$$ testing whether $b$ belongs to the subgroup generated by $a_1,\ldots,a_{{m}}$; if it does, it computes a list of coefficients $(z_1,\ldots,z_{{m}})$ such that $b=z_1a_1+\cdots+z_{{m}}a_{{m}}$. (The class on the right only contains an algorithm that prints the list.)

Acknowledgement {#acknowledgement .unnumbered}
---------------

We are grateful to Jiří Matoušek and Uli Wagner for many useful discussions, comments and suggestions that improved this paper a great deal. Moreover, this paper could hardly exist without our long-term collaboration, partly summarized in [@CKMSVW11] and [@polypost].

[^1]: The research of M. Č. was supported by the project CZ.1.07/2.3.00/20.0003 of the Operational Programme Education for Competitiveness of the Ministry of Education, Youth and Sports of the Czech Republic. The research by M. K.  was supported by the Center of Excellence – Inst. for Theor. Comput. Sci., Prague (project P202/12/G061 of GA ČR) and by the Project LL1201 ERCCZ CORES. The research of L. V. was supported by the Center of Excellence – Eduard Čech Institute (project P201/12/G028 of GA ČR). .5ex *2010 Mathematics Subject Classification*. Primary 55Q05; Secondary 55S91. .5ex *Key words and phrases*. Homotopy classes, equivariant, fibrewise, lifting-extension problem, algorithmic computation, embeddability, Moore–Postnikov tower.

[^2]: In the algorithmic context, we will work with a simplicial version called a Kan fibration, see [@May:SimplicialObjects-1992].

[^3]: Here a homotopy $h{\colon}[0,1]\times X\to Y$ is *fibrewise* if $\varphi(h(t,x))=g(x)$ for all $t\in[0,1]$ and $x\in X$. It is *relative to $A$* if, for $a\in A$, $h(t,a)$ is independent of $t$, i.e. $h(t,a)=f(a)$ for all $t\in [0,1]$ and $a\in A$.

[^4]: If $\varphi$ is a Kan fibration between finite $1$-connected simplicial sets then its fibre is a finite Kan complex and it is easy to see that it then must be discrete. Consequently, $\varphi$ is a covering map between $1$-connected spaces and thus an isomorphism.

[^5]: This problem (under our usual condition on the dimension of $X$) was considered in [@polypost], but with a different equivalence relation on the set of all extensions: [@polypost] dealt with the (slightly unnatural) *coarse classification*, where two extensions $\ell_0$ and $\ell_1$ are considered equivalent if they are homotopic as maps $X\to Y$, whereas here we deal with the *fine classification*, where the equivalence of $\ell_0$ and $\ell_1$ means that they are homotopic relative to $A$.

[^6]: Note that we cannot simply take $B$ to be a point in the lifting-extension problem with a nontrivial $G$, since there is no free action of $G$ on a point. Actually, $EG$ serves as an equivariant analogue of a point among free $G$-spaces.

[^7]: The homotopy fibre of $\varphi$ is the fibre of $\varphi'$, where $\varphi$ is factored through $Y'$ as above. It is unique up to homotopy equivalence, and so the connectivity is well defined.

[^8]: The complex is (the canonical triangulation of) the union of all products $\sigma \times \tau$ of disjoint simplices $\sigma,\,\tau \in K$, $\sigma \cap \tau = \emptyset$.

[^9]: Strictly speaking, we only need a membership test for *subsets*, i.e. when $A\subseteq X$ is a subset, we need an algorithm that tests whether an element of $X$ belongs to $A$ (while we *do not* need to test whether a bit string represents an element of $X$).

[^10]: These requirements (with the exception of the differentials) are automatically satisfied when the elements of the chain complex are represented directly as ${{{\mathbb Z}G}}$-linear combinations of the distinguished bases.

[^11]: We could equally well work with pairs $(X,A)$ of simplicial sets for which the relative chain complex $C_*(X,A)$ is equipped with effective homology (as observed, this is a weaker condition).

[^12]: By passing to the mapping cylinder $X'=({\Delta^{1}}\times A)\cup X$, we may even relax the condition on the pair $(X,A)$ to each of $A$, $X$ being equipped with effective homology separately since then the pair $(X',A)$ has effective homology (this is very similar to but easier than Proposition \[p:effective\_homotopy\_colimits\]) and the resulting generalized lifting-extension problem is equivalent to the original one.

[^13]: We recall that a contraction is a map $\sigma$ of degree $1$ satisfying $\partial\sigma+\sigma\partial={\mathop\mathrm{id}\nolimits}$.

[^14]: Our groups $H_G^*(X;\pi)$ are the equivariant cohomology groups of $X$ with coefficients in a certain system associated with $\pi$ (see the remark in [@Bredon:EquivariantCohomology-1967 Section I.9]) or, alternatively, they are the cohomology groups of $X/G$ with local coefficients specified by $\pi$.

[^15]: We do not assume that ${\mathcal A}$ is computable – this will not be the case e.g. for $[X,{{P_{{n}}}}]$ when $X$ is infinite.

[^16]: We remind that $s^1$ is a simplicial map sending the unique non-degenerate $2$-simplex of ${\Delta^{2}}$ to the $s_1$-degeneracy of the unique non-degenerate $1$-simplex of ${\Delta^{1}}$.

[^17]: Given two such homotopies, one may form out of them a map $({\mbox{$\xy
    <0pt,-\the\fontdimen22\textfont2>;p+<.1em,0em>:
    {\ar@{-}(0,0.1);(3,7)},
    {\ar@{-}(3,7);(6,0.1)},
    {\ar@{-}(3.2,7);(6.2,0.1)},
    {\ar@{-}(3.4,7);(6.4,0.1)}
    \endxy\;\!{}^{2}_{2}$}}\times X)\cup({\Delta^{2}}\times A)\to{{P_{{n}}}}$, whose extension to ${\Delta^{2}}\times X$ (suitably fibrewise) gives on ${d}_2{\Delta^{2}}\times X$ the required homotopy.

[^18]: It is also possible to define [H-]{}maps with sections $\psi(o)$ and $o$ merely homotopic. In this paper, such generality is not needed.

[^19]: Thus, the action needs only be free away from $A$ and the same generalization applies to the dimension.

[^20]: The fibres of $\psi$ are ${{n}}$-connected and isomorphic to those of $\ell^*Q\to X$. From the long exact sequence of homotopy groups of this fibration, it follows that $\ell^*Q\to X$ is also an $({{n}}+1)$-equivalence and its section must then be an ${{n}}$-equivalence.

[^21]: Start with an inclusion $({\Delta^{{{i}}}}\times*)\cup(0\times F){\rightarrow}\sigma^*{{P_{{n}}}}$ given by the zero section on the first summand and by the inclusion on the second. Extend this to a fibrewise map ${\Delta^{{{i}}}}\times F{\rightarrow}\sigma^*{{P_{{n}}}}$ which is a fibrewise homotopy equivalence, hence an isomorphism by the minimality of ${{P_{{n}}}}{\rightarrow}B$.

[^22]: When $Y$ is not finite, $\varphi_{{n}}$ has to be replaced by a certain collection of effective cochains on $Y$; details are explained in [@polypost].
