00footnotetext:  1 Mila, University of Montreal, 2 Microsoft Research, New
York, NY, 3 Google Deepmind, 4 CIFAR Fellow, 5 Google Research, Corresponding
authors<EMAIL_ADDRESS>
# Temporal Latent Bottleneck: Synthesis of Fast and Slow Processing Mechanisms
in Sequence Learning

Aniket Didolkar 1, Kshitij Gupta 1, Anirudh Goyal 1, Nitesh B. Gundavarapu 5
Alex Lamb 2, Nan Rosemary Ke 3, Yoshua Bengio 1,4

###### Abstract

Recurrent neural networks have a strong inductive bias towards learning
temporally compressed representations, as the entire history of a sequence is
represented by a single vector. By contrast, Transformers have little
inductive bias towards learning temporally compressed representations, as they
allow for attention over all previously computed elements in a sequence.
Having a more compressed representation of a sequence may be beneficial for
generalization, as a high-level representation may be more easily re-used and
re-purposed and will contain fewer irrelevant details. At the same time,
excessive compression of representations comes at the cost of expressiveness.
We propose a solution which divides computation into two streams. A slow
stream that is recurrent in nature aims to learn a specialized and compressed
representation, by forcing chunks of $K$ time steps into a single
representation which is divided into multiple vectors. At the same time, a
fast stream is parameterized as a Transformer to process chunks consisting of
$K$ time-steps conditioned on the information in the slow-stream. In the
proposed approach we hope to gain the expressiveness of the Transformer, while
encouraging better compression and structuring of representations in the slow
stream. We show the benefits of the proposed method in terms of improved
sample efficiency and generalization performance as compared to various
competitive baselines for visual perception and sequential decision making
tasks.

##  1 Introduction

The interplay between fast and slow mechanisms for information processing and
perception has been studied in both cognitive science and machine learning
DBLP:conf/nips/BaHMLI16; Hinton87usingfast. In the brain, short-term and long-
term memory have developed in a specialized way. Short-term memory is allowed
to change very quickly to react to immediate sensory inputs and perception. It
also tends towards high capacity storage of all pieces of information which
may be relevant for future reasoning jonides2008mind; atkinson1971control;
averbach1961short. By contrast, long-term memory changes slowly
kolodner1983maintaining; jeneson2012working, is highly selective and involves
repeated consolidation. It contains a set of memories that summarize the
entire past, only storing details about observations which are most relevant
goelet1986long; baddeley1984attention.

Deep Learning has seen a variety of architectures for processing sequential
data (hochrieter1997long; schuster1997bidirection; cho2014gru). For example.
recurrent neural networks compress information about a sequence into a single
hidden state. Transformers get rid of the recurrent state by dynamically
capturing information between positions using multi-head dot product attention
vaswani2017attention. Transformers have become the dominant architecture
across a wide range of domains including vision (dosovitskiy2020vit), natural
language (devlin2018bert; Radford2018ImprovingLU; brown2020language;
zhang2022opt; chowdhery2022palm; rae2022scaling), and reinforcement learning
(chen2021decision; janner2021reinforcement). They have eclipsed recurrent
neural networks (hochrieter1997long; schuster1997bidirection; cho2014gru) in
almost all sequence processing domains due to their high representational
capacity and scalability. Despite their wide applicability, it is well known
that Transformers are very data hungry and work well mainly at scale. This can
be attributed to their inductive bias towards modeling all possible pairwise
interactions in the sequence which results in no consolidation of information.
This lack of selectivity in the attention mechanism also leads to a high
computational complexity which scales quadratically with input size.
Additionally, modeling all possible pairwise interactions maybe extremely
wasteful and may result in capturing unnecessary information not useful for
the downstream task (goyal2021coordination; jaegle2021perceiver). The goal of
this work is to design an architecture for autoregressive modeling that has an
inductive bias towards learning temporally compressed representation that
retains the benefits of Transformers while preserving long-range interactions.

For learning temporally compressed representations, we start by dividing the
computation of the Transformer into two streams of processing - a fast stream
and a slow stream. Inspired by the idea of long-term and short-term memory, we
want the fast stream to have a short-term memory with a high capacity that
reacts quickly to sensory input. We refer to this fast stream as the
perceptual module and implement it using a Transformer since they are known to
have high representational capacity. On the other hand, we want the slow
stream to have a long-term memory which updates at a slower rate and
summarizes the most important information in the input sequence. We refer to
this slow stream as the Temporal Latent Bottleneck.

Implementation-wise, we divide the input into fixed size chunks (Figure 1).
The fast stream operates within each chunk while the slow stream consolidates
and aggregates information across chunks updating itself once per chunk. This
leads to information asymmetry between fast and slow stream as the fast stream
contains fine-grained local information while the slow stream contains coarse-
grained distant information. Such kind of information asymmetry has shown to
improve generalization and adaptation performance of learned policies in the
context of RL (goyal2019infobot; galashov2019information). The fast and slow
streams interact with each other though bottleneck of attention. The division
of computation into a fast and slow stream eliminates the need for capturing
all possible pairwise interactions and thus introducing selectivity in the
attention mechanism resulting in a much lower computational complexity which
is not quadratic in the input size. We show that the limited capacity of the
slow stream and consolidation of information by a recurrent neural network
prevents the model from capturing unnecessary information not useful for the
downstream task. We evaluate the proposed model in a number of domains showing
that it consistently outperforms competent baselines showing improved
generalization to scenarios not seen during training.

Figure 1:  Perceptual module + Temporal Latent Bottleneck Model.
${\mathcal{F}}$ denotes the perceptual module or the fast stream which is a
Transformer. ${\mathcal{I}}$ represents the temporal latent bottleneck state
(consisting of a set of vectors) that are updated using a recurrent function
denoted by ${\mathcal{G}}$. The given sequence is first divided into chunks of
size $K$ and each chunk $X_{l}$ is processed by ${\mathcal{F}}$ which consists
of interleaved Self Attention + FFN (denoted in blue) and Cross Attention +
FFN (denoted in green) layers. The Cross Attention + FFN layers allow the
representation of ${\mathcal{F}}$ to be conditioned on top-down information
from ${\mathcal{I}}$. The representations of the temporal latent bottleneck
state is updated using the outputs of ${\mathcal{F}}$ by a recurrent function
${\mathcal{G}}$, which consists of a Cross Attention + FFN layer as shown in
the circle.

##  2 Methodology

We now present the proposed approach in detail. Our model jointly leverages
the strengths of Transformers (vaswani2017attention) and recurrent neural
networks (cho2014gru; hochrieter1997long).

# $\mathcal{C}$(query, key, value): Cross Attention + FFN layer

# $\mathcal{S}$(query, key, value): Self Attention + FFN layer

# L: Num. Layers

# R: Num. $\mathcal{C}$ per $\mathcal{S}$

# X: Input sequence of length T. shape: [B x T x D]

# $\mathcal{I}$: The Temporal Bottleneck

# K: Chunk Size

X = torch.chunk(X, K, dim = 1) # List of length $\lfloor T/K\rfloor$ with each
element of size [B x K x D]

for $X_{c}$ in X:

for l in range(L):

$X_{c}$ = $\mathcal{S}^{l}$($X_{c},\quad X_{c},\quad X_{c}$)

if l % R == 0:

$X_{c}$ = $\mathcal{C}^{\lfloor
L/l\rfloor}$($X_{c},\quad\mathcal{I},\quad\mathcal{I}$)

$\mathcal{I}=\mathcal{C}(\mathcal{I},\quad X_{c},\quad X_{c})$

Algorithm 1 PyTorch-style pseudocode for proposed model

###  2.1 Desiderata for Fast and Slow Streams of Processing

We give the detailed description of the proposed model in the next section.
Here, we give an overview of our architecture and discuss some of its key
properties. Given an input sequence, it is first divided into chunks of size
$K$. Each chunk is processed by perceptual module represented by a Transformer
(denoted as $\mathcal{F}$). While processing each chunk, ${\mathcal{F}}$ is
also conditioned on information from the Temporal Latent Bottleneck module
${\mathcal{G}}$. The slow stream is a recurrent stream which has its own state
consisting of a set of $N$ vectors (or slots) also called temporal latent
bottleneck state denoted as ${\mathcal{I}}$ in Figure 1. In the following
sections, we use the term temporal latent bottleneck to refer to the temporal
latent bottleneck state ${\mathcal{I}}$. This state is updated once per chunk
using information from the perceptual module through a cross attention
mechanism.

The perceptual module operates within each chunk while the temporal latent
bottleneck operates across chunks slowly updating itself after each chunk has
been processed by the perceptual module. Thus, the only way the perceptual
module gets information about inputs beyond its own chunk is through the
temporal latent bottleneck. An added advantage of this is that the
computational complexity of the attention mechanism in the proposed model is
${\mathcal{O}}(\frac{T}{K}(K^{2}+KN))$ while that of a Transformer is
${\mathcal{O}}(T^{2})$, where $T$ is the length of the sequence, $K$ is the
chunk size, and $N$ is the number of temporal latent bottleneck state vectors.
Since $K<<T$ and $N<<T$, we can see that $\frac{T}{K}(K^{2}+KN)<T^{2}$.
Therefore the proposed model has a much lower computational complexity
compared to a Transformer. Furthermore, the capacity of the temporal latent
bottleneck is limited and much smaller than that of the perceptual module.
This encourages the temporal latent bottleneck to represent the most salient
information about the past while the perceptual module represents only local
information. This creates an information asymmetry between the two streams.
This information asymmetry leads to the perceptual module having a fine
grained view of the nearby inputs but a very coarse grained view of the
distant past. This is very different from the usual self-attention which
attends to all tokens in the sequence at the same level of granularity.

