# Multi-segment preserving sampling
for deep manifold sampler

Daniel Berenberg Prescient Design, Genentech Department of Computer Science,
Courant Institute of Mathematical Sciences, New York University  Jae Hyeon Lee
Prescient Design, Genentech Simon Kelow Prescient Design, Genentech Ji Won
Park Prescient Design, Genentech Andrew Watkins Prescient Design, Genentech
Vladimir Gligorijević Prescient Design, Genentech Richard Bonneau Prescient
Design, Genentech Stephen Ra Prescient Design, Genentech Kyunghyun Cho
Prescient Design, Genentech Department of Computer Science, Courant Institute
of Mathematical Sciences, New York University  Center for Data Science, New
York University  CIFAR Fellow

###### Abstract

Deep generative modeling for biological sequences presents a unique challenge
in reconciling the bias-variance trade-off between explicit biological insight
and model flexibility. The deep manifold sampler (Gligorijević et al., 2021)
was recently proposed as a means to iteratively sample variable-length protein
sequences. Sampling was done by exploiting the gradients from a function
predictor trained on top of the manifold sampler. In this work, we introduce
an alternative approach to guided sampling that enables the direct inclusion
of domain-specific knowledge by designating preserved and non-preserved
segments along the input sequence, thereby restricting variation to only
select regions. We call this method “multi-segment preserving sampling" and
present its effectiveness in the context of antibody design. We train two
models: a deep manifold sampler and a GPT-2 language model on nearly six
million heavy chain sequences annotated with the IGHV1-18 gene. During
sampling, we restrict variation to only the complementarity-determining region
3 (CDR3) of the input. We obtain log probability scores from a GPT-2 model for
each sampled CDR3 and demonstrate that multi-segment preserving sampling
generates reasonable designs while maintaining the desired, preserved regions.

##  1 Introduction

Protein sequence families, particularly antibodies, have both well-conserved
and variable regions. In antibodies, the heavy and light chain sequences
consist of highly conserved regions known as the framework as well as an array
of distinct hypervariable loops, known as complementarity-determining regions
(CDRs) (Reczko et al., 1995). Despite the intrinsic variability of CDRs,
conditional variation is often conferred by the gene locus admitting the
protein (Kelow et al., 2020). Much of an antibody’s antigen-binding affinity
is owed to the CDRs, while the framework remains fixed or requires minimal
change (Kuroda et al., 2012). For in silico modeling, integrating these
established aspects of structure and binding can drive the development of
better in situ antibody therapeutic design (Chiu et al., 2019). While work in
protein language modeling suggests that models can learn these evolutionary
conservation rules (Rives et al., 2021; Elnaggar et al., 2021; Madani et al.,
2020), it is an open challenge as to how to explicitly incorporate prior
insight at test-time generation, such as sequence-level annotations (Dunbar
and Deane, 2015), to restrict sampling in certain segments.

The deep manifold sampler was recently proposed as an effective method to
sample novel sequences by iterative, optionally gradient-guided steps, of
sequence denoising (Gligorijević et al., 2021). Empirically, gradient-based
guided sampling was shown to selectively encourage changes in functional
sites, implicitly leaving non-functional regions unperturbed. In this work, we
propose an alternative to the gradient-based guided design procedure in which
predefined regions of a sequence are explicitly preserved, leaving sampling to
take place in a priori known notable sequence regions. We conduct an
experiment on antibody sequences to demonstrate the deep manifold sampler’s
ability to focus sampling on a subset of sequence positions. We do so by
deliberately corrupting select regions of antibody sequences, that correspond
to CDRs, and evaluating the length distribution and composition of sampled
CDRs.

##  2 Background: the Deep Manifold Sampler

The deep manifold sampler (Gligorijević et al., 2021) is a denoising
autoencoder (DAE) specialized for handling variable-length sequences. As with
a typical DAE (Vincent et al., 2008), the deep manifold sampler consists of
three modules; a corruption process $C(\tilde{x}|x)$, an encoder $F$ and a
decoder $G$. Unlike the usual DAE however, the deep manifold sampler has an
extra module that determines the change in the length, which we call the
“length conversion” (Shu et al., 2020).

The deep manifold sampler assumes as input a sequence of discrete tokens,
$x=(x_{1},x_{2},\ldots,x_{|x|})$, where each token $x_{t}$ is an item from a
finite vocabulary $V$ of unique words or subwords. In the case of protein
sequence modeling, $V$ consists of all unique amino acids. The sequence $x$ is
corrupted with the corruption process $C$, resulting in a noisy input sequence
$\tilde{x}\sim C(\tilde{x}|x)$. This corruption process can be arbitrary as
long as it is largely local and unstructured. It may even alter the length of
the sequence, $|x|\neq|\tilde{x}|$.

The encoder $F$ turns the corrupted sequence $\tilde{x}$ into a set of hidden
vectors, $h=(h_{1},h_{2},\ldots,h_{|\tilde{x}|})$, where
$h_{t}\in\mathbb{R}^{d}$. The encoder can be implemented using any of the
widely-used deep architectures, such as transformers (Vaswani et al., 2017),
convolutional networks (Gehring et al., 2017) and recurrent networks
(Sutskever et al., 2014; Bahdanau et al., 2014). In this work, we follow the
original deep manifold sampler’s encoder, which was implemented as a
transformer.

The hidden vectors are pooled to form a single-vector representation:

$\displaystyle\bar{h}=\frac{1}{|\tilde{x}|}\sum_{t=1}^{|\tilde{x}|}h_{t}.$

This pooled representation is used by the length conversion to predict the
change in the length. At training time, this length change predictor is
trained to output $\Delta l^{*}=|\tilde{x}|-|x|$. When we sample sequences
from the deep manifold sampler after training, we use the predicted change
$\Delta l$ to adjust the size of the hidden vector set. The adjusted hidden
vector set consists of $|\tilde{x}|+\Delta l$ hidden vectors,
$z=(z_{1},\ldots,z_{|\tilde{x}|+\Delta l})$, where each vector is a weighted
sum of the previous hidden vectors $h_{1},h_{2},\cdots,h_{|\tilde{x}|}$. To
wit, we define

$\displaystyle
z_{t}=\sum_{t^{\prime}=1}^{|\tilde{x}|}\omega_{t,t^{\prime}}h_{t^{\prime}}$
(1)

with the position-based softmax weights $w_{t,t^{\prime}}$ preferring
$h_{t^{\prime}}$ closest to the length-scaled position
$|\tilde{x}|/(|\tilde{x}|+\Delta l)t$, as follows:

