# Improving Entity Linking by Modeling Latent
Entity Type Information

Shuang Chen,1 Jinpeng Wang,2 Feng Jiang,1,3 Chin-Yew Lin2
1 Harbin Institute of Technology, Harbin, China
2 Microsoft Research Asia 3 Peng Cheng Laboratory
<EMAIL_ADDRESS>{jinpwa<EMAIL_ADDRESS><EMAIL_ADDRESS>Contribution
during internship at Microsoft Research.

###### Abstract

Existing state of the art neural entity linking models employ attention-based
bag-of-words context model and pre-trained entity embeddings bootstrapped from
word embeddings to assess topic level context compatibility. However, the
latent entity type information in the immediate context of the mention is
neglected, which causes the models often link mentions to incorrect entities
with incorrect type. To tackle this problem, we propose to inject latent
entity type information into the entity embeddings based on pre-trained BERT.
In addition, we integrate a BERT-based entity similarity score into the local
context model of a state-of-the-art model to better capture latent entity type
information. Our model significantly outperforms the state-of-the-art entity
linking models on standard benchmark (AIDA-CoNLL). Detailed experiment
analysis demonstrates that our model corrects most of the type errors produced
by the direct baseline.

## Introduction

Entity Linking (EL) is the task of disambiguating textual mentions to their
corresponding entities in a reference knowledge base (e.g., Wikipedia). An
accurate entity linking system is crucial for many knowledge related tasks
such as question answering (?) and information extraction (?).

Traditional entity linkers mainly depend on manually designed features to
evaluate the local context compatibility and document-level global coherence
of referent entities (?; ?). The design of such features requires entity-
specific domain knowledge. These features can not fully capture relevant
statistical dependencies and interactions. One recent notable work (?) instead
pioneers to rely on pre-trained entity embeddings, learnable context
representation and differentiable joint inference stage to learn basic
features and their combinations from scratch. Such model design allows to
learn useful regularities in an end-to-end fashion and eliminates the need for
extensive feature engineering. It also substantially outperforms the
traditional methods on standard benchmark (e.g., AIDA-CoNLL). A line of
follow-up work (?; ?; ?) investigate potential improvement solution or other
task settings based on that.

Figure 1: One error case on AIDA-CoNLL development set of the full model of ?
(?). (a) Immediate context; (b) Attended contextual words sorted by attention
weights. The preposition “In” is a strong cue predictive of the type of
mention “Milwaukee” which is not captured by the local context model.

Such state-of-the-art entity linking models (?; ?) employ attention-based bag-
of-words context model and pre-trained entity embeddings bootstrapped from
word embeddings to assess topic level context compatibility. However, the
latent entity type information in the immediate context of the mention is
neglected. We suspect this may sometimes cause the models link mentions to
incorrect entities with incorrect type. To verify this, we conduct error
analysis of the well known DeepED111https://github.com/dalab/deep-ed model (?)
on the development set of AIDA-CoNLL (?), and found that more than half of
their error cases fall into the category of type errors where the predicted
entity’s type is different from the golden entity’s type, although some
predictive contextual cue for them can be found in their local context. As
shown in Fig. 1, the full model of ? (?) incorrectly links the mention
“Milwaukee” to the entity Milwaukee_Brewers. However, the preposition “In” is
a strong cue predictive of the type (location) of mention “Milwaukee” which is
helpful for disambiguation. The reason why the local context model of ? (?)
couldn’t capture such apparent cue is two folds. On one hand, the context
encoding module adopts a bag-of-words encoding scheme which is position
agnostic. As shown in Fig. 1(b), the attention mechanism is helpful for
selecting predictive words (e.g. “Milwaukee”, “games” etc.), but does not
capture the pattern that the previous word “In” of the mention “Milwaukee”
which very likely refers to an entity with location type. On the other hand,
the pre-trained entity embedding of ? (?) is not very sensitive to entity
types. For example, as shown in Table 8, when we query the most similar
entities with the entity Steve_Jobs, the top one returned entity is
Apple_Inc., which is a different type but releated at topic level. So it is
natural for the model of ? (?) to make type errors when it is trained to fit
such entity embeddings.

As is argued in (?), “context consistency is a strong proxy for type
compatibility”. Based on this claim, the mention’s immediate context is a
proxy of its type. For example, we consider the following context from
Wikipedia linking to the entity Apple in which the mention is replaced with
the [MASK] token.

> Fruits that tend to be more popular in this area are [MASK] , pears , and
> berries .

By reading the context surrounding the [MASK] token, we can easily determine
that the entities fitting this context should be a kind of fruit.

In this paper, we propose to inject latent entity type information into the
entity embeddings by modeling the immediate context surrounding the mention.
Specifically, we apply pre-trained BERT (?) to represent the entity context
and build a shared entity representation by aggregating all the entity
contexts linking to the same entity via average pooling. Pre-trained BERT
models naturally fit our purpose to represent the entity context surrounding
the [MASK] token as it is trained with masked language model objective. What’s
more, we integrate a BERT-based entity similarity feature into the local model
of ? (?) to better capture entity type information. This can leverage both the
pre-trained entity embeddings from BERT and the domain adaption capability of
BERT via fine-tuning.

We conduct entity linking experiments on standard benchmark datasets: AIDA-
CoNLL and five out-domain test sets. Our model achieves an absolute
improvement of 1.32% F1 on AIDA-CoNLL test set and average 0.80% F1 on five
out-domain test sets over five different runs. In addition, we conduct
detailed experiment analysis on AIDA-CoNLL development set which shows our
proposed model can reduce 67.03% type errors of the state-of-the-art model (?)
and more than 90% of the remaining type error cases are due to over estimation
of prior and global modeling problem which we leave as the further work.

Our contributions can be summarized as follows.

  * •

We show current state-of-the-art (SOTA) neural entity linking models based on
attention-based bag-of-words context model often produce type errors and
analyze the possible causes.

  * •

We propose a novel entity embedding method based on pre-trained BERT to better
capture latent entity type information.

  * •

We integrate a BERT-based entity similarity into the local model of a SOTA
model (?).

  * •

We verify the effectiveness of our model on standard benchmark datasets and
achieve significant improvement over the baseline. And the detailed experiment
analysis demonstrates that our method truly corrects most of the type errors
produced by the baseline.

## Background

### Entity Linking Problem

Formally, given a document $D$ consisting of a list of entity mentions
$m_{1},...,m_{n}$. The goal of an entity linking system is to assign each
$m_{i}$ a KB entity $e_{i}$ or predict that no corresponding entity in the KB
(i.e., $e_{i}$=NIL).

Due to potentially very large entity space (e.g. Wikipedia has more than 4
million entities), standard entity linking is often divided into two stages:
candidate generation which chooses potential candidates
$C_{i}=(e_{i1},...,e_{il_{i}})$ using a heuristic and entity disambiguation
which learns to select the best entity from the candidates using a statistical
model. In this work, we focus on the second stage entity disambiguation. As
for entity disambiguation, two different kinds of information can be
leveraged: local context compatibility and document-level global coherence
which respectively corresponds to the local model and the global model. Next,
we introduce the general formulation of entity linking problem with a focus on
the well known DeepED model (?).

#### General Formulation

An entity linking model integrating both local and global features can be
formulated as a conditional random field. Formally, we can define a scoring
function $g$ to evaluate the entity assignment $e_{1},...,e_{n}$ to mentions
$m_{1},...,m_{n}$ in a document $D$.

$\displaystyle
g(e_{1},...,e_{n}|D)=\sum_{i=1}^{n}\Psi(e_{i}|D)+\sum_{j\neq{i}}\Phi(e_{i},e_{j}|D)$
(1)

where the first term scores how well an entity fits its local context and the
second one measures the global coherence.

#### Local Model

Following ? (?), we instantiate the local model as an attention model based on
pre-trained word and entity embeddings. Specifically, for each mention
$m_{i}$, a pruned candidate set $C_{i}=(e_{i1},...,e_{il_{i}})$ is identified
in the candidate generation stage. We compute a local context score for each
$e\in C_{i}$ based on the K-word (in practice, K is set to 100 and stop words
are removed.) local context $c=\\{w_{1},...,w_{K}\\}$ surrounding $m_{i}$.

$\displaystyle\Psi_{\rm long}(e,c)={\mathbf{x}}_{e}^{\top}{\mathbf{B}}\,h(c)$
(2)

where ${\mathbf{B}}$ is a learnable diagonal matrix, ${\mathbf{x}}_{e}$ is the
embeddings of entity $e$, $h(c)$ applies a hard attention mechanism to context
words in $c$ to obtain the representation of the context.

Besides, ? (?) combined this context score with the prior $\hat{p}(e|m)$
(computed by mixing mention-entity hyperlink count statistics from Wikipedia,
a large Web corpus and YAGO.222See ? (?) for more details.) using a two-layer
feed-forward neural network in the local model.

$\displaystyle\Psi(e,m,c)=f(\Psi_{\rm long}(e,c),\log\hat{p}(e|m))$ (3)

#### Global Model

The second term in Equation 1 is given by:

$\displaystyle\Phi(e,e^{\prime})=\frac{2}{n-1}\,\,{\mathbf{x}}_{e}^{\top}{\mathbf{C}}\,{\mathbf{x}}_{e^{\prime}}$
(4)

where ${\mathbf{C}}$ is a diagonal matrix. The model defined by Equation 1 is
a fully-connected pairwise conditional random field. Exact maximum-a-
posteriori inference on this CRF, needed both at training and testing phrase,
is NP-hard (?). So they used max-product loopy belief propagation (LBP) to
estimate the max-marginal probability

$\displaystyle\hat{g}_{i}(e|D)\approx\max_{\begin{subarray}{c}e_{1},...,e_{i-1}\\\
e_{i+1},...,e_{n}\end{subarray}}g(e_{1},...,e_{n}|D)$ (5)

for each mention $m_{i}$. The final score for $m_{i}$ is given by:

$\displaystyle\rho_{i}(e)=f^{\prime}(\hat{g}_{i}(e|D),\hat{p}(e|m_{i}))$ (6)

where $f^{\prime}$ is another two-layer neural network and $\hat{p}(e|m_{i})$
is the prior feature.

## Related Work

Our work focuses on improving entity linking by capturing latent entity type
information with BERT. Specifically, our work related to previous approaches
in three aspects.

#### Entity Embedding

The entity linking task is essentially a zero-shot task where the answer of
test cases may not exist in the training data.333Only 58.6% answers of test
cases in AIDA-CoNLL dataset are existent in the training data. So we need to
build a shared entity embedding space for all entities which allows neural
entity linking models to generalize to both seen and unseen entities during
test time. Based on the distributional hypothesis (?), an entity is
characterized by its contexts. Different methods to characterize an entity’s
context result in different information its entity embedding can capture.
Previous work (?; ?) on learning entity representation are mostly extensions
of the embedding methods proposed by (?). An entity’s context is a bag-of-
words representation which mainly captures topic level entity relatedness
rather than entity type relatedness. In contrast, we propose a simple method
to build entity embeddings directly from pre-trained BERT (?) which can better
capture entity type information.

#### Type Information

Previous work attempt to integrate type information into the entity linking
task mostly by jointly modeling named entity recognition and entity linking.
Specifically, a line of work (?; ?; ?) jointly model entity linking and named
entity recognition to capture the mutual dependency between them using
structured CRF. These methods mainly differ in the design of hand-engineered
features. Recently, ? (?) perform multi-task learning using learned features
by extending Stack-LSTM (?). However, all of these work rely on extensive
annotation of the type of mentions which are difficult to obtain on most of
the entity linking datasets. In contrast, based on the assumption that
“context consistency is a strong proxy for type compatibility” from ? (?), we
propose to model a mention’s immediate context using BERT (?) to capture its
contextual latent entity type information.

#### Applications of BERT

Since the advent of the well-known BERT models (?), it has been applied
successfully to and has achieved state-of-the-art performance on many NLP
tasks. The main challenges which the entity linking task has over other tasks
e.g. sentence classification, named entity recognition, where BERT has been
applied are: (1) a very large label space, i.e. every mention has many target
entities and (2) the zero-shot nature of the entity linking task. Training
label embeddings from a small labeled dataset could not generalize to cover
unseen entities in test time. To tackle this problem, we introduce a novel
method to build entity embeddings from BERT by modeling the immediate context
of an entity.

## Model

Our model consists of two phrases: (1) Build entity embeddings from BERT (2)
Add a BERT-based entity similarity component to the local model. Next we will
describe each phrase in the following sections.

### Entity Embeddings from BERT

Given lists of mention context444A mention context of an entity is the
surrounding text of an anchor text, i.e. mention, pointing to the entity page
in Wikipedia. $\\{c_{i1},c_{i2},...,c_{iN}\\}$ in Wikipedia for every entity
$e_{i}\in\mathcal{E}$, we build the entity embeddings map
${\mathbf{B}}:\mathcal{E}\rightarrow\mathbb{R}^{d}$. Here, the anchor context
$c_{ij}=({\rm lctx}_{ij},{\rm m}_{ij},{\rm rctx}_{ij})$ where ${\rm m}_{ij}$
is the mention, ${\rm lctx}_{ij}$ is the left context and ${\rm rctx}_{ij}$ is
the right context.

#### Context Representation

A mention’s immediate context is a proxy for its type. Here, the mention’s
immediate context is a sequence of tokens where the mention ${\rm m}_{ij}$ is
replaced with a single [MASK] token. Then, we represent the immediate entity
context by extracting the upper most layer representation of pre-trained BERT
(?) corresponding to the [MASK] token.

$\displaystyle\mathbf{c}_{ij}={\rm BERT}(\\{{\rm lctx}_{ij},{\rm[MASK]},{\rm
rctx}_{ij}\\})$ (7)

#### Entity Representation

For each entity $e_{i}\in\mathcal{E}$, we randomly sample at most N anchor
contexts $\\{c_{i1},c_{i2},...,c_{iN}\\}$ from Wikipedia. Then the entity
representation of $e_{i}$ is computed by aggregating all the context
representation $\\{\mathbf{c}_{i1},\mathbf{c}_{i2},...,\mathbf{c}_{iN}\\}$ via
average pooling.

$\displaystyle{\mathbf{B}}_{e_{i}}=\frac{1}{N}\sum_{j=1}^{N}\mathbf{c}_{ij}$
(8)

As will be shown in the analysis section, the entity embeddings from BERT
better capture entity type information than those from ? (?).

### BERT-based Entity Similarity

The local context model of ? (?) mainly captures the topic level entity
relatedness information based on a long range bag-of-words context. To capture
latent entity type information, we design a BERT-based entity similarity score
$\Psi_{\rm BERT}(e,c)$. Specifically, given a short range (the immediate
context where the mention ${\rm m}$ lies) context $c=({\rm lctx},{\rm m},{\rm
rctx})$, we firstly encode $c$ using the same method defined by Equation 7.

$\displaystyle\mathbf{c}={\rm BERT}(\\{{\rm lctx},{\rm[MASK]},{\rm rctx}\\})$
(9)

Then we define the BERT-based entity similarity as the cosine similarity555We
also investigated calculating the similarity using a parameterized formula by
adding a diagonal matrix between them, but found no significant improvements
over Eq. 10. between the context representation $\mathbf{c}$ and the entity
representation ${\mathbf{B}}_{e}$.

$\displaystyle\Psi_{\rm BERT}(e,c)={\rm cosine}({\mathbf{B}}_{e},\mathbf{c})$
(10)

Finally, as for the local disambiguation model, we integrate the BERT-based
entity similarity $\Psi_{\rm BERT}(e,c)$ with the local context score
$\Psi_{\rm long}(e,c)$ (defined in Equation 2) and the prior
$\hat{p}(e|m_{i})$ with two fully connected layers of 100 hidden units and
ReLU non-linearities following the same feature composition methods as ? (?).

$\displaystyle\Psi_{\rm local}(e,m,c)$ $\displaystyle=f(\Psi_{\rm
long}(e,c),\Psi_{\rm BERT}(e,c),$ (11) $\displaystyle\log\hat{p}(e|m))$

As for the global disambiguation model, we firstly define the local context
score $\Psi_{\rm localctx}(e,c)$ by combining $\Psi_{\rm long}(e,c)$ and
$\Psi_{\rm BERT}(e,c)$.666Following ? (?), we did not integrate the prior
score $\hat{p}(e|m)$ into the local scoring module of the global
disambiguation model.

$\displaystyle\Psi_{\rm localctx}(e,c)$ $\displaystyle=f(\Psi_{\rm
long}(e,c),\Psi_{\rm BERT}(e,c))$ (12)

Then we adopt exactly the same global model as ? (?) which is already
introduced in the Background section. Specifically, we adopt loopy belief
propagation (LBP) to estimate the max-marginal probability $\hat{g}_{i}(e|D)$
and then combine it with the prior $\hat{p}(e|m_{i})$ using a two-layer neural
network to get the final score $\rho_{i}(e)$ for $m_{i}$.

$\displaystyle\Phi(e,e^{\prime})$
$\displaystyle=\frac{2}{n-1}\,\,{\mathbf{x}}_{e}^{\top}{\mathbf{C}}\,{\mathbf{x}}_{e^{\prime}}$
(13) $\displaystyle\hat{g}_{i}(e|D)$
$\displaystyle\approx\max_{\begin{subarray}{c}e_{1},...,e_{i-1}\\\
e_{i+1},...,e_{n}\end{subarray}}g(e_{1},...,e_{n}|D)$ (14)
$\displaystyle\rho_{i}(e)$
$\displaystyle=f^{\prime}(\hat{g}_{i}(e|D),\hat{p}(e|m_{i}))$ (15)

### Model Training

We minimize the following max-margin ranking loss:

$\displaystyle L(\theta)$ $\displaystyle=\sum_{D\in\mathcal{D}}\sum_{m_{i}\in
D}\sum_{e\in C_{i}}h(m_{i},e)+\lambda||\alpha||_{2}^{2}$ (16) $\displaystyle
h(m_{i},e)$ $\displaystyle=\max\big{(}0,\gamma-s(e_{i}^{*})+s(e)\big{)}$
$\displaystyle s(e)$ $\displaystyle=\begin{cases}\Psi_{\rm
local}(e,m,c)&\text{if local model only}\\\ \rho_{i}(e)&\text{local \& global
model}\end{cases}$

In order to discourage the model from biasing toward a particular feature, we
add a L2 regularization term ($\lambda||\alpha||_{2}^{2}$) w.r.t parameters
$\mathbf{\alpha}$ in feature composition function $f$ to the loss function in
Equation 16, where $\lambda$ is set $10^{-7}$.

## Experiments

### Datasets

In order to verify the effectiveness of our model, we conduct experiments on
standard benchmark datasets considering both in-domain and out-domain
settings. For in-domain setting, we use AIDA-CoNLL dataset (?) for training,
validation and testing. For out-domain setting, we evaluate the model trained
with AIDA-CoNLL on five popular out-domain test sets: MSNBC, AQUAINT, ACE 2004
datasets cleaned and updated by ? (?) and WNED-CWEB (CWEB), WNED-WIKI (WIKI)
automatically extracted from ClueWeb and Wikipedia (?). Following previous
work (?), we only consider in-KB mentions. Besides, our candidate generation
strategy follows that of ? (?) to make our results comparable.

### Setup

The main goal of this work is to introduce a BERT-based entity similarity to
capture latent entity type information which is supplementary to existing SOTA
local context model (?). So we evaluate the performance when integrating the
BERT-based entity similarity into the local context model of ? (?). We also
evaluate our model with or without global modeling method of ? (?). In
addition, we further compare our methods with other state-of-the-art models
(?; ?). To verify the contribution of our proposed BERT-based entity
embeddings, we also compare with a straightforward baseline which directly
replaces the encoder of ? (?) utilizing pre-trained BERT. To do so, we
introduce a $768\times 300$ dimensional matrix ${\mathbf{W}}$ which projects
BERT-based context representation $\mathbf{c}$ into ? (?)’s entity embeddings
space when calculating the similarity score.

### Hyper-parameter Setting

The resources (word and entity embeddings) used to train the local context
model of ? (?) are obtained from DeepED777https://github.com/dalab/deep-ed/.
For each entity, we randomly sample at most 100 anchor contexts from
Wikipedia888Using the same Wikipedia dump (Feb 2014) as the one which ? (?)
used to train their entity embeddings. to build the entity representation from
BERT. We discard any articles appearing in WIKI dataset when building the
entity representation from BERT. We take the anchor context as the surrounding
sentence where the mention lies and replace the mention with a single [MASK]
token. Each context is truncated to 128 tokens after WordPiece tokenization.
We use the PyTorch implementation of pre-trained BERT
models999https://github.com/huggingface/pytorch-pretrained-BERT and choose the
BERT-base-cased version. We adopt the Adam (?) implemented by BERT with
$\beta_{1}=0.9$, $\beta_{2}=0.999$. Empirically, we found that it is helpful
to set parameters in BERT a small initial learning rate and not BERT related
parameters a larger initial learning rate to avoid the whole model biasing
toward the BERT feature and disregarding other model components. In our
experiments, pre-trained BERT model is fine-tuned with initial learning rate
$10^{-5}$ whereas not BERT related parameters are trained with $10^{-3}$.
Similar learning rate usage can be found in the recent work by (?). Similar to
? (?), all the entity embeddings are fixed during fine-tuning. We randomly
initialize the not BERT related parameters using Gaussian distribution
$\mathcal{N}(0.0,0.02)$ and the bias term is zeroed.

Note that all the hyper-parameters used in the local context and global model
of ? (?) were set to the same values as theirs for direct comparison purpose.
Detailed hyper-parameters setting is described in the appendices. Our model is
trained with 4 NVIDIA Tesla P100 GPUs. We run each of our model five times
with different random seeds, and the performance is reported in the form of
average $\pm$ standard deviation.

Methods | AIDA-B
---|---
_Local models_ |
prior $\hat{p}(e|m)$ | 71.9
? (?) | 86.4
? (?) | 87.9
? (?) | 87.2
? (?) | 88.8
? (?) (reproduce) | $88.75\pm 0.30$
BERT-Entity-Sim (local) | $\mathbf{90.06}\pm 0.22$
_Local & Global models_ |
? (?) | 86.6
? (?) | 87.6
? (?) | 88.7
? (?) | 89.0
? (?) | 91.0
? (?) | 91.5
? (?) | $92.22\pm 0.14$
? (?) | $93.07\pm 0.27$
_Explicit entity type injection models in Analysis section_
Oracle type (Ultra-fine) | $95.38\pm 0.07$
Oracle type (FIGER) | $96.35\pm 0.14$
Predict type (Ultra-fine) | $91.35\pm 0.18$
Predict type (ZOE) | $91.42\pm 0.09$
BERT+G&H’s embeddings | $91.00\pm 0.72$
BERT-Entity-Sim (local & global) | $\mathbf{93.54}\pm 0.12$

Table 1: F1 scores on AIDA-B (test set).

### Results

Methods | MSNBC | AQUAINT | ACE2004 | CWEB | WIKI | Avg
---|---|---|---|---|---|---
prior $\hat{p}(e|m)$ | 89.3 | 83.2 | 84.4 | 69.8 | 64.2 | 78.18
? (?) | 78 | 85 | 81 | 64.1 | 81.7 | 77.96
? (?) | 79 | 56 | 80 | 58.6 | 63 | 67.32
? (?) | 75 | 83 | 82 | 56.2 | 67.2 | 72.68
? (?) | 90 | $\mathbf{90}$ | 86 | 67.5 | 73.4 | 81.38
? (?) | 92 | 87 | 88 | 77 | $\mathbf{84.5}$ | 85.70
? (?) | 93.7 $\pm$ 0.1 | 88.5 $\pm$ 0.4 | 88.5 $\pm$ 0.3 |  $\mathbf{77.9}$ $\pm$ 0.1 | 77.5 $\pm$ 0.1 | 85.22
? (?) |  $\mathbf{93.9}$ $\pm$ 0.2 | 88.3 $\pm$ 0.6 |  $\mathbf{89.9}$ $\pm$ 0.8 | 77.5 $\pm$ 0.1 | 78.0 $\pm$ 0.1 | 85.51
_Explicit entity type injection models in Analysis section_ |  |  |  |
Oracle type (Ultra-fine) | 96.8 $\pm$ 0.1 | 93.7 $\pm$ 0.2 | 92.0 $\pm$ 0.2 | 85.8 $\pm$ 0.1 | 84.0 $\pm$ 0.1 | 90.46
Oracle type (FIGER) | 97.1 $\pm$ 0.1 | 92.3 $\pm$ 0.2 | 93.1 $\pm$ 0.2 | 84.3 $\pm$ 0.2 | 84.4 $\pm$ 0.1 | 90.24
Predict type (Ultra-fine) | 93.4 $\pm$ 0.2 | 89.7 $\pm$ 0.2 | 89.1 $\pm$ 0.5 | 77.8 $\pm$ 0.1 | 76.8 $\pm$ 0.2 | 85.36
Predict type (ZOE) | 93.2 $\pm$ 0.2 | 89.5 $\pm$ 0.2 | 89.2 $\pm$ 0.4 | 77.6 $\pm$ 0.1 | 77.0 $\pm$ 0.1 | 85.30
BERT+G&H’s embeddings | 93.3 $\pm$ 0.4 | 89.1 $\pm$ 0.6 | 88.1 $\pm$ 0.6 | 75.7 $\pm$ 0.5 | 76.3 $\pm$ 0.5 | 84.50
BERT-Entity-Sim (local & global) | 93.4 $\pm$ 0.1 |  89.8 $\pm$ 0.4 | 88.9 $\pm$ 0.7 |  $\mathbf{77.9}$ $\pm$ 0.4 |  80.1 $\pm$ 0.4 | $\mathbf{86.02}$

Table 2: F1 scores on five out-domain test sets. Underlined scores denote the
corresponding model outperforms the baseline.

| FIGER | BBN | OntoNotes${}_{\text{fine}}$
---|---|---|---
Entity Embedding | $F1_{\text{mi}}$ | $F1_{\text{ma}}$ | Acc. | $F1_{\text{mi}}$ | $F1_{\text{ma}}$ | Acc. | $F1_{\text{mi}}$ | $F1_{\text{ma}}$ | Acc.
? (?) | 80.38 | 82.65 | 53.30 | 80.87 | 84.10 | 69.34 | 81.41 | 83.54 | 57.54
BERT based Entity Embedding | 88.69 | 90.98 | 69.07 | 91.30 | 93.35 | 85.36 | 90.74 | 92.52 | 73.94

Table 3: Results of type classification task on three typing systems: FIGER,
BBN, OntoNotes${}_{\text{fine}}$

Table 1 shows the micro F1 scores on in-domain AIDA-B dataset of the SOTA
methods and ours, which all use Wikipedia and YAGO mention-entity index. The
models are divided into two groups: local models and local & global models. As
we can see, our proposed model, BERT-Entity-Sim, outperforms all previous
methods. Our local model achieves a 1.31 improvement in terms of F1 over its
corresponding baseline (?), yielding a very competitive local model with an
average 90.06 F1 score even surpassing the performance of four local & global
models. Equipped with the global modeling method of ? (?), the performance of
our model further increase to 93.54 with an average 1.32 improvement in terms
of F1 over ? (?). In addition, our method outperforms ? (?) model by 0.47
point. The model of ? (?) is a multi-relational extension of ? (?)’s global
modeling method while keeps exactly the same local context model. Our better
local context model should be orthogonal with them and has potential more
applications on short texts (e.g. tweets) where global modeling has little
benefits. Moreover, BERT+G&H’s embeddings performs significantly worse than
the baseline (?) and our proposed BERT-Entity-Sim model. The reason is that
BERT-based context representation space and ?’s entity embeddings space are
heterogeneous. ?’s entity embeddings are bootstrapped from word embeddings
which mainly capture topic level entity relatedness, while BERT-based context
representation is derived from BERT which naturally captures type information.
The non-parallel information in both context and entity sides makes it
difficult to learn the alignment parameter ${\mathbf{W}}$ and results in the
poor generalization performance.

To evaluate the robustness of our model, Table 2 shows the performance of our
method and SOTA methods on five out-domain test sets. On average, our proposed
model (BERT-Entity-Sim) outperforms the local & global version of ?; ? (?; ?)
by an average 0.80 and 0.51 on F1.

### Analysis

Error Type | # Cases | Percentage (%)
---|---|---
Due to prior | 41 | 67.21
Due to global | 14 | 22.95
Due to local context | 6 | 9.84

Table 4: Remaining type error cases categorization

Typing System | $F1_{\text{mi}}$ | $F1_{\text{ma}}$ | Acc.
---|---|---|---
? (?) | 26.52% | 26.60% | 0.36%
? (?) | 66.12% | 67.98% | 46.08%

Table 5: Performance of two state-of-the-art fine grained entity typing
systems on AIDA-CoNLL development set

We conduct experiment analysis to answer the following questions:

  * •

Do the entity embeddings from BERT better capture latent entity type
information than that of ? (?)?

  * •

Does the proposed model correct the type errors in the baseline (?)?

  * •

Can straightforward integration of state-of-the-art fine grained entity typing
systems improve entity linking performance?

  * •

Can better global model further boost the performance of the proposed model?

Methods | AIDA-B | MSNBC | AQUAINT | ACE2004 | CWEB | WIKI | Avg
---|---|---|---|---|---|---|---
? (?) | 92.22 $\pm$ 0.14 | 93.7 $\pm$ 0.1 | 88.5 $\pm$ 0.4 | 88.5 $\pm$ 0.3 | 77.9 $\pm$ 0.1 | 77.5 $\pm$ 0.1 | 85.22
? (?) | 93.07 $\pm$ 0.27 | 93.9 $\pm$ 0.2 | 88.3 $\pm$ 0.6 | 89.9 $\pm$ 0.8 | 77.5 $\pm$ 0.1 | 78.0 $\pm$ 0.1 | 85.51
? (?) |  $\mathbf{94.64}$ $\pm$ 0.20 |  $\mathbf{94.6}$ $\pm$ 0.2 | 87.4 $\pm$ 0.5 | 89.4 $\pm$ 0.4 | 73.5 $\pm$ 0.1 | 78.2 $\pm$ 0.1 | 84.62
BERT-Entity-Sim (local & global) | 93.54 $\pm$ 0.12 | 93.4 $\pm$ 0.1 |  $\mathbf{89.8}$ $\pm$ 0.4 | 88.9 $\pm$ 0.7 | 77.9 $\pm$ 0.4 | 80.1 $\pm$ 0.4 | 86.02
BERT-Entity-Sim (local & DCA global) | 93.66 $\pm$ 0.17 | 94.5 $\pm$ 0.3 | 89.1 $\pm$ 0.3 |  $\mathbf{90.8}$ $\pm$ 0.4 |  $\mathbf{78.2}$ $\pm$ 0.2 |  $\mathbf{81.0}$ $\pm$ 0.3 | $\mathbf{86.72}$

Table 6: F1 scores of BERT-Entity-Sim equipped with the DCA global model (?)
on six test sets.

#### Effectiveness of BERT-based and Ganea & Hofmann (2017) Entity Embedding
in Entity Type Prediction

In order to verify our claim that the entity embeddings from BERT better
capture entity type information than those from ? (?), we carry out an entity
type prediction task based on its entity embedding. Specifically, we randomly
sample 100K entities from Wikipedia, and randomly split them into training set
(80K), development set (10K) and test set (10K). For each entity, we obtain
its entity types from three typing systems: FIGER (?), BBN (?) and
OntoNotes${}_{\text{fine}}$ (?) via the entity type mapping provided by ? (?).
The entity type prediction model is a simple linear classification
model101010Due to space limitation, we put the detailed description of this
model and training hyper-parameters in the Appendices. using the entity
embedding of an entity as features; limiting its capacity enables us to focus
on whether type information can be easily extracted from the entity
embeddings. We evaluate the model using standard entity typing metrics: Strict
Accuracy (Acc.), Micro F1 ($F1_{\text{mi}}$) and Macro F1 ($F1_{\text{ma}}$).

As shown in Table 3, our proposed entity embedding from BERT significantly
outperforms the entity embedding proposed by ? (?) on three typing systems
FIGER, BBN and OntoNotes${}_{\text{fine}}$. Specifically, our method improves
over the baseline with an absolute 8.31, 10.43 and 9.33 $F1_{\text{mi}}$ point
than the baseline on three typing systems respectively. This demonstrates that
our proposed entity embeddings from BERT indeed capture better latent entity
type information than ? (?).

#### Type Errors Correction

As we have mentioned in the introduction section, more than half of the
baseline model’s errors on the AIDA-A dataset are type errors. Type errors are
error cases111111We discard the error cases due to candidate generation
problem (i.e., gold entities that do not appear in mentions’ candidate list)
which cover 2.98% mentions of AIDA-A dataset. where (1) the predicted entity’s
type is different from the golden entity’s type; (2) contextual cue predictive
of the type of the mention exists; (3) errors are not due to annotation
errors. By doing so, we collect 185 type error cases which cover 57.45% of all
(322) error cases. This indicates that ? (?) produces many type errors due to
its inability to consider the entity type information in mention context. By
integrating the BERT-based entity similarity, our proposed model can correct
124 out of 185 (67.03%) type error cases of the baseline model which
demonstrates that we correct more than two third of the type errors produced
by the baseline. We have further examined and categorized the remaining 61
type error cases into three categories: (i) Due to prior: golden entities with
very low $\hat{p}(e|m_{i})$ prior, (ii) Due to global: both the local context
score and prior score support predicting the golden entity, but the overall
score supports predicting incorrect entity due to global modeling, (iii) Due
to local context: the local context score misleads the model predicting the
wrong entity, this is potentially due to the mention context can be
misleading, e.g. a document discussing cricket will favor resolving the
mention “Australian” in context “impressed by the positive influence of
Australian coach Dave Gilbert” to the entity Australia_national_cricket_team
instead of the gold entity Australia.

As shown in Table 4, 67.21% of the remaining type error cases are due to prior
problem which are hard to solve in the current feature combination framework.
We argue that prior should be considered as the final resort, only relying on
it when the model can not make decision based on other features. Besides,
there are 22.95% remaining type errors which are due to global modeling
problem which shows the limitation of the global modeling method of ? (?).
Finally, 9.84% type error cases are due to local context problem that our
BERT-based solution cannot address. We leave this to future work.

#### Incorporating Explicit Entity Types

We have shown that our BERT-based local context model which implicitly
captures entity type information and is effective in correcting two third of
type error cases. It is nature to conjecture that we can also correct type
errors by incorporating explicit type information into ? (?). We investigate
this approach in this section. Assuming that we have types for each mention
and candidate entity, we calculate the Jaccard similarity between them and use
it as a feature for local disambiguation model.

$\displaystyle{\rm JaccardSim}(e,m,c)=\frac{|T_{m}\cap T_{e}|}{|T_{m}\cup
T_{e}|}$ (17)

where $T_{m}$ and $T_{e}$ are the type sets of the mention $m$ and candidate
entity $e$ respectively. The new local context score function considering
explicit type information is defined as:

$\displaystyle\Psi^{\prime}_{\rm localctx}(e,m,c)$
$\displaystyle=f\big{(}\Psi_{\rm long}(e,c),{\rm JaccardSim}(e,m,c)\big{)}$

We consider both Oracle setting and Predict setting. In the oracle setting,
the mention’s types are set as the golden entity’s types.121212In practice,
this setting is unachievable due to potentially insufficient context and the
imperfect entity typing system. As for the entity’s types, we use two sources:
one is the ultra-fine type sets from ? (?) consisting of more than 10,000
ultra-fine grained types; the other one is the FIGER type sets (?) consisting
of 112 fine grained types. In the predict setting, we use two state-of-the-art
fine grained entity typing systems: 1) Ultra-fine (?) which predicts types in
ultra-fine type sets; 2) ZOE (?) which can predict types in FIGER type sets.