An advantage of having a compressed representation of the past is that it
allows the model to forget irrelevant information. For example, if an agent is
navigating in a large maze, it does not need to have fine grained knowledge of
its actions from the distant past. In the case of a Transformer, it would
attend to every step from the past (including steps from the distant past)
which may be irrelevant in the present context thus wasting its capacity in
modeling irrelevant details. Another important component of the proposed model
is top-down attention which conveys contextual information from the high-level
Temporal Latent Bottleneck module to the processing of low-level perceptual
module. Past works (mittal2020learning; fan2021addressing; hill2020grounded;
dai2019transformer) have shown that top-down attention improves generalization
and adaptation performance of the learned model. One difference between these
works and the proposed model is that in their case the multiple streams
operate at the same temporal granularity while in our case the streams operate
at a different time scales (because of information asymmetry). Through our
experiments, we show the advantage of the proposed architecture over these
works. Next, we describe the detailed implementation of the proposed model.

###  2.2 Computational Steps

We denote the input $X$ as a sequence of $T$ tokens -
$X=[x_{0},x_{1},x_{2},\ldots,x_{t}]$. We chunk this input into chunks of size
$K$ resulting in $\lfloor T/K\rfloor$ chunks. We refer to $l^{th}$ chunk as
$X_{l}$. We represent the state of the temporal latent bottleneck
$\mathcal{I}$ (i.e. the slow stream) as a set of $M$ $d$-dimensional vectors.
As mentioned previously, we denote the temporal latent bottleneck module as
${\mathcal{G}}$ and the perceptual module as ${\mathcal{F}}$. ${\mathcal{G}}$
updates the temporal latent bottleneck state while ${\mathcal{F}}$ processes
chunks $X_{l}$ to form the latent representation $\bar{X}_{l}$ -

$\displaystyle\text{{Perceptual Module}}\quad\bar{X}_{l}$
$\displaystyle={\mathcal{F}}(X_{l},{\mathcal{I}}_{l})$ (1)
$\displaystyle\text{{Temporal Latent Bottleneck
Module}}\quad{\mathcal{I}}_{l+1}$
$\displaystyle={\mathcal{G}}({\mathcal{I}}_{l},\bar{X}_{l})$ (2)

Preliminaries. The central components of our model are the key value attention
mechanism (Bahdanau2015NeuralMT; vaswani2017attention) and the FFN module
(vaswani2017attention). We use two forms of the attention mechanism -(1) Self
Attention (vaswani2017attention): In this the query and key vectors refer to
the same set of vectors; (2) Cross Attention (goyal2021coordination;
jaegle2021perceiver; goyal2019recurrent): In this the query and key vectors
refer to seperate sets of vectors.

Perceptual Module ${\mathcal{F}}$. As mentioned previously, the perceptual
module refers to the fast stream that acts directly on the input. The
perceptual module operates on each chunk separately. Therefore, at any time
the input to the perceptual module are the tokens corresponding to a
particular chunk $X_{l}=[x_{l\times K},x_{l\times K+1},\ldots,x_{l\times
K+K}]$. The perceptual module is a Transformer with self attention layers,
cross attention layers, and FFNs. It has 2 kinds of layers - (1) self
attention + FFN; (2) cross attention + FFN. The self attention + FFN layers
process the input tokens and the cross attention + FFN layers integrate top-
down information from the temporal latent bottleneck state ${\mathcal{I}}$ as
follows -

$\displaystyle X_{l}$
$\displaystyle=\textsc{Attention}(\text{LN}(X_{l}),\text{LN}({\mathcal{I}}),\text{LN}({\mathcal{I}}))+X_{l}$
$\displaystyle X_{l}$ $\displaystyle=\textsc{FFN}(\text{LN}(X_{l}))+X_{l}$ (3)

We include one cross attention + FFN layer per $R$ self attention + FFN
layers. The diagramatic representation of the perceptual module is presented
in Figure 1 (in the processing of chunk $X_{l}$). In the figure, we set $R=1$.

Temporal Latent Bottleneck Module ${\mathcal{G}}$. The temporal latent
bottleneck (TLB) module represents the slow stream that operates on the
temporal latent bottleneck state ${\mathcal{I}}$. ${\mathcal{I}}$ is updated
using information from a particular chunk processed by the perceptual module.
This update happens once for each chunk of the perceptual module resulting in
$\lfloor T/K\rfloor$ updates for ${\mathcal{I}}$. Since the temporal latent
bottleneck state ${\mathcal{I}}$ updates at a lower frequency than the
perceptual module, it is expected to capture more stable and slowly changing
features while the perceptual module captures faster changing features
resulting in multiple scales of information representation. An update to the
temporal latent bottleneck state ${\mathcal{I}}$ consists of a cross attention
operation where the queries come from ${\mathcal{I}}$ and the keys and values
come from the output of the perceptual module. This cross attention operation
is followed by an FFN update to ${\mathcal{I}}$. Consider the perceptual
module outputs for a chunk $l$ to be $\bar{X}_{l}=[\bar{x}_{l\times
K},\ldots,\bar{x}_{l\times K+K}]$. The update operation is implemented as
follows:

$\displaystyle\bar{{\mathcal{I}}}$
$\displaystyle=\textsc{Attention}(\text{LN}({\mathcal{I}}_{l}),\text{LN}(\bar{X}_{l}),\text{LN}(\bar{X}_{l}))+{\mathcal{I}}_{l}$
$\displaystyle{\mathcal{I}}_{l+1}$
$\displaystyle=\textsc{FFN}(\text{LN}(\bar{{\mathcal{I}}}))+\bar{{\mathcal{I}}}$
(4)

The temporal latent bottleneck module introduces the notion of recurrence in
our model. We show the details of this module in Figure 1 (inside the circle).

Perceptual Module + Temporal Latent Bottleneck Model. We now present our
complete architecture integrating both the perceptual module and the temporal
latent bottleneck together. Given a sequence of tokens
$X=[x_{0},x_{1},x_{2},\ldots,x_{t}]$. We chunk this input into chunks of size
$K$ resulting in $\lfloor T/K\rfloor$ chunks. The chunks are processed
sequentially one after the other. For a chunk $k$, it is first processed using
the perceptual module conditioned on information from the temporal latent
bottleneck state. The outputs of the chunk are used to update the temporal
latent bottleneck state ${\mathcal{I}}$. The resultant temporal latent
bottleneck state is then used to process the next chunk. The full model is
presented in Figure 1. We use a Transformer as the perceptual module in our
experiments. Thus our main contribution is introducing a temporal latent
bottleneck into Transformers and showing its advantages through a variety of
experiments. We also present the detailed algorithm for the proposed approach
in Algorithm 1.

The proposed model is similar to a parallel work called Block Recurrent
Transformers (delesley2022block). There are few differences between our work
and theirs. First, they use a sliding window attention, while we divide the
input into chunks. In their paper, they perform cross attention and self
attention in parallel while we find that doing them sequentially and
performing cross attention once per $R$ self attention steps yields better
results. We defer the rest of the discussion on related works to Appendix
Section LABEL:sec:related_work

##  3 Experiments

Table 1: Image Classification. Here we compare the performance of the proposed ViT + TLB model against ViT and SwinV2 on CIFAR10 and CIFAR100 datasets for $64\times 64$ images and $128\times 128$ images. Note that the model is trained only on the $64\times 64$ sized images and then transferred to $128\times 128$ sized images. Results averaged across 3 seeds. | CIFAR10 | CIFAR100
---|---|---
Model | $\bm{64\times 64}$ | $\bm{128\times 128}$ | $\bm{64\times 64}$ | $\bm{128\times 128}$
ViT | 93.75 | 73.18 | 69.53 | 47.4
Swin V2 | 97.66 | 84.9 | 79.95 | 58.59
ViT + TLB | 94.79 | 84.38 | 79.17 | 59.19

Our goal is to show the wide applicability and benefits offered by the
temporal latent bottleneck, which we refer to as TLB. We demonstrate that the
proposed model outperforms competitive baselines across many domains including
vision, reinforcement learning, and natural language. Our main goal is to show
that the proposed approach has high expressive power like Transformers while
also being sample efficient unlike Transformers. Thus our main baselines are
based on the original Transformer architecture. For example, we compare
against ViT (dosovitskiy2020vit) in image classification, Decision Transformer
(chen2021decision) in Reinforcement Learning, and Vanilla Transformer in rest
of the tasks. We also compare against some representative baseline that offer
some of the key properties that our model offers. For example, we compare
against state-of-the art Swin Transformer (swinv2) which is a strong baseline
for image classification and is also hierarchical similar to the proposed
model. We also compare against Transformer LS (zhu2021long) which also
processes long-term and short-term information using different attention
streams. Furthermore, we also compare against Feedback Transformer
(fan2021addressing), which also introduces top-down communication into
Transformers. Another key point of the proposed model is that any position
cannot attend to any information from the future beyond its chunk since the
temporal latent bottleneck only summarizes the past, not the future.
Meanwhile, all the baselines we consider have bidirectional context i.e. they
can attend to all of the past and the future. We observe that despite this
limitation, the proposed model outperforms all the considered baselines.

###  3.1 Temporal Latent Bottleneck For Perception