$\displaystyle w_{t,t^{\prime}}$
$\displaystyle=\frac{\exp(q_{t,t^{\prime}})}{\sum_{t^{\prime\prime}=1}^{|\tilde{x}|}\exp(q_{t,t^{\prime\prime}})}$
(2) $\displaystyle q_{t,t^{\prime}}$
$\displaystyle\propto\frac{-1}{2\sigma^{2}}\left(t^{\prime}-\frac{|\tilde{x}|}{|\tilde{x}|+\Delta
l}t\right)^{2}.$ (3)

In Eq. (3), $\sigma$ is a learned smoothing parameter. The decoder $G$ then
takes this transformed hidden vector sequence $z$ and outputs a corresponding
sequence of logit vectors,
$\tilde{y}=(\tilde{y}_{1},\ldots,\tilde{y}_{|\tilde{x}|+\Delta l})$, where
$\tilde{y}_{t}\in\mathbb{R}^{|V|}$. These logits are turned into probability
distributions over the vocabulary $V$ in many different ways. The original
deep manifold sampler implements a non-autoregressive approach (Gu et al.,
2017; Lee et al., 2018), where each logit is independently turned into a
distribution:

$p(y_{t}=v|\tilde{x},\Delta
l)=\frac{\exp\left(\tilde{y}_{t}^{v}+b^{v}\right)}{\sum_{v^{\prime}\in
V}\exp\left(\tilde{y}_{t}^{v^{\prime}}+b^{v^{\prime}}\right)},$ (4)

where $b^{v}$ is a bias for token $v$.

It is, however, also possible to use these logits together with a more
powerful output module, such as a conditional random field (CRF; Lafferty et
al. 2001), as was recently done in (Yi et al., 2021), and autoregressive
language models (Mikolov et al., 2010). For experiments in this paper, we use
a variant of the deep manifold sampler with a CRF at the end of the decoder.

At training time, we minimize the negative log-probability of the original
sequence $x$ given the corrupted version $\tilde{x}$ and the known $\Delta
l^{*}$ to train the encoder and decoder, while minimizing the negative log-
probability of $\Delta l^{*}$ to train the length change predictor. We
parameterize the latter as a classifier. Once training is done, we can draw a
series of samples from the deep manifold sampler by repeating the process of
corruption, length conversion, and reconstruction.

While the original deep manifold sampler has an additional function predictor
that can be used to guide the sampling procedure, we omit that here, as this
is optional and can be replaced with another computational oracle without
altering the sampling procedure that is the focus of this paper.

##  3 Multi-Segment Preserving Sampling

The deep manifold sampler was originally proposed in the context of protein
design in Gligorijević et al. (2021). Within this setting, we often consider
biological, chemical, and physical knowledge in order to impose constraints
that narrow down a large, combinatorial search space (Street and Mayo, 1999;
Woolfson, 2021). The deep manifold sampler, on the other hand, stays true to
the key principle of deep learning, that is, end-to-end learning, which makes
it challenging to explicitly incorporate this knowledge into both learning and
sampling. In this paper, we take one step towards enabling this into the
sampling procedure of the deep manifold sampler. We assume the availability of
knowledge in which segments of an original sequence, from which sampling
starts, must be preserved in order to maintain a set of desirable properties.
For example, in the case of antibody engineering, it may be desirable to only
alter CDR loops while leaving all framework residues intact (Kuroda et al.,
2012).

Figure 1: Multi-segment preserving sampling. (A) Non-preserved segments
$\bar{s}$ are corrupted using corruption process $C$, for which a given token
(yellow) may be randomly perturbed (blue). This is encoded into the hidden
vector set $h$. Length change predictor $p_{\theta}(\Delta l|\bar{h})$ outputs
$\Delta l$, which is distributed across $\bar{s}$ (Eq. 5). (B) Segment-
preserving sampling follows similar operations on preserved segment $s$ (red)
with notable differences. Corruption $C$ yields an unaltered sequence
$\tilde{x}$ and we carry over hidden vector $h_{t}$ of a token within
preserved segment $\tilde{s}$ with strength $\beta$ (Eq. 6).

Let $x=(x_{1},x_{2},\ldots,x_{|x|})$ be the initial sequence from which we run
the deep manifold sampler to draw a series of samples over the sequence
manifold. Instead of unconstrained sampling, we consider a scenario in which
we are provided with a set of non-overlapping segments of the sequence that
must be preserved in-order by their starting and ending indices (inclusive):

$\displaystyle s=((i_{1},j_{1}),\ldots,(i_{K},j_{K}))$

subject to $i_{1}>0$, $i_{k}\leq j_{k}$ for all $k$, $j_{k}<i_{k+1}$ for all
$k$, and $j_{K}<|x|-1$. We refer to this set as a preserved-segment set.
Likewise, we can imagine the complement segment set $\bar{s}$ that contains
all the segments that are between the to-be-preserved segments in $s$:

$\displaystyle\bar{s}=((0,i_{1}-1),(j_{1}+1,i_{2}-1),\ldots,(j_{K}+1,|x|-1)).$

In order to preserve these segments while altering the remaining parts of the
sequence, including their respective lengths, we make a series of
modifications to the sampling procedure of the deep manifold sampler. First,
we alter the corruption process $C$ such that it does not corrupt the
preserved segments. For instance, if the corruption process randomly adds or
removes tokens, this is only done to the segments in the complement set
$\bar{s}$ but not to those in $s$. The corrupted sequence $\tilde{x}$ contains
an indexing change due to insertions and deletions, so the description of the
segment set $s$ must be updated to reflect this — we denote the preserved
segment set of $\tilde{x}$ by $\tilde{s}$.

The encoder still encodes $\tilde{x}$ into the hidden vector set $h$, as
described in Section 2. While the length change prediction steps also stay the
same, the returned length change $\Delta l$ needs to be distributed across the
non-preserved segments in order to avoid altering the length of any preserved
segment in $\tilde{s}$. We do so proportional to the original lengths of the
non-preserved segments. Concretely, we add to the length of each non-preserved
segment $(\tilde{j}_{k}+1,\tilde{i}_{k+1}-1)$:

$\left\lceil\frac{(\tilde{i}_{k+1}-\tilde{j}_{k}+1)}{\sum_{k=-1}^{K}(\tilde{i}_{k+1}-\tilde{j}_{k}+1)}\Delta
l\right\rceil,$ (5)

where $\tilde{j}_{0}=0$ and $\tilde{i}_{K+1}=|\tilde{x}|-1$.

After distributing the length difference among the non-preserved segments, we
can now construct the index map $o$ that tells us which segment in the new
sequence corresponds to each of the preserved segment in $\tilde{x}$. In other
words,
$y_{o(\tilde{i}_{k}):o(\tilde{j}_{k})}=\tilde{x}_{\tilde{i}_{k}:\tilde{j}_{k}}$.
Let us use $o(\tilde{s})$ to denote the preserved-segment set derived from $s$
and the length distribution above.