As we can see from both Table 1 and Table 2, in the oracle setting, the best
model outperforms all the state-of-the-art entity linking models by a large
margin, even surpass ? (?) by 3.28 F1 points on AIDA-CoNLL test set. This
result shows that a better type prediction system can further improve upon the
state-of-the-state entity linking systems. However, in the predict setting,
the type injection models have worse performance than the baseline. The
degradation might be attributed to the poor performance of the two state-of-
the-art fine grained entity typing systems. To verify this, we measure the
performance of the two typing systems on AIDA-CoNLL development set.131313The
mention’s golden types are set as its linked entity’s types. As shown in Table
5, the ultra-fine entity typing system (?) only achieves 26.52%
$F1_{\text{mi}}$ score while the ZOE system (?) achieves 66.12%
$F1_{\text{mi}}$ score141414The size of type sets of ultra-fine typing system
is much larger than that of ZOE. which are insufficient to improve state-of-
the-art entity linking system with more than 92% F1 score.

#### Better Global Model

In order to investigate whether better global model can further boost the
performance of our model, we incorporate the recent proposed Dynamic Context
Augmentation (DCA)151515https://github.com/YoungXiyuan/DCA/ (?). DCA is a
global entity linking model featuring better efficiency and effectiveness than
that of ? (?) by breaking the “all-mention coherence” assumption. Compared to
BERT-Entity-Sim equipped with ? (?)’s global model in Table 8, BERT-Entity-Sim
(local & DCA global) model gains a further improvement of 0.12 F1 on AIDA-B
and 0.70 F1 on five out-domain test sets on average. This shows that better
global model indeed can further boost the performance of our proposed model.

