# Learning sparse transformations through backpropagation

Peter Bloem
Knowledge Representation and Reasoning Group
Vrije Universiteit Amsterdam

<EMAIL_ADDRESS>

###### Abstract

Many transformations in deep learning architectures are sparsely connected.
When such transformations cannot be designed by hand, they can be learned,
even through plain backpropagation, for instance in attention mechanisms.
However, during learning, such sparse structures are often represented in a
dense form, as we do not know beforehand which elements will eventually become
non-zero.

We introduce the _adaptive, sparse hyperlayer_ , a method for learning a
sparse transformation, paramatrized _sparsely_ : as index-tuples with
associated values. To overcome the lack of gradients from such a discrete
structure, we introduce a method of randomly sampling connections, and
backpropagating over the randomly wired computation graph.

To show that this approach allows us to train a model to competitive
performance on real data, we use it to build two architectures. First, an
attention mechanism for visual classification. Second, we implement a method
for _differentiable sorting_ : specifically, learning to sort unlabeled MNIST
digits, given only the correct order.

##  1 Introduction

Deep learning is most effective when the transformations we apply to our data
are in some way constrained, based on the knowledge we have about our task.
For instance, we know that images have a highly local structure, so instead of
using fully connected transformations, we use convolutions, connecting input
units to hidden units based on locality in the data.

In other words, we replace a densely connected transformation by a sparsely
connected one. Sometimes, we know the sparse structure of this transformation
beforehand (which connections should exist, and which should not). In other
cases, we do not know what structure works best, or worse, the structure
should be derived from the data every time the transformation is applied, as
in attention mechanisms, or sorting networks. Such sparse transformations are
commonly parametrized by dense tensors of equal size, using methods such as
sparsemax [12], or Sinkhorn [13] operators to enforce sparsity in the
resulting matrix

We propose a different approach: instead of parametrizing a sparse tensor by a
dense one, we use a sparse parametrization.

For sparse tensors with fixed structure, sparse descriptions are common: we
store every nonzero element in the tensor as an index-tuple together with its
values. For all other elements, we assume value zero. This scheme is well-
established, and allows the _values_ of the sparse tensor to be learned
efficiently through backpropagation. However, if we want to learn the
_structure_ of the tensor as well, we run into a problem: since the index
tuples are necessarily integers, we cannot derive a meaningful gradient to use
in gradient descent. Approaches like the Gumbel-softmax trick [7] or the
REINFORCE algorithm [25] can be used to approximate such a gradient, but these
require a categorical distribution over the space of all integer index-tuples,
resulting in another dense parametrization.

Instead, we parametrize each integer index tuple by a distribution over a
continuous space containing all integer index tuples. We then sample index
tuples randomly, and distribute the corresponding value over these by the
associated probability. The gradient propagates back only through these mixed
values, and the discrete index tuples are taken as constants.

We call this mechanism a _sparse layer_. The parameters of the sparse layer
can be trained as free parameters, or they can be the output of another
network, a _source_ network. This turns the sparse layer into a _sparse
hyperlayer_ (or hypernetwork) [3]. The source network can simply derive the
sparse parameters from another parameter space to constrain or bias the
learned sparse tensors (for instance to allow only tensors implementing
convolutions to be learned). The source network may also derive the sparse
parameters from the current input, allowing an _adaptive sparse hyperlayer_ ,
to implement, for instance, an attention mechanism.

We perform several experiments to validate this approach. First, in order to
visualize the behavior of the model under gradient descent, we simply learn
the identity matrix from batches of normally distributed vectors. While this
is a simple problem we show that a comparable REINFORCE-based model cannot
solve the task for anything but very small vectors.

Second, to test the model on a real problem, we compare to the Recurrent
Attention Model [15] on the Cluttered MNIST-100 dataset, a challenging dataset
that embeds MNIST digits in $100\times 100$ images with added noise. We show
that our approach outperforms the RAM model, while being end-to-end trainable
with plain backpropagation.

Finally, we turn to the problem of _differentiable sorting_. We use the
principle of the sparse hyperlayer to implement a differentiable version of
quicksort. While the sorting algorithm itself contains no trainable
parameters, it allows us to sort a set of $n$ tensors by $n$ scalar _keys_ in
such a way that we get a gradient over the keys which can be backpropagated to
the network used to compute the keys. We test this approach by passing MNIST
digits through a randomly initialized ConvNet to derive a key, sorting by the
keys, and backpropagating to train the ConvNet.

All code is available on-line under, an open-source
license.111https://github.com/MaestroGraph/sparse-hyper

##  2 The adaptive, sparse hyperlayer

Figure 1: Schematic representation of how the sparse layer is constructed for
vector input $\mathbold{x}$ and output $\mathbold{y}$.

We define our model as a transformation of one tensor $x$ to another $y$, both
of arbitrary rank and shape. The most common transformation of one vector into
another by a matrix of weights follows as a special case.

#### Notation

We use the notation $\mathbold{T}[i,j,k]$ for the element of tensor
$\mathbold{T}$ that is indexed by indices $i$, $j$ and $k$. We will use an
interpunct to represent subtensors, for instance, $\mathbold{M}[\cdot,j]$
represents the $j$-th column of matrix $\mathbold{M}$.

Unless otherwise noted, operations between tensors are computed element-wise.
Multiplication between matrices of unequal size represents matrix
multiplication.

We use $[f..t]$ to indicate a range of integers (including both endpoints) and
$\mathbold{x}[f..t]$ to represent a subvector of vector $\mathbold{x}$ indexed
by that range (similarly for tensors). For tensor $\mathbold{X}$ and binary
tensor $\mathbold{I}$ of the same size, $\mathbold{X}[\mathbold{I}]$ refers to
the set of those elements for which $\mathbold{I}$ is 1 and
$\mathbold{X}[\neg\mathbold{I}]$ refers to the set of elements for which
$\mathbold{I}$ is 0. If this set can be arranged into a tensor in a
straightforward way (for instance if $\mathbold{x}$ is a vector), we will take
$\mathbold{X}[\mathbold{I}]$ to represent that tensor.

###  2.1 Model

Let $\mathbold{x}$, the _input_ , be a tensor in
${\mathbb{R}}^{i_{1}\times\ldots\times i_{n}}$ and let $\mathbold{y}$, the
_output_ , be a tensor in ${\mathbb{R}}^{o_{1}\times\ldots\times o_{m}}$. A
_sparse layer_ is a compressed representation of a weight tensor
$\mathbold{W}$ representing a fully connected layer, so that the layer
computes the operation $\mathbold{W}\cdot\mathbold{x}=\mathbold{y}$, where the
dot represents a tensor contraction defined below, which equals matrix
multiplication if $\mathbold{x}$ and $\mathbold{y}$ are vectors.

The shape of $\mathbold{W}$ is determined by the shapes of $\mathbold{x}$ and
$\mathbold{y}$ as $\mathbold{W}\in{\mathbb{R}}^{h_{1}\times\ldots\times
h_{r}}$ with $r=n+m$. The specific tensor contraction computed is defined as
follows: let $a_{1},\ldots,a_{n}$ represent indices of $\mathbold{x}$, and let
$b_{1},\ldots,b_{m}$ represent indices of $\mathbold{y}$. We then define
$\mathbold{W}\cdot\mathbold{x}=\mathbold{y}$ as:

$\mathbold{y}[b_{1},\ldots,b_{m}]=\sum_{a_{1},\ldots,a_{n}}\mathbold{W}[b_{1},\ldots,b_{m},a_{1},\ldots,a_{n}]\cdot\mathbold{x}[a_{1},\ldots,a_{n}]$

That is, for each element of $\mathbold{y}$ indexed by $b_{1},\ldots,b_{m}$,
$\mathbold{W}$ contains a subtensor
$\mathbold{W}[\cdot,\ldots,\cdot,b_{1},\ldots,b_{m}]$ of the same shape as
$\mathbold{x}$, and $\mathbold{y}[b_{1},\ldots,b_{m}]$ is the dot product of
that subtensor and $\mathbold{x}$. In network terms, $\mathbold{W}$ represents
a fully connected layer: for every input node there is one weight in
$\mathbold{W}$ for every possible connection to an output node.

We assume that the rank of the tensor and the output dimensions stay constant
over all inputs. The input dimensions can vary if eager execution is used, but
not the input rank.

We will assume that $\mathbold{W}$ is sparse. Our aim is to learn both its
structure and values using a sparse parametrization: that is, we enumerate the
index tuples of its nonzero elements and assume that anything not enumerated
has value zero. To do this in a differentiable way, we define a matrix
$\mathbold{D}\in{\mathbb{R}}^{k\times r}$ as real-valued representatives of
the index tuples, and two length-$k$ vectors $\mathbold{\sigma}$ and
$\mathbold{v}$. Broadly, the rows of $\mathbold{D}$ encode points near likely
integer index tuples. $\mathbold{\sigma}$ encodes the corresponding certainty:
the smaller $\mathbold{\sigma}[i]$, the more certain we are that $D[i,\cdot]$
is in the right place. Finally, $\mathbold{v}_{i}$ is the value of the element
in the matrix at index $\mathbold{D}[i,\cdot]$.

We map $\mathbold{D}$ to the space of legal index tuples, by applying a
sigmoid function and scaling to the hyper-rectangle containing the tuples.
Each scalar $\mathbold{\sigma}[k]$ is passed through a softplus function to
make it positive, expanded to a length-$r$ vector, and multiplied by the
dimensions of $\mathbold{W}$, resulting in a vector $\mathbold{\sigma}_{k}$,
so that $\text{diag}(\mathbold{\sigma}_{k})$ represents a convariance matrix
that covers an equal proportion of available index tuples in each direction.
222We also add a small value $\tau$ (a hyperparameter), set to 0.1 in all
experiments, to stop the variance from converging too close to zero (which
occasionally helps to avoid local minima).

To form a sparse matrix based on these parameters, we generate several
_integer_ index tuples from each continuous index tuple
$\mathbold{D}[i,\cdot]$:

  * •

The $2^{r}$ integer tuples nearest to $D[i,\cdot]$ are always included.

  * •

We sample $a_{l}$ _local_ index tuples uniformly from a region of size
$l_{1},\ldots,l_{r}$ around $\text{round}(d_{j})$. If the region overlaps the
bounds of the allowed index tuples it is aligned to the bound.

  * •

We sample $a_{g}$ _global_ index tuples uniformly over all possible integer
index tuples.

These three sets of tuples are concatenated into an integer valued matrix
$\mathbold{D}^{\prime}\in{\mathbb{R}}^{k(2^{d}+a_{l}+a_{g})\times r}$.

Each sampled integer index tuple $d_{j}=\mathbold{D}^{\prime}[j,\cdot]$
receives a _proportion_ from each continuous index-tuple
$d_{i}=\mathbold{D}[i,\cdot]$ defined as $p_{ij}=N(d_{j}\mid
d_{i},\mathbold{\sigma}_{i})$. If any index tuple occurs more than once, the
proportion of the duplicates is set to zero (algorithm given in the appendix).
The proportions are then normalized so that the contribution of each
continuous index tuple sums to one over all integer index tuples:

$p^{\prime}_{ij}=p_{ij}/\sum_{k}p_{ik}$

We then compute a value
$\mathbold{v}^{\prime}[j]=\sum_{i}p^{\prime}_{ij}\mathbold{v}[i]$ for each
sampled integer tuple. Effectively, each generated index tuple is assigned a
part of $\mathbold{v}[i]$ proportional to its probability under
$N(d_{i},\mathbold{\sigma}_{i})$.

Together, the generated integer index tuples $\mathbold{D}^{\prime}$ and their
values $\mathbold{v}^{\prime}$ define a sparse matrix $\mathbold{W}$. The
precise procedure is given in Algorithm 1.

Algorithm 1 Sample a sparse matrix $W$ with integer index tuples from sparse
parameters $\mathbold{D}$ and $\mathbold{v}$.

given:
$\mathbold{D}\in{\mathbb{R}}^{k\times
r};\mathbold{\sigma},\mathbold{v}\in{\mathbb{R}}^{k}$
scalars $a_{g},a_{l},(l_{1},\ldots,l_{r})$

initialize $\mathbold{D}^{\prime}\in{\mathbb{N}}^{k(2^{r}+a_{l}+a_{g})\times
r}$, $\mathbold{v}^{\prime}\in{\mathbb{R}}^{k(2^{r}+a_{l}+a_{g})}$

for $i\in[0..k]$:
$\mathbold{d}_{i}\leftarrow\text{sigmoid}(\mathbold{x})\cdot[h_{1},\ldots,h_{r}]$
$\mathbold{\sigma}_{i}\leftarrow$
softplus$(\mathbold{\sigma}[i]+2)\cdot[h_{1},\ldots,h_{r}]\cdot 0.1+\tau$