Table 2: Here we show the performance of the proposed ViT + TLB model against two baselines - One with no access to the past and One with no top-down information (i.e. high level to low level communication). We can see that the model suffers a drop in performance for both the baseline thus showing the importance of past information and top-down communication. Results averaged across 3 seeds. |  |  | CIFAR10
---|---|---|---
Model | Past | Top | $\bm{64\times 64}$ | $\bm{128\times 128}$
| Info | Down |  |
ViT + TLB | $\checkmark$ | $\checkmark$ | 94.79 | 84.38
No Past Info. | $\times$ | $\times$ | 91.30 | 72.92
No Top-Down Condn | $\checkmark$ | $\times$ | 93.75 | 83.59

Image Classification. Recently, Transformers have been widely applied for
visual perception and have shown strong performance improvements over CNNs in
tasks such as image classification, semantic segmentation, instance
segmentation, etc. In this work we focus on image classification using
Transformers. For a model to do well on image classification, it should learn
to only focus on the relevant information and ignore other details (eg.
background information). Self attention does not inherently have this
inductive bias of ignoring irrelevant information since it models all pairwise
interactions between the inputs. We posit that adding a limited bandwidth
temporal latent bottleneck into the Transformer will allow the model to focus
only on the most important information in the image which should enable the
model to perform well.

Results. We test our hypothesis on the CIFAR10 and CIFAR100
(Krizhevsky09learningmultiple) image classification datasets. We also test the
generalization abilities of the models by comparing their performance on
images of higher resolution ($128\times 128$) than seen during training
($64\times 64$). We use ViT (dosovitskiy2020vit) and Swin Transformer V2
(denoted as Swin V2) swinv2 as our baselines. Swin Transformer V2 has a key
strength of generalizing to higher resolution images than those seen during
training, making it a strong baseline. The input image is split into patches
of size $4\times 4$ and fed in rastor order to all the models. For the
proposed model we use ViT as the perceptual module and add a temporal latent
bottleneck module to it. We call this model ViT + TLB. To predict the
classification scores, we take the mean across the final temporal latent
bottleneck state vectors and pass the resulting representation through an MLP.
We present the results for this experiment in table 1. We can see that ViT +
TLB outperforms ViT for all cases and performs competitively to Swin
Transformer V2. For further hyperparameter details, we refer the reader to
Appendix section LABEL:appendix:image_classification.

Figure 2: We want to analyze the information which is being used to influence
the processing of Temporal Latent Bottleneck. To calculate this, we calculate
the attention scores for different patches and we mask out all the patches
that are not in the top 30% of the attention scores. We can see that for both
the images it recovers the foreground almost perfectly which shows it learns
to focus on the most important information required to solve the downstream
task.

Quantitative Analysis. One essential component of our model is top-down
conditioning. Top down information helps in integrating information from the
past as well as high-level information into the perceptual module. We
hypothesize that both these kinds of information are important for the model
to perform well. To test this, we design two baselines - (1) ViT + TLB (No
Past Info): In this baseline, we do not allow the TLB to communicate to the
perceptual module, therefore the perceptual module has no information about
the past; (2) ViT + TLB (No Top-Down Condn): In this baseline, we have a
separate temporal latent bottleneck module at every layer, therefore the
perceptual module has access to past information but does not have access to
any high-level information through top-down feedback. We show the results for
this ablation in Table 2. We can see that the performance of both the
baselines is worse than the proposed ViT + TLB model. This shows that both
high-level information through top-down feedback and information from the past
is important for the model to perform well.

Qualitative Analysis. To get a better understanding of what the temporal
latent bottleneck is doing, we visualize the parts of the image where the
temporal latent bottleneck pays most attention while it is being updated by
the perceptual module. We present this visualization in Figure 2. We can see
that the temporal latent bottleneck learns to pay the most attention to the
foreground in each case. This further confirms our hypothesis that the limited
capacity bottleneck focuses on the most important information required to
solve the downstream task.

Figure 3: Self Supervised Learning Results of linear probing on the CIFAR 10
dataset for models pretrained on the STL 10 dataset. We can see that the
proposed SiT + TLB approach outperforms SiT.

Self Supervised Learning. Many recent works have used Vision Transformers for
self-supervised learning (bao2021beit; ahmed2021sit; he2021masked;
caron2021emerging; li2021mst; li2021efficient). Here we show a proof-of-
concept that introducing a temporal latent bottleneck in Vision Transformers
results in better self-supervised representations. We consider the SiT model
from ahmed2021sit for this experiment. They use 3 objectives to pretrain their
model - (1) The Reconstruction Objective - Reconstructs the input image, (2)
The Rotation Prediction Objective - Predicts the rotation angle from
[$0^{\circ}$, $90^{\circ}$, $180^{\circ}$, $270^{\circ}$], and (3) The
Constrastive Objective (similar to SimCLR (simclr)). For the proposed
approach, we introduce a temporal latent bottleneck into SiT resulting in the
SiT + TLB model. SiT also uses additional trainable contrastive and rotation
tokens as input for calculating the contrastive and rotation objectives
respectively. For SiT + TLB, we take the mean across the temporal latent
bottleneck state vectors and use the resulting representation for computing
the rotation and contrastive objectives. We use a chunk length of 20 for the
SiT + TLB model. We pretrain the model for 400 epochs and evaluate the
pretrained model at different epochs using linear probing.

Results. To evaluate the model, we pretrain the model on the STL10 dataset
(pmlr-v15-coates11a) and evaluate the learned representation using linear
probing on the CIFAR10 dataset (Krizhevsky09learningmultiple). We present the
results for this experiment in Figure 3. We can see that the proposed approach
outperforms SiT thus showing the effectiveness of the proposed architecture
for self-supervised learning. For additional experimental results and details,
we refer the reader to Appendix section LABEL:appendix:ssl.

###  3.2 Temporal Latent Bottleneck for Sequential Decision Making

Transformers have recently been used for sequential decision making in
reinforcement learning tasks such as Atari and BabyAI (chen2021decision;
iii2022improving). These works deploy Transformers in the offline RL setting
where a large number of trajectories are available either through another
trained agent or an expert agent. The Transformer is trained as an
autoregressive generative model that predicts actions conditioned on the past
context. We incorporate the temporal latent bottleneck module into the
Transformer and explore its benefits in the RL setting. We test the proposed
model in the BabyAI (babyai-env) and Atari (atari-env) benchmarks. We describe
our setups in detail below.

Instruction Based Decision Making: BabyAI. BabyAI (babyai-env) provides a
suite of environments where the agent has to carry out a given instruction in
a partially-observable maze. These instructions include competencies such as
going to an object in the maze, placing an object beside another object in the
maze, opening a door with a key, etc. Some environments in the benchmark
contain instructions that combine multiple competencies sequentially. For
example, pick up a red ball and open the door in front of you after you pick
up the grey ball on your left and pick up a red box. Each environment in Baby
AI benchmark has a different type of instruction that tests a different
competency. The BossLevel is the most complicated environment that contains
instructions from all competencies. For more details regarding the various
environments from the BabyAI benchmark, we refer the reader to Appendix
section LABEL:appendix:babyai.

Figure 4:  Single Task BabyAI. (Left) Here we compare the performance of
Transformer and Transformer + TLB on the BossLevel task from BabyAI. We can
see that while both the models converge to a similar success rate, Transformer
+ TLB converges faster than Transformer. Multi Task BabyAI. (Right) Here we
compare the performance of Transformer and Transformer + TLB on 8 tasks from
the BabyAI suite of environments. A single model is trained for all the 8
tasks. We can see that Transformer + TLB converges faster and achieves a
better performance than Transformer.

We train our models with behavior cloning using expert trajectories from an
oracle. For evaluation, we test the model by directly deploying it in the
environment. We report the success rate which measures whether the agent
successfully carried out the given instruction or not. We use a Transformer
(vaswani2017attention) as the baseline in these experiments. For the proposed
model, we introduce a temporal latent bottleneck into the Transformer-based
perceptual module. For the baseline Transformer model, we append the language
instruction to the sequence of states allowing the model to attend to the
language instruction at each layer. For the proposed model, the language
instruction is appended to each chunk, allowing each chunk to attend to it.

Results. We consider two settings - Single task and Multi task. In the single
task setting, we evaluate the proposed approach on individual environments
from the BabyAI benchmark while in the multi-task setting we train a single
model on 8 different environments.

Single Task. We present the results for BossLevel in Figure 4 (left) and
present the results for the other tasks in Appendix Figure
LABEL:fig:babyai_single_task. We can see that while Transformer and
Transformer + TLB achieve almost similar performance at convergence. However,
Transformer + TLB is much more sample efficient, converging much faster. We
posit that the temporal latent bottleneck module prohibits the model from
paying attention to unnecessary information which allows it to converge
faster.

Multi Task. We present the results for the multi task setting in Figure 4
(right). We train the model on 8 environments - PutNext, Unlock, Synth,
GoToSeq, SynthLoc, GoToImpUnlock, BossLevel. We evaluate the model on the same
8 environments. We report the average success rate across 8 games. We can see
that the Transformer + TLB model converges faster and also outperforms the
Transformer. We refer the reader to the appendix for more details regarding
the model and training.

Table 3: Atari. Here we show that adding a temporal latent bottleneck into decision Transformer improves performance across various atari games. Results are averaged across 10 seeds. Game | DT | DT + TLB
---|---|---
Breakout |  71.51$\pm$20.58 | 87.63$\pm$16.24
Pong |  13.68$\pm$2.00 | 14.71$\pm$1.78
Qbert |  3268$\pm$1773.07 | 5019.75$\pm$1647.13
Seaquest |  1039.11$\pm$122.90 | 1248.22$\pm$86.62