The actual length conversion happens just like before, as in Eq. (1). We
however add an extra step after the length conversion in order to give the
decoder a hint about preserved segments and their contents. This is done by
carrying over the original hidden vector $h_{t}$ of a token within a preserved
segment:

$z_{t}\leftarrow\begin{cases}(1-\beta)z_{t}+\beta h_{o^{-1}(t)},&\text{if
}t\in o(\tilde{s})\\\ z_{t},&\text{if }t\notin o(\tilde{s})\\\ \end{cases}$
(6)

$o^{-1}$ is the inverse index map, and $\beta\in[0,1]$ is the strength of
carry-over.

The decoder turns this length-converted and segment-preserving hidden sequence
$z$ into a sequence of logit vectors $\tilde{y}$, just like the original
sampling procedure. We then modify the logit vector corresponding to a token
with a preserved segment to force the sampled outcome to preserve the token
identity:

$\tilde{y}_{t}^{v}\leftarrow\begin{cases}\infty,&\text{ if }t\in
o(\tilde{s})\text{ and }v=\tilde{x}_{o^{-1}(t)}\\\ -\infty,&\text{ if }t\in
o(\tilde{s})\text{ and }v\neq\tilde{x}_{o^{-1}(t)}\\\
\tilde{y}_{t}^{v},&\text{ if }t\notin o(\tilde{s})\end{cases}$ (7)

In the case of non-autoregressive modeling, this would result in a Categorical
distribution for a preserved token to assign the entire probability mass
($=1$) to the original token identity. If a CRF is used at the end, this would
prevent any sequence that violates preservation from being decoded out with
non-zero probability.

We can repeat this sampling step with the newly sampled sequence and the
corresponding preserved-segment set. This allows us to iteratively draw a
series of samples while preserving the segments from the original sequence,
designated by the preserved-segment set $s$. Because this iterative sampling
procedure preserves multiple segments and their contents, we refer to this
procedure as multi-segment preserving sampling (Figure 1).

##  4 Related Work

There are two alternative sequence-modeling paradigms that are closely related
to the deep manifold sampler. We briefly describe each of them here in the
context of whether and how multi-segment preservation can be implemented.

###  4.1 Masked Language Models

A masked language model is a special case of a DAE, similar to the deep
manifold sampler (Devlin et al., 2018; Liu et al., 2019). A corruption process
$C$ in a masked language model is designed to apply one of three types of
corruption: (1) replace a token with a special $\left<\text{mask}\right>$
token, (2) replace a token with another, randomly-selected token, and (3) no
alteration, to a random subset of the tokens within each sequence. All of
these types do not alter the length of the sequence. The masked language model
then reconstructs only the corrupted subset, rather than the full sequence as
in the deep manifold sampler.

Masked language modeling was originally motivated as a way to pretrain a
large-scale neural network rather than as a generative model from which to
draw sequences. While Wang and Cho (2019) and Goyal et al. (2021) demonstrated
that masked language models can yield well-formed sequences, they are neither
as popular nor applicable as as other models — such as autoregressive language
models or the deep manifold sampler — for sequence generation because they do
not have a mechanism to automatically model the length distribution.

With the caveat that the length of a sequence cannot be altered at sampling
time, a masked language model can be used for multi-segment preserving
sampling. This can still be useful as a “plug-and-play" proposal distribution
for a number of downstream tasks including rational design and directed
evolution of proteins (Woolfson, 2021; Arnold, 1998; Yang et al., 2019; Meier
et al., 2021). However, this approach is limited compared to the proposed
strategy of multi-segment preserving sampling with the deep manifold sampler,
as our proposal is able to both dynamically adapt the length of a sequence and
preserve segments.

###  4.2 Denoising Sequence-to-Sequence Models

A denoising sequence-to-sequence (Seq2Seq) model, where the decoder is
autoregressive, has been studied previously in the context of natural language
processing (Hill et al., 2016; Lewis et al., 2019). Unlike masked language
models, and similar to the deep manifold sampler, the denoising Seq2Seq model
can adaptively change the length of a sequence. However, unlike the deep
manifold sampler, there is less control over the direct manipulation of the
intermediate hidden vectors, as some of the dependencies between the tokens in
the output sequence are captured directly by the decoder without relying on
the intermediate representation between the encoder and decoder. It is however
an interesting future direction to compare the denoising Seq2Seq model against
the deep manifold sampler.

With respect to multi-segment preservation, denoising Seq2Seq models do not
readily admit such a sampling strategy. This is due to the inherent
intractability in decoding from an autoregressive model with unbounded
context. This intractability is often addressed by approximate decoding, such
as beam search, which is known to have suboptimal behaviors despite its
successful and wide use (Welleck et al., 2020, 2019). Several studies have
proposed to extend beam search to incorporate such constraints (Hokamp and
Liu, 2017; Post and Vilar, 2018). Unfortunately most of these approaches incur
great computational cost, as their computational complexity grows often
linearly with respect to the number of preserved segments — or the beam size
must grow accordingly — because the underlying algorithm decodes in a greedy
left-to-right fashion with a limited hypothesis set (beam). While it is
possible to modify a denoising Seq2Seq model to admit multi-segment preserving
sampling by letting the decoder only reconstruct non-preserved segments, this
is out of scope for this paper.

##  5 Experiments

The proposed algorithm for multi-segment preserving sampling is designed to
completely preserve designated segments. Here, we demonstrate a potential
application in antibody design enabled by our algorithm coupled with the deep
manifold sampler. Antibodies with a particular V-gene have fixed lengths in
the framework as well as in the CDR1 and CDR2 regions. As a result, antibodies
display most of their diversity in length and amino acid composition in CDR3
(Glanville et al., 2009). To demonstrate the effectiveness of our approach and
restricted variation of the preserved segments, we select all unique human
antibody sequences with the IGHV1-18 gene from the Observed Antibody Space
(OAS) database (Olsen et al., 2022) for multi-segment preserving sampling.
Using a deep manifold sampler, we sample exclusively from the CDR3, while
preserving other regions, and show the length and log-probability (GPT-2)
distributions of the generated sequences qualitatively coincide with that of
the test data. Table 1 illustrates examples of sampled CDR3 regions under
different settings of carry-over strength $\beta$.

$\beta$ | Aligned CDR3 sequence | Edit distance
---|---|---
N/A (original) | ARDPEWDPF-QANY-YYYGMDV | 0
0.0 | ARDPEWDPF-QAN--YYYGMDV | 3
0.1 | ARDPEWDPFFQANYNYYYGMVD | 3
0.5 | KRDPEWDRF-QAPY-YTVGMDV | 5
0.9 | ARGPECDPH-QAV-DIYYGMDV | 6
Table 1: Example outputs of multi-segment preserving sampling when restricting
variation to the CDR3 region under different settings of $\beta$. Display is
restricted to the sampled region, the rest is preserved by construction.