$\mathbold{D}^{\prime}[i..i+2^{r},\cdot]\leftarrow$ the $2^{r}$ integer index
tuples nearest to $\mathbold{d}_{i}$
$\mathbold{D}^{\prime}[i+2^{r}..i+2^{r}+a_{l},\cdot]\leftarrow a_{l}$ tuples
uniformly over $(l_{1},\ldots,l_{r})$ around $\mathbold{d}_{i}$
$\mathbold{D}^{\prime}[i+2^{r}+a_{l}..i+2^{r}+a_{l}+a_{g},\cdot]\leftarrow
a_{g}$ tuples uniformly over all tuples

for $i\in[1..k]$, $j\in[1..2^{r}+a_{g}+a_{l}]$:
$p_{ij}=N(\mathbold{D}[j,\cdot]\mid\mathbold{d}_{i},\mathbold{\sigma}_{i})$

for $j\in[1..2^{r}+a_{g}+a_{l}]$:
$\mathbold{v}^{\prime}[j]=\sum_{i}\mathbold{v}[i]\frac{p_{ij}}{\sum_{k}p_{ik}}$

return $\mathbold{D}^{\prime}$, $\mathbold{v}^{\prime}$

We can now perform our transformation as

$\mathbold{y}=\mathbold{W}\cdot\mathbold{x}$

using standard sparse-times-dense matrix multiplication. During
backpropagation, we compute the gradient _only_ over $\mathbold{v}^{\prime}$,
taking $\mathbold{D}^{\prime}$ as a constant. This still allows us to learn
the values of $\mathbold{D}$ and $\mathbold{\sigma}$, since
$\mathbold{v}^{\prime}$ is computed using all parameters.

For a matrix-by-matrix multiplication, where $\mathbold{W}$ , $\mathbold{x}$
and $\mathbold{y}$ are all matrices, the algorithm can be applied without
modification, although in that case it does not generalize in a simple manner
to higher-dimensional tensors.

In some cases both the distribution on the index tuples and the method of
sampling index tuples can be tailored to the task at hand. Section 3.3,
provides an example.

##  3 Experiments

To show that the sparse layer can learn sparse transformations effectively,
and can be employed to solve practical and challenging problems, we test it in
three experiments.

Figure 2: Results of the identity experiment, comparing the performance of the
reinforce-based baseline (dashed) to that of the sparse layer (line). Color
indicates size. Error bars denote the _standard deviation_ over $r$ runs. The
first three sparse layer experiments were stoped after 10 000, 20 000 and 40
000 iterations respectively.

###  3.1 Learning the identity matrix

As a simple toy example, to illustrate the way the sparse layer behaves, we
learn the identity matrix: the input is a size-$n$ vector $\mathbold{x}$ from
$N(0,\mathbold{I}^{n})$, we compute the mean-squared-error loss between
$\mathbold{x}$ and $\mathbold{W}x$ with $\mathbold{W}$ a sparse layer (with no
source network), and backpropagate as show above.

We also train a REINFORCE-based model as a baseline, which parametrizes
$\mathbold{W}$ in the same way. Each epoch, we sample from each probability
distribution representing an index tuple, a single continuous value. We round
this value to the nearest integer index tuple, and construct a sparse matrix
$\mathbold{W}$ from the resulting integer index tuples. We use REINFORCE to
backpropagate through the sampling step.

We aim to sample a log-linear number of index-tuples in $n$ (versus the
quadratic total). To this end we set $a_{l}$ and $a_{g}$ so that
$a_{l}+a_{g}<2\log_{2}n$. 333With only four sizes tested, we should be
reluctant to conclude that larger identity matrices can also be trained to
convergence with a sparse number of samples. We leave this question to future
research.

We evaluate by rounding the continuous index tuples to the nearest integer
values and computing the loss over 10 000 newly sampled instances. Each point
in the graph represents such an evaluation.

Figure 2 shows the results. We see that the baseline seems to work, if slowly,
up to a size of 8, but fails for size 16. The sparse layer is able to train to
convergence up to size 64. For greater sizes, we still see the model move
towards the correct solution, but training to full convergence requires more
resources than were available. As in the size-32 example shown in Figure 3,
most index tuples move to the diagonal quickly, but it takes more iterations
for the final ones to find their place.

A more elegant use of REINFORCE may lead to better results, but this
experiment does highlight the fundamental difference between the two
approaches. Consider for instance, that for $n=4$, REINFORCE must take 4
samples, one for each index tuple. The downstream loss is then used to
approximate the gradient for all four of these ‘actions’, with each stochastic
node receiving the same loss. The loss is distributed by the individual
_probability_ of each sample but not by the individual _quality_ of each
sample.

Conversely, the sparse layer, after sampling, functions as a single
computation graph: those samples that hit the right index tuples receive
positive feedback and those that hit the wrong ones receive negative feedback.
The backpropagation algorithm can distribute the loss accurately back down the
computation graph as it was used in the forward pass.

Figure 3: Visualization of the sparse layer after 0, 1 000, 5 000, 9 000 and
13 000 batches, in the size-32 experiment. Solid blue circles indicate the
means of the continuous tuples. Transparent circles represent the
corresponding variance. Gray diamonds indicate the locations of integer index
tuples.

###  3.2 Attention

model | error
---|---
RAM (best reported) | 8.11 %
ours (1 glimpse, $32\times 32$) | 0.85 %
ours (8 glimpses, $12\times 12$) | 1.01 %
Table 1: The results of the attention experiment. The baseline consists of the
same ConvNet we use as a source network extended with a classification layer
(details in the appendix).

As the previous experiment shows, a large, unconstrained sparse layer, can
take a long time to converge. The model becomes most effective when we use a
source network to constrain which sparse tensors the network is able to
represent. We start with an extreme example in the form of _attention_. We are
given a large input image with a smaller region of interest which determines
its class. The task of our layer is to extract the region of interest, and
pass it to a classification network.

In this setting, our input $\mathbold{x}$ is an image tensor containing 3
dimensions: channels $c=1$, height $h_{\mathbold}{x}=100$ and width
$w_{\mathbold}{x}=100$. Our sparse layer transforms this to a smaller $k\times
k$ image $\mathbold{y}$ (which we’ll call a _glimpse_ , after [15]) also
represented as a 3-tensor. The sparse layer $\mathbold{W}$ for this
transformation is therefore a 6-tensor with dimensions
$(c,k,k,c,h_{\mathbold}{x},w_{\mathbold}{x})$.

It may be tempting to have the source network simply learn the paramaters of
$\mathbold{W}$ without constraint. However, doing this results “feedforward
behavior”. That is, it simply selects a black pixel to transmit a 1 and a
white pixel to transmit a 0. For the network to behave as an an attention
mechanism, we need to constrain it much further.

First, we learn only along two of the dimensions of $\mathbold{W}$:
$h_{\mathbold}{x}$, $h_{\mathbold}{y}$. For the others we fix their values so
that each element is determined by one element in $\mathbold{W}$. In network
terms: each node in the output receives a single incoming connection, and we
learn only which node in the input it should be connected to.444For multiple
channels, each input channel is connected only to a corresponding output
channel, but we use only single-channel images in this experiment. The values
$\mathbold{v}$ are learnable, but shared between all connections in a glimpse.

Figure 4: The glimpses after the final epoch, for the 1-glimpse network
(above) and the 8-glimpse network (below). Positive values are coded, blue,
negative values are coded red. Values near zero are coded yellow.

For convenience of implementation, we implement each glimpse in a separate
sparse layer. Though it may be beneficial to combine the glimpses in a single
tensor, we have not yet tested this approach.

A source network (architecture given in the appendix) reads the input image,
and produces, for each glimpse, 4 values, representing the lower left corner
of the bounding box for the glimpse and the upper right. We then compute
$k\times k$ equally spaced points in this bounding box and connect these
points in the input to their corresponding $k\times k$ points in the output.
The sigmoid and rescaling are applied afterwards.

We then proceed as described in Section 2.1, sampling integer index tuples for
each continuous tuple in each glimpse. We feed the resulting glimpses to a
2-layer MLP network which maps the glimpses to a class.

We test this approach with the $100\times 100$ MNIST-cluttered dataset
from[15]. We resample the data,555Using the script provided at
https://github.com/deepmind/mnist-cluttered. The sampled data can be
downloaded from https://github.com/MaestroGraph/sparse-hyper/creating a
training set of 60 000 images and a test set of 10 000 images. All
hyperparameters were chosen using a validation split, and the test set was
only used once.

Figure 5: Schematic representation of differentiable quicksort. A _key
network_ maps each 3-digit number to a scalar key (applying the same ConvNet
to each digit). The keys are used to create three half-permutation, which
compose to form a full permutation required to sort the keys. We apply this
permutation to the data $\mathbold{x}$, and backpropagate the loss to train
the network that generated the keys.

We test two configurations: a network with a single glimpse of $32\times 32$,
and a network with 8 glimpses of $12\times 12$ (following [15]).

Table 1 shows the results. Figure 4 visualizes the learned glimpses. We note,
that while the 1-glimpse network classifies with high accuracy, it does not
always behave exactly as expected from an attention mechanism. In many cases
it selects only part of the digit. We suspect that this is a kind of
intermediate between a feedforward network and an attention mechanism: by
selecting a specific part of each digit, the source network communicates
upstream part of the classification information, lightening the load of the
upstream network. Further research is required to study this behavior. The
8-glimpse network seems to behave better, focusing more on the entire digit,
although this does not lead to better classification accuracy.

Without further research, we will not claim that this is a competitive
attention mechanism, but this experiment does show that the adaptive, sparse
hyperlayer can be trained effectively through backpropogation, in a realistic
setting.

###  3.3 Differentiable sorting

Finally, we turn our attention to the problem of _differentiable sorting_ , or
equivalenty, of _learning permutations_. Some early successes in this area
have come in the form of pointer networks [23] and Gumbel-sinkhorn networks
[13].

These approaches both, to some extent, attempt to bias a parametrized network
towards learning sorting behavior. Our approach is more modular. We first
define a _key network_ over the instances to be sorted. The key network
assigns a single, real value to each instance. We then implement, using
adaptive sparse layers, a _differentiable_ version of quicksort [6] that
allows us to compare the output to the correctly sorted version, and
backpropagate the loss to train the key network. We call this approach more
modular, because the network that performs the sorting contains no parameters.
The permutation is entirely parametrized by the key network, and is easily
interpretable (the order of the keys determines the learned permutation). For
a schematic illustration of the following, see Figure 5.

In order to implement quicksort using sparse layers, we first introduce the
concept of a _half-permutation_. A _first-order_ half permutation is a
permutation which arranges the given elements into the top or bottom half of
the output, but preserves their ordering otherwise. More precisely, let
$\mathbold{o}$ be a length-$n$ binary vector with equal numbers of $0$ and $1$
elements, and let $\mathbold{x}$ be an input vector. The 0-order half
permutation defined by $\mathbold{o}$ re-arranges its input so that the result
is the concatenation of $\mathbold{x}[\mathbold{o}]$ and
$\mathbold{x}[\neg\mathbold{o}]$. We denote the permutation matrix
implementing this half-permutation $P^{1}(\mathbold{o})$.

Note that if we define

$\mathbold{o}[i]=\begin{cases}0&\text{if
}\mathbold{x}[i]<\text{median}(\mathbold{x})\\\ 1&\text{otherwise}\end{cases}$

then $P^{1}(\mathbold{o})$ implements the first step of quicksort: it divides
the input in to two “buckets” (the top and bottom half of the output),
otherwise maintaining its order.

For subsequent steps we define higher order half-permutations. A $d$-th order
half-permutation is a permutation of $n$ elements, where $n$ is divisible by
$2^{d}$, defined by permutation matrix $P^{d}(\mathbold{o})$: a block-diagonal
matrix, with $(d-1)$-order half-permutions along its diagonal. Specifically,
the matrix covering elements $\left[m..m+n2^{-(d-1)}\right]$ of the diagonal,
is $P^{d-1}\left(\mathbold{o}\left[m..m+n2^{-(d-1)}\right]\right)$.

We can define $\mathbold{o}$ for the $d$-th step of quicksort as follows.
Divide the range $[1..n]$ into chunks of size $n2^{-(d-1)}$ and let $r(i)$ be
the chunk containing index $i$. We then define:

$\mathbold{o}(x)[i]=\begin{cases}0&\text{if
}\mathbold{x}[i]<\text{median}(\mathbold{x}[r(i)])\\\
1&\text{otherwise.}\end{cases}$

Assuming that our input has a length $n$ that is a power of 2, we can now
implement quicksort666Specifically, quicksort, with median pivots. In normal
sorting this is not a popular approach, but in our case, it is crucial to
guarantee that a depth of $\log_{2}n$ is sufficient to to sort the input. by
composing a total of $\log_{2}n$ half-permutations. Call the input
$\mathbold{x}_{0}$ and let