Atari. (chen2021decision) recently introduced the Decision Transformer (DT)
which learns to play various games in the Atari benchmark from suboptimal
trajectories of a learned agent. Decision Transformer models the offline RL
problem as a conditional sequence modelling task. The model uses a causal mask
and supervised training to match the actions in the offline dataset
conditioned on the future expected returns and the past history. This is done
by feeding into the model the states, actions, and the return-to-go
$\hat{R}_{c}=\sum_{c^{\prime}=c}^{C}r_{c}$, where $c$ denotes the timesteps.
This results in the following trajectory representation:
$\tau=\big{(}\hat{R}_{1},s_{1},a_{1},\hat{R}_{2},s_{2},a_{2},\hat{R}_{3},s_{3},a_{3},\ldots\big{)}$,
where $a_{c}$ denotes the actions and $s_{c}$ denotes the states. At test
time, the start state $s_{1}$ and desired return $\hat{R}_{1}$ is fed into the
model and it autoregressively generates the rest of the trajectory.
Experimental results show that DT can leverage the strong generalization
capabilities of Transformers and achieve the desired returns in a wide variety
of tasks in Atari and OpenAI Gym, outperforming previous approaches in offline
RL.

Table 4: Long Range Dependencies. Here we compare the performance of the proposed model against the recently proposed long-short Transformer model (zhu2021long) and the vanilla Transformer model (vaswani2017attention). We can see that the proposed model outperforms both the baselines thus showing the superiority of the proposed model in modelling long-range and hierarchical dependencies. Results averaged across 5 seeds. Model | ListOps | Text
---|---|---
|  | Classification
Transformer |  37.64$\pm$0.0001 |  64.0$\pm$0.0001
Transformer LS |  37.5$\pm$0.0002 |  65.5$\pm$0.0003
Transformer + TLB | 38.2$\pm$0.0001 | 82.08$\pm$0.44

We use the same setup as used in (chen2021decision) for our experiments. We
set the context length to a fixed number $C$. During training, $C$ timesteps
from an episode are sampled and fed into the model resulting in a trajectory
of length $3{\bm{C}}$ (considering 3 modalities - returns-to-go, states, and
actions). Each modality is processed into an embedding of size $d$. The state
is processed using a convolutional encoder into an embedding of size $d$. The
resulting trajectory is fed into the decision Transformer. The outputs
corresponding to the states $s_{c}$ are fed into a linear layer to predict the
action $a_{c}$ to be taken at timestep $c$. For the proposed model, we
incorporate a temporal latent bottleneck module into the Decision Transformer.

Results. We present our results in Table 3. The model is trained on 1% of the
Atari DQN-replay dataset (agarwal2019striving) (500K transitions for each
game). We use the same 4 games used in (chen2021decision): Pong, Seaquest,
Qbert, and Breakout. We can see that the proposed model outperforms Decision
Transformer in all the considered games thus showing the effectiveness of the
proposed model. More details regarding the model and training can be found in
the appendix section LABEL:appendix:atari.

###  3.3 Temporal Latent Bottleneck for Long Range Dependencies

Here, we test the effectiveness of the proposed model in modelling long range
dependencies. We apply the proposed model on the ListOps and text
classification tasks from the Long Range Arena (LRA) benchmark (yi2020long).
Both these tasks have very long sequences ranging from 1K to 4K tokens. Thus,
for a model to do well, it has to learn to capture dependencies across very
long time scales. Additionally, all these tasks have an inherent hierarchical
structure. For example, Listops consists of nested list operations which makes
it hierarchical. For text classification, the inputs consist of text in the
form of bytes. Therefore, the model has to learn to compose bytes into
characters and characters into words. We hypothesize that the multi-scale
hierarchical nature of the proposed model will be extremely useful in
modelling such hierarchical information.

Results. For this experiment, we use the same setup as(zhu2021long). For the
proposed model, we use a Transformer as the perceptual model and implement the
temporal latent bottleneck as described in Section 2.2. We take the mean
across the temporal latent bottleneck state vectors and use the resulting
representation for classification. We compare the model against the long-short
Transformer (LS) model (zhu2021long), which is a recently proposed model for
the long range arena benchmark, and the vanilla Transformer model
(vaswani2017attention). We present the results in Table 4. We can see that the
proposed model outperforms both the baselines in both the tasks thus showing
its usefulness in modeling long range dependencies. For further details, we
refer the reader to Appendix section LABEL:appendix:long_range_arena.

(a) ListOps (b) Text Classification

Figure 5:  (a) Here we show the performance on ListOps as a function of the
number of samples in the dataset. We do only one pass over the entire data and
find that Transformer +TLB takes much fewer samples to converge as compared to
the baseline Transformer LS. (b) Here we show the convergence curves of both
the Transformer + TLB model and the Transformer LS model on the text
classification task. In this case, we do not perform only one pass over the
dataset since we observe that both models do not reach convergence in a single
pass. Therefore, we report the number of training steps on the x-axis. We can
see that the proposed model achieves much higher score than the baseline.

In Fig. 5, we plot the convergence curves for ListOps and Text Classification.
For ListOps (Figure 5(a)), we plot the convergence curves against the number
of samples i.e. we do only one pass over the dataset hence the model does not
see any example more than once. We can see that the proposed Transformer + TLB
model is much more sample efficient than the baseline Transformer LS model.
For Text Classification (Figure 5(b)), we plot the convergence curves against
the number of training steps. We find that doing only one pass over the
dataset does not work well for both the baseline and the proposed model hence
we use number of training steps on the x-axis. We can see that while initially
both models converge at a similar pace, the proposed model achieves a much
higher performance.

Table 5: Text Classification - Performance Ablation Here, we compare the wall-clock time and memory during the training and inference phase of the text classification task w.r.t baseline transformer model. Chunk | 1000 | 100 | 40 | 20 | 10
---|---|---|---|---|---
Size |  |  |  |  |
Inference Speed | 3.5x | 3.6x | 3.3x | 2.2x | 1.2x
Inference Memory | 0.09x | 0.08x | 0.12x | 0.08x | 0.1x
Training Speed | 4.4x | 4.4x | 2.2x | 1.4x | 0.7x
Training Memory | 0.14x | 0.08x | 0.49x | 0.40x | 0.42x

We measure the wall-clock time and memory required for text classification
task as we vary the chunk size in Table 5. All TLB models have an increased
memory efficiency and supports faster inference speeds with respect to the
baseline transformer model. The training speeds also get better with increased
chunking. The only exception is very small chunk sizes, where the training is
slower than the baseline because of increased temporal unrolling. However, as
shown in Figure 5, such models are very sample efficient resulting in lesser
training steps overall.

Analysis. Here we perform an ablation to show that the Temporal Latent
Bottleneck does not only contain short-term information but also summarizes
information from long term past. To test this hypothesis we design a baseline
in which the current chunk attends to the previous few chunks instead of
attending to the temporal latent bottleneck. We find that this baseline
achieves a performance of 32.10$\pm$0.019% compared to the proposed models
38.2$\pm$0.0001% on the ListOps task. This shows that the Temporal Latent
Bottleneck contains information about the long-term past. Additionally, here
also we perform an experiment to probe the importance of top-down
communication (i.e. high level to low level feedback). To do this we use the
same Transformer + TLB (No Top-Down Condn) baseline used in Table 2. We find
that this baseline achieves a performance of 37.57$\pm$0.003% which is lower
than the performance of the proposed Transformer + TLB model which achieves
38.2$\pm$0.0001% which further shows that top-down information from high-level
to low-level is important for the model to perform well.

We perform additional experiments to give us more insight into the behavior of
the proposed model. We present these experiments in Appendix Section
LABEL:appendix:long_range_arena. We also compare the model to additional
efficient transformer baselines for all LRA tasks in Appendix Table
LABEL:tab:effecient_baslines_lra.

Figure 6: Copying Task. Here we compare the performance of the proposed
Transformer + TLB model to the Feedback Transformer model on the copying task.
We can see that the Transformer + TLB achieves perfect accuracy for all the
studied sequence lengths while the the performance of Feedback Transformer
starts dropping after sequence length 400.

Sequence | Feedback | Transformer +
---|---|---
Length | Transformer | TLB
100 | 11800 | 6200
200 | 16600 | 9100
300 | 35100 | 12700
400 | NA | 14600
500 | NA | 13600
600 | NA | 19300
Figure 7: Copying Sample Efficiency Ablation. Here we present the number of
unique samples required for the models to reach to perfect accuracy on the
copying task. NA indicates that the model does not reach perfect accuracy. We
can see that in all cases the Transformer + TLB model is more sample efficient
than the Feedback Transformer model.

Temporal Latent Bottleneck for Copying Task. Here, we study the copying task
used in (hochrieter1997long). In the copying task, the model receives a
sequence of 10 digits followed by blank inputs for a large number of steps,
and then the model is asked to output the sequence of digits it received
initially. Therefore, the model has to remember the original sequence of
digits across long time scales. We can control the sequence length of this
task by controlling the length of the blank input.

The main motive behind studying this task is comparing the model to the
Feedback Transformer model introduced in (fan2021addressing) which also has
top-down attention similar to the proposed model but does not represent
information at multiple scales. We compare both the models on the copying task
for sequence lengths 100, 200, 300, 400, 500, and 600. We present the results
for this task in Figure 7. We can see that while both Transformer + TLB and
Feedback Transform perform well for low sequence lengths, the performance of
Feedback Transformer drops for longer sequence lengths above 400 while the
proposed Transformer + TLB model still achieves perfect accuracy at long
sequence lengths. We also compare the sample efficiencies to achieve perfect
accuracy for both the models. We present this result in Table 7. We can see
that the proposed Transformer + TLB is more sample effecient than the baseline
Feedback Transformer achieving perfect accuracy in much lesser number of
samples in each case. For further details we refer the reader to Appendix
Section LABEL:sec:copying.