Notice that ? (?) achieves a high performance on in-domain AIDA-CoNLL test
set, but doesn’t perform well on five out-domain test sets (even inferior than
? (?)). We found that ? (?) includes an explicit type similarity which is
based on a typing system161616It yields 95% accuracy on AIDA-A according to
their paper. trained with AIDA-train NER annotation. This explicit type
similarity feature is tailored for AIDA-CoNLL data set and doesn’t achieve
good generalization performance on out-domain test sets. In contrast, our
BERT-Entity-Sim model capturing latent type information has potential better
generalization performance with an average 2.10 F1 improvement over them.

### Case Study

Model | Context | Context Sim | Golden Entity
---|---|---|---
Our | In Milwaukee , Marc Newfield homered off Jose Parra ( 5-4 ) … | - | Milwaukee
(1) In Cleveland , Kevin Seitzer ’s two-out single … | 0.968 | Cleveland
(2) In Boston , Troy O’Leary homered off the right-field … | 0.956 | Boston
(3) In Houston , Jeff Bagwell homered and Donne Wall … | 0.951 | Houston
(4) In Los Angeles , Greg Gagne had a run-scoring single … | 0.949 | Los_Angeles
(5) In Houston , Andy Benes allowed two runs over seven innings … | 0.947 | Houston
Baseline | ninth ninth seventh seventh Milwaukee Milwaukee inning games games victory … | - | Milwaukee
(1) eighth ninth Milwaukee inning league runs victory fourth rallied earned … | 0.941 | Milwaukee_Brewers
(2) Denny runs fifth fifth allowed game fourth San win win … | 0.940 | Philadelphia_Phillies
(3) Royals league games runs game won won win Minnesota straight … | 0.938 | Minnesota_Twins
(4) Cleveland fifth games sixth inning innings Friday extra Sox month … | 0.934 | Cleveland_Indians
(5) games streak stay Reynoso runs runs second run won fourth … | 0.926 | Miami_Marlins

Table 7: Nearest contexts for the example in Fig. 1 in BERT’s and baseline’s
context representation space

Model | Steve_Jobs | National_Basketball_Association | Beijing
---|---|---|---
? (?) | Apple_Inc. | Sacramento_Kings | Seoul
Steve_Wozniak | Golden_State_Warriors | Shanghai
Bill_Gates | Los_Angeles_Clippers | China
BERT based Entity Embedding | Steve_Wozniak | American_Basketball_Association | Guangzhou
Bill_Gates | Women’s_National_Basketball_Association | Shanghai
Steve_Ballmer | National_Basketball_League_(United_States) | Nanjing

Table 8: Examples of nearest entities in ? (?) and BERT based entity
representation space

We demonstrate the effectiveness of our proposed model by retrieving the
nearest neighbours in both the context representation space and entity
representation space.

#### Nearest Contexts