$\displaystyle\mathbold{x}_{i}$
$\displaystyle=P^{i}(\mathbold{o}(\mathbold{x}_{i-1}))\cdot\mathbold{x}_{i-1}{\;\text{.}}$
(1)

After applying $\log_{2}n$ half-permutations, $\mathbold{x}_{1+\log_{2}n}$
contains the sorted input.

To allow a meaningful gradient to propagate through through this computation,
we implement the half-permutations as sparse layers, parametrized by
$\mathbold{o}$. We replace the discrete, integer-based definition of
$\mathbold{o}$ by a continuous one:

$\mathbold{o}^{\prime}=\text{sigmoid}\left((\mathbold{x}_{i}-\text{median}(\mathbold{x}[r(i)]))C\right)$

Where $C$ is a hyperparameter set to 10 in all experiments. Note that as the
distance to the median grows (for instance if we learn to place the keys
further apart), $\mathbold{o}^{\prime}$ converges to $\mathbold{o}$.

We then use $\mathbold{o}^{\prime}$ to parametrize a sparse layer that
approximates $P^{d}(\mathbold{o}^{\prime})$ as follows. We sample $a$ random
binary vectors ${\mathbold{o}_{i}}$ representing valid half-permutations of
order $d$ by starting with the vector that represents the identity permutation
(note that this is different for each $d$) and permuting the values in each
chunk of size $n2^{-(d-1)}$ randomly.777Since permutations are costly to
compute in most deep learning frameworks, we sample a matrix of 500 000 random
permutations at initialization, and sample random rows from that. We also add
$\text{round}(\mathbold{o}^{\prime})$ to the sample.

We convert each $\mathbold{o}$ to a sequence of $\mathbold{r}(\mathbold{o})$
row indices, representing the nonzero elements of $P^{d}(\mathbold{o})$
(assuming that the columns are indexed sequentially, algorithm in the
appendix). Each such sequence $\mathbold{r}(\mathbold{o})$ is assigned
proportion

$p(\mathbold{o})=\prod_{i}\begin{cases}\mathbold{o}^{\prime}[i]&\text{if
}\mathbold{o}[i]=1\\\ 1-\mathbold{o}^{\prime}[i]&\text{otherwise.}\end{cases}$

Duplicate sequences $\mathbold{r}(\mathbold{o})$ are detected by the method
described in the appendix, and their proportion is set to zero. We assign this
proportion over all integer tuples generated from $\mathbold{o}$. We combine
the resulting index tuples for all binary vectors in the sample into a single
sparse matrix, with the assigned proportions as their values.

Finally, we normalize the proportions so that all columns in the resulting
sparse matrix sum to 1.

To see how the gradient propagates backwards, it is instructive to imagine the
case $n=1$. In this case the key network produces two keys, and the half-
permutation is either the identity matrix $\mathbold{I}$ or $1-\mathbold{I}$.
Let’s say we get $\mathbold{I}$ (the keys suggest the instances are already
ordered) and by distribution over sampled $\mathbold{o}_{i}$, the off-diagonal
elements become slightly higher than zero and the diagonal elements slightly
lower than 1. If these keys are incorrect (the instances should instead be
swapped), gradient descent will increase the off-diagonal elements and
decrease the diagonal elements. This means decreasing the proportion assigned
to $\mathbold{o}_{0}=(0,1)$ and increasing the proportion assigned to
$\mathbold{o}_{1}=(1,0)$. Since this is the result of Equation 3.3, gradient
descent pushes both keys closer to their median, and towards the center of the
sigmoid curve. Eventually they will swap place, and be pushed away from each
other.

To test this algorithm we devise the following experiment. We sample $n$
random 3-digit numbers (with $n$ a power of 2) and represent each by three
randomly sampled MNIST digits of the correct label. We pass these through a
key network which processes each digit individually using the same ConvNet,
concatenates their outputs and passes it through an MLP to produce a single
scalar key (details in the appendix).

We sort the digits using the scheme above and compare the outputs to the
sorted target, using binary cross-entropy as a loss function.888We clamp the
output to $(0,1)$ to avoid small floating-point inaccuracies. To evaluate, we
ignore the sorting network, generating only the key, and compare the
permutation required to sort the keys to the permutation required to sort the
digits. We report the error (out of 10 000 samples): the proportion of
instances for which the two permutations are not exactly the same.

Hyperparameters were chosen using a validation split of the MNIST training
data, with the test used used only for the final experiment.

Figure 6: Results of the sorting experiment. Error bars indicate the _standard
deviation_ over $r$ repeats of the experiment.

#### Intermediate loss

Simply comparing the input to its sorted counterpart works well for short
sequences, but for longer sequences we can enrich the loss by comparing
intermediate steps. et $d=1+\log_{2}n$ be the index of the last half-
permutation, let $\mathbold{x}_{i}$ be defined as in (1), and let
$\mathbold{t}_{d}$ be the sorted target. Feeding $\mathbold{t}_{d}$ through
the transposes of the half-permutations in reverse order should retrieve
$\mathbold{x}$ (if the keys are in the correct order). Let

$\displaystyle\mathbold{t}_{i-1}$
$\displaystyle={P^{i}(\mathbold{o}(\mathbold{x}_{i-1}))}^{T}\cdot\mathbold{t}_{i}{\;\text{.}}$

We now define the loss as the binary cross-entropy between $\mathbold{x}_{i}$
and $\mathbold{t}_{i}$ summed over all $i\in[1..d]$.

Figure 7 illustrates the intermediate steps at the start of learning. Note how
the intermediate losses provide guidance at each step: the final target row
shows that the first element should be 0, and the preceding target row shows
that the first two elements should each be mixtures of a 0 and a 1. The row
above shows that the first four elements (the first “bucket” in the quicksort
algorithm) should be mixtures of the first four digits.

We train in batches of 64, with a learning rate of 0.00005, on three-digit
numbers in instances of size 4, 8 and 16. For size $n$, we set $a=n$. The
results are shown in Figure 6.

We note that for size 4 instances, the method performs very well, reaching an
error below 10%. For size 8, the performance converges to a similar value, but
with greater variance, and for size 16 we reach a minimum of around 40% error.
We also note that these experiments took relatively long to run: a single run
for each size took on average 1h 40m, 7h 10m and 32h 14m respectively.

Whether the method in its current form can usefully be applied, depends on the
setting: for tasks that are easier than digit recognition, performance may
converge sooner, and we may be able to sort larger numbers of items. In other
settings, such as sorting by user preference for recommendation, sorting with
a medium amount of accuracy may already yield acceptable results.

Figure 7: An illustration of the intermediate loss for the task of sorting a
sequence of 8 single-digit numbers. The left side shows the input as it is
transformed (in the first step of training). The right side shows the target
being reverse-sorted.

##  4 Related work

Learning of sparse transformations has a long history. Approaches based on
parametrizing sparse transformations by dense weight vectors include the use
of loss terms like L1-regularization [16, 5, 18] and transformations like
Sparsemax [12] and Gumbel-Sinkhorn [13] that transform the dense input to
something closer to a sparse tensor. Sparsity in hidden units and other
representations has also been extensively studied [11, 17] and found to be
beneficial (whether our method may be effective in this area is a matter of
future work).

Another way to induce sparsity in neural networks is through _pruning_ :
enforcing sparsity, and actively setting low values to zero [24, 4, 5]. In
this context sparsity is often employed as a way of compressing neural
networks: reducing their descriptive complexity while maintaining performance.

The notion of adaptivity, making the weights of a transformation conditional
on the input, or reparametrizing the weights to constrain the structure, goes
back at least to [20] with more recent examples including [3, 9, 21].

Our method can also be cast as a way to learn the structure or topology of a
neural network along with its weights. Most existing methods for in this area
use evolutionary methods [10] or reinforcement learning [1, 26]. Approaches
that do operate purely through backpropagation (apart from the hypernetworks
already mentioned) include [22], which introduces a trainable ReLU unit to
dynamically disable nodes, and differentiable plasticity [14], which similarly
uses a per-connection relevance weight, derived using Hebbian principles, to
allow connections to be ignored. To the best of our knowledge, the sparse
layer is the first that allows sparse connections to be learned without a
dense parametrization.

##  5 Conclusion

We have introduced a mechanism for learning sparse transformations, using
sparse datastructures. It works by defining a simple probability distribution
over the indices of the matrix. Instead of sampling one deterministic matrix,
as our REINFORCE baseline does, we sample multiple sparse connections within
the same matrix, and distribute the value over multiple connections. In other
words: where the stochastic nodes of REINFORCE keep the topology of the
computation graph fixed and sample random values, we sample a random
computation graph, which consists entirely of deterministic nodes. The benefit
is that the gradient which is backpropagated matches the forward computation
exactly, and accurately distributes the loss.

###  5.1 Limitations and future work

In our experiments, we have shown primarily that the sparse layer can be
learned effectively at a certain scale, and works when embedded in larger
architectures. Further research is required to fully map out the method’s
potential and pitfalls.

The model seems to have a strong trade-off between the sparsity of sampled
index tuples and the number of iterations required for the model to converge.
In many settings, especially when the model is entirely unconstrained,
sampling a sparse proportion of the total matrix may lead to infeasibly long
training times. Whether a suitable tradeoff can be found depends on the task,
and on whether an effective constraint for the sparse structure can be
devised.

We have not yet shown that the sparse layer is effective at a scale where the
matrices in question could absolutely not be embedded in a dense
datastructure. Early experiments show that learning can be performed at this
scale, although convergence to a very precise solution (as in the identity
experiments) is difficult to attain.

While we have presented our method in the context of sparsely connected tensor
contractions, this may not be the most generic formulation. Utimately, the
principle applies to any situation where single, unfeasibly large computation
graph can be explored by defining a probability distribution on sparse
subgraphs. If we can reasonably expect such a distribution to converge to a
single subgraph, we can train a model without ever seeing the whole
computation graph. This view may lead to generalizations beyond sparse tensor
operations, and to a more formal treatment of the method, and its properties.

#### Acknowledgements

This publication was supported by the Amsterdam Academic Alliance Data Science
(AAA-DS) Program Award to the UvA and VU Universities. All experiments were
executed on the DAS-5 cluster [2]; we thank the administrators for their kind
assistance.

## References

  * [1] Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar.  Designing neural network architectures using reinforcement learning.  arXiv preprint arXiv:1611.02167, 2016.
  * [2] Henri Bal, Dick Epema, Cees de Laat, Rob van Nieuwpoort, John Romein, Frank Seinstra, Cees Snoek, and Harry Wijshoff.  A medium-scale distributed system for computer science research: Infrastructure for the long term.  Computer, (5):54–63, 2016.
  * [3] David Ha, Andrew Dai, and Quoc V Le.  Hypernetworks.  arXiv preprint arXiv:1609.09106, 2016.
  * [4] Song Han, Huizi Mao, and William J Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  arXiv preprint arXiv:1510.00149, 2015.
  * [5] Song Han, Jeff Pool, John Tran, and William Dally.  Learning both weights and connections for efficient neural network.  In Advances in neural information processing systems, pages 1135–1143, 2015.
  * [6] Charles AR Hoare.  Quicksort.  The Computer Journal, 5(1):10–16, 1962.
  * [7] Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax.  arXiv preprint arXiv:1611.01144, 2016.
  * [8] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [9] David Krueger, Chin-Wei Huang, Riashat Islam, Ryan Turner, Alexandre Lacoste, and Aaron Courville.  Bayesian hypernetworks.  arXiv preprint arXiv:1710.04759, 2017.
  * [10] Ilya Loshchilov and Frank Hutter.  Cma-es for hyperparameter optimization of deep neural networks.  arXiv preprint arXiv:1604.07269, 2016.
  * [11] Alireza Makhzani and Brendan Frey.  K-sparse autoencoders.  arXiv preprint arXiv:1312.5663, 2013.
  * [12] Andre Martins and Ramon Astudillo.  From softmax to sparsemax: A sparse model of attention and multi-label classification.  In International Conference on Machine Learning, pages 1614–1623, 2016.
  * [13] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek.  Learning latent permutations with gumbel-sinkhorn networks.  arXiv preprint arXiv:1802.08665, 2018.
  * [14] Thomas Miconi, Jeff Clune, and Kenneth O Stanley.  Differentiable plasticity: training plastic neural networks with backpropagation.  arXiv preprint arXiv:1804.02464, 2018.
  * [15] Volodymyr Mnih, Nicolas Heess, Alex Graves, et al.  Recurrent models of visual attention.  In Advances in neural information processing systems, pages 2204–2212, 2014.
  * [16] Jiquan Ngiam, Zhenghao Chen, Sonia A Bhaskar, Pang W Koh, and Andrew Y Ng.  Sparse filtering.  In Advances in neural information processing systems, pages 1125–1133, 2011.
  * [17] Bruno A Olshausen and David J Field.  Sparse coding with an overcomplete basis set: A strategy employed by v1?  Vision research, 37(23):3311–3325, 1997.
  * [18] Dae Hoon Park, Chiu Man Ho, and Yi Chang.  Achieving strong regularization for deep neural networks.  2018\.
  * [19] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  2017\.
  * [20] Jürgen Schmidhuber.  A self-referential weight matrix.  In ICANN’93, pages 446–450. Springer, 1993.
  * [21] Shinichi Shirakawa, Yasushi Iwata, and Youhei Akimoto.  Dynamic optimization of neural network structures using probabilistic modeling.  arXiv preprint arXiv:1801.07650, 2018.
  * [22] Suraj Srinivas and R Venkatesh Babu.  Learning neural network architectures using backpropagation.  arXiv preprint arXiv:1511.05497, 2015.
  * [23] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.  Pointer networks.  In Advances in Neural Information Processing Systems, pages 2692–2700, 2015.
  * [24] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li.  Learning structured sparsity in deep neural networks.  In Advances in Neural Information Processing Systems, pages 2074–2082, 2016.
  * [25] Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Machine learning, 8(3-4):229–256, 1992.
  * [26] Barret Zoph and Quoc V Le.  Neural architecture search with reinforcement learning.  arXiv preprint arXiv:1611.01578, 2016.