###  5.1 Training details

We obtained 5,971,552 unique human antibody heavy chain sequences with the
IGHV1-18 gene from the OAS database, with 2,000 and 10,000 sequences set aside
for validation and test sets respectively and the remaining used for
training.111 Only sequences with ”Redundancy $>$ 1” were retained.  We trained
a deep manifold sampler on the training set with a constant learning rate of
$10^{-4}$ for 60K mini-batch steps with the batch size of 128. The model
consisted of a two-layer transformer encoder and decoder, each with 8 heads
and the total embedding dimension of 256 and feed-forward layer dimension of
1024. The last layer consists of a CRF for final sequence generation. The rest
of the training procedure was the same as described in Gligorijević et al.
(2021).

In addition, we also trained an autoregressive GPT-2 model using HuggingFace
Transformers library v4.16.2 (Wolf et al., 2020) on the same training set in
order to demonstrate that the sampler-generated sequences capture the amino-
acid token distribution observed in the training set. The model consisted of 6
attention layers with 8 heads and a total embedding dimension of 512 and was
trained with a constant learning rate of $4\times 10^{-4}$ for 25K mini-batch
steps with batch size of 1024. The other parameters were set to the default
values provided by the package.

###  5.2 Sampling details and results

For each sequence in the test set, we applied multi-segment preserving
sampling for one iteration, preserving all non-CDR3 regions with four
different $\beta$ values of 0, 0.1, 0.5, and 0.9.222 The region annotation was
obtained from the OAS data unit files.

Figure 2 and Figure 3 show the length and log-probability (GPT-2)
distributions of the generated sequences with changes in CDR3 and the test
data across all selected $\beta$ values. The CDR3 length distribution of the
generated samples matches the natural sequence length distribution for each
value of $\beta$. The GPT-2 log-probability distribution of the samples has
lower overall mean compared to that of the test distribution but is still
within the same range, indicating that the samples are plausible. Both
distributions vary only slightly with different values of $\beta$. These two
results show the effectiveness of the sampling strategy for generating diverse
antibody sequences, restricted to user-defined regions.

In Figure 4, we illustrate the distribution of the number of edits in the
generated sequences relative to the input seed sequences, including
substitutions, insertions, and deletions. The distributional mean increases
slightly with higher values of $\beta$. For future work, we plan on a more
systematic understanding of the effects of carry-over strength $\beta$ on
sample quality and diversity.