We follow ? (?) to retrieve training examples using nearest neighbour in the
context representation space. For our model, we use the context representation
$\mathbf{c}$ defined by Equation 9. For the baseline model, we use the
attention-based context representation $h(c)$ defined in Equation 2. This can
reveal which training instances support the prediction of a model. As shown in
Table 7, for the example in Figure 1, the most similar contexts retrieved by
our model’s context representation are all with preposition “In” ahead of the
mention and the golden entities of them are all American cities. In contrast,
the baseline’s local context is a bag-of-words representation which we denote
using the top 10 attended contextual words sorted by attention weights. The
most similar contexts retrieved by baseline’s context representation share
common words like “games”, “victory” and the golden entities of them are all
baseball teams. This explains why the baseline model incorrectly links the
mention “Milwaukee” to Milwaukee_Brewers while our model can link to the
correct entity Milwaukee.

#### Nearest Entities

We also retrieve nearest entities in the embedding space of ? (?) and ours. As
we can see, we query Steve_Jobs, the nearest entity in ? (?) is Apple_Inc.
which is a different type. In contrast, all the entities retrieved by our
approach share the same types like person, entrepreneur etc. Another example
is when we query National_Basketball_Association, the most similar entities in
? (?) are NBA teams which are topically related, while the entities retrieved
by our approach are all basketball leagues.

## Conclusion

In this paper, we propose to improve entity linking by capturing latent entity
type information with BERT. Firstly, we build entity embeddings from BERT by
averaging all the context representation extracted from pre-trained BERT. Then
we integrate a BERT-based entity similarity into the local model of the state-
of-the-art method by (?). The experiment results show that our model
significantly outperforms the baseline with an absolute improvement of 1.32%
F1 on in-domain AIDA-CoNLL test set and average 0.80% F1 on five out-domain
test datasets. The detailed experiment analysis shows that our method corrects
most of the type errors produced by the baseline. In the future, we would like
to design global modeling methods which can take advantage of the BERT
architecture and investigate other ways to use the prior feature.

## Acknowledgments

This work is partly funded by National Key Research and Development Program of
China via grant 2018YFC0806800 and 2018YFC0832105.

## Appendices

### Classification Model of Entity Prediction Task

Given an entity $e$, we firstly retrieve its entity embedding $\mathbf{e}$,
then compute the probability for each type in the typeset $T$:

$\displaystyle p_{j}^{e}=\sigma(\mathbf{w_{j}}^{\top}\mathbf{e}+b)$ (18)

where $\sigma$ is the sigmoid function, $\mathbf{w_{j}}$ and $b$ are
respectively the weight and bias parameter. For each entity $e$, it is labeled
with $t^{e}$, a binary vector of all types where $t_{j}^{e}=1$ if the $j^{\rm
th}$ type is in the set of gold types of $e$ and 0 otherwise. We optimize a
multi-label binary cross entropy objective:

$\displaystyle L_{\rm type}=-\sum_{j}t_{j}^{e}\log
p_{j}^{e}+(1-t_{j}^{e})\log(1-p_{j}^{e})$ (19)

We optimize the model with Adam with an initial learning rate of 1e-3. Each
model is trained for up to 200 epoches and training stops when the performance
on the development set does not improve for 6 consecutive epoches.

### Detailed Hyper-parameters Setting (Table 9)

Hyper-parameters | Value
---|---
BERT-based entity embedding dims | 768
dumping factor | 0.5
number of LBP loops | 10
batch size | 1 document
| ($\leq 64$ mentions)
$\gamma$ (margin) | 0.01
epoch (local model) | 2
epoch (local & global model) | 10

Table 9: Values of hyper-parameters.

## References

  * [Cheng and Roth 2013] Cheng, X., and Roth, D.  2013\.  Relational inference for wikification.  In EMNLP, 1787–1796.
  * [Chisholm and Hachey 2015] Chisholm, A., and Hachey, B.  2015\.  Entity disambiguation with web links.  TACL 3\.
  * [Choi et al. 2018] Choi, E.; Levy, O.; Choi, Y.; and Zettlemoyer, L.  2018\.  Ultra-fine entity typing.  In ACL, 87–96.
  * [Devlin et al. 2019] Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K.  2019\.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In NAACL.
  * [Durrett and Klein 2014] Durrett, G., and Klein, D.  2014\.  A joint model for entity analysis: Coreference, typing, and linking.  TACL.
  * [Dyer et al. 2015] Dyer, C.; Ballesteros, M.; Ling, W.; Matthews, A.; and Smith, N. A.  2015\.  Transition-based dependency parsing with stack long short-term memory.  In ACL, 334–343.
  * [Ganea and Hofmann 2017] Ganea, O.-E., and Hofmann, T.  2017\.  Deep joint entity disambiguation with local neural attention.  In EMNLP.
  * [Ganea et al. 2016] Ganea, O.-E.; Ganea, M.; Lucchi, A.; Eickhoff, C.; and Hofmann, T.  2016\.  Probabilistic bag-of-hyperlinks model for entity linking.  In WWW.
  * [Gillick et al. 2014] Gillick, D.; Lazic, N.; Ganchev, K.; Kirchner, J.; and Huynh, D.  2014\.  Context-dependent fine-grained entity type tagging.  arXiv preprint arXiv:1412.1820.
  * [Globerson et al. 2016] Globerson, A.; Lazic, N.; Chakrabarti, S.; Subramanya, A.; Ringaard, M.; and Pereira, F.  2016\.  Collective entity resolution with multi-focal attention.  In ACL, volume 1.
  * [Guo and Barbosa 2016] Guo, Z., and Barbosa, D.  2016\.  Robust named entity disambiguation with random walks.  Semantic Web, (Preprint).
  * [Harris 1954] Harris, Z. S.  1954\.  Distributional structure.  Word 10(2-3).
  * [Hoffart et al. 2011] Hoffart, J.; Yosef, M. A.; Bordino, I.; Fürstenau, H.; Pinkal, M.; Spaniol, M.; Taneva, B.; Thater, S.; and Weikum, G.  2011\.  Robust disambiguation of named entities in text.  In EMNLP.
  * [Hoffmann et al. 2011] Hoffmann, R.; Zhang, C.; Ling, X.; Zettlemoyer, L.; and Weld, D. S.  2011\.  Knowledge-based weak supervision for information extraction of overlapping relations.  In ACL.
  * [Huang, Heck, and Ji 2015] Huang, H.; Heck, L.; and Ji, H.  2015\.  Leveraging deep neural networks and knowledge graphs for entity disambiguation.  arXiv preprint arXiv:1504.07678.
  * [Hwang et al. 2019] Hwang, W.; Yim, J.; Park, S.; and Seo, M.  2019\.  A comprehensive exploration on wikisql with table-aware word contextualization.  arXiv preprint arXiv:1902.01069.
  * [Kingma and Ba 2014] Kingma, D. P., and Ba, J.  2014\.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980.
  * [Lazic et al. 2015] Lazic, N.; Subramanya, A.; Ringgaard, M.; and Pereira, F.  2015\.  Plato: A selective context model for entity resolution.  TACL.
  * [Le and Titov 2018] Le, P., and Titov, I.  2018\.  Improving entity linking by modeling latent relations between mentions.  In ACL, 1595–1604.
  * [Le and Titov 2019a] Le, P., and Titov, I.  2019a.  Boosting entity linking performance by leveraging unlabeled documents.  In ACL.
  * [Le and Titov 2019b] Le, P., and Titov, I.  2019b.  Distant learning for entity linking with automatic noise detection.  In ACL.
  * [Ling and Weld 2012] Ling, X., and Weld, D. S.  2012\.  Fine-grained entity recognition.  In AAAI.
  * [Luo et al. 2015] Luo, G.; Huang, X.; Lin, C.-Y.; and Nie, Z.  2015\.  Joint entity recognition and disambiguation.  In EMNLP, 879–888.
  * [Martins, Marinho, and Martins 2019] Martins, P. H.; Marinho, Z.; and Martins, A. F.  2019\.  Joint learning of named entity recognition and entity linking.  In ACL: Student Research Workshop.
  * [Mikolov et al. 2013] Mikolov, T.; Sutskever, I.; Chen, K.; Corrado, G. S.; and Dean, J.  2013\.  Distributed representations of words and phrases and their compositionality.  In NIPS, 3111–3119.
  * [Milne and Witten 2008] Milne, D., and Witten, I. H.  2008\.  Learning to link with wikipedia.  In CIKM.  ACM.
  * [Nguyen, Theobald, and Weikum 2016] Nguyen, D. B.; Theobald, M.; and Weikum, G.  2016\.  J-nerd: joint named entity recognition and disambiguation with rich linguistic features.  TACL 4:215–229.
  * [Papernot and McDaniel 2018] Papernot, N., and McDaniel, P.  2018\.  Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning.  arXiv preprint arXiv:1803.04765.
  * [Ratinov et al. 2011] Ratinov, L.; Roth, D.; Downey, D.; and Anderson, M.  2011\.  Local and global algorithms for disambiguation to Wikipedia.  In ACL.
  * [Wainwright, Jordan, and others 2008] Wainwright, M. J.; Jordan, M. I.; et al.  2008\.  Graphical models, exponential families, and variational inference.  Foundations and Trends® in Machine Learning 1(1–2):1–305.
  * [Weischedel and Brunstein 2005] Weischedel, R., and Brunstein, A.  2005\.  Bbn pronoun coreference and entity type corpus.  Linguistic Data Consortium.
  * [Yamada et al. 2016] Yamada, I.; Shindo, H.; Takeda, H.; and Takefuji, Y.  2016\.  Joint learning of the embedding of words and entities for named entity disambiguation.  CoNLL.
  * [Yang et al. 2019] Yang, X.; Gu, X.; Lin, S.; Tang, S.; Zhuang, Y.; Wu, F.; Chen, Z.; Hu, G.; and Ren, X.  2019\.  Learning dynamic context augmentation for global entity linking.  In EMNLP.
  * [Yih et al. 2015] Yih, W.-t.; Chang, M.-W.; He, X.; and Gao, J.  2015\.  Semantic parsing via staged query graph generation: Question answering with knowledge base.  In ACL.
  * [Zhou et al. 2018] Zhou, B.; Khashabi, D.; Tsai, C.-T.; and Roth, D.  2018\.  Zero-shot open entity typing as type-compatible grounding.  In EMNLP.


# Binary Subgroups of Direct Products

Martin R. Bridson  Martin R. Bridson
Mathematical Institute
Andrew Wiles Building
Oxford OX2 6GG
UK<EMAIL_ADDRESS>
###### Abstract.

We explore an elementary construction that produces finitely presented groups
with diverse homological finiteness properties – the binary subgroups,
$B(\Sigma,\mu)<G_{1}\times\dots\times G_{m}$. These full subdirect products
require strikingly few generators. If each $G_{i}$ is finitely presented,
$B(\Sigma,\mu)$ is finitely presented. When the $G_{i}$ are non-abelian limit
groups (e.g. free or surface groups), the $B(\Sigma,\mu)$ provide new examples
of finitely presented, residually-free groups that do not have finite
classifying spaces and are not of Stallings-Bieri type. These examples settle
a question of Minasyan relating different notions of rank for residually-free
groups. Using binary subgroups, we prove that if $G_{1},\dots,G_{m}$ are
perfect groups, each requiring at most $r$ generators, then
$G_{1}\times\dots\times G_{m}$ requires at most $r\lfloor\log_{2}m+1\rfloor$
generators.

###### Key words and phrases:

Binary subgroups, finiteness properties, VSP Theorem, residually-free groups

###### 1991 Mathematics Subject Classification:

20F05, 20J05

For my friend Vaughan Jones, in memoriam

##  1\. Introduction

In the study of infinite groups, the problem of deciding which finite subsets
of a given group $G$ generate finitely presentable subgroups is notoriously
difficult: there is no algorithm that can solve this problem when $G$ is a
direct product of two non-abelian free groups for example [17]. Even when one
knows that finite presentations exist, constructing them can remain impossibly
difficult [4].

In this article we will explore an elementary construction that provides a new
source of finitely presented subdirect products of groups; we call them binary
subgroups. This construction takes as input two positive integers $m$ and $r$,
an $m$-tuple of $r$-generator groups with markings
$\mu=(\mu_{i}:F_{r}\to\hskip-9.95863pt\to G_{i})_{i=1}^{m}$, and an $r$-tuple
of finite sets of positive integers $\Sigma=(\sigma_{1},\dots,\sigma_{r})$,
with each $|\sigma_{i}|=m$. It outputs a subgroup
$B(\Sigma,\mu)<G_{1}\times\dots\times G_{m}$ that is finitely presented if all
of the $G_{i}$ are finitely presented. $B(\Sigma,\mu)$ is constructed from the
binary expansions of the elements of $\bigcup\sigma_{i}$. I hope to convince
the reader that this construction is an intriguing source of groups that
merits further study.

An important feature of the groups $B(\Sigma,\mu)$ is that they require
strikingly few generators: see Corollaries 1.3 and 1.4. The case where each
$G_{i}$ is free will be of particular interest. Indeed the construction of
$B(\Sigma,\mu)$ is motivated in large part by my work with Howie, Miller and
Short [5, 6] exploring the structure of subgroups of direct products of free
groups, surface groups and limit groups. The VSP Theorem from [6] will play a
prominent role in our discussion, as will homological finiteness properties.