##  Appendix A Appendix

###  A.1 Hyperparameters and other experimental details

All experiments were executed on a single compute node, containing a single
GTX TitanX GPU (Maxwell generation) with 12 GB on-board memory, dual 8-core
2.4 GHz (Intel Haswell E5-2630-v3) CPUs and 64 GB memory.

All experiments were implemented in Pytorch 0.4 [19]. The Adam optimizer [8]
was used in all experiments. Standard neural network layers were initialized
using the Pytorch defaults. Specifically, uniform Glorot initialization for
fully connected layers and convolution layers. No dropout or early stopping
were used in any experiments. No weight decay, clipping or regularization was
used.

#### Identity

A batch size of 64 is used in all experiments. For the baseline, we test the 9
learning rates $0.1,0.05,0.01,\ldots,0.00001$ and report the best result. For
the sparse layer, all hyperparameters are tuned by hand. In all cases this
resulted in a learning rate of 0.005, except for 0.001 for the size-64
experiment. For the size $n$ of 8, 16, 32 and 64 experiments, we set
$(a_{l},a_{g})$ to $(1,2)$, $(2,2)$, $(2,8)$ and $(2,10)$ respectively. The
sampling region $(l_{1},l_{2})$ is set to $(\log_{2}n,\log_{2}n)$.

#### Attention

type | out ch./size | kernel | padding | activation
---|---|---|---|---
Conv2d | 32 | 3,3 | 1 | ReLU
Conv2d | 32 | 3,3 | 1 | ReLU
MaxPool |  | 4, 4 | 0 |
Conv2d | 64 | 3,3 | 1 | ReLU
Conv2d | 64 | 3,3 | 1 | ReLU
MaxPool |  | 2, 2 | 0 |
Conv2d | 128 | 3,3 | 1 | ReLU
Conv2d | 128 | 3,3 | 1 | ReLU
Flatten |  |  |  |
Linear | 512 |  |  | ReLU
Linear | 512 |  |  | ReLU
Linear | $4\cdot g$ |  |  |
Table 2: Architecture of the source network for the attention experiment. $g$
is the number of glimpses used.

Table 2 shows the architecture of the source network. The glimpses are
flattened, concated and fed to a 2-layer MLP with a 128-unit ReLU activated
hidden layer, and a 10-unit softmax output layer. We use binary cross-entropy
loss. We train for 70 epochs, using a batch size of 128 and a learning rate of
0.0001. We set $a_{g}=16$, $a_{l}=32$ and use a sampling region of $(20,20)$.

In rare cases, the 1-glimpse model enters a state with all elements of
$\mathbold{D}$ at high values, at which point the gradient through the sigmoid
function vanishes, and training fails. Such cases can be eliminated by
resetting the parameters, or re-running the model with a different random
seed. This behavior has not been observed for the network with multiple
glimpses.

#### Sorting

Convnet |  $(1,28,28)$ input |  |  |
---|---|---|---|---
type | out ch./size | kernel | padding | activation
Conv2d | 16 | 3,3 | 1 | ReLU
Conv2d | 16 | 3,3 | 1 | ReLU
Conv2d | 16 | 3,3 | 1 | ReLU
BatchNorm2d |  |  |  |
MaxPool |  | 2, 2 | 0 |
Conv2d | 64 | 3,3 | 1 | ReLU
Conv2d | 64 | 3,3 | 1 | ReLU
Conv2d | 64 | 3,3 | 1 | ReLU
BatchNorm2d |  |  |  |
MaxPool |  | 2, 2 | 0 |
Conv2d | 128 | 3,3 | 1 | ReLU
Conv2d | 128 | 3,3 | 1 | ReLU
Conv2d | 128 | 3,3 | 1 | ReLU
BatchNorm2d |  |  |  |
MaxPool |  | 2, 2 | 0 |
Flatten |  |  |  |
Linear | 256 |  |  | ReLU
Linear | 128 |  |  | ReLU
Linear | 8 |  |  |
MLP |  $(8\cdot d)$ input |  |  |
Linear | 256 |  |  | ReLU
Linear | 1 |  |  |
Table 3: Architecture of the key network. Biases were disabled in layers
directly preceding batch normalization. Each digit is fed through the ConvNet
separately. The results are concatenated and fed through the MLP to produce a
single key for the three-digit number.

Table 3 shows the architecture of the key extraction network.

###  A.2 Implementation notes

#### Flattening tensors

Sparse tensor support is limited in many frameworks, and it may not be
possible to implement (2.1) as it is described here. In such cases, the
operation can be implemented by flattening $\mathbold{x}$ into a vector
$\mathbold{x}^{\prime}$, flattening $\mathbold{W}$ into a matrix
$\mathbold{W}^{\prime}$ and reshaping the resulting vector
$\mathbold{y}^{\prime}=\mathbold{W}^{\prime}x^{\prime}$ into a tensor
$\mathbold{y}$. Here, we provide some details on how to implement such an
operation. Let $\mathbold{x}\in{\mathbb{R}}^{n_{1}\times\ldots\times n_{N}}$.
Let $fl(\mathbold{x})=\mathbold{x}^{\prime}$ be the canonical “flatten”
function, defined so that $\mathbold{x}^{\prime}$ is a vector of
$i_{1}\times\ldots\times i_{n}$ elements, with

$\mathbold{x}[a_{1},...,a_{n}]=\mathbold{x}^{\prime}[fi(\\{a_{i}\\},\\{n_{i}\\})]\,\,\,\,\text{with}\,\,\,\,fi(\\{a_{i}\\},\\{n_{i}\\})=\sum_{i}a_{i}\prod_{j=i+1}^{N}n_{j}{\;\text{.}}$

Let $rs(\mathbold{x}^{\prime},(i_{1},\ldots,i_{n}))$ be the inverse of
$fl(\cdot)$. We first compute the index-tuples and values for the regular
sparse tensor as before. We then translate each index tuple in
$\mathbold{D}^{\prime}$ to an index pair for $W^{\prime}$. If the original
index tuple is $(b_{1},...,b_{m},a_{1},...,a_{n})$, we translate this to
$(fi(\\{b_{j}\\},\\{m_{j}\\}),fi(\\{a_{i}\\},\\{n_{i}\\}))$ and construct a
sparse matrix $\mathbold{W}^{\prime}$ for these indices (with the original
values). We compute the vector
$\mathbold{y}^{\prime}=\mathbold{W}^{\prime}\mathbold{x}^{\prime}$, and
reshape it to retrieve $\mathbold{y}$ as
$\mathbold{y}=rs(\mathbold{y}^{\prime},(m_{1},\ldots,m_{M}))$.

Support for a batch dimension must also be implemented carefully: in the
adaptive setting, each instance generates a different sparse matrix. In our
implementation we effectively flatten a batch of $b$ sparse $n\times m$
matrices into a single larger $bn\times bm$ matrix with the matrices of the
batch arranged along the diagonal. This allows us to compute the batch using a
single sparse matrix multiplication.

Note that the translation from real to integer indices happens in the original
tensor rank. The flattening of the index tuples only happens once the integer
tuples have been computed.

#### Gradient accumulation

In a naive implementation, distributing the probabilities of all continuous
tuples over all sampled integer tuples and normalizing requires a dense matrix
that is likely larger than $\mathbold{W}$. If $\mathbold{W}$ is large enough
to make this infeasible, we compute the gradient in multiple passes. For each
pass, we compute the gradient for only a subset of the continuous tuples, in a
complete forward and backward pass. The computation graph is then cleared and
the process is repeated for the next subset of continuous tuples (keeping the
sample of integer tuples the same), accumulating the gradients over the
parameters.

#### Detecting duplicates

For efficient computation of the sparse layer, we have found that the best
approach is to sample the integer index tuples with replacement, uniformly
over a region, and to set the probability of duplicate tuples to zero. This
ensures that tuples do not receive extra probability mass from being sampled
twice, yet allows us to sample with replacement, with is more efficient.

For a given matrix $\mathbold{D}^{\prime}\in{\mathbb{R}}^{k\times r}$ of
sampled integer tuples, we convert each row $(d_{1},\ldots,d_{r})$ to a unique
integer using the Cantor tuple function:

$\displaystyle u(d_{1},d_{2})$
$\displaystyle=\frac{1}{2}(d_{1}+d_{2})(d_{1}+d_{2}+1)+d_{2}$ $\displaystyle
u(d_{1},\ldots,d_{r})$
$\displaystyle=u\left(d_{1},u(d_{2},\ldots,d_{r})\right)$

We then (non-differentiably) sort the resulting vector of unique indices,
$\mathbold{u}$, and compare it to a vector $\mathbold{u}^{\prime}$ defined as
$\mathbold{u}^{\prime}[i]=\mathbold{u}^{\prime}[i+1]$, to create a binary
vector that masks all repeated occurrences of the same tuple (but not the
first). We reverse the sort to apply the mask to the original tuples.

Finally, we use this mask to set the probabilities corresponding to these
tuples to zero. It is important to do this _before_ normalizing the
probabilities, or they will not sum to $1$.

#### Computing $P^{d}(\mathbold{o})$ from $\mathbold{o}$

$P^{d}(\mathbold{o})\in{\mathbb{R}}^{n\times n}$is a permutation matrix: it
has a unique nonzero value in each column and in each row, each taking value
1. We will compute a sequence $\mathbold{r}(\mathbold{o})$ such that the index
tuples $(\mathbold{r}(\mathbold{o})_{i},i)$ with $i\in[1..n]$ represent the
nonzero elements of $P^{d}(\mathbold{o})$. Algorithm 2 computes this sequence
from $\mathbold{o}$.

Algorithm 2 Compute $\mathbold{r}(\mathbold{o})$ from $\mathbold{o}$. The
function $\text{cumsum}(x,c)$ computes the cumulative sum over $x$, resetting
after every $c$ elements.

$\mathbold{u}=[1..2^{d}]\cdot n2^{-d}+n2^{-(d+1)}$ # starting indices of upper
buckets
$\mathbold{l}=[1..2^{d}]\cdot n2^{-d}$ # starting indices of lower buckets

$\mathbold{c}_{\mathbold}{u}\leftarrow\text{cumsum}(\mathbold{o},n2^{-d})$
$\mathbold{c}_{\mathbold}{l}\leftarrow\text{cumsum}(1-\mathbold{o},n2^{-d})$

return
$\mathbold{r}\leftarrow\mathbold{o}\cdot(\mathbold{c}_{\mathbold}{u}-1)+(\mathbold{o}-1)\cdot(\mathbold{c}_{\mathbold}{l}-1)$


# Homology manifolds and euclidean bundles

Fabian Hebestreit  Universität Bielefeld, Fakultät für Mathematik, 33501
Bielefeld, Germany<EMAIL_ADDRESS>,  Markus Land  Ludwig-
Maximilians-Universität München, Mathematisches Institut, 80333 München,
Germany<EMAIL_ADDRESS>,  Michael Weiss  Universität Münster,
Mathematisches Institut, 48149 Münster, Germany<EMAIL_ADDRESS>and
Christoph Winges  Ludwig-Maximilians-Universität München, Mathematisches
Institut, 80333 München, Germany<EMAIL_ADDRESS>
###### Abstract.