##  4 Conclusion

We have developed an approach aimed at introducing selectivity in the
interactions across time-steps in a transformer by splitting processing into
two streams: (a) a slow stream that is updated in a recurrent manner and (b) a
fast stream that processes the visual input. The two streams are parameterized
independently and interact with each other via attentional bottleneck. The
information processed by the fast stream is used to change the state of the
slow stream, and the information in the slow stream is used by the fast stream
as contextual information to process the input. Through our experiments we
show that the proposed approach works well across wide range of domains and
problems. One limitation of the proposed model is that the chunk size is fixed
and treated as a hyperparameter which requires some domain knowledge. Future
work should explore methods for dynamic chunking.

##  5 Acknowledgement

The authors would like to thank Compute Canada for providing the computational
resources used in this project. The authors also gratefully acknowledge the
funding from Samsung, IBM and CIFAR.

## Checklist

Please do not modify the questions and only use the provided macros for your
answers. Note that the Checklist section does not count towards the page
limit. In your paper, please delete this instructions block and only keep the
Checklist section heading above along with the questions/answers below.

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] Appendix Section LABEL:sec:details

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [No] All the datasets we use are
openly available

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [No]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A] The datasets we use do not contain any sensitive
information.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]


# The Mordell-Lang conjecture for semiabelian varieties defined over fields of
positive characteristic

Dragos Ghioca  Department of Mathematics
University of British Columbia
1984 Mathematics Road
Canada V6T 1Z2<EMAIL_ADDRESS>and  She Yang  Beijing International
Center for Mathematical Research
Peking University
Beijing 100871
China<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a semiabelian variety defined over an algebraically closed field
$K$ of prime characteristic. We describe the intersection of a subvariety $X$
of $G$ with a finitely generated subgroup of $G(K)$.

###### Key words and phrases:

semiabelian varieties; finite fields; Mordell-Lang conjecture

###### 2020 Mathematics Subject Classification:

Primary: 11G10; Secondary: 14G17

##  1\. Introduction

The purpose of this note is to prove a variant of the Mordell-Lang conjecture
for semiabelian varieties defined over fields of positive characteristic. More
precisely, let $G$ be a semiabelian variety defined over an algebraically
closed field $K$, i.e., there exists a short exact sequence of algebraic
groups defined over $K$:

(1.0.1) $1\longrightarrow\mathbb{G}_{m}^{N}\longrightarrow G\longrightarrow
A\longrightarrow 1,$

where $N\geq 0$ is an integer and $A$ is an abelian variety. Assuming $K$ has
characteristic $p>0$, then for any subvariety $X\subseteq G$ defined over $K$
and any finitely generated subgroup $\Gamma\subset G(K)$, we describe the
intersection $X(K)\cap\Gamma$. In particular, we fix an error in the paper
[Ghi08] of the first author where a simplified form of the aforementioned was
claimed in the case $G$ is defined over a finite subfield of $K$; we present
several examples showing that the intersection $X(K)\cap\Gamma$ involves the
more general $F$-sets appearing in Definition 1.5.

###  1.1. General background

The Mordell-Lang conjecture for semiabelian varieties $G$ defined over fields
of characteristic $0$ predicts that the intersection of a subvariety
$X\subseteq G$ with a finitely generated subgroup $\Gamma$ of $G$ is a finite
union of cosets of subgroups of $\Gamma$. This conjecture was proven by
Laurent [Lau84] in the case of tori, Faltings [Fal91] in the case of abelian
varieties, and by Vojta [Voj96] in the general case of semiabelian varieties.
In particular, their results show that if $X$ is an irreducible subvariety of
$G$ which intersects a finitely generated group in a Zariski dense subset,
then $X$ must be a translate of a semiabelian subvariety of $G$.

The picture for positive characteristic fields $K$ is more complicated due to
the existence of the Frobenius endomorphism for varieties defined over finite
fields; in particular, it is no longer true that only translates of
semiabelian subvarieties of $G$ have the property that they intersect a
finitely generated subgroup of $G$ in a Zariski dense subset. Hrushovski
[Hru96] obtained the right shape for the irreducible subvarieties $X$ whose
intersection with a finitely generated subgroup $\Gamma$ is Zariski dense.

######  Theorem 1.1 (Hrushovski [Hru96]).

Let $G$ be a semiabelian variety defined over an algebraically closed field
$K$ of characteristic $p$. Let $\Gamma\subset G(K)$ be a finitely generated
subgroup and let $X\subseteq G$ be an irreducible subvariety with the property
that $X(K)\cap\Gamma$ is Zariski dense in $X$. Then there exists $\gamma\in
G(K)$, there exists a semiabelian subvariety $G_{0}\subseteq G$ defined over
$K$, there exists a semiabelian variety $H$ along with a subvariety
$X_{0}\subseteq H$ both defined over a finite subfield $\mathbb{F}_{q}$ of
$K$, and there exists a surjective group homomorphism $h:G_{0}\longrightarrow
H$ such that $X=\gamma+h^{-1}(X_{0})$.

However, [Hru96] left open the description of the actual intersection between
the subvariety $X$ and the group $\Gamma$; next, we will address exactly this
issue.

###  1.2. The case of semiabelian varieties defined over finite fields and of
finitely generated subgroups invariant under the Frobenius endomorphism

Essentially, Hrushovski’s result (see Theorem 1.1) reduced the description of
the intersection $X(K)\cap\Gamma$ to the case when the ambient semiabelian
variety is defined over a finite field. Moosa and Scanlon [MS04, MS02]
addressed precisely this problem under an additional assumption on the
subgroup $\Gamma$; in order to state their main result, we introduce a little
bit of notation.

######  Definition 1.2.

For a semiabelian variety $G$ defined over a finite subfield $\mathbb{F}_{q}$
of an algebraically closed field $K$ of characteristic $p$, we define a
_groupless $F$-set_ any subset of $G(K)$ of the form:

(1.0.2) $\left\\{\alpha_{0}+\sum_{i=1}^{r}F^{kn_{i}}(\alpha_{i})\colon
n_{i}\in\mathbb{N}\right\\},$

where $r\geq 0$, $\alpha_{0},\alpha_{1},\dots,\alpha_{r}\in G(K)$ and
$k\in\mathbb{N}$, while $F$ is the Frobenius endomorphism of $G$ corresponding
to the finite field $\mathbb{F}_{q}$.

For any finitely generated subgroup $\Gamma\subset G(K)$, we define a
_groupless $F$-set in $\Gamma$_ as a groupless $F$-set contained in $\Gamma$.
Also, an _$F$ -set in $\Gamma$_ is any set of the form $S+B$, where $S$ is a
groupless $F$-set in $\Gamma$ and $B$ is a subgroup of $\Gamma$ (as always,
for any two subsets $B$ and $C$ of $G$, we have that $C+B$ is simply the set
of all $c+b$ where $b\in B$ and $c\in C$).

######  Remark 1.3.

In [MS04, Theorem B], Moosa and Scanlon allowed for the possibility that a
groupless $F$-set involves sums of $F$-orbits as in equation (1.0.2) of the
form

(1.0.3) $\alpha_{0}+\sum_{i=1}^{r}F^{k_{i}n_{i}}(\alpha_{i})\text{ (as $n_{i}$
vary in $\mathbb{N}$),}$

for given, but potentially distinct, positive integers $k_{i}$. However, each
$F$-set from equation (1.0.3) is a union of finitely many $F$-sets given as in
Definition 1.2 (simply by working with $k$ as the least common multiple of
$k_{1},\dots,k_{r}$).

######  Theorem 1.4 (Moosa-Scanlon [MS04]).

Let $G$ be a semiabelian variety defined over a finite subfield
$\mathbb{F}_{q}$ of an algebraically closed field $K$ and let
$F:G\longrightarrow G$ be the Frobenius endomorphism associated to the finite
field $\mathbb{F}_{q}$. Let $X\subseteq G$ be a subvariety defined over $K$
and let $\Gamma\subset G(K)$ be a finitely generated subgroup. If $\Gamma$ is
invariant under $F^{\ell}$ for some $\ell\in\mathbb{N}$, then $X(K)\cap\Gamma$
is a finite union of $F$-sets in $\Gamma$.

###  1.3. The case of an arbitrary finitely generated subgroup

It is natural to ask whether the above description from Theorem 1.4 of the
intersection $X(K)\cap\Gamma$ remains valid also when $\Gamma$ is no longer
invariant under a power of the Frobenius endomorphism of $G$ (but only assume
$\Gamma$ is finitely generated).

One could consider the $\mathbb{Z}[F]$-submodule $\tilde{\Gamma}\subset G(K)$
spanned by $\Gamma$ and since $F$ is integral over $\mathbb{Z}$ (seen as a
subring of ${\rm End}(G)$), then $\tilde{\Gamma}$ is still finitely generated
and so, Moosa-Scanlon’s result (see Theorem 1.4) yields that
$X(K)\cap\tilde{\Gamma}$ is a finite union of $F$-sets in $\tilde{\Gamma}$.
So, the problem reduces to understanding the intersection of an $F$-set $S$ in
$\tilde{\Gamma}$ with $\Gamma$. The first author [Ghi08, Theorem 3.1] proved
that when $S$ is a _groupless_ $F$-set in $\tilde{\Gamma}$, then its
intersection with $\Gamma$ is a finite union of groupless $F$-sets in
$\Gamma$. Also, the first author analyzed in [Ghi08] the intersection with
$\Gamma$ of an arbitrary $F$-set in $\tilde{\Gamma}$; however, the final
assertion from [Ghi08, Step 3, p. 3842] claiming that the general case of an
$F$-set reduces to the groupless case is not valid, as shown by the
constructions from Section 2 (see Examples 2.1 and 2.2 which were found by the
second author). Essentially, the error from [Ghi08] was to claim that the
pullback of a groupless $F$-set in $\tilde{\Gamma}$ through a group
homomorphism restricted to $\Gamma$ must be an $F$-set in $\Gamma$ (as in
Definition 1.2). Furthermore, Example 2.3 shows that when $\Gamma$ is an
arbitrary finitely generated subgroup, the intersection $X(K)\cap\Gamma$ can
be quite wild; this motivates our Definition 1.5 which yields the right form
of the sets appearing in the intersection of a subvariety of $G$ with a
finitely generated group.