In addition to economical generation and finiteness properties, we shall be
concerned with the co-nilpotency class of binary subgroups. Co-nilpotency is a
characteristic of finitely presented, residually free groups that originates
in [8]; it played a prominent role in [5, 6]. Let
$S<\Lambda_{1}\times\dots\times\Lambda_{m}$ be a finitely presented subgroup
of a direct product of non-abelian limit groups (e.g. free groups), and
suppose that we have reduced to the case where $S$ intersects each
$\Lambda_{i}$ non-trivially and the coordinate projections $S\to\Lambda_{i}$
are onto (in other words, $S$ is a full subdirect product). It is proved in
[6] that in this case $S$ contains some term of the lower central series of a
subgroup of finite index $D_{0}<\Lambda_{1}\times\dots\times\Lambda_{m}$. If
the first such term is $\gamma_{c+1}(D_{0})$, then the co-nilpotency class of
$S$ is defined to be $c$. Thus $S$ has co-nilpotency class $0$ if it is of
finite index and it has co-nilpotency class $1$ if it is virtually the kernel
of a map from a product of non-abelian limit groups to an infinite abelian
group. Groups of the latter kind are, by definition, of Stallings-Bieri type;
they have been extensively studied in connection with higher finiteness
properties [20, 2]. One of the achievements of [5] was to exhibit the first
examples of finitely presented, residually free groups whose co-nilpotency
class is greater than $1$. The binary subgroups that we shall describe provide
a more elementary construction of such groups with a variety of co-nilpotency
classes. For example, the co-nilpotency classes of the groups $B_{0}(m)$ and
$B_{1}(m)$ constructed below go to infinity with $m$.

###  1.1. Paradigms: the Binary Subgroups $B_{0}(m)$ and $B_{1}(m)$

Before delving into more technical matters, I want to illustrate the basic
construction of this article with explicit examples. We work with a free group
of rank $r$, denoted by $F$, and fix a basis $\\{a_{1},\dots,a_{r}\\}$.
Throughout, $F^{m}$ will denote the $m$-th direct power $F\times\dots\times
F$.

We consider two subgroups $B_{0}(m)<B_{1}(m)<F^{m}$. The subgroup $B_{0}(m)$
is generated by the $r\lfloor 1+\log_{2}m\rfloor$ elements $a_{ij}$ defined as
follows: consider the array $A(m)$ with $m$ columns and $\lfloor
1+\log_{2}m\rfloor$ rows where column $k$ is the binary expansion of $k$, with
units at the top; for $j=0,\dots,\lfloor\log_{2}m\rfloor$ let
$\varepsilon_{j}(m)$ be the word in the alphabet $\\{0,1\\}$ that is the
$j$-th row of $A(m)$ (so $k=\sum_{j}\varepsilon_{j}(k)2^{j}$); we treat
$\varepsilon_{j}(m)$ as a multi-index and, for each $a_{i}$, define $a_{ij}\in
F^{m}$ to be the element obtained by raising $a_{i}$ to this multi-index, with
the convention $a_{i}^{1}=a_{i}$ and $a_{i}^{0}=1$ (the identity).

For example, when $m=18$,

Table 1. The binary array $A(m)$ for $m=18$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\varepsilon_{0}$ | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0
$\varepsilon_{1}$ | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1
$\varepsilon_{2}$ | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0
$\varepsilon_{3}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0
$\varepsilon_{4}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1
Table 2. The binary elements $a_{ij}$ when $m=18$ $a_{i0}=$ | ($a_{i}$, | 1, |  $a_{i}$, | 1, |  $a_{i}$, | 1, |  $a_{i}$, | 1, |  $a_{i}$, | 1, |  $a_{i}$, | 1, |  $a_{i}$, | 1, |  $a_{i}$, | 1, |  $a_{i}$, | 1)
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$a_{i1}=$ | (1, |  $a_{i}$, |  $a_{i}$, | 1, | 1, |  $a_{i}$, |  $a_{i}$, | 1, | 1, |  $a_{i}$, |  $a_{i}$, | 1, | 1, |  $a_{i}$, |  $a_{i}$, | 1, | 1, |  $a_{i}$)
$a_{i2}=$ | (1, | 1, | 1, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, | 1, | 1, | 1, | 1, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, | 1, | 1, | 1)
$a_{i3}=$ | (1, | 1, | 1, | 1, | 1, | 1, | 1, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$, | 1, | 1, | 1)
$a_{i4}=$ | (1, | 1, | 1, | 1, | 1, | 1, | 1, | 1, | 1, | 1, | 1, | 1, | 1, | 1, | 1, |  $a_{i}$, |  $a_{i}$, |  $a_{i}$)

The subgroup $B_{1}(m)<F^{m}$ is obtained from $B_{0}(m)$ by adjoining the
diagonal elements $\delta_{i}:=(a_{i},\dots,a_{i})$,

$B_{1}(m)=\langle B_{0},\delta_{1},\dots,\delta_{r}\rangle<F^{m}.$

In our discussion of finiteness properties, the most natural ones to consider
are finite presentation, type ${\rm{FP}}_{k}$ and weak ${\rm{FP}}_{k}$
(written ${\rm{wFP}}_{k}$). A group $G$ is of type ${\rm{FP}}_{k}$ if the
trivial $\mathbb{Z}G$-module $\mathbb{Z}$ has a projective resolution in which
the modules up to dimension $k$ are finitely generated, and $G$ has type
${\rm{wFP}}_{k}$ if $H_{i}(G_{0},\mathbb{Z})$ is finitely generated for all
$i\leq k$ and all subgroups $G_{0}<G$ of finite index. Finite presentation
implies ${\rm{FP}}_{2}$ and ${\rm{FP}}_{k}$ implies ${\rm{wFP}}_{k}$.

We use the standard notation for the lower central series of a group,
$\gamma_{1}(G)=G$ and $\gamma_{c+1}(G)=[G,\gamma_{c}(G)]$. We also use the
standard term rank and write $d(G)$ for the cardinality of a smallest
generating set for $G$.

######  Theorem 1.1.

For $r\geq 2,m\geq 3$,

  1. (1)

the rank of $B_{0}(m)<F^{m}$ is $r(\lfloor 1+\log_{2}m\rfloor)$;

  2. (2)

the rank of $B_{1}(m)<F^{m}$ is $r(\lfloor 2+\log_{2}m\rfloor)$;

  3. (3)

$B_{0}(m)$ contains $\gamma_{m-1}(F^{m})$;

  4. (4)

$B_{1}(m)$ contains $\gamma_{c}(F^{m})$, where $c=\lceil(m-1)/2\rceil$;

  5. (5)

$B_{0}(m)$ is finitely presented but not of type ${\rm{wFP}}_{3}$;

  6. (6)

if $m\leq 4$ then $B_{1}(m)=F^{m}$;

  7. (7)

if $m\geq 5$ then $B_{1}(m)$ is finitely presented, type ${\rm{wFP}}_{3}$ but
not ${\rm{wFP}}_{4}$;

  8. (8)

$\forall c\ \exists$ polynomial $p_{c}(t)$ of degree $c$ such that if
$m>p_{c}(\log_{2}m)$ and $D_{0}<F^{m}$ is of finite index, then
${{\gamma_{c}(D_{0})\not\subseteq B_{1}(m)}}$.

One can replace $F$ by a non-abelian limit group in this theorem – see Theorem
4.4.

The general binary subgroup $B(\Sigma)<F^{m}$ is obtained from
$\Sigma=(\sigma_{1},\dots,\sigma_{r})$ by writing the binary expansions of the
elements of each $\sigma_{i}$ as the columns of an array, as above – the
$i$-th array $A_{i}$ will have $l_{i}$ rows where $l_{i}=\max\\{\lfloor
1+\log_{2}x\rfloor\mid x\in\sigma_{i}\\}$; the generators $a_{ij}\in
B(\Sigma)$ are obtained by raising $a_{i}$ to the multi-index given by the
$j$-th row of $A_{i}$ (see Section 5 for more details).

Given any $m$-tuple of $r$-generator groups with markings
$(\mu_{i}:F\to\hskip-9.95863pt\to G_{i})_{i=1}^{m}$, we take the image of
$B(\Sigma)<F^{m}$ under the epimorphism $\mu=(\mu_{1},\dots,\mu_{m})$ to
define $B(\Sigma,\mu)$. With this notation we have:

######  Theorem 1.2.

$B(\Sigma,\mu)<G_{1}\times\dots\times G_{m}$ contains the $(m-1)$st term of
the lower central series and is closed in the profinite topology. Moreover,
there is an algorithm that, given $\Sigma,\mu$ and finite presentations of
$G_{1},\dots,G_{m}$, will construct a finite presentation for $B(\Sigma,\mu)$.
If the $G_{i}$ are limit groups, then there is an algorithm that will
determine for each $k\geq 2$ whether $B(\Sigma,\mu)$ is of type
${\rm{wFP}}_{k}$.

The passage from $B(\Sigma,\mu)$ to $B(\Sigma)<F^{m}$ is an example of how one
can push forward subdirect products: see Sections 2.3 and 5.2, where we also
examine the results of pulling back subgroups.

###  1.2. Economical generation

Philip Hall [12] initiated the study of economical generating sets for direct
powers of finite perfect groups. The theory was subsequently developed
extensively by Jim Wiegold [21] and others, and elements of it were extended
to cover infinite groups [22]: if $G$ is finitely generated and perfect, then
$G^{m}$ requires at most $O(\log m)$ generators. Theorems 1.1 and 1.2 allow us
to extend this statement about $d(G^{m})$ to direct products of distinct
groups. For if $G_{1},\dots,G_{m}$ each require at most $r$ generators, then
by pushing forward $B_{0}(m)<F^{m}$ we obtain a subgroup
$B<G_{1}\times\dots\times G_{m}$ with $d(B)\leq r\lfloor 1+\log_{2}m\rfloor$
that contains a term of the lower central series of the product, and if the
$G_{i}$ are perfect then each term of the lower central series is equal to the
entire product.

######  Corollary 1.3.

If $G_{1},\dots,G_{m}$ are perfect and $d(G_{i})\leq r$, then
$d(G_{1}\times\dots\times G_{m})\leq r\lfloor 1+\log_{2}m\rfloor.$

For direct powers of finitely presented superperfect groups, the logarithmic
growth of $d(G^{m})$ can be promoted to a polylogarithmic bound on the number
of relators needed to present $G^{m}$ (see [3]), but we do not have such a
result for more general direct products.

###  1.3. Economical embeddings of residually free groups

In [6] an algorithm is established that, given a finite presentation of a
residually free group $G$, will construct a canonical embedding of $G$ into
its existential envelope $\exists\\!\\!{\rm{E}}(G)$, which is a direct product
of finitely many limit groups (see Section 3 below for definitions). If $G$ is
centerless, then the number of direct factors in $\exists\\!\\!{\rm{E}}(G)$ is
the product rank of $G$, i.e. the largest integer ${\rm{rk}_{F}}(G)$ such that
$G$ contains a direct power of non-abelian free groups
$F_{2}^{{\rm{rk}_{F}}(G)}$. If a direct product of finitely many limit groups
contains $G$ then it contains $\exists\\!\\!{\rm{E}}(G)$ and has at least
${\rm{rk}_{F}}(G)$ direct factors.

In [18], Ashot Minasyan proved that if $d(G)=k$ then
$\exists\\!\\!{\rm{E}}(G)$ is a product of at most
$\exp(C_{\varepsilon}k^{2+\varepsilon})$ limit groups, where $\varepsilon>0$
is arbitrary and $C_{\varepsilon}$ is a constant that goes to infinity with
$\varepsilon$. He asked if this upper bound could be improved to a polynomial
in $k$. Theorem 1.1 answers his question in the negative: one cannot do better
than an exponential function of $k$. To see this, note that parts (3) and (4)
of the theorem imply that $B_{0}(m)$ and $B_{1}(m)$ both have product rank
$m$.

######  Corollary 1.4.

There exist sequences of finitely presented, centerless, residually-free
groups $B(m)$ with product rank ${\rm{rk}_{F}}(B(m))=m$ requiring only
$d(B(m))=O(\log m)$ generators.

This article is organised as follows. In Section 2 we gather some basic facts
about nilpotent groups and subdirect products, and state the VSP Theorem. In
Section 3 we recall some elements of the theory of residually free groups and
present the results that we need from [5, 6, 13, 14] relating finiteness
properties of subdirect products to coordinate projections. Section 4 contains
the proof of Theorem 1.1. In Section 5 we discuss the general construction of
binary subgroups, the process of pushing them forward and pulling them back,
and certain redundancies in the general construction. In the final section we
discuss possible variations, open questions, and directions for future work,
including an enticing connection with coding theory.

Acknowedgements: I thank Ben Green and Yonathan Fruchter for helpful
discussions concerning the connection to coding theory described in Section 6.
I thank Claudio Llosa Isenrich for encouraging comments and for drawing my
attention to Ashot Minasyan’s question [18]. And I thank my co-authors from
[5, 6], Jim Howie, Chuck Miller and Hamish Short, for many years of
stimulating and enjoyable conversations about subdirect products of limit
groups.

##  2\. Preliminaries

###  2.1. Nilpotent groups

With the exception of Proposition 2.2, the material in this section is
standard and can be found in Chapter 11 of the classical reference [11]. The
terms of the lower central series of a group $G$ are defined by
$\gamma_{1}(G)=G$ and $\gamma_{n+1}(G)=[G,\gamma_{n}(G)]$. If
$\gamma_{c+1}(G)=1$ but $\gamma_{c}(G)\neq 1$ then $G$ is said to be nilpotent
of class $c$. The free nilpotent group of class $c$ and rank $k$ is
$N(k,c):=F_{k}/\gamma_{c+1}(F_{k})$; every $k$-generator nilpotent group of
class at most $c$ is a quotient of this group.