We construct a Poincaré complex whose periodic total surgery obstruction
vanishes but whose Spivak normal fibration does not admit a reduction to a
stable euclidean bundle. This contradicts the conjunction of two claims in the
literature: Namely, on the one hand that a Poincaré complex with vanishing
periodic total surgery obstruction is homotopy equivalent to a homology
manifold, which appears in work of Bryant–Ferry–Mio–Weinberger, and on the
other that the Spivak normal fibration of a homology manifold always admits a
reduction to a stable euclidean bundle, which appears in work of
Ferry–Pedersen.

FH, MW and CW were supported by the German Research Foundation (DFG) through
the collaborative research centres “Integral structures in Geometry and
Representation theory” (grant no. TRR 358–491392403) at the University of
Bielefeld, “Geometry: Deformations and Rigidity” (grant no. SFB
1442–427320536) at the University of Münster and “Higher invariants” (grant
no. SFB 1085–224262486) at the University of Regensburg, respectively. MW is
furthermore a member of the cluster “Mathematics Münster: Dynamics-Geometry-
Structure” (grant no. EXC 2044–390685587) funded by the DFG at the University
of Münster.

In his celebrated work on algebraic surgery theory, Ranicki associates to an
oriented Poincaré duality complex $X$ an invariant, the total surgery
obstruction $\mathrm{tso}(X)$ of $X$, which for $\dim(X)\geq 5$ vanishes if
and only if $X$ is realised by a closed, topological manifold [Ran79]. It
encodes in a single invariant whether the Spivak normal fibration of $X$
admits a reduction to a stable euclidean bundle, and if so, whether any such
reduction gives rise to a degree one normal map with trivial surgery
obstruction. Through Siebenmann’s famous periodicity mistake and the
consequent hunt for the missing manifolds, the question arose whether a
similar total surgery obstruction for homology manifolds exists. This was
finally established in [BFMW96] in terms of (what we shall refer to as) the
periodic total surgery obstruction $\overline{\mathrm{tso}}(X)$ of $X$, a
slightly coarser variant of Ranicki’s $\mathrm{tso}(X)$. Based on earlier work
of Ferry and Pedersen [FP95] that the Spivak normal fibration of a homology
manifold always admits a reduction to a stable euclidean bundle, they proved
that $\overline{\mathrm{tso}}(X)=0$ if and only if $X$ is realised by a
homology manifold, and established a surgery exact sequence for homology
manifolds.

The main goal of this note is to show that the results of [BFMW96] and [FP95]
are incompatible by constructing Poincaré complexes $X$ with
$\overline{\mathrm{tso}}(X)=0$ but whose Spivak normal fibration do not admit
reductions to euclidean bundles.

######  Acknowledgements.

The authors heartily thank Shmuel Weinberger for helpful discussions.

######  Preliminaries.

We will need the following facts surrounding the visible symmetric signatures
and (periodic) total surgery obstructions of oriented Poincaré complexes. In
this part, $X$ will usually refer to a general space, whereas $P$ refers to an
oriented Poincaré complex.

  1. (i)

For a space $X$, we write
$\mathrm{L}^{\mathrm{vr}}(X)=\mathrm{L}((\mathscr{D}(\mathbb{Z})_{/X})^{\mathrm{f}},\Qoppa^{\mathrm{vr}}_{\epsilon})$
for its _visible quadratic_ (the case $\mathrm{r}=\mathrm{q}$) and _visible
symmetric_ (the case $\mathrm{r}=\mathrm{s}$) L-theory of Weiss and Ranicki,
see [Ran92, Section 9] where the visible symmetric L-groups are denoted
$VL^{*}(\mathbb{Z},X)$ in case $X$ is represented by a finite simplicial
complex and [CDH+23, Variant 4.4.15] for a general treatment. Here
$(\mathscr{D}(\mathbb{Z})_{/X})^{\mathrm{f}}$ denotes the full subcategory of
the compact objects $(\mathscr{D}(\mathbb{Z})_{/X})^{\omega}$ of
$\mathscr{D}(\mathbb{Z})_{/X}$ on finite objects, i.e. those whose $K$-theory
class lies in the image of
$\mathrm{K}_{0}(\mathbb{Z})\to\mathrm{K}_{0}(\mathbb{Z}\pi_{1}(X))\cong\mathrm{K}_{0}((\mathscr{D}(\mathbb{Z})_{/X})^{\omega})$
and $\epsilon$ denotes the trivial rank $0$ spherical fibration over $X$ to
align with notation from [CDH+23, CDH+20a]. The visible L-spectra are
functorial in $X$; for a map $f\colon X\to Y$ we write
$f_{!}\colon\mathrm{L}^{\mathrm{vr}}(X)\to\mathrm{L}^{\mathrm{vr}}(Y)$ for the
induced map. We also have
$\Qoppa^{\mathrm{vq}}_{\epsilon}=\Qoppa^{\mathrm{q}}_{\epsilon}$, so that
visible quadratic L-theory is simply quadratic L-theory. Moreover, the
algebraic $\pi$-$\pi$-theorem says that for $X$ connected, the map $X\to
B\pi_{1}(X)$ induces an isomorphism in visible quadratic L-theory, see [Ran92,
Section 10] and [CDH+20b, Corollary 1.2.33]. The cofibre of the map
$\mathrm{L}^{\mathrm{vq}}(X)\to\mathrm{L}^{\mathrm{vs}}(X)$ is denoted
$\mathrm{L}^{\mathrm{vn}}(X)$ and called the _visible normal_ L-theory of $X$.
In classical terminology, the choice of working with finite objects
corresponds to choosing decoration “h” for the L-spectra.

  2. (ii)

We have $\mathrm{L}^{\mathrm{vq}}(\ast)=\mathrm{L}^{\mathrm{q}}(\mathbb{Z})$,
$\mathrm{L}^{\mathrm{vs}}(\ast)=\mathrm{L}^{\mathrm{s}}(\mathbb{Z})$, and
$\mathrm{L}^{\mathrm{vn}}(\ast)=\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$, the
usual quadratic, symmetric, and normal L-theory spectrum of the integers, the
latter two of which are ring spectra. In fact, they are
$\mathbb{E}_{\infty}$-ring spectra, but this will not matter for the purposes
of this paper. From
$\mathrm{L}^{\mathrm{n}}_{0}(\mathbb{Z})\cong\mathbb{Z}/8\mathbb{Z}$ we see
that $\mathrm{L}^{\mathrm{n}}(\mathbb{Z})[\tfrac{1}{2}]=0$ so that the map
$\mathrm{L}^{\mathrm{q}}(\mathbb{Z})[\tfrac{1}{2}]\to\mathrm{L}^{\mathrm{s}}(\mathbb{Z})[\tfrac{1}{2}]$
is an equivalence. Note also that $\mathrm{L}^{\mathrm{q}}(\mathbb{Z})$ does
not refer to the $\mathrm{q}$th symmetric L-group as it would in Ranicki’s
notation.

  3. (iii)

When $P$ is an oriented Poincaré complex of dimension $d$, there is a
canonical point $\sigma^{\mathrm{vs}}(P)$ in
$\Omega^{d}\mathrm{L}^{\mathrm{vs}}(P)$, called the _visible symmetric
signature_ of $P$, see [Ran92, Example 9.13] and [CDH+23, Corollary 4.4.20].
Its image $\sigma^{\mathrm{vn}}(P)$ in $\Omega^{d}\mathrm{L}^{\mathrm{vn}}(P)$
is called the _visible normal signature_ of $P$. These data fit into the
following commutative square whose left vertical arrow is the canonical
forgetful map between oriented Poincaré bordism and oriented normal bordism
[Ran79].

${\Omega^{\mathrm{SP}}(X)}$${\mathrm{L}^{\mathrm{vs}}(X)}$${\Omega^{\mathrm{SN}}(X)}$${\mathrm{L}^{\mathrm{vn}}(X)}$

The upper horizontal map takes the (Poincaré bordism class of a) map $f\colon
P\to X$ to $f_{!}(\sigma^{\mathrm{vs}}(P))$. In particular
$\sigma^{\mathrm{vs}}(P)$ is the image of $[\mathrm{id}_{P}]$ in
$\Omega^{\mathrm{SP}}_{n}(P)$, see [Ran92, Section 19]. Oriented normal
bordism satisfies excision giving an equivalence
$\Omega^{\mathrm{SN}}(X)\simeq X\otimes\mathrm{MSG}$, and the lower horizontal
arrow for $X=\ast$ is called _Ranicki’s normal orientation_ , while the top
horizontal arrow is often referred to as the _Sullivan–Ranicki orientation_.

  4. (iv)

For an oriented closed topological manifold $M$, we may view
$[\mathrm{id}_{M}]$ as an element of $\Omega^{\mathrm{STop}}_{n}(M)$, the
oriented bordism of topological manifolds. By topological transversality
[KS77], $\Omega^{\mathrm{STop}}(X)$ is equivalent to $X\otimes\mathrm{MSTop}$
for any space $X$, showing that $\sigma^{\mathrm{vs}}(M)$ canonically lifts
along the assembly map
$M\otimes\mathrm{L}^{\mathrm{s}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{vs}}(M)$ in
this case.

  5. (v)