Figure 2: The normalized distribution of the CDR3 lengths of the deep manifold
sampler-generated sequences (“Samples") and the test set sequences (“Training
(OAS)") with four different $\beta$ parameters. From Top Left, Clockwise:
Samples were generated with $\beta=0,0.1,0.9$, and $0.5$. Figure 3: The
normalized distribution of the GPT-2 scores of the deep manifold sampler-
generated sequences (“Samples") and the test set sequences (“Training (OAS)")
with four different $\beta$ parameters. From Top Left, Clockwise: Samples were
generated with $\beta=0,0.1,0.9$, and $0.5$. Figure 4: The distribution of
edit distances between generated samples and their seed sequences with varying
settings of $\beta$ (0, 0.1, 0.5, and 0.9).

##  6 Conclusion

We have proposed a sampling procedure for the deep manifold sampler that
explicitly preserves designated segments of the input sequence, allowing
variation to occur only in non-preserved regions. We find that this approach,
multi-segment preserving sampling, is applicable to a number of design
problems in the life sciences where we often want to use prior knowledge made
available in these domains. With biological sequence design for example, we
want to sample new, diverse designs that avoid perturbing well-conserved
regions of the input. In this way, we demonstrate the utility of multi-segment
preserving sampling by restricting sampling to the CDR3 regions of a
collection of antibody heavy chains with the IGHV1-18 gene and validating the
resulting CDR3 designs against a separate GPT-2 model. As shown in Figure 3,
the sampled CDR3 regions admit high log-probability scores by the GPT-2 model,
providing evidence that the samples are plausible. Additionally, the CDR3
length distribution of the samples traces the observed length distribution in
the training set, suggesting that the model adequately captures the
variability in non-preserved segment lengths, despite the lack of explicit
provision during training. In future work, we will extend our exploration on
the effect of the carry-over strength $\beta$ in terms of sample quality as
well as its usage in conjunction with the function predictor for guided
sampling proposed in Gligorijević et al. (2021).

## References

  * Arnold [1998] Frances H Arnold.  Design by directed evolution.  _Accounts of chemical research_ , 31(3):125–131, 1998.
  * Bahdanau et al. [2014] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ , 2014.
  * Chiu et al. [2019] Mark L Chiu, Dennis R Goulet, Alexey Teplyakov, and Gary L Gilliland.  Antibody structure and function: the basis for engineering therapeutics.  _Antibodies_ , 8(4):55, 2019.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Dunbar and Deane [2015] James Dunbar and Charlotte M. Deane.  ANARCI: antigen receptor numbering and receptor classification.  _Bioinformatics_ , 32(2):298–300, 09 2015.  ISSN 1367-4803.  doi: 10.1093/bioinformatics/btv552.  URL https://doi.org/10.1093/bioinformatics/btv552.
  * Elnaggar et al. [2021] Ahmed Elnaggar, Michael Heinzinger, Christian Dallago, Ghalia Rihawi, Yu Wang, Llion Jones, Tom Gibbs, Tamas Feher, Christoph Angerer, Martin Steinegger, Debsindhu Bhowmik, and Burkhard Rost.  Prottrans: Towards cracking the language of life’s code through self-supervised deep learning and high performance computing, 2021.
  * Gehring et al. [2017] Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin.  Convolutional sequence to sequence learning.  In _International Conference on Machine Learning_ , pages 1243–1252. PMLR, 2017.
  * Glanville et al. [2009] Jacob Glanville, Wenwu Zhai, Jan Berka, Dilduz Telman, Gabriella Huerta, Gautam R Mehta, Irene Ni, Li Mei, Purnima D Sundar, Giles MR Day, et al.  Precise determination of the diversity of a combinatorial antibody library gives insight into the human immunoglobulin repertoire.  _Proceedings of the National Academy of Sciences_ , 106(48):20216–20221, 2009.
  * Gligorijević et al. [2021] Vladimir Gligorijević, Daniel Berenberg, Stephen Ra, Andrew Watkins, Simon Kelow, Kyunghyun Cho, and Richard Bonneau.  Function-guided protein design by deep manifold sampling.  _bioRxiv_ , 2021.
  * Goyal et al. [2021] Kartik Goyal, Chris Dyer, and Taylor Berg-Kirkpatrick.  Exposing the implicit energy networks behind masked language models via metropolis–hastings.  _arXiv preprint arXiv:2106.02736_ , 2021.
  * Gu et al. [2017] Jiatao Gu, James Bradbury, Caiming Xiong, Victor OK Li, and Richard Socher.  Non-autoregressive neural machine translation.  _arXiv preprint arXiv:1711.02281_ , 2017.
  * Hill et al. [2016] Felix Hill, Kyunghyun Cho, and Anna Korhonen.  Learning distributed representations of sentences from unlabelled data.  _arXiv preprint arXiv:1602.03483_ , 2016.
  * Hokamp and Liu [2017] Chris Hokamp and Qun Liu.  Lexically constrained decoding for sequence generation using grid beam search.  _arXiv preprint arXiv:1704.07138_ , 2017.
  * Kelow et al. [2020] Simon P. Kelow, Jared Adolf-Bryfogle, and Roland L. Dunbrack.  Hiding in plain sight: structure and sequence analysis reveals the importance of the antibody de loop for antibody-antigen binding.  _mAbs_ , 12(1):1840005, 2020.  doi: 10.1080/19420862.2020.1840005.  URL https://doi.org/10.1080/19420862.2020.1840005.  PMID: 33180672.
  * Kuroda et al. [2012] Daisuke Kuroda, Hiroki Shirai, Matthew P Jacobson, and Haruki Nakamura.  Computer-aided antibody design.  _Protein engineering, design & selection_, 25(10):507–522, 2012.
  * Lafferty et al. [2001] John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira.  Conditional random fields: Probabilistic models for segmenting and labeling sequence data.  In _Proceedings of the Eighteenth International Conference on Machine Learning_ , ICML ’01, page 282–289, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.  ISBN 1558607781.
  * Lee et al. [2018] Jason Lee, Elman Mansimov, and Kyunghyun Cho.  Deterministic non-autoregressive neural sequence modeling by iterative refinement.  _arXiv preprint arXiv:1802.06901_ , 2018.
  * Lewis et al. [2019] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_ , 2019.
  * Liu et al. [2019] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ , 2019.
  * Madani et al. [2020] Ali Madani, Bryan McCann, Nikhil Naik, Nitish Shirish Keskar, Namrata Anand, Raphael R. Eguchi, Po-Ssu Huang, and Richard Socher.  Progen: Language modeling for protein generation, 2020.
  * Meier et al. [2021] Joshua Meier, Roshan Rao, Robert Verkuil, Jason Liu, Tom Sercu, and Alex Rives.  Language models enable zero-shot prediction of the effects of mutations on protein function.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Mikolov et al. [2010] Tomas Mikolov, Martin Karafiát, Lukas Burget, Jan Cernockỳ, and Sanjeev Khudanpur.  Recurrent neural network based language model.  In _Interspeech_ , volume 2, pages 1045–1048. Makuhari, 2010.
  * Olsen et al. [2022] Tobias H Olsen, Fergus Boyles, and Charlotte M Deane.  Observed antibody space: A diverse database of cleaned, annotated, and translated unpaired and paired antibody sequences.  _Protein Science_ , 31(1):141–146, 2022.
  * Post and Vilar [2018] Matt Post and David Vilar.  Fast lexically constrained decoding with dynamic beam allocation for neural machine translation.  _arXiv preprint arXiv:1804.06609_ , 2018.
  * Reczko et al. [1995] Martin Reczko, Andrew CR Martin, Henrik Bohr, and Sándor Suhai.  Prediction of hypervariable cdr-h3 loop structures in antibodies.  _Protein Engineering, Design and Selection_ , 8(4):389–395, 1995.
  * Rives et al. [2021] Alexander Rives, Joshua Meier, Tom Sercu, Siddharth Goyal, Zeming Lin, Jason Liu, Demi Guo, Myle Ott, C. Lawrence Zitnick, Jerry Ma, and Rob Fergus.  Biological structure and function emerge from scaling unsupervised learning to 250 million protein sequences.  _Proceedings of the National Academy of Sciences_ , 118(15), 2021.  ISSN 0027-8424.  doi: 10.1073/pnas.2016239118.  URL https://www.pnas.org/content/118/15/e2016239118.
  * Shu et al. [2020] Raphael Shu, Jason Lee, Hideki Nakayama, and Kyunghyun Cho.  Latent-variable non-autoregressive neural machine translation with deterministic inference using a delta posterior.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 8846–8853, 2020.
  * Street and Mayo [1999] Arthur G Street and Stephen L Mayo.  Computational protein design.  _Structure_ , 7(5):R105–R109, 1999.
  * Sutskever et al. [2014] Ilya Sutskever, Oriol Vinyals, and Quoc V Le.  Sequence to sequence learning with neural networks.  _Advances in neural information processing systems_ , 27, 2014.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Vincent et al. [2008] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol.  Extracting and composing robust features with denoising autoencoders.  In _Proceedings of the 25th international conference on Machine learning_ , pages 1096–1103, 2008.
  * Wang and Cho [2019] Alex Wang and Kyunghyun Cho.  Bert has a mouth, and it must speak: Bert as a markov random field language model.  _arXiv preprint arXiv:1902.04094_ , 2019.
  * Welleck et al. [2019] Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston.  Neural text generation with unlikelihood training.  _arXiv preprint arXiv:1908.04319_ , 2019.
  * Welleck et al. [2020] Sean Welleck, Ilia Kulikov, Jaedeok Kim, Richard Yuanzhe Pang, and Kyunghyun Cho.  Consistency of a recurrent language model with respect to incomplete decoding.  _arXiv preprint arXiv:2002.02492_ , 2020.
  * Wolf et al. [2020] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online, October 2020. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/2020.emnlp-demos.6.
  * Woolfson [2021] Derek N Woolfson.  A brief history of de novo protein design: minimal, rational, and computational.  _Journal of Molecular Biology_ , 433(20):167160, 2021.
  * Yang et al. [2019] Kevin K Yang, Zachary Wu, and Frances H Arnold.  Machine-learning-guided directed evolution for protein engineering.  _Nature methods_ , 16(8):687–694, 2019.
  * Yi et al. [2021] Ren Yi, Kyunghyun Cho, and Richard Bonneau.  Nettime: Improving multitask transcription factor binding site prediction with base-pair resolution.  _bioRxiv_ , 2021.


# A lower bound for the number of pinned angles determined by a Cartesian
product set

and  Oliver Roche-Newton  Institute for Algebra, Johannes Kepler Universität
Linz, Austria<EMAIL_ADDRESS>
###### Abstract.

We prove that, for any $B\subset\mathbb{R}$, the Cartesian product set
$B\times B$ determines $\Omega(|B|^{2+c})$ distinct angles.

##  1\. Introduction

Given three distinct points $p,q,r\in\mathbb{R}^{2}$, let $\mathcal{A}(p,q,r)$
denote the angle determined by the three points with $q$ as the centre. Given
a set $P\subset\mathbb{R}^{2}$ with cardinality $|P|=n$, define

$\mathcal{A}(P):=\\{\mathcal{A}(p,q,r):p,q,r\in P\\}.$

This paper is concerned with lower bounds for the size of the set
$\mathcal{A}(P)$ as a function of $|P|$. As a starting point, observe that the
bound

(1) $|\mathcal{A}(P)|\gg|P|$

holds for any set $P$ which is not contained in a line.111Throughout this
note, the notation $X\gg Y$ and $Y\ll X,$ are equivalent and mean that $X\geq
cY$ for some absolute constant $c>0$. In addition, we use the symbols
$\gtrsim$ and $\lesssim$ to supress logarithmic factors. To be precise
$X\gtrsim Y$ and $Y\lesssim X,$ are equivalent and mean that $X\geq cY(\log
Y)^{-c^{\prime}}$ for some absolute constants $c,c^{\prime}>0$. One method for
proving (1) is to use Beck’s Theorem. If there are $\Omega(|P|)$ points from
$P$ on a line $\ell$, we may fix any point $q\in P\setminus\ell$ and a point
$p\in P\cap\ell$, and observe that the angles

$\mathcal{A}(p,q,r),\,\,r\in P\cap\ell$

are distinct. Otherwise, it follows from Beck’s Theorem that there is a point
$q\in P$ which determines $\Omega(|P|)$ directions with the other elements of
$P$, and this immediately implies that $q$ determines $\Omega(|P|)$ angles
with these points, using $q$ as the centre of the angles.

The bound (1) cannot be improved in general. For instance, one may consider a
point set $P$ consisting of $n-1$ points distributed equally on a circle,
along with the centre of the circle. A similar example can be constructed
whereby $n-2$ points are on a single line, and the two additional points are
arranged to be symmetric with respect to the line such that the directions to
the points on the line form an arithmetic progression.

Figure 1. This picture shows two degenerate examples sets of $n$ points
determining $O(n)$ distinct angles. Essentially all of the examples that we
are aware of for points sets with this property are derived from variations of
these two configurations.

We would like to prove that, if we impose some additional conditions on $P$ to
avoid these special configurations, then $|\mathcal{A}(P)|\gg|P|^{1+c}$ holds
for some absolute constant $c>0$. To put this another way, we would ultimately
like to classify the points sets which determine few angles. For context, let
us consider the analogue of this question for the Erdős distance problem. Let
$\mathcal{D}(P):=\\{\|p-q\|:p,q\in P\\}$ denote the set of distinct distances
determined by a point set $P\subset\mathbb{R}^{2}$. A breakthrough work of
Guth and Katz [6] established that the near-optimal bound

$|\mathcal{D}(P)|\gg\frac{|P|}{\log|P|}$

holds for all $P\subset\mathbb{R}^{2}$. The problem of determining the
structure of sets which have close to the minimum possible number of distinct
distances has attracted considerable attention. It is expected that such sets
have a lattice-type structure, and it was conjectured by Erdős [3] that an
extremal example must contain $\Omega(\sqrt{|P|})$ points on a line, although
very little is currently known for this family of problems. For the analogous
question concerning the structure of sets which determine few congruence
classes of triangles, see a recent paper of Mansfield and Passant [9].

Some work on super linear bounds for distinct angles was carried out in a very
recent work of Konyagin, Passant and Rudnev [7], in which they proved that the
bound

$|\mathcal{A}(P)|\gtrsim|P|^{1+\frac{3}{23}}$

holds under the condition that $P$ is in convex position and not all of the
points lie on a circle. Going back a little further, Pach and Sharir [10]
proved an optimal bound for the maximum number of representations of a single
angle. It is conceivable, bearing in mind the two examples illustrated above,
that a condition that no $n-2$ points of $P$ lie on a line or circle is enough
to guarantee a better than linear bound for $|\mathcal{A}(P)|$. However, to
the best of our knowledge, it is not even known that such a bound holds under
the much stronger assumption that the point set $P$ is in general position
(that is, no $3$ points lie on a line and no $4$ points lie on a circle).

In this paper, we consider something of an intermediate case raised in [7],
where the point set $P=B\times B$ is a Cartesian product. In this case, we are
able to improve the trivial estimate (1), as follows.

######  Theorem 1.

For any finite set $B\subset\mathbb{R}^{2}$,

$|\mathcal{A}(B\times B)|\gg|B|^{2+\frac{1}{14}}.$

Moreover, there exists $q\in B\times B$ such that

$|\\{\mathcal{A}(p,q,r):p,r\in B\times B\\}|\gg|B|^{2+\frac{1}{14}}.$

In terms of the techniques at our disposal, the advantage of restricting to
the case when $P$ is a Cartesian product is that it allows us to convert this
geometric problem into an arithmetic question in the spirit of the sum-product
problem. The problem reduces to a question about growth of a given set under a
combination of additive and convex operations. Such questions have been
studied using incidence geometry, going back to the work of Elekes, Nathanson
and Ruzsa [2]. Recently, an elementary “squeezing” argument has led to new
progress in this direction; see, for example, [11], [4] and [1]. Of particular
relevance here is the work of [5], where these techniques were used to prove
superquadratic growth estimates for convex expanders. The proof of Theorem 1
is also built upon applications of the squeezing argument.

##  2\. Preliminary results

In the proof of Theorem 1, we will use the following bipartite variant of
Beck’s Theorem. The result can be proved by a simple adaptation of the well-
known proof of Beck’s Theorem via an application of the Szemerédi-Trotter
Theorem. For the convenience of the reader, a full proof is given below. The
statement can also be derived as an immediate corollary of Theorem 1.9 from a
recent paper of Lund, Pham and Thu [8].

######  Theorem 2.

There exists a sufficiently small absolute constant $c>0$ such that the
following statement holds. Let $P$ and $Q$ be disjoint sets of $N$ points in
$\mathbb{R}^{2}$ and suppose that at most $cN$ points from $Q$ are collinear.
Then there exists $p=(p_{1},p_{2})\in P$ such that the set of directions

$\left\\{\frac{p_{2}-q_{2}}{p_{1}-q_{1}}:(q_{1},q_{2})\in Q\right\\}$

has cardinality at least $cN$.

###### Proof.

Given $S\subset\mathbb{R}^{2}$, and an integer $t\geq 2$, let $L_{t}(S)$
denote the set of lines

$L_{t}(S):\\{\ell:|\ell\cap S|\geq t\\}.$

It follows from the Szemerédi-Trotter Theorem that

(2) $|L_{t}(S)|\ll\frac{|S|^{2}}{t^{3}}+\frac{|S|}{t}.$

Now, for two distinct points $p\in P$ and $q\in Q$, let $\ell_{p,q}$ denote
the line connecting $p$ and $q$. We say that $p$ and $q$ are $k$-connected if

$2^{k}\leq|\ell_{p,q}\cap Q|<2^{k+1}.$

Note that that every pair $(p,q)\in P\times Q$ is $k$-connected for exactly
one integer $k\geq 0$, and so

$N^{2}=\sum_{k\geq 0}|\\{(p,q)\in P\times Q:\text{ $p$ and $q$ are
$k$-connected}\\}|.$

We will prove the theorem with the absolute constant $c$ defined to be

(3) $c:=\frac{1}{33C^{\prime}},$

where $C^{\prime}$ is another absolute constant arising from applications of
the Szemerédi-Trotter Theorem.

Suppose for a contradiction that at most $\frac{N^{2}}{2}$ of the pairs in
$P\times Q$ are $k$-connected with $k\leq k_{0}$ for some sufficiently large
absolute constant $k_{0}$ to be specified later. In particular, and using also
the assumption that no more than $cN$ points of $Q$ lie on any line, we have

$\displaystyle\frac{N^{2}}{2}$
$\displaystyle\leq\sum_{k=k_{0}+1}^{\lceil\log_{2}(cN)\rceil+1}|\\{(p,q)\in
P\times Q:\text{ $p$ and $q$ are $k$-connected}\\}|$
$\displaystyle=\sum_{k=k_{0}+1}^{\lceil\log_{2}(cN)\rceil+1}\sum_{\,\,\ell:2^{k}\leq|\ell\cap
Q|<2^{k+1}}|\ell\cap P|\cdot|\ell\cap Q|$
$\displaystyle<\sum_{k=k_{0}+1}^{\lceil\log_{2}(cN)\rceil+1}2^{k+1}\sum_{\,\,\ell:2^{k}\leq|\ell\cap
Q|<2^{k+1}}|\ell\cap P|$
$\displaystyle\leq\sum_{k=k_{0}+1}^{\lceil\log_{2}(cN)\rceil+1}2^{k+1}\cdot
I(P,L_{2^{k}}(Q))$ $\displaystyle\leq
C\sum_{k=k_{0}+1}^{\lceil\log_{2}(cN)\rceil+1}2^{k}\left(|P|^{2/3}|L_{2^{k}}(Q)|^{2/3}+|P|+|L_{2^{k}}(Q)|\right)$
$\displaystyle\leq
C^{\prime}\sum_{k=k_{0}+1}^{\lceil\log_{2}(cN)\rceil+1}\left(\frac{N^{2}}{2^{k}}+2^{k}N\right)$
$\displaystyle\leq C^{\prime}\left(\frac{N^{2}}{2^{k_{0}}}+8cN^{2}\right),$

where $C$ and $C^{\prime}$ are absolute constants coming from applications of
the Szemerédi-Trotter Theorem, and $C^{\prime}$ is the constant which appeared
in the definition of $c$ back in (3).

By choosing $k_{0}$ to be sufficiently large (concretely, we can set
$k_{0}:=\lceil\log_{2}(4C^{\prime})\rceil$), it follows that the first term on
the right hand side can be absorbed into the left hand side to give

$\frac{N^{2}}{4}\leq 8C^{\prime}cN^{2}=\frac{8}{33}N^{2},$

obtaining the intended contradiction.

Therefore, we may restrict our attention to the case when at least
$\frac{N^{2}}{2}$ of the pairs in $P\times Q$ are $k$-connected for some
$k\leq k_{0}$. It follows from the pigeonhole principle that there is some
$p\in P$ such that

$|\\{q\in Q:\text{$p$ and $q$ are $k$-connected for some $k\leq
k_{0}$}\\}|\geq\frac{N}{2}.$

It then follows that the number of directions between $p$ and $Q$ is at least

$\frac{N}{2^{k_{0}+2}}\geq\frac{N}{32C^{\prime}}>cN.$

∎

The key ingredient for the proof of Theorem 1 is the following new result.

######  Theorem 3.

For any finite sets $X,Y,\subset\mathbb{R}$

$|4f(X-Y)-3f(X-Y)|\gtrsim\min\\{|X|,|Y|\\}^{5/2},$

where the function $f$ is given by the formula $f(x)=\arctan(e^{x})$.

Theorem 3 can be derived from Theorem 2.6 in [5]. A special case of this
result which is tailored slightly to our purposes is stated below.

######  Theorem 4.

Let $f:\mathbb{R}\to\mathbb{R}$ be a continuous, strictly increasing and
strictly convex function, and let $h_{3}>h_{2}>h_{1}$ be real numbers. Suppose
that the curve

(4) $\\{(f(t+h_{2})-f(t+h_{1}),f(t+h_{3})-f(t+h_{2})):t\in\mathbb{R}\\}$

is the graph of a strictly convex or strictly concave function. Suppose that
$A=\\{a_{1}<\ldots<a_{N}\\}$ is a finite set of positive real numbers
satisfying the spacing condition

$\min\\{a_{i+1}-a_{i}:i\in[N-1]\\}\geq\max\\{h_{2}-h_{1},h_{3}-h_{2}\\}.$

Then

$|2f(A+h_{1})-2f(A+h_{1})+2f(A+h_{2})-f(A+h_{2})|\cdot\\\
\cdot|2f(A+h_{3})-2f(A+h_{3})+2f(A+h_{2})-f(A+h_{2})|\gg\frac{N^{5}}{(\log
N)^{3}}.$

To apply Theorem 4 with the function $f(x)=\arctan(e^{x})$, we need to verify
the technical condition that the parametrically defined curve (4) is concave.
This is the content of the following lemma.

######  Lemma 1.

Let $f(x)=\arctan(e^{x})$ and suppose that $h_{1}<h_{2}<h_{3}$ are real
numbers. The curve

$\\{(f(t+h_{2})-f(t+h_{1}),f(t+h_{3})-f(t+h_{2})):t\in\mathbb{R}\\}$

is the graph of a strictly concave function.

###### Proof.

A direct and slightly laborious calculation gives

$\frac{d^{2}y}{dx^{2}}=\frac{2(1+e^{2(t+h_{3})})(1+e^{2(t+h_{1})})(e^{t+h_{3}}-e^{t+h_{2}})(e^{2(t+h_{1})}-e^{2(t+h_{3})})}{(e^{t+h_{2}}-e^{t+h_{1}})(1+e^{2(t+h_{3})})^{2}(e^{t+h_{2}}-e^{t+h_{1}})}.$

This is strictly negative for all $t$. Indeed, all of the factors are strictly
positive for all $t$, with the exception of

$e^{2(t+h_{1})}-e^{2(t+h_{3})},$

which is always negative. Since the second derivative is strictly negative, it
follows that the curve is the graph of a strictly concave function.

∎

###### Proof of Theorem 3.

Label the elements of $X=\\{x_{1}<\dots<x_{m}\\}$ and
$Y=\\{y_{1}<\dots<y_{n}\\}$ in ascending order. Consider the set of all nearly
neighbouring distances

$U=\\{x_{k+2}-x_{k}:1\leq k\leq m-2\\}\cup\\{y_{k+2}-y_{k}:1\leq k\leq n-2\\}$

and let $u$ denote the minimal element of $U$.

Case 1 \- Suppose that $u=x_{k+2}-x_{k}$ for some $1\leq k\leq n-2$. Let

$A=\left\\{-y_{2k}:1\leq k\leq\frac{n}{2}\right\\}.$

Apply Theorem 4 with this $A$ and with

$h_{1}=x_{k},\,h_{2}=x_{k+1},\,h_{3}=x_{k+2}.$

It follows that

$|4f(X-Y)-3f(X-Y)|\gtrsim|Y|^{5/2}.$

Case 2 \- Suppose that $u=y_{k+2}-y_{k}$ for some $1\leq k\leq m-2$. Let

$A=\left\\{x_{2k}:1\leq k\leq\frac{m}{2}\right\\}.$

Apply Theorem 4 with this $A$ and with

$h_{1}=-x_{k+2},\,h_{2}=-x_{k+1},\,h_{3}=-x_{k}.$

It follows that

$|4f(X-Y)-3f(X-Y)|\gtrsim|X|^{5/2},$

as required. ∎

##  3\. Proof of Theorem 1

We need to take care that a forthcoming application of the logarithmic
function is applied only to postitive values. For this reason, we split the
set $B$ into two disjoint sets $B_{1}$ and $B_{2}$ such that

$|B_{1}|=|B_{2}|\geq\left\lfloor\frac{|B|}{2}\right\rfloor$

and with the property that the largest element of $B_{1}$ is smaller than than
smallest element of $B_{2}$.

Write $P=B_{1}\times B_{1}$ and $Q=B_{2}\times B_{2}$. First, it follows from
Theorem 2 that there exists $(a,b)\in P$ such that $(a,b)$ determines
$\Omega(|B|^{2})$ directions with the set $Q$. That is,

(5) $\left|\frac{B_{2}-b}{B_{2}-a}\right|\gg|B|^{2}.$

We can calculate that

$\mathcal{A}((x,y),(a,b),(x^{\prime},y^{\prime}))=\arctan\left(\frac{y-b}{x-a}\right)-\arctan\left(\frac{y^{\prime}-b}{x^{\prime}-a}\right).$

Define

$\mathcal{A}(Q,(a,b),Q)=\\{\mathcal{A}(p,(a,b),r):p,r\in Q\\}.$

Then

(6) $|\mathcal{A}(B\times
B)|\geq|\mathcal{A}(Q,(a,b),Q)|=\left|\arctan\left(\frac{B_{2}-b}{B_{2}-a}\right)-\arctan\left(\frac{B_{2}-b}{B_{2}-a}\right)\right|.$

Let $X=\log(B_{2}-b)$ and $Y=\log(B_{2}-a)$. Note that these sets are well-
defined, since the sets $B_{2}-a$ and $B_{2}-b$ consist of strictly positive
elements. Applying Theorem 3 with these input sets gives

$\left|4\arctan\left(\frac{B_{2}-b}{B_{2}-a}\right)-3\arctan\left(\frac{B_{2}-b}{B_{2}-a}\right)\right|\gtrsim|B|^{5/2}.$

Plünnecke’s Theorem then gives

$\displaystyle|B|^{5/2}$
$\displaystyle\lesssim\left|4\arctan\left(\frac{B_{2}-b}{B_{2}-a}\right)-3\arctan\left(\frac{B_{2}-b}{B_{2}-a}\right)\right|$
$\displaystyle\leq\frac{\left|\arctan\left(\frac{B_{2}-b}{B_{2}-a}\right)-\arctan\left(\frac{B_{2}-b}{B_{2}-a}\right)\right|^{7}}{\left|\frac{B_{2}-b}{B_{2}-a}\right|^{6}}.$

Applying (5) and recalling (6) completes the proof.

### Acknowledgements

The author was supported by the Austrian Science Fund FWF Projects P 34180 and
PAT 2559123. I am grateful to Krishnendu Bhowmick, Misha Rudnev and Audie
Warren for helpfully sharing their insights.

## References

  * [1] P. J. Bradshaw, ‘Growth in Sumsets of Higher Convex Functions’, Combinatorica 43 (2023), no. 4, 769-789.
  * [2] G. Elekes, M. Nathanson and I. Ruzsa, ‘Convexity and sumsets’, J. Number Theory. 83 (1999), 194-201.
  * [3] P. Erdős, ‘On some metric and combinatorial geometric problems‘, Discrete Mathematics 60, (1986), 147-153.
  * [4] B. Hanson, O. Roche-Newton and M. Rudnev, ‘Higher convexity and iterated sum sets’, Combinatorica 42 (2022), no. 1, 71-85.
  * [5] B. Hanson, O. Roche-Newton and S. Senger, ‘Convexity, superquadratic growth, and dot products’, J. London Math. Soc. 107 (2023), 1900-1923.
  * [6] L. Guth and N. H. Katz ‘On the Erdős distinct distance problem in the plane’, Ann. of Math. (2) 181 (2015), no. 1, 155-190.
  * [7] S. V. Konyagin, J. Passant and M. Rudnev, ‘On Distinct Angles in the Plane’, arXiv:2402.15484 (2024).
  * [8] B. Lund, T. Pham and V. T. H. Thu, ‘Radial projection theorems in finite spaces’, arXiv:2205.07431 (2022).
  * [9] S. Mansfield and J. Passant, ‘A structural theorem for sets with few triangles’, Combinatorica 44 (2024), no. 1, 155-178.
  * [10] J. Pach and M. Sharir, ‘Repeated angles in the plane and related problems’,  J. Combin. Theory Ser. A 59 (1992), 12-22.
  * [11] I. Z. Ruzsa, G. Shakan, J. Solymosi and E. Szemerédi, ‘On distinct consecutive differences’, Combinatorial and additive number theory IV 425-434, Springer Proc. Math. Stat., 347, Springer, Cham, (2021).
  * [12] T. Schoen and I. Shkredov, ‘On sumsets of convex sets’, Combin. Probab. Comput. 20 (2011), no. 5, 793-798.