If $\\{a_{1},\dots,a_{k}\\}$ is a basis for $F_{k}$, then the basic
commutators $[a_{i_{1}},\dots,a_{i_{n}}]$ of weight $n$ project under the
natural map $F_{k}\to F_{k}/\gamma_{n+1}(F_{k})$ to a basis of the free
abelian group $\gamma_{n}(F_{k})/\gamma_{n+1}(F_{k})$, the rank of which is
given by the Witt formula

$W_{n}(k)=\frac{1}{n}\sum_{d|n}\mu(d)k^{n/d}$

where $\mu(d)$ is the Möbius function. By making repeated use of this
observation, we see that $N(k,c)$ is a polycyclic group whose Hirsch length
(cohomological dimension) is $h(k,c)=\sum_{i=1}^{c}W_{i}(k)$. A simple
induction then shows that every subgroup of $N(k,c)$ requires at most $h(k,c)$
generators. The crude approximation $W_{n}(k)\leq k^{n}$ gives
$h(k,c)\leq\sum_{i=1}^{c}k^{i}$, which is all that we shall need for the
polynomial in the last item of Theorem 1.1.

######  Lemma 2.1.

If $H$ is a subgroup of a $k$-generator nilpotent group $G$ of class at most
$c$, then $d(H)\leq h(k,c)$.

###### Proof.

By choosing an epimorphism $N(k,c)\to\hskip-9.95863pt\to G$ and replacing $H$
with its preimage in $N(k,c)$ we may assume that $G=N(k,c)$, and this case is
covered by the preceding discussion. ∎

The following is the main output that we require from this subsection.

######  Proposition 2.2.

Let $\Lambda_{1},\dots,\Lambda_{m}$ be finitely generated groups each of which
maps onto a non-abelian free group. Suppose
$D=\Lambda_{1}\times\dots\times\Lambda_{m}$ has a $k$-generator subgroup $S$
that contains $\gamma_{c}(D_{0})$ where $D_{0}<D$ is a subgroup of finite
index. Then $m\leq h(k,c)/W_{c}(2)$.

###### Proof.

The hypothesis yields a surjection $D\to\hskip-9.95863pt\to F_{2}^{m}$ which
maps $\gamma_{i}(D)$ onto $\gamma_{i}(F_{2})^{m}$. We compose
$D\to\hskip-9.95863pt\to F_{2}^{m}$ with the canonical surjection
$F_{2}^{m}\to\hskip-9.95863pt\to N(2,c)^{m}$. Let $\overline{S}$ and
$\overline{D}_{0}$ be the images of $S$ and $D_{0}$ under this composition.
Then $d(\overline{S})\leq k$ and $\overline{S}$ is a nilpotent group of class
at most $c$ containing $\gamma_{c}(\overline{D}_{0})$. The latter has finite
index in the $m$-th direct power of $\gamma_{c}(F_{2})/\gamma_{c+1}(F_{2})$,
which is a free abelian group of rank $mW_{c}(2)$, hence
$d(\gamma_{c}(\overline{D}_{0}))=mW_{c}(2)$. Therefore $mW_{c}(2)\leq h(k,c),$
by Lemma 2.1. ∎

The following well-known facts are proved by induction on the nilpotency
class.

######  Lemma 2.3.

Let $N$ be a finitely generated nilpotent group. A subset $\Theta\subset N$
generates $N$ if and only if the image of $\Theta$ in the abelianization
$N^{\rm{ab}}=H_{1}(N,\mathbb{Z})$ generates $N^{\rm{ab}}$.

######  Lemma 2.4.

If a nilpotent group $N$ is generated by a finite set of elements of finite
order, then $N$ is finite.

###  2.2. Subdirect Products and the VSP Theorem

A subgroup of a direct product $S<G_{1}\times\dots\times G_{m}$ is termed a
subdirect product if $S$ projects onto each $G_{i}$; it is a full subdirect
product if, in addition, $S\cap G_{i}\neq 1$ for all $i$. If one wishes to
understand the finitely generated subgroups of direct products of groups drawn
from a class that is closed under the taking of finitely generated subgroups,
then one can reduce to the study of full subdirect products by projecting away
from factors where $S\cap G_{i}=1$ and replacing each $G_{j}$ by the
projection of $S$ to $G_{j}$; free groups form one such class and limit groups
form another.

We refer the reader to [8] for a more thorough account of subdirect products.

The results of the present paper rely heavily on the following theorem from
[6].

######  Theorem 2.5 (The VSP Theorem [6]).

Let $S<D=G_{1}\times\dots\times G_{m}$ be a subgroup of a direct product of
finitely presented groups. If the projection $p_{ij}(S)<G_{i}\times G_{j}$ has
finite index for all $1\leq i<j\leq m$, then

  1. (1)

$S$ is finitely presented;

  2. (2)

$\gamma_{m-1}(D_{0})<S$ for some $D_{0}<D$ of finite index;

  3. (3)

$S$ is closed in the profinite topology on $D$.

Moreover, there is an algorithm that, given finite presentations of the groups
$G_{i}$ and a finite set $\Theta\subset D$ generating $S$, will construct a
finite presentation $\langle\Theta\mid R\rangle$ for $S$.

Item (1) of this theorem is considerably deeper than item (2), the latter
being an instance of the following general observation [8].

######  Lemma 2.6.

Let $k\geq 2$ and let $G_{1},\dots,G_{m}$ be groups. If
$S<D=G_{1}\times\dots\times G_{m}$ projects onto each $k$-tuple of factors,
then $\gamma_{c}(D)<S$ where $c=\lceil(m-1)/(k-1)\rceil$.

To prove this, one first notes that since $S$ projects onto each factor,
$S\cap G_{i}$ is normal in $G_{i}$, so it is enough to show that $S\cap G_{i}$
contains all iterated commutators $[x_{1},\dots,x_{c}]$. And such commutators
can be obtained explicitly from the hypothesis; for example, when $m=3$ and
$k=2$, one has $([x,y],1,1)=[\,(x,\ast,1),\ (y,1,\ast)\,].$

######  Corollary 2.7.

Let $k\geq 2$. If $G_{1},\dots,G_{m}$ are finitely generated and
$S<D=G_{1}\times\dots\times G_{m}$ projects onto each pair of factors, then
the projection of $S$ to a $k$-tuple of factors $T=G_{i_{1}}\times\dots\times
G_{i_{k}}$ will be surjective if and only if the composition $S\to T\to
T^{\rm{ab}}=H_{1}(T,\mathbb{Z})$ is surjective.

###### Proof.

$S$ contains $\gamma_{m-1}(D)$ and hence the image of $S$ in $T$ contains
$\gamma_{m-1}(T)$, so $S\to T$ is surjective if and only if $S\to
T/\gamma_{m-1}(T)$ is surjective. The result now follows from Lemma 2.3. ∎

######  Corollary 2.8.

Let $G_{1},\dots,G_{m}$ be finitely generated groups, each of which is
generated by elements of finite order. If $S<D=G_{1}\times\dots\times G_{m}$
projects onto each pair of factors, then $S$ has finite index in $D$.

###### Proof.

$S$ contains $\gamma_{m-1}(D)$ and Lemma 2.4 tells us that $D/\gamma_{m-1}(D)$
is finite. ∎

######  Remark 2.9 (Algorithms).

Corollary 2.7 makes the process of determining whether a subgroup $S$ of a
direct product of finitely presented groups maps onto all $k$-tuples of
factors algorithmically decidable, provided one has the a priori knowledge
that $S$ projects to each pair of factors. Similarly, the problem of deciding
if $S$ projects to a subgroup of finite index in each $k$-tuple of factors is
decidable given this knowledge.

###  2.3. Pushing forward and pulling back

Given an $m$-tuple of group epimorphisms $\mu_{i}:H_{i}\to\hskip-9.95863pt\to
G_{i}$, the push-forward of a subgroup $S<H_{1}\times\dots\times H_{m}$ is its
image $\mu(S)<G_{1}\times\dots\times G_{m}$ under
$\mu=(\mu_{1},\dots,\mu_{m})$. The pull-back of a subgroup
$T<G_{1}\times\dots\times G_{m}$ is $\mu^{-1}(T)$.

The following lemma is immediate from the definitions.

######  Lemma 2.10.

If $S<G_{1}\times\dots\times G_{m}$ projects to $k$-tuples of factors, then so
does any pull-back or push-forward of $S$. And if $S$ contains the $c$-th term
of the lower central series of the product, then so does any pull-back or
push-forward of $S$.

##  3\. Residually free groups, limits groups and coordinate projections

A group $G$ is residually free if for every $g\in G\smallsetminus\\{1\\}$
there exists a homomorphism $\phi:G\to F$, with $F$ free, such that
$\phi(g)\neq 1$; and $G$ is fully residually free if for every finite set
$S\subset G$ there is a homomorphism $G\to F$ that is injective on $S$.
Finitely generated, fully residually free groups are more commonly called
limit groups, reflecting the powerful geometric approach to their study
initiated by Sela [19] et seq. This important and much-studied class of groups
contains free groups (obviously), free abelian groups, and the fundamental
groups of all closed surfaces of euler characteristic at most $-2$.

The study of finitely presented, residually free groups $\Gamma$ reduces to
the study of subdirect products of limit groups because there is a canonical
(and algorithmic) embedding
$\Gamma\hookrightarrow\exists\\!\\!{\rm{E}}(\Gamma)$ where
$\exists\\!\\!{\rm{E}}(\Gamma)$, the existential envelope of $\Gamma$, is a
direct product of limit groups [1], [6]. (At most one of the direct factors is
abelian, and the intersection of $\Gamma$ with this is the centre of
$\Gamma$.) The following theorem is therefore an important tool in classifying
which residually free groups are finitely presented. This is the main result
of [5]. The first item provides a converse to the VSP Theorem in the setting
of limit groups, while the second item points to the key role that finiteness
properties play in understanding residually free groups.

######  Theorem 3.1 ([6]).

Let $S<D=\Lambda_{1}\times\dots\times\Lambda_{m}$ be a full subdirect product,
where the $\Lambda_{i}$ are non-abelian limit groups.

  1. (1)

If $S$ is finitely presented, then the projection
$p_{ij}(S)<\Lambda_{i}\times\Lambda_{j}$ has finite index for $1\leq i<j\leq
m$.

  2. (2)

If $S$ is not of finite index in $D$, then $S$ is not of type
${\rm{wFP}}_{m}$.

Point (2) was improved upon by Kochloukova [13] and Kuckuck [14], who tied the
finiteness properties of $S$ more closely to projections to $k$-tuples. The
following statement combines their results.

######  Theorem 3.2 ([13], [14]).

For $2\leq k\leq m$, a full subdirect product of non-abelian limit groups
$S<\Lambda_{1}\times\dots\times\Lambda_{m}$ projects to a subgroup of finite
index in each $k$-tuple of factors
$\Lambda_{i(1)}\times\dots\times\Lambda_{i(k)}$ if and only if $S$ is of type
${\rm{wFP}}_{k}$.

Henceforth we shall abbreviate the phrase “projects to a subgroup of finite
index in” to “virtually surjects to”.

##  4\. Proof of Theorem 1.1

With the results of the previous sections in hand, most of the assertions of
Theorem 1.1 will follow once we verify that $B_{0}(m)<F^{m}$ surjects to pairs
of factors but does not virtually surject certain triples, while
$B_{1}(m)<F^{m}$ surjects all triples of factors but does not virtually
surject certain $4$-tuples.

Notation: We write $L_{i}\cong F$ for the $i$-th summand of $F^{m}$ throughout
this section.

###  4.1. Proof that $B_{0}(m)<F^{m}$ projects onto pairs of factors

Consider columns $p$ and $q$ of the array $A(m)$, with $p<q$. Since $p<q$,
there is at least one bit in the binary expansion of $p$ where it has $0$
while $q$ has $1$; if this place is bit $k$, then in row $k$ we have
$(\varepsilon_{k}(p),\varepsilon_{k}(q))=(0,1)$, hence $a_{ik}$ projects to
$(1,a_{i})\in L_{p}\times L_{q}$. Since $p\neq 0$, there is also a non-zero
bit in its expansion; if this is place $l$, then
$(\varepsilon_{l}(p),\varepsilon_{l}(q))\in\\{(1,0),\,(1,1)\\}$, hence
$a_{il}$ maps to either $(a_{i},1)$ or $(a_{i},a_{i})$ in $L_{p}\times L_{q}$.
In either case, we see that $\\{(a_{i},1),\,(1,a_{i}),\,(a_{i},a_{i})\\}$ is
contained in the projection of $B_{0}(m)$. This holds for $i=1,\dots,r$ and
all $1\leq p<q\leq m$, so $B_{0}(m)$ projects onto each pair of factors, as
claimed.∎

######  Remark 4.1.

Having worked through the above proof with the original notation, we shall
abbreviate several of the similar proofs that follow by noting that the
essential feature of $A(m)$ was that the subgroup $C<\mathbb{Z}^{m}$ generated
by the row vectors $\varepsilon_{i}$ projects onto the summands
$\mathbb{Z}^{2}<\mathbb{Z}^{m}$ corresponding to each pair of coordinates.

In the spirit of the above remark, the key fact for the following lemma is
that the projection of $C$ to $\mathbb{Z}^{3}\times 1<\mathbb{Z}^{m}$ only has
dimension $2$.

######  Lemma 4.2.

$B_{0}(m)<F^{m}$ does not virtually surject to certain triples of factors.

###### Proof.