To better incorporate the orientation behaviour of the above elements, one
considers
$\mathrm{L}^{\mathrm{n}}_{1/2}(\mathbb{Z})=\mathbb{Z}\times_{\mathbb{Z}/8\mathbb{Z}}\tau_{\geq
0}\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$, the _1/2-connective normal L-theory_.
We then obtain canonical maps
$\mathrm{MSG}\to\mathrm{L}^{\mathrm{n}}_{1/2}(\mathbb{Z})$ as well as
$\tau_{\geq
0}\mathrm{L}^{\mathrm{s}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{n}}_{1/2}(\mathbb{Z})$
lifting the normal orientation
$\mathrm{MSG}\to\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$ and the canonical
projection
$\mathrm{L}^{\mathrm{s}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$.

  6. (vi)

The assembly map in visible normal L-theory is an equivalence:
$X\otimes\mathrm{L}^{\mathrm{n}}(\mathbb{Z})\xrightarrow{\simeq}\mathrm{L}^{\mathrm{vn}}(X)$,
see [Ran92, Section 15]. We then denote by $\mathrm{L}^{\mathrm{vs}}_{1/2}(X)$
the pullback of
$\mathrm{L}^{\mathrm{vs}}(X)\to\mathrm{L}^{\mathrm{vn}}(X)\leftarrow
X\otimes\mathrm{L}^{\mathrm{n}}_{1/2}(\mathbb{Z})$ and note that above square
refines to the following square.

${\Omega^{\mathrm{SP}}(X)}$${\mathrm{L}^{\mathrm{vs}}_{1/2}(X)}$${\Omega^{\mathrm{SN}}(X)}$${\mathrm{L}^{\mathrm{vn}}_{1/2}(X)}$

Hence, the visible symmetric signature $\sigma^{\mathrm{vs}}(P)$ canonically
lifts to a point $\sigma^{\mathrm{vs}}_{1/2}(P)$ of
$\mathrm{L}^{\mathrm{vs}}_{1/2}(P)$. Its image $\sigma^{\mathrm{vn}}_{1/2}(P)$
in $\mathrm{L}^{\mathrm{vn}}_{1/2}(P)$ is called the _normal fundamental class
of $P$_.

  7. (vii)

For a space $X$, we write
${\overline{\mathscr{S}}}^{\mathrm{alg}}(X)=\operatorname*{cofib}[X\otimes\mathrm{L}^{\mathrm{s}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{vs}}(X)]$
for the cofibre of the assembly map and
$\mathscr{S}^{\mathrm{alg}}(X)=\operatorname*{cofib}[X\otimes\tau_{\geq
0}\mathrm{L}^{\mathrm{vs}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{s}}_{1/2}(X)]$.
There is a canonical map
$\mathscr{S}^{\mathrm{alg}}(X)\to{\overline{\mathscr{S}}}^{\mathrm{alg}}(X)$
induced by the maps $\tau_{\geq
0}\mathrm{L}^{\mathrm{s}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{s}}(\mathbb{Z})$
and $\mathrm{L}^{\mathrm{vs}}_{1/2}(X)\to\mathrm{L}^{\mathrm{vs}}(X)$.

  8. (viii)

The image of $\sigma^{\mathrm{vs}}_{1/2}(P)$ under the canonical map
$\Omega^{d}\mathrm{L}^{\mathrm{vs}}_{1/2}(P)\to\Omega^{d}\mathscr{S}^{\mathrm{alg}}(P)$
is denoted $\mathrm{tso}(P)$ and called the _total surgery obstruction_ of
$P$. By point (iv) above, $\mathrm{tso}(P)$ vanishes in case $P$ is homotopy
equivalent to a closed topological manifold, and the main result of [Ran79]
says that for $\dim(P)\geq 5$, the converse holds as well.

The image $\overline{\mathrm{tso}}(P)$ of $\mathrm{tso}(P)$ under the
canonical map
$\Omega^{d}\mathscr{S}^{\mathrm{alg}}(P)\to\Omega^{d}{\overline{\mathscr{S}}}^{\mathrm{alg}}(P)$,
the _periodic total surgery obstruction_ , is equally the image of
$\sigma^{\mathrm{vs}}(P)$ under the canonical map
$\Omega^{d}\mathrm{L}^{\mathrm{vs}}(P)\to\Omega^{d}{\overline{\mathscr{S}}}^{\mathrm{alg}}(P)$.
[BFMW96, Main theorem] says that for $\dim(P)\geq 6$,
$\overline{\mathrm{tso}}(P)$ is a complete obstruction for $P$ being homotopy
equivalent to a closed homology manifold. Our results below imply that in this
generality, the argument given in loc. cit. is not applicable, see also
[BFMW24].

  9. (ix)

As a consequence of the fact that visible normal L-theory is excisive and the
above definitions, there are equivalences
${\overline{\mathscr{S}}}^{\mathrm{alg}}(X)\simeq\operatorname*{cofib}[X\otimes\mathrm{L}^{\mathrm{q}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{vq}}(X)]$
as well as
$\mathscr{S}^{\mathrm{alg}}(X)=\operatorname*{cofib}[X\otimes\tau_{\geq
1}\mathrm{L}^{\mathrm{q}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{vq}}(X)]$. Indeed,
to see the latter, we note that there is the following commutative diagram

${X\otimes\tau_{\geq
0}\mathrm{L}^{\mathrm{s}}(\mathbb{Z})}$${X\otimes\mathrm{L}^{\mathrm{n}}_{1/2}(\mathbb{Z})}$${\mathrm{L}^{\mathrm{vs}}(X)}$${\mathrm{L}^{\mathrm{vn}}(X)}$

whose induced map from the top left corner to the pullback is the canonical
map $X\otimes\tau_{\geq
0}\mathrm{L}^{\mathrm{s}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{vs}}_{1/2}(X)$.
The claimed description of its cofibre then follows from the canonical
equivalence $\tau_{\geq
1}\mathrm{L}^{\mathrm{q}}(\mathbb{Z})\simeq\operatorname*{fib}[\tau_{\geq
0}\mathrm{L}^{\mathrm{s}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{n}}_{1/2}(\mathbb{Z})]$.

  10. (x)

The image $\mathrm{ro}(P)$ of $\mathrm{tso}(P)$ under the boundary map
$\Omega^{d}\mathscr{S}^{\mathrm{alg}}(P)\to\Omega^{d-1}[P\otimes\tau_{\geq
1}\mathrm{L}^{\mathrm{q}}(\mathbb{Z})]$, the _reduction obstruction_ , is a
complete obstruction for the Spivak normal fibration of $P$ to admit a
reduction to a stable euclidean bundle [Ran79]. We denote by
$\overline{\mathrm{ro}}(P)$ the image of $\mathrm{ro}(P)$ under the canonical
map induced by $\tau_{\geq
1}\mathrm{L}^{\mathrm{q}}(\mathbb{Z})\to\mathrm{L}^{\mathrm{q}}(\mathbb{Z})$.
Note that $\overline{\mathrm{ro}}(P)$ is then also the image of
$\overline{\mathrm{tso}}(P)$ under the boundary map
$\Omega^{d}{\overline{\mathscr{S}}}^{\mathrm{alg}}(P)\to\Omega^{d-1}[P\otimes\mathrm{L}^{\mathrm{q}}(\mathbb{Z})]$.

  11. (xi)

Using the above, Ranicki [Ran79] shows that the space of paths from
$\mathrm{tso}(P)$ to $0$ inside
$\Omega^{\infty+d}\mathscr{S}^{\mathrm{alg}}(P)$ is canonically equivalent to
the topological manifold block structure space $\widetilde{\mathscr{S}}(P)$.
In particular, the topological block structure space
$\widetilde{\mathscr{S}}(M)$ of a topological manifold $M$ identifies
canonically with $\Omega^{\infty+d+1}\mathscr{S}^{\mathrm{alg}}(M)$. Likewise,
[BFMW96] ought to give an identification of the homology manifold block
structure space $\widetilde{\mathscr{S}}^{H}(P)$ with the space of paths from
$\overline{\mathrm{tso}}(P)$ to $0$ inside
$\Omega^{\infty+d}{\overline{\mathscr{S}}}^{\mathrm{alg}}(P)$.

Again, our results below imply that this last claim suffers from the defect
indicated in point (viii): Even its consequence on $\pi_{0}$ currently relies
on the existence of euclidean normal bundles for homology manifolds, see
[BFMW24].

Before coming to our main results, the construction of certain Poincaré
complexes, we prove the following positive result about the existence of
euclidean reductions of Spivak normal fibrations of oriented Poincaré
complexes.

######  1 Proposition.

Let $X$ be an oriented $d$-dimensional Poincaré complex such that
$\overline{\mathrm{ro}}(X)=0$. Then the following statements are equivalent:

  1. (i)

The Spivak normal fibration of $X$ admits a reduction to a stable euclidean
bundle,

  2. (ii)

there exists a degree one map $M\to X$ where $M$ is an oriented closed
topological manifold, and

  3. (iii)

the fundamental class $[X]\in H_{d}(X;\mathbb{Z}[\tfrac{1}{2}])$ lifts to a
fundamental class in $\mathrm{ko}_{d}(X)[\tfrac{1}{2}]$.

###### Proof.

An argument of Sullivan’s shows that (i) implies that there exists a degree
one _normal_ map $M\to X$ for some closed topological manifold $M$, see
[Wal99, Prop. 10.2] or [LM24, Theorem 7.19] for the smooth case. Using
topological transversality [KS77] the same argument applies to the topological
case. In particular, (i) implies (ii). Given (ii), we find that $[M\to X]$
determines an element of $\mathrm{MSTop}_{d}(X)$ which lifts the fundamental
class $[X]\in H_{d}(X;\mathbb{Z})$. In particular, after inverting $2$, one
may use the Sullivan–Ranicki orientation
$\mathrm{MSTop}[\tfrac{1}{2}]\to\tau_{\geq
0}\mathrm{L}^{\mathrm{s}}(\mathbb{Z})[\tfrac{1}{2}]\simeq\mathrm{ko}[\tfrac{1}{2}]$
to lift the fundamental class in $H_{d}(X;\mathbb{Z}[\tfrac{1}{2}])$ to
$\mathrm{ko}_{d}(X)[\tfrac{1}{2}]$. See [LN18, Corollary 5.4 & following
Remark] for an equivalence
$\mathrm{L}^{\mathrm{s}}(\mathbb{Z})[\tfrac{1}{2}]\simeq\mathrm{KO}[\tfrac{1}{2}]$
of $\mathbb{E}_{\infty}$-ring spectra and [LNS23, Section 8] for perspectives
on the Sullivan–Ranicki orientation and general information about
$\pi_{0}\mathrm{Map}_{\mathbb{E}_{\infty}}(\mathrm{MSTop}[\tfrac{1}{2}],\mathrm{ko}[\tfrac{1}{2}])$.111By
a result of Sullivan’s [MM79, 5.12 & 5.24], one has
$\mathrm{Map}_{\mathbb{E}_{\infty}}(\mathrm{MSTop}[\tfrac{1}{2}],\mathrm{ko}[\tfrac{1}{2}])\simeq\mathrm{Map}_{\mathbb{E}_{\infty}}(\mathrm{MSO}[\tfrac{1}{2}],\mathrm{ko}[\tfrac{1}{2}])$.
Finally, consider the exact sequence

$\pi_{d}(X\otimes\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))\xrightarrow{(\ast)}\pi_{d}(X\otimes\tau_{\leq
0}\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))\to\pi_{d-1}(X\otimes\tau_{\geq
1}\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))\to\pi_{d-1}(X\otimes\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))$

and recall that the second to last group contains the element $\mathrm{ro}(X)$
which is sent to $\overline{\mathrm{ro}}(X)=0$ in the final group above. Note
that the map labelled $(\ast)$ is 2-locally surjective, as follows from the
2-local splitting of $\mathrm{L}^{\mathrm{q}}(\mathbb{Z})$ into Eilenberg-Mac
Lane spectra. Away from $2$, we may use the equivalence
$\mathrm{L}^{\mathrm{q}}(\mathbb{Z})[\tfrac{1}{2}]\simeq\mathrm{KO}[\tfrac{1}{2}]$
so that under assumption (iii)222Note that for $E$ any spectrum, the canonical
map $\pi_{d}(X\otimes\tau_{\geq 0}E)\to\pi_{d}(X\otimes E)$ is an isomorphism.
the map $(\ast)[\tfrac{1}{2}]$ is also surjective, showing that
$\mathrm{ro}(X)=0$ and hence (i).

∎

We note that $\overline{\mathrm{ro}}(X)=0$ is implied by
$\overline{\mathrm{tso}}(X)=0$, in which case the following also appears in
[BFMW24].

######  2 Corollary.

Let $X$ be an oriented Poincaré complex with $\overline{\mathrm{ro}}(X)=0$. If
$\dim(X)\leq 6$, then the Spivak normal fibration admits a reduction to a
stable euclidean bundle.

###### Proof.

It follows from work of Thom [Tho54] that any homology class of degree $\leq
6$ is represented by a smooth, in particular by a topological, closed
manifold, so 1 (ii) is valid. ∎

######  3 Remark.

In the above argument, we have used that for an oriented Poincaré complex $X$,
$\overline{\mathrm{ro}}(X)=0$ implies that $\mathrm{ro}(X)$ vanishes
2-locally. One may wonder whether the same is true for the total surgery
obstructions: If $\overline{\mathrm{tso}}(X)=0$, does it follow that
$\mathrm{tso}(X)$ vanishes 2-locally? We do not know the answer to this
question currently. Note, however, that the 2-local splitting of
$\mathrm{L}^{\mathrm{q}}(\mathbb{Z})$ does not induce a $2$-local splitting of
${\overline{\mathscr{S}}}^{\mathrm{alg}}(X)$ into
$\mathscr{S}^{\mathrm{alg}}(X)$ and a second summand: Indeed, suppose that $X$
is $d$-dimensional aspherical Poincaré complex and $\pi_{1}(X)$ is a
Farrell–Jones group. Then ${\overline{\mathscr{S}}}^{\mathrm{alg}}(X)=0$ but
$\mathscr{S}^{\mathrm{alg}}(X)_{(2)}\simeq[X\otimes\tau_{\leq
0}\mathrm{L}^{\mathrm{q}}(\mathbb{Z})]_{(2)}\neq 0$. Nevertheless, at least
conjecturally, one has $\mathrm{tso}(X)=0$ whenever $X$ is aspherical, see
[Lüc24, Conjecture 9.178].

We come to the main contribution of this paper.

######  Main Theorem.

There exists an oriented Poincaré complex $E$ with
$\overline{\mathrm{tso}}(E)=0$ whose Spivak normal fibration does not admit a
reduction to a euclidean bundle.

We consider the following construction. Let
$\bar{x}\in\pi_{\ell}(\mathrm{Bgl}_{1}(\SS))$ be an element of positive degree
$\ell$ and order $n$. Let $M(\mathbb{Z}/n\mathbb{Z},\ell)$ be the
corresponding mod $n$ Moore space in dimension $\ell$. By assumption, there is
then a map $x\colon M(\mathbb{Z}/n\mathbb{Z},\ell)\to\mathrm{Bgl}_{1}(\SS)$
whose composite with the tautological map $S^{\ell}\to
M(\mathbb{Z}/n\mathbb{Z},\ell)$ is $\bar{x}$. By framed surgeries below the
middle dimension, we may construct a map $f\colon M\to
M(\mathbb{Z}/n\mathbb{Z},\ell)$ inducing an isomorphism on $\pi_{\ell}$ with
$M$ a stably framed (smooth) $m$-manifold for any $m>2\ell$; e.g. by framed
surgery on an appropriately embedded $\ell$-sphere in $S^{\ell}\times
S^{m-\ell}$. Let $k\geq\ell+1$ be sufficiently large, so that $-xf\colon
M\to\mathrm{Bgl}_{1}(\SS)$ lifts along
$\mathrm{Baut}_{*}(S^{k})\to\mathrm{Bgl}_{1}(\SS)$ and let $\pi\colon E\to M$
be the associated pointed spherical fibration over $M$. By choice of $k$, the
resulting map $E\to M(\mathbb{Z}/n\mathbb{Z},\ell)$ is then again an
isomorphism on $\pi_{\ell}$. Moreover, $E$ is a Poincaré complex with Spivak
normal fibration classified by the composite

$E\xrightarrow{\pi}M\xrightarrow{xf}\\{-d\\}\times\mathrm{Bgl}_{1}(\SS)\subseteq\mathrm{Pic}(\SS),$

where $d=m+k$ is the dimension of $E$.

###### Proof of Main Theorem.