######  Definition 1.5.

For a semiabelian variety $G$ defined over a finite subfield $\mathbb{F}_{q}$
of an algebraically closed field $K$ of characteristic $p$ and a finitely
generated subgroup $\Gamma\subset G(K)$, we define a _generalized $F$-set in
$\Gamma$_ any subset of $\Gamma$ of the form:

(1.0.4) $\left(\pi|_{\Gamma}\right)^{-1}(S),$

where $\pi:G\longrightarrow H$ is a surjective group homomorphism of
semiabelian varieties both defined over a finite subfield of $K$ for which
$\dim(\ker(\pi))>0$, $\pi|_{\Gamma}$ is its restriction to the subgroup
$\Gamma$, and $S\subset H(K)$ is a groupless $F$-set in $\pi(\Gamma)$.

Note that $H$ may be defined over another finite subfield
${\mathbb{F}}_{q^{\prime}}\subset K$ and thus the set $S$ from equation
(1.0.4) is a groupless $F$-set in $\pi(\Gamma)$ where $F$ stands for the
Frobenius endomorphism of $H$ associated to the finite field
${\mathbb{F}}_{q^{\prime}}$.

###  1.4. Our results

Now we can state our main results, first for describing the intersection with
a finitely generated group of a subvariety of a semiabelian variety defined
over a finite field.

######  Theorem 1.6.

Let $G$ be a semiabelian variety defined over a finite subfield
$\mathbb{F}_{q}$ of an algebraically closed field $K$ of characteristic $p$.
Let $X\subset G$ be a subvariety defined over $K$ and let $\Gamma\subset G(K)$
be a finitely generated subgroup. Then the intersection $X(K)\cap\Gamma$ is a
union of finitely many groupless $F$-sets in $\Gamma$ along with finitely many
generalized $F$-sets in $\Gamma$.

Our Examples 2.1, 2.2 and 2.3 show that the sets appearing as intersections
between a subvariety $X$ of a semiabelian variety $G$ defined over a finite
field with a finitely generated subgroup can be quite complicated, well-beyond
the world of $F$-sets from Definition 1.2. However, when $X$ is a curve or $G$
is a simple semiabelian variety (i.e., either a simple abelian variety or a
$1$-dimensional torus), then we can show that the intersection
$X(K)\cap\Gamma$ is a finite union of $F$-sets in $\Gamma$.

######  Theorem 1.7.

Let $G$ be a semiabelian variety defined over a finite subfield of an
algebraically closed field $K$ of prime characteristic, let $X\subseteq G$ be
a subvariety defined over $K$ and let $\Gamma\subset G(K)$ be a finitely
generated subgroup. If either $\dim(X)=1$ or $G$ is a simple semiabelian
variety, then $X(K)\cap\Gamma$ is a finite union of $F$-sets.

Next, combining our Theorem 1.6 with Hrushovski’s result (see Theorem 1.1), we
obtain the description of the intersection of a subvariety of an arbitary
semiabelian variety $G$ defined over a field of prime characteristic with a
finitely generated subgroup of $G$. For this end we introduce the notion of
_pseudo-generalized $F$-sets_.

######  Definition 1.8.

Let $G$ be a semiabelian variety defined over an algebraicaly closed field $K$
of characteristic $p$ and let $\Gamma\subset G(K)$ be a finitely generated
subgroup. A _pseudo-generalized $F$-set in $\Gamma$_ is a set of the form

$x_{0}+\left(\pi|_{\Gamma_{0}}\right)^{-1}(S),$

where $x_{0}\in\Gamma$, $G_{0}\subseteq G$ is a semiabelian subvariety,
$\Gamma_{0}=G_{0}(K)\cap\Gamma$, $H$ is a semiabelian variety defined over a
finite subfield ${\mathbb{F}}_{q}\subset K$, $\pi:G_{0}\longrightarrow H$ is a
surjective group homomorphism of semiabelian varieties, and $S\subset H(K)$ is
a groupless $F$-set in $\pi(\Gamma_{0})$.

######  Remark 1.9.

In Definition 1.8, if $G$ is defined over a finite subfield of $K$, then the
pseudo-generalized $F$-sets from Definition 1.8 cover both the groupless
$F$-sets in $\Gamma$ from Definition 1.2 and also the generalized $F$-sets in
$\Gamma$ from Definition 1.5, but it is a bit more general than those two
types of sets.

######  Theorem 1.10.

Let $G$ be a semiabelian variety defined over an algebraicaly closed field $K$
of characteristic $p$, let $X\subseteq G$ be a subvariety and let
$\Gamma\subset G(K)$ be a finitely generated group. Then $X(K)\cap\Gamma$ is a
finite union of pseudo-generalized $F$-sets in $\Gamma$.

###  1.5. Plan for our paper

In Section 2 we introduce three examples which progressively show the
complexity of the sets appearing as intersections between a subvariety of a
semiabelian variety $G$ with a finitely generated group. Even though in our
examples, $G$ is defined over a finite field, each such example can be
“embedded” as isotrivial semiabelian subvarieties of a semiabelian variety
defined over an arbitrary field of positive characteristic, thus providing
complex examples of pseudo-generalized $F$-sets. In Section 3 we prove
Theorems 1.6 and 1.10. Also, we prove Theorem 1.7 as a consequence of two more
precise results (see Propositions 3.1 and 3.2) regarding the structure of the
intersection $X(K)\cap\Gamma$ when either $X$ is a curve, or $G$ is a simple
semiabelian variety.

##  2\. Examples

Our first example already shows that $X(K)\cap\Gamma$ is not always an $F$-set
in $\Gamma$ (when $\Gamma$ is not invariant under the Frobenius endomorphism
of $G$).

######  Example 2.1.

We let $G={\mathbb{G}}_{m}^{2}\times E$, where $E$ is a supersingular elliptic
curve defined over $\mathbb{F}_{p}$; for example, we can take $E$ be the
elliptic curve given by the equation in affine coordinates $y^{2}=x^{3}+1$
when $p=5$, in which case, we have that the square $F^{2}$ of the usual
Frobenius endomorphism of $E$ corresponding to $\mathbb{F}_{5}$ equals the
multiplication map $[-5]$ on $E$. We let $C\subset{\mathbb{G}}_{m}^{2}$ be the
line given by the equation $x_{2}=x_{1}+1$ and then let $X=C\times E$. We let
$K=\overline{\mathbb{F}_{p}(t)}$ and let $P\in E(K)$ be a nontorsion point.
Finally, we let $\Gamma\subset G(K)$ be the cyclic group spanned by
$Q:=(t,t+1,P)\subset G(K)$. Then

(2.0.1) $X(K)\cap\Gamma=\left\\{p^{n}Q\colon n\geq 0\right\\}.$

Furthermore, the set from (2.0.1) cannot be expressed as a groupless $F$-set;
the closest it comes to being an $F$-set is expressing it as the following
slight twist of groupless $F$-sets. We let $Q_{1}:=(t,t+1,0)\in G(K)$ and
$Q_{2}:=(1,1,P)\in G(K)$ and then the set from (2.0.1) is the union of the
following two sets:

(2.0.2) $\left\\{F^{2n}(Q_{1})+F^{4n}(Q_{2})\colon n\geq 0\right\\}\text{ and
}\left\\{F^{2n+1}(Q_{1})-F^{4n+2}(Q_{2})\colon n\geq 0\right\\}.$

Now, comparing the sets from (2.0.2) with the actual (groupless) $F$-sets, the
difference seems quite small and so, one might think that perhaps slightly
extending the definition of $F$-sets as in equation (2.0.2) would be enough.
The main issue in Example 2.1 comes from the fact that the Frobenius
endomorphism has “different weights” on the abelian, respectively affine part
of $G$; so, it might be reasonable for one to think that allowing different
weights also in the definition of a groupless $F$-set by considering sets of
the form:

$\left\\{\sum_{i=1}^{r}\sum_{j=1}^{s}F^{k_{i,j}\cdot n_{j}}(\alpha_{j})\colon
n_{j}\geq 0\text{ for }j=1,\dots,s\right\\}$

would suffice for describing $X(K)\cap\Gamma$. However, the next example shows
that no simple extension of the definition of $F$-sets would work.

######  Example 2.2.

We still work with $G={\mathbb{G}}_{m}^{2}\times E$, but this time the
elliptic curve $E$ is ordinary; for example, we could take $p=5$ and let $E$
be the elliptic curve given by the equation in affine coordinates
$y^{2}=x^{3}+x$. One can check that the Frobenius endomorphism corresponding
to ${\mathbb{F}}_{5}$ satisfies the integral equation $F^{2}-2F+5=0$ on $E$.
We let as before $K=\overline{\mathbb{F}_{p}(t)}$ and we work with the cyclic
group $\Gamma$ spanned by $Q:=(t,t+1,P)\in G(K)$ for some non-torsion point
$P\in E(K)$. Then letting $X=C\times E$, where $C\subset{\mathbb{G}}_{m}^{2}$
is the line $x_{2}=x_{1}+1$, we get that