The non-zero entries in columns $1,2,3$ are concentrated in two rows, namely
$\varepsilon_{0}$ and $\varepsilon_{1}$, so the projection of $B_{0}(m)$ to
$H_{1}(L_{1}\times L_{2}\times L_{3},\mathbb{Z})\cong\mathbb{Z}^{3r}$ has rank
at most (in fact exactly) $2r$. ∎

###  4.2. Proof that $B_{1}(m)<F^{m}$ projects to triples

Consider columns $p<q<s$ of the array $A(m)$. The essential point to prove
this time is that we get a basis for $\mathbb{Z}^{3}$ by adjoining the element
$(1,1,1)$ (coming from $\delta_{i}=(a_{i},\dots,a_{i})$) to the elements
$(\varepsilon_{j}(p),\varepsilon_{j}(q),\varepsilon_{j}(s))_{j}$ obtained by
reading the entries in columns $p,q,s$ in each row of the array.

Since $p<s$, there is at least one place in the binary expansion of $p$ where
it has $0$ while $s$ has $1$; if this place is bit $k$, then from columns
$p,q,s$ of row $k$ we have either $(0,1,1)$ or $(0,0,1)$. Similarly, as $p<q$,
in some row we get either $(0,1,1)$ or $(0,1,0)$. If we get two distinct
vectors from this argument, then together with $(1,1,1)$ (coming from
$\delta_{i}$) they will span $\mathbb{Z}^{3}$. This fails if we get $(0,1,1)$
twice, in which case we use the condition $q<s$ to get a vector $(1,0,1)$ or
$(0,0,1)$: adding either to $\\{(1,1,1),\,(0,1,1)\\}$ gives a basis for
$\mathbb{Z}^{3}$. ∎

######  Lemma 4.3.

If $m\geq 5$ then $B_{1}(m)<F^{m}$ does not virtually surject to certain
4-tuples of factors.

###### Proof.

We focus on columns $2$ to $5$ of the array $A(m)$ and argue that the
projection of $B_{1}(m)<F^{m}$ to $Z:=H_{1}(L_{2}\times L_{3}\times
L_{4}\times L_{5},\mathbb{Z})\cong\mathbb{Z}^{4r}$ only has rank $3r$.

To see this, consider the rank-$4$ summand $Z_{1}<Z$ that is spanned by the
images of $(a_{1},1,1,1),$ $(1,a_{1},1,1),\ (1,1,a_{1},1),\ (1,1,1,a_{1}).$
The only rows of $A(m)$ that have non-zero entries in columns $2,3,4,5$ are
$\varepsilon_{0},\varepsilon_{1},\varepsilon_{2}$, where we have

$(0,1,0,1),\ (1,1,0,0),\ (0,0,1,1).$

Thus the projection of $\langle a_{1j}\mid j=0,1,2,\dots\rangle$ to $Z_{1}$
has rank $3$. The diagonal element $\delta_{1}$ contributes $(1,1,1,1)$, but
we already have this as the sum of the images of $a_{11}$ and $a_{12}$. A
similar argument applies to the summand $Z_{i}<Z$ corresponding to the
generator $a_{i}\in F$. Thus the image of $B_{1}(m)$ in $Z$ has rank $3r$, as
claimed. ∎

###  4.3. The remainder of the proof

In the light of the preceding results in this section, items (3) and (4) of
Theorem 1.1 are covered by Lemma 2.6, while items (5) and (7) are covered by
Theorems 2.5 and 3.2. We shall prove the remaining items in order.

Let $k=\lfloor 1+\log_{2}m\rfloor$. We defined $B_{0}(m)$ by taking a
generating set $a_{ij}$ with $rk$ elements, so certainly $d(B_{0}(m))\leq rk$.
To see that $d(B_{0}(m))=rk$, we observe that $B_{0}(m)$ maps onto a direct
product of $k$ copies of $F=F_{r}$: the desired map is the coordinate
projection onto $\Lambda^{[2]}:=L_{1}\times L_{2}\times L_{4}\dots\times
L_{2^{k-1}}$; in this projection, $a_{ij}$ maps to $a_{i}\in L_{2^{j}}$. This
proves assertion (1) of the theorem.

The proof of item (2) is similar. In this case, to see that $B_{1}(m)$
requires at least $r(k+1)$ generators we prove that its projection to the
abelianization of $\Lambda^{[2]}\times L_{3}$ is surjective. The new
difficulty that we face is that in the rank-$3$ summand of
$V_{i}<H_{1}(L_{1}\times L_{2}\times L_{3},\mathbb{Z})$ corresponding to the
basis element $a_{i}\in F$, the only contributors among the $a_{ij}$ are
$a_{i0}$ and $a_{i1}$, who contribute $(1,0,1,0,...)$ and $(0,1,1,0,...)$
respectively. But the element $\delta_{i}\prod_{j>1}a_{ij}^{-1}$ contributes
$(1,1,1,0,...)$ to $\Lambda^{[2]}\times L_{3}$, ensuring that the image of
$B_{1}(m)$ contains $V_{i}$. And $a_{ij}$ maps to $a_{i}\in L_{2^{j}}$ for
$j>1$, as before. Thus $B_{1}(m)$ maps onto $H_{1}(\Lambda^{[2]}\times
L_{3},\mathbb{Z})\cong\mathbb{Z}^{r(k+1)}$, so $d(B_{1}(m))\geq r(k+1)$.

The proof of item (6) is similar to that of item (2). The three rows of $A(4)$
are $(1,0,1,0),$ $(0,1,1,0),\,(0,0,0,1)$ and together with $\delta=(1,1,1,1)$
these span $\mathbb{Z}^{4}$. In the spirit of remark 4.1, this translates
easily into the fact that $B_{1}(4)$ contains each of the $4r$ generators of
$F^{4}$. Alternatively, we can observe (i) that $B_{1}(4)$ maps onto
$H_{1}(F^{4},\mathbb{Z})$ because it contains each of the $r$ summands
$\mathbb{Z}^{4}$ corresponding to a choice of basis vector, and (ii)
$B_{1}(4)$ contains $[F^{4},F^{4}]$, by Lemma 2.6.

Item (8) is an immediate consequence of (2) and Proposition 2.2. In more
detail, since $h(r,c)\leq\sum_{i=1}^{c}r^{i}$ and $\lfloor
2+\log_{2}m\rfloor>\log_{2}m$, it suffices to define
$p_{c}(t)=\frac{1}{W_{c}(2)}\sum_{i=1}^{c}t^{i}$. ∎

###  4.4. Binary subgroups of direct products of limit groups

Let $\Lambda_{1},\dots,\Lambda_{m}$ be non-abelian limit groups, and suppose
that there exist epimorphisms $\mu_{i}:F_{r}\to\Lambda_{i}$ that induce an
isomorphism on abelianizations. Of particular interest is the case where each
$\Lambda_{i}$ is the fundamental group of a closed surface of genus $g$, with
$r=2g$ and $\mu_{i}:F_{r}\to\Lambda_{i}$ a standard choice of generators. Let
$B_{j}(m;\mu)<D=\Lambda_{1},\dots,\Lambda_{m}$ be the image of $B_{j}(m)$
under $\mu=(\mu_{1},\dots,\mu_{m})$.

######  Theorem 4.4.

With the above notation, for all non-abelian limit groups $\Lambda_{i}$ such
that $\mu_{i}:F_{r}\to\Lambda_{i}$ induces an isomorphism on
$H_{1}(-,\mathbb{Z})$:

  1. (1)

the rank of $B_{0}(m;\mu)$ is $r(\lfloor 1+\log_{2}m\rfloor)$;

  2. (2)

the rank of $B_{1}(m;\mu)$ is $r(\lfloor 2+\log_{2}m\rfloor)$;

  3. (3)

$B_{0}(m;\mu)$ contains $\gamma_{m-1}(D)$;

  4. (4)

$B_{1}(m;\mu)$ contains $\gamma_{c}(D)$, where $c=\lfloor 1+(m-1)/2\rfloor$;

  5. (5)

$B_{0}(m;\mu)$ is finitely presented but not of type ${\rm{wFP}}_{3}$;

  6. (6)

if $m\leq 4$ then $B_{1}(m;\mu)=D$;

  7. (7)

if $m\geq 5$ then $B_{1}(m;\mu)$ is finitely presented, type ${\rm{wFP}}_{3}$
but not ${\rm{wFP}}_{4}$;

  8. (8)

$\forall c\ \exists$ polynomial $p_{c}(t)$ such that if $m>p_{c}(\log_{2}m)$
and $D_{0}<\Lambda_{1}\times\dots\times\Lambda_{m}$ is of finite index, then
${{\gamma_{c}(D_{0})\not\subseteq B_{1}(m)}}$.

The polynomial $p_{c}(t)$ depends only on $c$, not the particular
$\Lambda_{i}$ considered: again we may take
$p_{c}(t)=\frac{1}{W_{c}(2)}\sum_{i=1}^{c}t^{i}$.

###### Proof.

The proofs of Theorem 1.1 and the supporting results were crafted so that they
extend mutatis mutandis to this setting. ∎

In fact, our earlier proofs apply to more general settings: the interested
reader will have little difficulty in verifying the following observations.
(Lemma 2.10 is needed here.)

######  Addenda 4.5.

  1. (i)

If one drops the requirement that $\mu$ induces an isomorphism on
$H_{1}(-,\mathbb{Z})$, then items (3), (4), (6) and (8) of Theorem 4.4 remain
valid while the equalities in (1) and (2) are replaced by inequalities
$d(B_{j}(m;\mu))\leq r(\lfloor j+1+\log_{2}m\rfloor)$. The positive assertions
in (5) and (7) remain valid but the negative assertions may fail.

  2. (ii)

If one weakens the hypotheses further, requiring only that each $\Lambda_{i}$
is an $r$-generator finitely presented group that maps onto a non-abelian free
group, then the same set of conclusions as in (i) remains valid.

  3. (iii)

If one weakens the hypotheses yet again, requiring only that each
$\Lambda_{i}$ is an $r$-generator finitely presented group, then the only
additional item to become invalid is (8).

##  5\. Binary Subgroups: the general construction

We maintain the notation that $F$ is the free group of rank $r$ with basis
$\\{a_{1},\dots,a_{r}\\}$.

First we consider arbitrary binary subgroups of direct powers of free groups.

######  Definition 5.1.

Let $m\geq 2$ and $r\geq 2$ be integers. For $i=1,\dots,r$, let
$\sigma_{i}=(x_{i1},\dots,x_{im})$ be a list of distinct positive integers.
Let $l_{i}=\max_{k}\ \lfloor 1+\log_{2}x_{ik}$. We associate to $\sigma_{i}$
the $l_{i}$-by-$m$ matrix $A[\sigma_{i}]$ whose $k$-th column is the binary
expansion of $x_{ik}$. More precisely, the $(j,k)$-entry of $A[\sigma_{i}]$ is
$\varepsilon_{j}(k)$ if $x_{ik}=\sum_{j}\varepsilon_{j}(k)2^{j}$. We treat the
$j$-th row of $A[\sigma_{i}]$ as a multi-index and define $a_{ij}\in F^{m}$ by
raising the generator $a_{i}\in F$ to this multi-index (cf. Table 2).

Let $\Sigma=(\sigma_{1},\dots,\sigma_{r})$. We define $B(\Sigma)<F^{m}$ to be
the subgroup generated by $\\{a_{ij}\mid 1\leq i\leq r,\ 1\leq j\leq
l_{i}\\}$.

######  Example 5.2.

$B_{0}(m)$ is the group one gets by taking $\sigma_{1}=\dots=\sigma_{r}$ and
$x_{ik}=k$.

$B_{1}(m)$ is the group one gets by taking $\sigma_{1}=\dots=\sigma_{r}$ and
$x_{ik}=2k+1$.

The proof in Section 4.1 that $B_{0}(m)$ surjects pairs of factors applies
equally well to $B(\Sigma)$.

######  Lemma 5.3.

The projection of $B(\Sigma)<F^{m}$ to each pair of factors is surjective.

From the VSP Theorem we deduce:

######  Proposition 5.4.

$B(\Sigma)<F^{m}$ is finitely presented and contains $\gamma_{m-1}(F^{m})$.

######  Remark 5.5 (Algorithms).

Following Remark 2.9, with Lemma 5.3 in hand we see that there is an algorithm
that allows one to explore, for each $k$, whether $B(\Sigma)<F^{m}$
(virtually) projects onto all $k$-tuples of factors and hence to bound the
higher finiteness properties and co-nilpotency class of $B(\Sigma)$ using
Theorem 3.2 and Lemma 2.6.

###  5.1. Pushing forward and the proof of Theorem 1.2

The following defines the most general binary subgroups that we consider.

######  Definition 5.6.

Let $\Sigma=(\sigma_{1},\dots,\sigma_{r})$ be as in definition 5.1 and let
$(\mu_{i}:F\to\hskip-9.95863pt\to G_{i})_{i=1}^{m}$ be an $m$-tuple of
$r$-generator groups. We define $B(\Sigma,\mu)$ to be the image in
$G_{1}\times\dots\times G_{m}$ of $B(\Sigma)<F^{m}$ under the epimorphism
$\mu=(\mu_{1},\dots,\mu_{m})$.

We invoke the VSP Theorem once more – in tandem with Lemma 2.10 and Remark 2.9
it yields:

######  Theorem 5.7.