Let $\bar{x}\in\pi_{4}(\mathrm{Bgl}_{1}(\SS))\cong\mathbb{Z}/24\mathbb{Z}$ be
a generator of the 3-torsion and consider the Poincaré complex $E$ associated
to $\bar{x}$ as constructed above. Then, the composite

$E\xrightarrow{\pi}M\xrightarrow{f}M(\mathbb{Z}/3\mathbb{Z},4)\xrightarrow{x}\mathrm{Bgl}_{1}(\SS)$

classifies the Spivak normal fibration of $E$ but does not lift along
$\mathrm{BTop}\to\mathrm{Bgl}_{1}(\SS)$. Indeed, on $\pi_{4}$ it induces an
inclusion $\mathbb{Z}/3\mathbb{Z}\subseteq\mathbb{Z}/24\mathbb{Z}$, which
cannot factor through
$\mathbb{Z}\oplus\mathbb{Z}/2\cong\pi_{4}(\mathrm{BTop})$ [Mil88, Lemma 9]. It
then remains to show $\overline{\mathrm{tso}}(E)=0$. To that end, note first
that $E$ is simply connected. As a consequence of the $\pi$-$\pi$-theorem, we
thus find that the map

$\Omega^{d}{\overline{\mathscr{S}}}^{\mathrm{alg}}(E)\to\Omega^{d-1}[E\otimes\mathrm{L}^{\mathrm{q}}(\mathbb{Z})]$

is split injective on homotopy groups. In particular, to verify that
$\overline{\mathrm{tso}}(E)=0$, it suffices to show that
$\overline{\mathrm{ro}}(E)=0$. To do so, recall that the composite $E\to
M(\mathbb{Z}/3\mathbb{Z},4)\to\\{-d\\}\times\mathrm{Bgl}_{1}(\mathbb{S})$ is
the Spivak normal fibration $D_{E}$ of $E$. In particular, we obtain a map
$\mathrm{Th}(D_{E})\to\Omega^{d}\mathrm{Th}(x)$, where $\mathrm{Th}(-)$ is the
Thom spectrum functor. Applying Spanier–Whitehead duality and Atiyah duality,
we obtain an induced stable map $D(\mathrm{Th}(x))\to E$ which induces the
following commutative diagram.

${\pi_{-1}(D(\mathrm{Th}(x))\otimes\tau_{\geq
1}\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))}$${\pi_{d-1}(E\otimes\tau_{\geq
1}\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))}$${\pi_{-1}(D(\mathrm{Th}(x))\otimes\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))}$${\pi_{d-1}(E\otimes\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))}$

Now, the element $\mathrm{ro}(E)$ in the top right corner is in the image of
the upper horizontal map, by naturality of Thom classes. The proof that
$\overline{\mathrm{ro}}(E)$, and hence $\overline{\mathrm{tso}}(E)$, vanishes
is hence finished once we show that the left lower corner in the above diagram
is trivial. To that end, one first computes that $D(\mathrm{Th}(x))$ is
equivalent to
$\operatorname*{fib}(\mathbb{S}\xrightarrow{x}\mathbb{S}^{-4}/3)$; generally
the Thom spectrum of a map $\Sigma X\to\mathrm{Bgl}_{1}(\SS)$, for a pointed
space $X$, identifies with the cofibre of the induced map
$\Sigma^{\infty}X\to\SS$, for example the argument in [Lan22, Section A.13]
applies verbatim to general suspensions in place of spheres. Consequently, we
obtain an exact sequence

$\pi_{0}(\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))\stackrel{{\scriptstyle
x}}{{\longrightarrow}}\pi_{4}(\mathrm{L}^{\mathrm{q}}(\mathbb{Z})/3)\longrightarrow\pi_{-1}(D(\mathrm{Th}(x))\otimes\mathrm{L}^{\mathrm{q}}(\mathbb{Z}))\to
0$

with first group isomorphic to $\mathbb{Z}$ and middle one isomorphic to
$\mathbb{Z}/3\mathbb{Z}$. We claim that the map labelled $x$ in this sequence
is surjective. To prove this, we may localise at $3$, so that
$\mathrm{L}^{\mathrm{q}}(\mathbb{Z})$ may be replaced by $\mathrm{KO}$, see
again [LN18, Corollary 5.4] and the following remark. Then the claim follows
from the fact that the map $\mathbb{S}/3\to\mathrm{KO}/3$ induced by the unit
of $\mathrm{KO}$ induces a bijection on $\pi_{4}$ [Ada66, Thm. 1.7].333This
statement can equivalently be phrased as saying that $x$, thought of as a map
$\Sigma^{4}\mathbb{S}/3\to\mathbb{S}/3$ is a $v_{1}$-map in the sense of
chromatic homotopy theory, i.e. induces an isomorphism in $K$-theory. ∎

######  4 Remark.

The above proof of Main Theorem works, essentially verbatim, more generally
for any non-trivial element $\bar{x}\in\pi_{4k-1}(\mathbb{S})$ of odd order
$n$ which is in the image of the $J$-homomorphism. Indeed, one first observes
that [Bru68, Theorem 4.7 & Remark 4.9], together with the equivalence
$\mathrm{Top}/\mathrm{PL}\simeq K(\mathbb{Z}/2,3)$ [KS77], says that the odd
torsion of $\pi_{4k}(\mathrm{BTop})$ maps via the canonical map
$\mathrm{BTop}\to\mathrm{Bgl}_{1}(\mathbb{S})$ isomorphically onto the kernel
of Adams’ $e$-invariant. Since $e(\bar{x})$ is non-zero [Ada66, Theorem 1.5 &
1.6] we deduce that the Spivak normal fibration of the Poincaré complex $E$
constructed from $\bar{x}$ does not admit a reduction to a euclidean bundle.
To see that $\overline{\mathrm{tso}}(E)=0$, it again suffices to show that the
composite

$\mathbb{S}\xrightarrow{x}\Omega^{4k}\mathbb{S}/n\to\Omega^{4k}\mathrm{KO}/n$

is surjective on $\pi_{0}$. To do this, one can reduce to the case where
$n=p^{l}$ for some odd prime $p$. Then we use that the image of the
$J$-homomorphism maps isomorphically onto $\pi_{4k-1}(L_{K(1)}\mathbb{S})$ and
that the map $\pi_{4k}(\mathrm{KO}/n)\to\pi_{4k}(\mathrm{KU}/n)$ is an
isomorphism. Doing this, it will suffice to show that the map

$\pi_{4k}(L_{K(1)}\mathbb{S}/n)\to\pi_{4k}(\mathrm{KU}/n),$

induced by the unit of $\mathrm{KU}$ and the fact that $\mathrm{KU}/n$ is
$K(1)$-local, is an isomorphism. This follows from an inspection of the long
exact sequence induced from the equivalence
$L_{K(1)}\mathbb{S}\simeq(\mathrm{KU}^{\scriptscriptstyle\wedge}_{p})^{h\mathbb{Z}_{p}^{\times}}$
together with the fact that $n$ divides the order of
$\pi_{4k-1}(L_{K(1)}\mathbb{S})$. Concrete examples of elements $\bar{x}$ as
needed are given by generators of the $p$-torsion of $\pi_{2p-3}(\mathbb{S})$
for any odd prime $p$. The case $p=3$ is the one we used above.

## Consequences

Let us list a number of consequences of the above constructions.

  1. (i)

Main Theorem invalidates an implicit assumption made in the proof of the main
result of [BFMW96], as is explained also in the recent erratum [BFMW24] to
loc. cit. If, however, [BFMW96, Main theorem] is correct as stated, then the
Poincaré complexes $E$ constructed before the proof of Main Theorem are
homotopy equivalent to closed homology manifolds whose Spivak normal
fibrations do not admit reductions to stable euclidean bundles provided
$\bar{x}\in\pi_{\ell}(\mathrm{Bgl}_{1}(\SS))$ has odd order and is in the
image of the $J$-homomorphism, see 4. This would invalidate [FP95, Theorem
16.6].

  2. (ii)

Weinberger informed us that he knows an argument that [BFMW96, Main Theorem]
is correct as stated provided the Poincaré complex $X$ admits a
$\pi$-$\pi$-2-patch structure. This addition would imply that our complexes
are realised by closed homology manifolds, as we show in 5 below that the
Poincaré complexes $E$ constructed above admit such a structure.

  3. (iii)

Weinberger also informed us that he knows an argument that a certain family
version of [BFMW96, Main theorem], see point (xi) above, is correct for
families with typical fibre a topological manifold. We will show below that
this implies that the fibrations $\pi\colon E\to M$ constructed before the
proof of Main Theorem are fibre homotopy equivalent to block bundles with
typical fibre a homology manifold provided
$\bar{x}\in\pi_{\ell}(\mathrm{Bgl}_{1}(\SS))$ has odd order, see 8. Again, it
follows that $E$ is homotopy equivalent to a closed homology manifold.
Moreover, if $\bar{x}$ does not lie in the kernel of Adams’ $e$-invariant,
then the Spivak normal fibration of $E$ does not admit a reduction to a
euclidean bundle, see 4.

  4. (iv)

The discussion of Quinn’s resolution obstruction for homology manifolds in
[BFMW96] also uses that the Spivak normal fibration admits a reduction to a
euclidean bundle, and hence suffers the same defect as [BFMW96, Main Theorem].

### Patch structures

Let us recall that a $\pi$-$\pi$-2-patch structure on a Poincaré complex $X$
consists of two manifolds $M$ and $M^{\prime}$ whose boundary inclusions
$\partial M\subseteq M$ and $\partial M^{\prime}\subseteq M^{\prime}$ are
equivalences on $1$-truncations, and homotopy equivalences
$\varphi\colon\partial M\simeq\partial M^{\prime}$ as well as $\psi\colon
X\simeq M\cup_{\varphi}M^{\prime}$.

######  5 Proposition.

The Poincaré complexes $E$ constructed above admit $\pi$-$\pi$-2-patch
structures provided $\ell\geq 3$.

###### Proof.

We note that $M(\mathbb{Z}/n\mathbb{Z},\ell)\cong\Sigma
M(\mathbb{Z}/n\mathbb{Z},\ell-1)$ and consider a transverse inverse image
$N\subseteq M$ of $M(\mathbb{Z}/n\mathbb{Z},\ell-1)$ along $f\colon M\to
M(\mathbb{Z}/n\mathbb{Z},\ell)$. By construction $N\subseteq M$ is a
codimension one submanifold with trivial normal bundle. Since
$M(\mathbb{Z}/n\mathbb{Z},\ell-1)$ is simply connected, by ambient surgeries
on $N$, one can achieve that $N$ is simply connected as well, see [Qui74] for
general results along these lines. Consequently, $M\setminus N$ decomposes
into a disjoint union of two pieces which are the interiors of compact
manifolds $M^{+}$ and $M^{-}$ with common boundary $N$. Moreover, $M^{\pm}$ is
again simply connected, so that the inclusion $N\subseteq M^{\pm}$ is an
equivalence on 1-types. In other words, $M$ is obtained from two manifolds
$M^{+}$ and $M^{-}$ by glueing along a diffeomorphism $\partial
M^{+}\cong\partial M^{-}$. Moreover, the fibration classified by
$M\to\mathrm{Baut}_{*}(S^{k})$ is trivial when restricted to $M^{\pm}$. It
follows that $E$ is obtained from the two manifolds $M^{+}\times S^{k}$ and
$M^{-}\times S^{k}$ by glueing along a homotopy equivalence $\partial
M^{+}\times S^{k}\simeq\partial M^{-}\times S^{k}$, which is the promised
$\pi$-$\pi$-2-patch structure on $E$. ∎

### The fibrewise periodic tso

We will use a number of observations about the fibrewise periodic total
surgery obstruction that we explain first. Let $M$ be a simply connected
pointed Poincaré complex of dimension $d$ and $\pi\colon E\rightarrow B$ an
oriented $M$-fibration with a section $s$.

  1. -

We recall that $M$ admits a canonical orientation in
$\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$-homology via the map
$\mathrm{MSG}\to\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$, i.e. a point
$\sigma^{\mathrm{n}}(M)$ in
$\Omega^{d}[M\otimes\mathrm{L}^{\mathrm{n}}(\mathbb{Z})]$, capping with which
induces Poincaré duality. Applying this construction fibrewise, we obtain a
canonical section $\sigma^{\mathrm{n}}(\pi)$ of the parametrised spectrum
$\Omega^{d}[(E,B)\otimes_{B}\mathrm{L}^{\mathrm{n}}(\mathbb{Z})]$ of
$\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$-modules.

  2. -