(2.0.3) $X(K)\cap\Gamma=\left\\{p^{n}Q\colon n\geq 0\right\\}.$

However, one can show that the set from (2.0.3) _cannot_ be split into
finitely many sets of the form:

(2.0.4) $\left\\{\sum_{i=1}^{r}\sum_{j=1}^{s}F^{k_{i,j}n_{j}}(Q_{j})\colon
n_{j}\geq 0\text{ for }j=1,\dots,s\right\\},$

for any given $r,s\in\mathbb{N}$ and any choice of non-negative integers
$k_{i,j}$ and any choice of given points $Q_{j}\in G(K)$. In other words, even
the most complex definition of a groupless $F$-set as in equation (2.0.4)
would still not cover a possible intersection $X(K)\cap\Gamma$.

Now, Examples 2.1 and 2.2 may still suggest that the intersection
$X(K)\cap\Gamma$ could be expressed using more general (groupless) $F$-sets in
which one would allow also the multiplication-by-$p$ map on $G$ playing a
similar role as the Frobenius endomorphism. However, the next example shows
that $X(K)\cap\Gamma$ may have a very complex structure.

######  Example 2.3.

We let $A$ and $B$ be semiabelian varieties defined over a finite subfield
$\mathbb{F}_{q}$ of an algebraically closed field $K$, let $G=A\times B$, and
let $F$ be the corresponding Frobenius endomorphism associated to
$\mathbb{F}_{q}$. We let $h$ be the minimal (monic) polynomial with integer
coefficients for which $h(F)=0$ on $B$. Depending on the abelian part of the
semiabelian variety $B$, the degree $m$ of the polynomial $h$ may be
arbitrarily large.

We let $C\subset B$ be a curve defined over $\mathbb{F}_{q}$ with trivial
stabilizer in $B$ and let $P\in C(K)$ be a non-torsion point; one can even
choose $C$ and $P$ so that $C(K)$ intersects the cyclic $\mathbb{Z}[F]$-module
$\Gamma_{1}$ spanned by $P$ precisely in the orbit of $P$ under the Frobenius
endomorphism $F$. We also let $Q_{1},\dots,Q_{m}\in A(K)$ be linearly
independent points (note that $A(K)\otimes_{\mathbb{Z}}\mathbb{Q}$ is an
infinite dimensional $\mathbb{Q}$-vector space). Then we consider $X:=A\times
C$ and also, consider the group $\Gamma\subset G(K)$ spanned by the points:

$R_{1}:=(Q_{1},P)\text{; }R_{2}:=(Q_{2},F(P))\text{;
}R_{3}:=\left(Q_{3},F^{2}(P)\right)\text{; }\cdots\text{;
}R_{m}:=\left(Q_{m},F^{m-1}(P)\right).$

Then letting $\pi_{2}:G\longrightarrow B$ be the projection of $G=A\times B$
on the second coordinate, we have that $\pi_{2}(\Gamma)=\Gamma_{1}$ because
$\Gamma_{1}$ is spanned by the points

$P\text{, }F(P)\text{, }F^{2}(P),\cdots,F^{m-1}(P)\in B(K)$

since $\Gamma_{1}$ is the cyclic $\mathbb{Z}[F]$-module spanned by $P$ and
$h(F)(P)=0$. So, we can find $m$ sequences
$\left\\{a^{(i)}_{n}\right\\}_{n\geq 0}$ of integers (for $i=0,\dots,m-1$)
such that for any $n\geq 0$, we have that

(2.0.5) $F^{n}(P)=\sum_{i=0}^{m-1}a^{(i)}_{n}\cdot F^{i}(P).$

Equation (2.0.5) yields that $X(K)\cap\Gamma$ is the set:

(2.0.6) $\left\\{\sum_{i=1}^{m}a^{(i-1)}_{n}\cdot R_{i}\colon n\geq
0\right\\}.$

So, due to the potential complexity of the coefficients of the polynomial $h$
satisfied by the Frobenius endomorphism (on the semiabelian variety $B$), the
sequences $\left\\{a^{(i)}_{n}\right\\}_{n\geq 0}$ may be quite complicated.

##  3\. Proofs of our main results

###### Proof of Theorem 1.6..

We proceed by induction on $\dim(X)$; the case when $\dim(X)=0$ is obvious
since then $X(K)\cap\Gamma$ is a finite set and so, each of the groupless
$F$-sets from our intersection are singletons (corresponding to $r=0$ in
equation (1.0.2)).

Clearly, it suffices to assume $X$ is irreducible. Also, we may assume
$X(K)\cap\Gamma$ is Zariski dense in $X$ since otherwise we could replace $X$
by the Zariski closure of $X(K)\cap\Gamma$ and be done by the inductive
hypothesis.

We let $U:={\rm Stab}_{G}(X)$ be the stabilizer of $X$ in $G$. We have two
possibilities depending on whether $U$ is finite, or not.

Case 1. $\dim(U)>0$.

In this case, we let $\pi_{0}:G\longrightarrow G/U$ be the natural group
homomorphism; in particular, $G_{0}:=G/U$ is a semiabelian variety defined
over a finite field since $U$ is defined over a finite extension of
$\mathbb{F}_{q}$. We let $\Gamma_{0}:=\pi_{0}(\Gamma)$ and also, let
$X_{0}:=\pi_{0}(X)$.

Since $\dim(U)>0$, then $\dim(X_{0})<\dim(X)$ and so, by the inductive
hypothesis, we have that $X_{0}(K)\cap\Gamma_{0}$ is a union of finitely many
groupless $F$-sets $B_{i}$ in $\Gamma_{0}$ along with finitely many
generalized $F$-sets $C_{i}$ in $\Gamma_{0}$. We have that

(3.0.1)
$X(K)\cap\Gamma=\pi_{0}^{-1}\left(X_{0}(K)\cap\Gamma_{0}\right)\cap\Gamma=\left(\pi_{0}|_{\Gamma}\right)^{-1}\left(X_{0}(K)\cap\Gamma_{0}\right).$

Clearly, each $(\pi_{0}|_{\Gamma})^{-1}(B_{i})$ is a generalized $F$-set in
$\Gamma$ as in Definition 1.5. Now, each $C_{i}$ is a set of the form

$\left(f|_{\Gamma_{0}}\right)^{-1}(S_{0})=f^{-1}(S_{0})\cap\Gamma_{0},$

where $f:G_{0}\longrightarrow H$ is a surjective group homomorphism of
semiabelian varieties over $K$ in which $\dim(\ker(f))>0$ and $H$ is defined
over a finite extension of $\mathbb{F}_{q}$, and $S_{0}$ is a groupless
$F$-set in $f(\Gamma_{0})\subset H(K)$ as in Definition 1.2. So, using
(3.0.1), along with the fact that

(3.0.2)
$\pi_{0}^{-1}\left(f^{-1}(S_{0})\cap\Gamma_{0}\right)\cap\Gamma=\left(f\circ\pi_{0}\right)^{-1}(S_{0})\cap\Gamma,$

then we obtain that $X(K)\cap\Gamma$ has the desired form as in the conclusion
of Theorem 1.6.

Case 2. $U$ is finite.

In this case, we let $\tilde{\Gamma}$ be the $\mathbb{Z}[F]$-submodule spanned
by $\Gamma$ inside $G(K)$; since $F$ is integral over $\mathbb{Z}$ (inside
${\rm End}(G)$), then $\tilde{\Gamma}$ is also a finitely generated subgroup
of $G(K)$. According to [MS04] (see Theorem 1.4), we have that

(3.0.3)
$X(K)\cap\tilde{\Gamma}=\bigcup_{i=1}^{\ell}\left(S_{i}+\Gamma_{i}\right),$

where each $S_{i}\subset\tilde{\Gamma}$ is a groupless $F$-set as in
Definition 1.2, while each $\Gamma_{i}$ is a subgroup of $\tilde{\Gamma}$.
Now, since

(3.0.4) $X(K)\cap\Gamma=\left(X(K)\cap\tilde{\Gamma}\right)\cap\Gamma,$

it suffices to prove that for each $i=1,\dots,\ell$, there exists a subset
$A_{i}\subseteq X(K)\cap\Gamma$ which is a union of finitely many groupless
$F$-sets in $\Gamma$ along with finitely many generalized $F$-sets in $\Gamma$
such that

(3.0.5) $(S_{i}+\Gamma_{i})\cap\Gamma\subseteq A_{i};$

then combining equations (3.0.3), (3.0.4) and (3.0.5), we would get that

$X(K)\cap\Gamma=\bigcup_{i=1}^{\ell}\left(S_{i}+\Gamma_{i}\right)\cap\Gamma=\bigcup_{i=1}^{\ell}A_{i}$

is indeed a finite union of groupless $F$-sets in $\Gamma$ along with finitely
many generalized $F$-sets in $\Gamma$, as claimed in the conclusion of Theorem
1.6.

In order to prove the existence of a set $A_{i}$ (for each $i=1,\dots,\ell$)
as in equation (3.0.5), we deal with two additional cases.

Case 2a. $\Gamma_{i}$ is an infinite subgroup.

In this case, we let $X_{i}$ be the Zariski closure of $S_{i}+\Gamma_{i}$;
clearly, $X_{i}\subseteq X$. We claim that $X_{i}$ is a proper subvariety of
$X$. Indeed, by construction, $\Gamma_{i}\subseteq{\rm Stab}_{G}(X_{i})$ and
since $\Gamma_{i}$ is infinite, then we cannot have that $X_{i}=X$ because
${\rm Stab}_{G}(X)$ is finite. So, $\dim(X_{i})<\dim(X)$ and by our inductive
hypothesis, we have that that $A_{i}:=X_{i}(K)\cap\Gamma$ satisfies the
conclusion from Theorem 1.6; therefore