For all $m$-tuples of finitely presented $r$-generator groups
$(\mu_{i}:F\to\hskip-9.95863pt\to G_{i})_{i=1}^{m}$ and all $r$-tuples
$\Sigma$ of lists of $m$ distinct positive integers, the subgroup
$B(\Sigma,\mu)<G_{1}\times\dots\times G_{m}=:D$ is finitely presented, closed
in the profinite topology, and contains $\gamma_{m-1}(D)$. Moreover, there is
an algorithm that, given finite presentations of $G_{1},\dots,G_{m}$, will
construct a finite presentation for $B(\Sigma,\mu)$. And for each $k\geq 2$
there is an algorithm that will determine if $B(\Sigma,\mu)$ (virtually)
surjects all $k$-tuples of factors $G_{i_{1}}\times\dots\times G_{i_{k}}$.

This completes the proof of Theorem 1.2, because the additional assertion
concerning finiteness properties of limit groups is covered by Theorem 3.2.

###  5.2. Pulling back

Let $B(\Sigma,\mu)<G_{1}\times\dots\times G_{m}$ be as above. Given any
$m$-tuple of epimorphisms $(\pi_{i}:H_{i}\to G_{i})_{i=1}^{m}$, with the
groups $H_{i}$ finitely presented, we consider the pull-back
$\pi^{-1}B(\Sigma,\mu)<E:=H_{1}\times\dots\times H_{m}$. In the light of Lemma
2.10 and the VSP Theorem we see that $\pi^{-1}B(\Sigma,\mu)$ will again be
finitely presented, closed in the profinite topology, and contain
$\gamma_{m-1}(E)$. And there is an algorithm that, given finite presentations
of $H_{1},\dots,H_{m}$, will construct a finite presentation for
$\pi^{-1}B(\Sigma,\mu)$.

This construction is of particular interest in the case where the $H_{i}$ are
limit groups and the $G_{i}$ are free groups. We shall explore it further in
[7].

###  5.3. Redundancy, variations and standard forms

It is natural to wonder to what extent $B(\Sigma)<F^{m}$ determines $\Sigma$.
Deciding isomorphism among the groups $B(\Sigma)$ does not seem to be a
trivial matter. It is clear that $\Sigma$ is not uniquely determined:
permuting the order of the sets $\sigma_{i}$ corresponds to permuting the
chosen basis of $F$, and in the case $\sigma=\sigma_{1}=\dots=\sigma_{m}$
permuting the order of the elements in $\sigma$ merely permutes the direct
factors of $F$. (One might remove these ambiguities by insisting on a standard
form in which the $\sigma_{i}$ and their elements are listed in a natural
order.) Beyond this, even in the case $\sigma=\sigma_{1}=\dots=\sigma_{r}$
there are further redundancies: if no column of the matrix $A[\sigma]$
contains an entry $1$ in both of the rows $j_{1}$ and $j_{2}$, then one can
replace row $j_{1}$ by the sum of these rows to obtain $A[\sigma^{\prime}]$
with $\sigma^{\prime}\neq\sigma$. This operation leaves $B(\Sigma)$ invariant,
merely changing the preferred generating set $a_{ij}$ by performing the
Nielsen move $a_{ij_{1}}\mapsto a_{ij_{1}}a_{ij_{2}}$ for each $i$.

An important point to note is that when we perform such row operations, we are
constrained by wanting to work within the context of integer matrices with
entries in $\\{0,1\\}$. If we were to work instead over the field with 2
elements, then we would be free to perform row operations; we could then carry
out Gaussian elimination to transform the matrix $A[\sigma]$ into a canonical
form without altering $B(\Sigma)$. This freedom can be gained at the expense
of switching from the free group $F=F_{r}$ to the free product $W_{r}$ of $r$
copies of $\mathbb{Z}/2\mathbb{Z}$. One might be tempted to think that this
switch would lead to a neater theory, and it would certainly tighten the
connection with binary linear codes, but the following observation shows that
this alternative is useless if one is interested in constructing groups with
exotic finiteness properties.

We fix an epimorphism $F\to W_{r}$ and extend it coordinate-wise to obtain
$\mu:F^{m}\to W_{r}^{m}$.

######  Proposition 5.8.

For all choices of $\Sigma$, the subgroup $B(\Sigma,\mu)<W_{r}^{m}$ is of
finite index.

###### Proof.

Follows immediately from Lemma 5.3 and Corollary 2.8. ∎

##  6\. Connections and challenges

$B_{0}(m)$ has the minimum number of generators among the binary subgroups of
$F^{m}$. It is striking that one only needs to add $r$ additional generators
to obtain $B_{1}(m)$, which surjects all triples of factors and therefore has
stronger finiteness properties. It is natural to ask what the minimum number
of generators is for a binary subgroup that surjects $4$-tuples of factors,
$5$-tuples, etc. More generally, it might be interesting to explore the nature
of small collections of integers $\Sigma$ such that $B(\Sigma)<F^{m}$ maps
onto $k$-tuples of factors, where $k<m$ is fixed. In particular, one might
count such collections and explore the asymptotics of the counting functions.

Note that Corollary 2.7 reduces these issues to problems in linear algebra
over $\mathbb{Z}$; in the case $\Sigma=(\sigma,\dots,\sigma)$, one would just
be exploring submatrices of $A[\sigma]$, and the problem is so natural that it
has surely been studied in other contexts. Note too that Theorem 3.2 provides
a direct connection with the homological finiteness properties of $B(\Sigma)$.
The challenge of understanding how the co-nilpotency class of $B(\Sigma)$
varies with $\Sigma$ seems harder.

###  6.1. Binary Codes

It seems likely that some answers to the type of question raised above might
be found by exploring the link to linear codes that I shall now sketch. I am
grateful to Ben Green for suggesting this connection, and I am grateful to
Yonathan Fruchter for further conversations about it.

A binary linear code of length $m$ is a linear subspace $C$ of the vector
space $\mathbb{F}_{2}^{m}$; the rank of the code is the dimension of $C$. The
dual code $C^{\perp}<\mathbb{F}_{2}^{m}$ consists of the vectors orthogonal to
$C$ with respect to the usual inner product $x.y=\sum x_{i}y_{i}$. The non-
zero vectors in $C$ are called codewords, and the minimum Hamming distance of
a codeword from the zero vector is the weight of the code. A linear code of
length $m$, dimension $k$ and weight $d$ is called an $[m,k,d]$-code. Such
codes have been intensively studied in the context of error correction in
computer science and communication.

Each of the arrays that we used to define binary subgroups $B<F^{m}$ defines a
binary code of length $m$: we take $C$ to be the span of the rows of the
array, read as elements of $\mathbb{F}_{2}^{m}$. Conversely, given an
$[m,k,d]$-code with basis $c_{1},\dots,c_{k}$, we define the $k\times m$ array
(matrix) whose rows are the vectors $c_{i}$ to be $A[\sigma]$, thereby
defining $\sigma$ and hence $B[C]:=B(\Sigma)<F_{r}^{m}$, where
$\Sigma=(\sigma,\dots,\sigma)$. (More generally, given an $r$-tuple of codes,
we could take a basis for each code to obtain matrices $A[\sigma_{i}]$
defining $(\sigma_{1},\dots,\sigma_{r})$ – but for the purposes of this
discussion the first case is enough.)

Let $C_{0}(m)<\mathbb{F}_{2}^{m}$ be the code defined by the array for
$B_{0}(m)<F^{m}$ (see Table 1). The argument that we used in Section 4.1 to
prove that $B_{0}(m)<F^{m}$ does not surject the triple of factors
$L_{1}\times L_{2}\times L_{3}<F^{m}$ shows that $C_{0}(m)$ does not project
onto $\mathbb{F}_{2}^{3}\times 0<\mathbb{F}_{2}^{m}$. Indeed it shows that
$(1,1,1,0,\dots)$ is orthogonal to $C_{0}(m)$, hence the dual code
$C_{0}(m)^{\perp}$ has weight at most $3$. In fact, it has weight exactly $3$,
because if there were a vector $y\in C_{0}(m)^{\perp}$ whose only non-zero
coordinates were $i$ and $j$, then the projection of $B_{0}(m)<F^{m}$ to
$L_{i}\times L_{j}$ (even $H_{1}(L_{i}\times L_{j},\mathbb{F}_{2})$) would not
be surjective. Likewise, the dual of the linear code
$C_{1}(m)<\mathbb{F}_{2}^{m}$ corresponding to $B_{1}(m)<F^{m}$ has weight
$4$. (In retrospect, one sees that $B_{0}(m)$ and $B_{1}(m)$ correspond to the
Hadamard and extended Hadamard codes, which are dual to the Hamming and
extended Hamming codes, whose weights are well-known to be $3$ and $4$.) In
general, if a code $C$ has length $m$ and the weight of the dual code
$C^{\perp}$ is $d^{\prime}>2$ then the corresponding binary subgroup
$B[C]<F^{m}$ fails to project onto some $d^{\prime}$-tuple of factors in
$F^{m}$ and hence is not of type ${\rm{wFP}}_{d^{\prime}}$.

These observations suggest that in order to produce binary subgroups $B<F^{m}$
with a small number of generators and strong finiteness properties, one should
turn to the literature on coding theory in search of $[m,k,d]$ binary codes
with $k$ small and the weight $d^{\prime}$ of the dual code large, keeping in
mind that we are obliged to work over $\mathbb{Z}$ rather than
$\mathbb{F}_{2}$ (cf. Proposition 5.8). Yonathan Fruchter has made progress in
this direction (private communication) and points out the relevance of
selective families and superimposed codes [9].

###  6.2. Kähler Groups

The work of Delzant and Gromov [10] highlighted the important role that
subdirect products of surface groups play in the struggle to understand which
finitely presented groups are fundamental groups of compact Kähler manifolds.
In a subsequent article, Claudio Llosa Isenrich and I will exploit the
constraints that he established in [16] to investigate whether binary
subgroups of direct products of surface groups can be Kähler.

###  6.3. Implementation

Picking up on the theme of Corollary 2.7 and Remarks 2.9 and 5.5, I would be
interested to know how practical it is to implement the algorithms whose
existence is discussed in this article, in particular the algorithm that takes
as input a list $\sigma$ of $m$ distinct positive integers and gives as output
(1) a finite presentation of the binary subgroup $B<F_{2}^{m}$ that it
defines, and (2) the maximum $k$ such that $B$ is of type ${\rm{wFP}}_{k}$.

For (1), it would be necessary to implement a special case of the Effective
1-2-3 Theorem from [6] – cf. [15].

## References

  * [1] G. Baumslag, A. Myasnikov and V.N. Remeslennikov, Algebraic geometry over groups I: Algebraic sets and ideal theory, J. Algebra, 219 (1999), 16–79.
  * [2] R. Bieri, Homological dimension of discrete groups, Queen Mary College Mathematical Notes. Queen Mary College, Department of Pure Mathematics, London, 1981.
  * [3] M.R. Bridson, Concise presentations of direct products, Proc. Amer. Math. Soc. 150 (2022), 1361–1368.
  * [4] M.R. Bridson and H. Wilton, On the difficulty of presenting finitely presentable groups, Groups Geom. Dyn. 5 (2011), 301–325.
  * [5] M.R. Bridson, J. Howie, C.F. Miller III and H. Short, Subgroups of direct products of limit groups, Ann. of Math. 170 (2009), 1447–1467
  * [6] M.R. Bridson, J. Howie, C.F. Miller III and H. Short, On the finite presentation of subdirect products and the nature of residually free groups, Amer. J. Math., 135 (2013), 891–933.
  * [7] M.R. Bridson and C. Llosa Isenrich, Kähler groups, the co-nilpotency of subdirect products, and Sidki doubles, in preparation.
  * [8] M.R. Bridson and C.F. Miller,  Structure and finiteness properties of subdirect products of groups,  Proc. Lond. Math. Soc. (3) 98 (2009), 631–651.
  * [9] A.E.F. Clementi, A. Monti and R. Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, 12th ACM-SIAM SODA, 2001, pp. 709–718.
  * [10] T. Delzant and M. Gromov, Cuts in Kähler groups. In Infinite Groups:Geometric, Combinatorial and Dynamical Aspects, Progress in Math. 248, Birkhäuser, Basel 2005.
  * [11] M. Hall, Jr., “The theory of groups”, MacMillan Co., New York, 1959.
  * [12] P. Hall, The Eulerian functions of a group, Quart. J. Math 7 (1936), 134–151.
  * [13] D.H. Kochloukova, On subdirect products of type ${\rm FP}_{m}$ of limit groups, J. Group Theory 13 (2010), 1–19.
  * [14] B. Kuckuck, Subdirect products of groups and the $n$-$(n+1)$-$(n+2)$ conjecture, Quart. J. Math. 64 (2015), 1293–1318.
  * [15] C. Llosa Isenrich, Finite presentations for Kähler groups with arbitrary finiteness properties, J. Algebra 476 (2017), 344–367.
  * [16] C. Llosa Isenrich, Complex hypersurfaces in a direct product of Riemann surfaces, arXiv:1806.02357.
  * [17] C. F. Miller III, “On group-theoretic decision problems and their classification”, Ann. Math. Studies, No. 68, Princeton University Press (1971).
  * [18] A. Minasyan, On subgroups of right angled Artin groups with few generators, Intl. J. Alg. Comp. 25 (2015), 675–688.
  * [19] Z. Sela, Diophantine geometry over groups I: Makanin-Razborov diagrams, IHÉS Publ. Math. 93 (2001), 31–105.
  * [20] J. R. Stallings, A finitely presented group whose 3–dimensional homology group is not finitely generated, Amer. J. Math. , 85 (1963) 541–543.
  * [21] J. Wiegold, Growth sequences of finite groups IV, J. Austral. Math. Soc. Ser. 29 (1980), 14–16.
  * [22] J. Wiegold and J.S. Wilson, Growth sequences of finitely generated groups, Arch. Math. 30 (1978), 337–343.