Similarly, we may consider the parametrised spectrum
${\overline{\mathscr{S}}}^{\mathrm{alg}}(\pi)$ over $B$ sending a point $b\in
B$ to ${\overline{\mathscr{S}}}^{\mathrm{alg}}(E_{b})$. The periodic total
surgery obstructions $\overline{\mathrm{tso}}(E_{b})$ of the fibres $E_{b}$
then assemble into a section $\overline{\mathrm{tso}}(\pi)$ of
$\Omega^{d}{\overline{\mathscr{S}}}^{\mathrm{alg}}(\pi)$.

We will now operate under the following.

######  Assumption.

Given a oriented Poincaré fibration $\pi\colon E\rightarrow B$, with typical
fibre $F$, then $\pi$ is fibre homotopy equivalent to a block bundle with
typical fibre a homology manifold (homotopy equivalent to $F$) if and only if
the just described section $\overline{\mathrm{tso}}(\pi)$ vanishes.

As indicated above, when the typical fibre $F$ is a closed topological
manifold, this follows from a family version of the results of [BFMW96], which
Weinberger confirmed to us is valid. In particular, when
$\overline{\mathrm{tso}}(\pi)$ vanishes and $B$ is a manifold, $E$ is homotopy
equivalent to a homology manifold.

######  6 Lemma.

The following are equivalent for a pointed oriented Poincaré fibration
$\pi\colon E\to B$ with simply connected fibres.

  1. (i)

Giving a trivialisation of the fibrewise periodic total surgery obstruction
$\overline{\mathrm{tso}}(\pi)$, and

  2. (ii)

giving a lift of the fibrewise normal orientation $\sigma^{\mathrm{n}}(\pi)$
to a section of
$\Omega^{d}[(E,B)\otimes_{B}\mathrm{L}^{\mathrm{s}}(\mathbb{Z})]$.

###### Proof.

We consider the following diagram of $B$-parametrised spectra: (we write
everywhere the value of these objects over a point $b$, and note that all
constructions are functorial in $b$).

${\mathrm{L}^{\mathrm{vq}}(E_{b},s(b))}$${(E_{b},s(b))\otimes\mathrm{L}^{\mathrm{s}}(\mathbb{Z})}$${\mathrm{L}^{\mathrm{vs}}(E_{b},s(b))}$${{\overline{\mathscr{S}}}^{\mathrm{alg}}(E_{b})}$${(E_{b},s(b))\otimes\mathrm{L}^{\mathrm{n}}(\mathbb{Z})}$${\mathrm{L}^{\mathrm{vn}}(E_{b},s(b))}$$\scriptstyle{\simeq}$$\scriptstyle{\simeq}$

The horizontal and vertical composites are each fibre sequences. This is
because ${\overline{\mathscr{S}}}^{\mathrm{alg}}(E_{b})$ is the cofibre of the
assembly map in (visible) symmetric L-theory, which is, by construction, an
equivalence on the basepoint $s(b)$. We then note that the algebraic
$\pi$-$\pi$-theorem implies that the quadratic L-theory term on the very top
vanishes as we assume $E_{b}$ to be simply connected. Moreover, we recall that
the assembly map in visible normal L-theory is an equivalence. We therefore
find the two indicated equivalences. Passing to spaces of sections we obtain
similar fibre sequences and equivalences. Now, by construction, the canonical
section of $b\mapsto(E_{b},s(b))\otimes\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$
corresponds under the two indicated equivalences to the canonical section of
$b\mapsto\mathrm{L}^{\mathrm{vs}}(E_{b},s(b))$ taking the fibrewise symmetric
signature of the bundle $E\to B$. Therefore, a lift of the left vertical map
on spaces of sections is equivalent to the datum of a nullhomotopy of the
image of the symmetric signature section in
$\Gamma(B,{\overline{\mathscr{S}}}^{\mathrm{alg}}(E))$, which, by definition,
is $\overline{\mathrm{tso}}(\pi)$. ∎

######  7 Theorem.

Let $\pi\colon E\to B$ be an oriented pointed spherical fibration with typical
fibre homotopy equivalent to $S^{d}$ whose associated element in
$\mathrm{BSG}^{0}(B)$ is of odd order. Then there exists a trivialization of
$\overline{\mathrm{tso}}(\pi)$.

###### Proof.

Recall that $\mathrm{BSG}$ and $\mathrm{Bsl}_{1}(\SS)$ denote the same
infinite loop space. We will show that the data in (ii) of 6 can be given.
First, we note that by classical orientation theory, the composite

$\mathrm{Bsl}_{1}(\SS_{(2)})\to\mathrm{Bgl}_{1}(\SS_{(2)})\to\mathrm{Bgl}_{1}(\mathrm{MSG}_{(2)})$

is canonically trivialised. More precisely, the null-homotopy is induced by
the canonical null-homotopy of the fibre sequence

$\mathrm{Bsl}_{1}(\SS_{(2)})\to\mathrm{Bgl}_{1}(\SS_{(2)})\to\mathrm{B}\mathbb{Z}_{(2)}^{\times}$

and a map
$\mathrm{B}\mathbb{Z}_{(2)}^{\times}\to\mathrm{Bgl}_{1}(\mathrm{MSG}_{(2)})$.
On endomorphism spaces, this latter map sends a 2-local unit $q$ to the self
map of $\mathrm{MSG}_{(2)}$ which is given by multiplication with $q$.

Next, we note that the assumption that $\pi\in\mathrm{BSG}^{0}(B)$ is of odd
order is equivalent to the statement that the composite

$B\to\mathrm{Bsl}_{1}(\SS)\to\mathrm{Bsl}_{1}(\SS_{(2)})$

is null homotopic, where the first map is the classifying map for the stable
spherical fibration associated to $\pi\colon E\to B$. We therefore have two
null-homotopies of the composite

$B\to\mathrm{Bsl}_{1}(\SS)\to\mathrm{B}\mathbb{Z}_{(2)}^{\times}$

which together determine a map $B\to\mathbb{Z}_{(2)}^{\times}$. The composite

$B\to\mathrm{Bsl}_{1}(\SS)\to\mathrm{Bsl}_{1}(\mathrm{MSG})\to\mathrm{Bsl}_{1}(\mathrm{L}^{n}(\mathbb{Z}))$

which induces the fibrewise normal orientation, i.e. the canonical section of
the bundle $(E,B)\otimes_{B}\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$ discussed
above, is therefore also null-homotopic in two ways, whose difference is
determined by the composite

$B\to\mathbb{Z}_{(2)}^{\times}\to\mathrm{gl}_{1}(\mathrm{MSG}_{(2)})\to\mathrm{gl}_{1}(\mathrm{L}^{\mathrm{n}}(\mathbb{Z})).$

As a consequence, we find that we can lift the fibrewise normal orientation to
a section of the bundle
$E\otimes_{B}\mathrm{L}^{\mathrm{s}}(\mathbb{Z})_{(2)}$ \- simply because we
can tautologically lift the section coming from the trivialisation of
$E_{(2)}\to B$ itself, and can then multiply by the appropriate 2-local unit.
Finally, we use that $B$ is compact, see also [Ada63, Theorem 1.1] for a
similar argument: This implies that the section $B\to
E\otimes\mathrm{L}^{\mathrm{s}}(\mathbb{Z})_{(2)}$ factors as a section of
$E\otimes\mathrm{L}^{\mathrm{s}}(\mathbb{Z})$ followed by the 2-localisation
map (which is a filtered colimit over multiplication by odd numbers) divided
by an odd number $\alpha$. The induced section of
$E\otimes\mathrm{L}^{\mathrm{n}}(\mathbb{Z})$ is then $\alpha$ times the
canonical section. We may therefore multiply the section of
$E\otimes\mathrm{L}^{\mathrm{s}}(\mathbb{Z})$ with $\alpha$ and use that
$\alpha^{2}\equiv 1$ modulo $8$ and that
$\mathrm{L}^{\mathrm{n}}_{0}(\mathbb{Z})$ is $\mathbb{Z}/8$ to obtain a lift
of the fibrewise normal orientation as needed. ∎

######  8 Corollary.

For the spherical fibrations $\pi\colon E\to M$ constructed from
$\bar{x}\in\pi_{\ell}(\mathrm{Bgl}_{1}(\SS))$ before the proof of Main
Theorem, we have $\overline{\mathrm{tso}}(\pi)=0$ provided the order $n$ of
$\bar{x}$ is odd.

###### Proof.

By 7, it suffices to show that the classifying map of $\pi$, viewed as an
element in $\mathrm{BSG}^{0}(M)$, is of odd order. But by construction, this
classifying map is in the image of the map
$\mathrm{BSG}^{0}(M(\mathbb{Z}/n\mathbb{Z},\ell))\to\mathrm{BSG}^{0}(M)$ and
the source of this map is a finite group of odd order. ∎

## References

  * [Ada63] J. F. Adams, _On the groups $J(X)$. I_, Topology 2 (1963), 181–195.
  * [Ada66] by same author, _On the groups $J(X)$. IV_, Topology 5 (1966), 21–71.
  * [BFMW96] J. Bryant, S. Ferry, W. Mio, and S. Weinberger, _Topology of homology manifolds_ , Ann. of Math. (2) 143 (1996), no. 3, 435–467.
  * [BFMW24] by same author, _Erratum to “Topology of homology manifolds”_ , Ann. of Math. (2), to appear (2024).
  * [Bru68] G. Brumfiel, _On the homotopy groups of ${\rm BPL}$ and ${\rm PL/O}$_, Ann. of Math. (2) 88 (1968), 291–311.
  * [CDH+20a] B. Calmès, E. Dotto, Y. Harpaz, F. Hebestreit, M. Land, K. Moi, D. Nardin, T. Nikolaus, and W. Steimle, _Hermitian K-theory for stable $\infty$-categories II: Cobordism categories and additivity_, arXiv:2009.07224 (2020).
  * [CDH+20b] by same author, _Hermitian K-theory for stable $\infty$-categories III: Grothendieck–Witt groups of rings_, arXiv:2009.07225 (2020).
  * [CDH+23] by same author, _Hermitian K-theory for stable $\infty$-categories I: Foundations_, Selecta Math. (N.S.) 29 (2023), no. 1, Paper No. 10, 269\.
  * [FP95] S. C. Ferry and E. K. Pedersen, _Epsilon surgery theory_ , Novikov conjectures, index theorems and rigidity, Vol. 2 (Oberwolfach, 1993), London Math. Soc. Lecture Note Ser., vol. 227, Cambridge Univ. Press, Cambridge, 1995, pp. 167–226.
  * [KS77] R. C. Kirby and L. C. Siebenmann, _Foundational essays on topological manifolds, smoothings, and triangulations_ , Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1977, With notes by John Milnor and Michael Atiyah, Annals of Mathematics Studies, No. 88.
  * [Lan22] M. Land, _Reducibility of low-dimensional Poincaré duality spaces_ , Münster J. Math. 15 (2022), no. 1, 47–81.
  * [LM24] W. Lück and T. Macko, _Surgery Theory: Foundations_ , Grundlehren der mathematischen Wissenschaften, Springer Cham, 2024.
  * [LN18] M. Land and T. Nikolaus, _On the relation between $K$\- and $L$-theory of $C^{*}$-algebras_, Math. Ann. 371 (2018), no. 1-2, 517–563.
  * [LNS23] M. Land, T. Nikolaus, and M. Schlichting, _L-theory of $C^{\ast}$-algebras_, Proc. Lond. Math. Soc. (3) 127 (2023), no. 5, 1451–1506.
  * [Lüc24] W. Lück, _Isomorphism Conjectures in $K$\- and $L$-Theory_, Springer, in preparation, 2024.
  * [Mil88] R. J. Milgram, _Some remarks on the Kirby-Siebenmann class_ , Algebraic topology and transformation groups (Göttingen, 1987), Lecture Notes in Math., vol. 1361, Springer, Berlin, 1988, pp. 247–252.
  * [MM79] I. Madsen and R. J. Milgram, _The classifying spaces for surgery and cobordism of manifolds_ , Annals of Mathematics Studies, No. 92, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1979.
  * [Qui74] F. Quinn, _Almost canonical inverse images_ , Comment. Math. Helv. 49 (1974), 168–174.
  * [Ran79] A. A. Ranicki, _The total surgery obstruction_ , Algebraic topology, Aarhus 1978 (Proc. Sympos., Univ. Aarhus, Aarhus, 1978), Lecture Notes in Math., vol. 763, Springer, Berlin, 1979, pp. 275–316.
  * [Ran92] by same author, _Algebraic $L$-theory and topological manifolds_, Cambridge Tracts in Mathematics, vol. 102, Cambridge University Press, Cambridge, 1992.
  * [Tho54] R. Thom, _Quelques propriétés globales des variétés différentiables_ , Comment. Math. Helv. 28 (1954), 17–86.
  * [Wal99] C. T. C. Wall, _Surgery on compact manifolds_ , second ed., Mathematical Surveys and Monographs, vol. 69, American Mathematical Society, Providence, RI, 1999.