$\left(S_{i}+\Gamma_{i}\right)\cap\Gamma\subseteq A_{i},$

where $A_{i}$ is a union of finitely many groupless $F$-sets along with
finitely many generalized $F$-sets, as desired for (3.0.5).

Case 2b. $\Gamma_{i}$ is finite.

In this case, letting $s:=\\#\Gamma_{i}$, we have that $S_{i}+\Gamma_{i}$ is a
union of $s$ groupless $F$-sets as in Definition 1.2. Now, [Ghi08, Theorem
3.1] shows that the intersection of a groupless $F$-set with a finitely
generated group is a itself a finite union of groupless $F$-sets; so,

$A_{i}:=(S_{i}+\Gamma_{i})\cap\Gamma$

is a finite union of groupless $F$-sets in $\Gamma$ as desired for (3.0.5).

This concludes our proof of Theorem 1.6. ∎

Theorem 1.7 is an immediate corollary of our next two results which provide a
more precise form of the intersection between a subvariety $X$ of $G$ with a
finitely generated subgroup of $G(K)$ when $X$ is a curve, respectively when
$G$ is a simple semiabelian variety.

######  Proposition 3.1.

Let $G$ be a semiabelian variety defined over a finite subfield of an
algebraically closed field $K$, let $\Gamma\subset G(K)$ be a finitely
generated subgroup, and let $X\subseteq G$ be an irreducible curve.

  * (i)

If $\dim\left({\rm Stab}_{G}(X)\right)>0$, then $X(K)\cap\Gamma$ is a coset of
a subgroup of $\Gamma$.

  * (ii)

If ${\rm Stab}_{G}(X)$ is finite, then $X(K)\cap\Gamma$ is a finite union of
groupless $F$-sets.

###### Proof.

The proof of part (i) is immediate since then $X=\gamma+G_{1}$, for some point
$\gamma\in G(K)$ and some $1$-dimensional connected algebraic subgroup
$G_{1}\subseteq G$. So, then the intersection $X(K)\cap\Gamma$ is simply a
coset of the subgroup $G_{1}(K)\cap\Gamma$ of $\Gamma$.

Now, we assume ${\rm Stab}_{G}(X)$ is finite. Then we let $\tilde{\Gamma}$ be
the $\mathbb{Z}[F]$-submodule of $G(K)$ spanned by $\Gamma$; by Theorem 1.4,
we have that $\tilde{\Gamma}$ intersects $X(K)$ in a finite union of $F$-sets
$S_{i}$ in $\tilde{\Gamma}$. But then at the expense of replacing each $S_{i}$
with finitely many other $F$-sets, we may assume that each such $F$-set is
groupless (see also the proof of Case 2b in Theorem 1.6). Finally, another
application of [Ghi08, Theorem 3.1] yields that each $S_{i}\cap\Gamma$ is a
finite union of groupless $F$-sets in $\Gamma$, as desired. ∎

######  Proposition 3.2.

Let $G$ be a simple semiabelian variety defined over a finite subfield of an
algebraically closed field $K$, let $\Gamma\subset G(K)$ be a finitely
generated group, and let $X\subset G$ be a proper subvariety. Then
$X(K)\cap\Gamma$ is a finite union of groupless $F$-sets in $\Gamma$.

###### Proof.

First of all, we note that if $\Gamma$ is a finite group, then clearly
$X(K)\cap\Gamma$ is a finite set and thus a finite union of groupless
$F$-sets, as desired.

So, from now on, we assume that $\Gamma$ is infinite. According to our Theorem
1.6, we know that $X(K)\cap\Gamma$ is a finite union of groupless $F$-sets in
$\Gamma$ along with (possibly) finitely many generalized $F$-sets in $\Gamma$.
Now, for any such generalized $F$-set in $\Gamma$ (call it $S$), we have that

$S=\left(\pi|_{\Gamma}\right)^{-1}(S_{0}),$

where $\pi:G\longrightarrow H$ is a surjective group homomorphism of
semiabelian varieties defined over a finite subfield of $K$, $S_{0}$ is a
groupless $F$-set in $\pi(\Gamma)\subset H(K)$ and moreover,
$\dim(\ker(\pi))>0$. But since $G$ is a simple semiabelian variety, this means
that $\ker(\pi)=G$, i.e., $H$ is the trivial group variety and so, $S$ would
have to be the entire subgroup $\Gamma$. But then its Zariski closure in $G$
is an infinite algebraic subgroup of $G$ (note that $\Gamma$ is assumed now to
be infinite) and so, once again because $G$ is simple, we would conclude that
$\Gamma$ is Zariski dense in $G$. But then because $S=\Gamma$ is contained in
$X$, we would have that $X=G$, contradicting the fact that $X$ is a proper
subvariety of $G$. Therefore, we have no generalized $F$-sets in $\Gamma$
contained in the intersection $X(K)\cap\Gamma$.

This concludes our proof for Proposition 3.2. ∎

Theorem 1.10 follows easily from our Theorem 1.6 combined with Theorem 1.1.

###### Proof of Theorem 1.10..

Clearly, as argued in the proof of Theorem 1.6, it suffices to prove Theorem
1.10 assuming that $X$ is an irreducible subvariety of $G$ and
$X(K)\cap\Gamma$ is Zariski dense in $X$. Then Theorem 1.1 yields that

$X=\gamma+\pi^{-1}(X_{0}),$

where $\pi:G_{0}\longrightarrow H$ is a surjective group homomorphism of
semiabelian varieties, while $G_{0}$ is a semiabelian subvariety of $G$ and
$\gamma\in G(K)$; moreover, $H$ and the subvariety $X_{0}\subseteq H$ are
defined over over a finite subfield ${\mathbb{F}}_{q}\subset K$. Then for
$x\in G(K)$, we have $x\in X(K)$ if and only if “$x-\gamma\in G_{0}(K)$ and
$\pi(x-\gamma)\in X_{0}(K)$”. We denote $\Gamma_{0}=G_{0}(K)\cap\Gamma$.

Pick $x_{0}\in X(K)\cap\Gamma$. Let $g_{0}=x_{0}-\gamma\in G_{0}(K)$. We have
$x_{0}+\Gamma_{0}=(\gamma+G_{0}(K))\cap\Gamma$. As a result, for any
$x\in\Gamma$, we have $x-\gamma\in G_{0}(K)$ if and only if there exists
$\gamma_{0}\in\Gamma_{0}$ such that $x=x_{0}+\gamma_{0}$. Thus
$x-\gamma=g_{0}+\gamma_{0}$ and so, $\pi(x-\gamma)\in X_{0}(K)$ yields
$\pi(\gamma_{0})\in-\pi(g_{0})+X_{0}(K)$.

Let $X_{0}^{\prime}=-\pi(g_{0})+X_{0}$ which is a subvariety of $H$. The
discussion above implies that
$X(K)\cap\Gamma=x_{0}+(\pi|_{\Gamma_{0}})^{-1}(X_{0}^{\prime}(K)\cap\pi(\Gamma_{0}))$.
So, considering the subvariety $X_{0}^{\prime}\subseteq H$, along with the
finitely generated subgroup $\pi(\Gamma_{0})$ of $H(K)$, then we apply Theorem
1.6 to conclude that the intersection $X_{0}^{\prime}(K)\cap\pi(\Gamma_{0})$
is a finite union of generalized $F$-sets in $\pi(\Gamma_{0})$ along with
finitely many groupless $F$-sets in $\pi(\Gamma_{0})$. But whether $S$ is a
generalized $F$-set in $\pi(\Gamma_{0})$ or a groupless $F$-set in
$\pi(\Gamma_{0})$, $x_{0}+(\pi|_{\Gamma_{0}})^{-1}(S)$ will always be a
pseudo-generalized $F$-set in $\Gamma$ (see also Remark 1.9). This shows that
$X(K)\cap\Gamma$ is a finite union of pseudo-generalized $F$-sets in $\Gamma$,
as desired. ∎

Acknowledgement. The second author is very grateful to his advisor Junyi Xie
who introduced this topic to him.

The first author is supported by a Discovery NSERC grant, while the second
author is supported by an NSFC Grant (No. 12271007).

## References

  * [Fal91] G. Faltings, _The general case of S. Lang’s conjecture_. Barsotti Symposium in Algebraic Geometry (Abano Terme, 1991), 175-182, Perspect. Math., 15, Academic Press, San Diego, CA, 1994.
  * [Ghi08] D. Ghioca, _The isotrivial case in the Mordell-Lang theorem_ , Trans. Amer. Math. Soc. 360 (2008), no. 7, 3839–3856.
  * [Hru96] E. Hrushovski, _The Mordell-Lang conjecture for function fields_. J. Amer. Math. Soc. 9 (1996), no. 3, 667–690.
  * [Lau84] M. Laurent, _Équations diophantiennes exponentielles_ , Invent. Math. 78 (1984), 299–327.
  * [MS02] R. Moosa and T. Scanlon, _The Mordell-Lang conjecture in positive characteristic revisited_ , Model theory and applications, 273–296, Quad. Mat., 11, Aracne, Rome, 2002.
  * [MS04] R. Moosa and T. Scanlon, _F-structures and integral points on semiabelian varieties over finite fields_ , Amer. J. Math. 126 (2004), 473–522.
  * [Voj96] P. Vojta, _Integral points on subvarieties of semiabelian varieties. I_ , Invent. Math. 126 (1996), no. 1, 133–181.