# A Strengthening of Freiman’s $3k-4$ Theorem

Béla Bollobás and Imre Leader and Marius Tiba  Department of Pure Mathematics
and Mathematical Statistics, Wilberforce Road, Cambridge, CB3 0WA, UK, and
Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152,
USA<EMAIL_ADDRESS>Department of Pure Mathematics and
Mathematical Statistics, Wilberforce Road, Cambridge, CB3 0WA, UK
<EMAIL_ADDRESS>Department of Pure Mathematics and Mathematical
Statistics, Wilberforce Road, Cambridge, CB3 0WA, UK<EMAIL_ADDRESS>
###### Abstract.

In its usual form, Freiman’s $3k-4$ theorem states that if $A$ and $B$ are
subsets of ${\mathbb{Z}}$ of size $k$ with small sumset (of size close to
$2k$) then they are very close to arithmetic progressions. Our aim in this
paper is to strengthen this by allowing only a bounded number of possible
summands from one of the sets. We show that if $A$ and $B$ are subsets of
${\mathbb{Z}}$ of size $k$ such that for any four-element subset $X$ of $B$
the sumset $A+X$ has size not much more than $2k$ then already this implies
that $A$ and $B$ are very close to arithmetic progressions.

The first author was partially supported by NSF grant DMS-1855745

##  1\. Introduction

Starting with the classical Cauchy-Davenport theorem [3, 4, 5], the sizes of
sumsets in Abelian groups have been studied in a host of papers. A new
direction in this study was introduced in [1]: given sets of integers $A$ and
$B$, say, does $B$ have a small subset $B^{\prime}$ such that $|A+B^{\prime}|$
is large, perhaps even comparable to $|A+B|$? In particular, in [1] the
following result was proved.

######  Theorem 1.

Let $A$ and $B$ be finite non-empty subsets of $\mathbb{Z}$ with
$|A|\geqslant|B|$. Then there exist elements $b_{1},b_{2},b_{3}\in B$ such
that

$|A+\\{b_{1},b_{2},b_{3}\\}|\geqslant|A|+|B|-1.$

Freiman’s $3k-4$ theorem (see Freiman [6, 7] and also Lev and Smeliansky [10]
and Stanchescu [12]), states the following, in the case where the sets have
the same size.

Let $A$ and $B$ be finite subsets of ${\mathbb{Z}}$ with $|A|=|B|=k$ such that
$|A+B|=2k-1+r$, where $r\leqslant k-3$. Then there are arithmetic progressions
$P$ and $Q$ of the same common difference, containing $A$ and $B$
respectively, such that each has size $k+r$.

A result of this kind is often called an ‘inverse’ theorem, as it describes
what happens when an inequality is close to being tight. (These are also often
known as ‘stability’ results.)

What about a ‘bounded sumset’ version of Freiman’s $3k-4$ theorem? Our aim in
this paper is to show that indeed we can weaken the condition that $A+B$ is
small to just a condition that all sumsets of $A$ with a bounded number of
terms of $B$ are small. This is really rather surprising. One could view this
as a kind of inverse result to Theorem 1.

######  Theorem 2.

There are constants $c,\varepsilon_{0}>0$ such that for all
$\varepsilon<\varepsilon_{0}$ the following holds. Let $A$ and $B$ be finite
non-empty subsets of $\mathbb{Z}$ with $n=|A|=|B|$. Suppose that for any four
elements $b_{1},b_{2},b_{3},b_{4}\in B$ we have

$|A+\\{b_{1},b_{2},b_{3},b_{4}\\}|\leqslant(2+\varepsilon)n-1.$

Then there are arithmetic progressions $P,Q$ in $\mathbb{Z}$ of size
$(1+\varepsilon+c\varepsilon^{2})n$ with the same common difference such that
$B\subset Q$ and

$|A\Delta P|\leqslant c\varepsilon n.$

The key point in this result is that the sizes of the progressions $P$ and $Q$
are ‘about’ $(1+\varepsilon)n$: the precise form of the error term in this, as
quadratic in $\varepsilon$, is not so important. Note that the dependence of
the error terms (the sizes of $|A\Delta P|$ and $|B\Delta Q|$), as linear
functions of $\varepsilon$, is best possible. This may be seen by taking $B$
to be an interval of length $n$ and $A$ to consist of of an interval of length
$(1-2\varepsilon)n$ together with, on either side of it, random half-sized
subsets of the adjacent intervals of length $2\varepsilon n$.

We remark that the condition that $A$ has small symmetric difference with $P$
cannot be strengthened to insist that $A$ lies inside $P$. This is because one
may always have a few ‘rogue’ points in $A$, far from the rest of $A$. The
same would not apply to $B$, because adding a few faraway points to $B$ is a
great help in selecting the four points.

It would be extremely interesting to decide whether this result remains valid
if we consider three elements instead of four. To elaborate on this, the way
that Theorem 1 is proved is by taking the three points of $B$ as follows: we
first take the smallest and largest points of $B$ (the reader will see that we
have to take those points, as may be seen from the case when the two sets are
intervals), and then choosing the third point at random from the remaining
points of $B$. It is very surprising that these two different ingredients mesh
together so well, to give exactly the lower bound required. However, and this
is the key point, this approach cannot be used to prove a three-element
version of Theorem 2. Indeed, this may be seen by taking $B=[0,n]$ and
$A=X\cup(X+n)$ where $X$ is a random set of density $1/2$ in an interval of
length $n$.

The plan of the paper is as follows. In Section 2 we mention some background
results from [1] that we will need. We do give a brief summary of the proof of
Theorem 1, to help make the paper self-contained and also because the methods
there form a good ‘toy case’ of the arguments in our main result. Indeed,
those background results from [1] that we do not prove here may be proved by
methods very similar to those in the proof of Theorem 1. Then in Section 3 we
present our main result.

Our notation is standard. To make our paper more readable, we often omit
integer-part signs when these do not affect the argument.

Sometimes we write ‘$x\mod d$’ as shorthand for the infinite arithmetic
progression $\\{y\in\mathbb{Z}:y\equiv x\mod d\\}$, and refer to it as a fibre
mod $d$. When $S$ is a subset of $\mathbb{Z}$ we often write $S^{x}$ for the
intersection of this fibre with $S$ – when the value of $d$ is clear. (We
sometimes write $S^{x}$ as $S^{x}_{d}$ when we want to stress the value of
$d$.) Thus $S^{x}=S\cap\pi^{-1}(x)$, where $\pi=\pi_{d}$ denotes the natural
projection from $\mathbb{Z}$ to $\mathbb{Z}_{d}$. We also write
$\widetilde{S}$ for $\pi_{d}(S)$.

When we write a probability or an expectation over a finite set, we always
assume that the elements of the set are being sampled uniformly. Thus, for
example, for a finite set $X\subset\mathbb{Z}$ we denote the expectation and
probability when we sample uniformly over all $x\in X$ by respectively
$\operatorname*{\mathbb{E}}_{x\in X}\text{ and
}\operatorname*{\mathbb{P}}_{x\in X}.$

For more general background on sumsets, see the survey of Breuillard, Green
and Tao [2] or the books of Nathanson [11] or Tao and Vu [13]. For extensions
of Freiman’s $3k-4$ theorem to other settings, such as $\mathbb{Z}_{p}$ in
particular, see Grynkiewicz [8].

To end the Introduction, we give a brief overview of the proof of Theorem 2.
With $B$ having first element $0$ and last element $m$, we start by showing
that (unless we are done) $A$ must have a large projection onto
${\mathbb{Z}}_{m}$. This is accomplished by a careful analysis of what happens
when we take our four points of $B$ to be $0$, $m$ and two random points: it
is the interaction of the two random points that is critical here. From this
we find that $B$ is contained in a quite short arithmetic progression, and in
turn this will imply that $A$ is also relatively close to an arithmetic
progression. However, these progressions are not small enough to give Theorem
2, and so we need an argument that ‘boosts’ this. This is a very delicate
analysis of, again, how the two random translates interact with each other and
with the two fixed translates. In fact, it is rather surprising that this
boosting argument actually works: in length it is most of the proof. (It is
Theorem 9 below).

##  2\. Prerequisites

We start by giving an indication of the proof of Theorem 1. As explained
above, the main idea is to fix two elements as the first and last elements of
$B$ and then to select the remaining element at random.

Let $B$ have first element $0$ and last element $m$. Then
$A+\\{0,m\\}=A\cup(A+m)$ satisfies
$\pi_{m}(A)=\pi_{m}\big{(}A\cup(A+m)\big{)}=\widetilde{A}$, and

$\bigg{|}A\cup(A+m)\bigg{|}\geqslant|A|+|\widetilde{A}|.$ (1)

To see this, note that $(A+m)^{x}=A^{x}+m$ for every $x\in{\mathbb{Z}}$.
Hence, if $x\in\widetilde{A}=\pi_{m}(A)$ then $(A+m)^{x}=A^{x}+m\neq A^{x}$,
so
$\bigg{|}\big{[}A\cup(A+m)\big{]}^{x}\bigg{|}=\bigg{|}A^{x}\cup(A+m)^{x}\bigg{|}\geqslant|A^{x}|+1.$
Consequently,

$\bigg{|}A\cup(A+m)\bigg{|}\geqslant\sum_{x\in\widetilde{A}}\bigg{|}[A\cup(A+m)]^{x}\bigg{|}\geqslant\sum_{x\in\widetilde{A}}|A^{x}|+1=|A|+|\widetilde{A}|,$

completing the proof of (1).

We mention that the way that the proof of Theorem 1 in [1] now proceeds is to
consider the excess contribution to $|A\cup(A+m)|$ that comes when we form the
union with $A+b$, where $b$ is chosen uniformly at random from the remaining
points of $B$. One finds that this has expectation at least $|A|$ times
$1-|\widetilde{A}|/|\widetilde{B}|$. If this is negative then the bound (1) is
already enough to finish the proof, while if it is positive then it is easy to
check that together with (1) it gives the required bound.

This actually gives the following stronger version of Theorem 1. Let $A$ and
$B$ be finite non-empty subsets of integers with $|A|\geqslant|B|$ and $B$
having smallest element $0$ and greatest element $m$. Then we have

$\max_{b_{1},b_{2},b_{3}\in
B}\bigg{|}A+\\{b_{1},b_{2},b_{3}\\}\bigg{|}\geqslant\operatorname*{\mathbb{E}}_{b\in
B\setminus\\{m\\}}\bigg{|}A+\\{0,b,m\\}\bigg{|}\geqslant|A|+|B|-1.$ (2)

We now pass to some related results from [1]. These are proved along broadly
similar lines to the above results. The first one is about the case of
equality.

######  Theorem 3.

Let $A$ and $B$ be finite non-empty subsets of $\mathbb{Z}$ with $|A|=|B|$,
with $\min(B)=0$ and $\max(B)=m$. Suppose that when we choose an element $b$
of $B\setminus\\{0,m\\}$ uniformly at random we have

$\operatorname*{\mathbb{E}}_{b\in
B\setminus\\{0,m\\}}\bigg{|}A+\\{0,b,m\\}\bigg{|}\leqslant|A|+|B|-1.$ (3)

Then $A$ and $B$ are arithmetic progressions with the same common difference.

In particular, suppose that when we choose any three elements
$b_{1},b_{2},b_{3}$ of $B$ we have

$\bigg{|}A+\\{b_{1},b_{2},b_{3}\\}\bigg{|}\leqslant|A|+|B|-1.$

Then $A$ and $B$ are arithmetic progressions with the same common difference.

Then we need another version of Theorem 1.

######  Theorem 4.

Let $A$ and $B$ be finite non-empty subsets of $\mathbb{Z}$, with $\min(B)=0$
and $\max(B)=m$. Then

$\operatorname*{\mathbb{E}}_{b\in
B\setminus\\{m\\}}\bigg{|}A+\\{0,b,m\\}\bigg{|}\geqslant|A|+|\pi_{m}(A)|+|A|\max\bigg{(}0,\frac{|B|-1-|\pi_{m}(A)|}{|B|-1}\bigg{)}.$

We note also a simple variant of the ideas above.

######  Lemma 5.

Let $A$, $B$ and $A_{1}$ be finite non-empty subsets of $\mathbb{Z}$, with
$\min(B)=0$ and $\max(B)=m$. Then with $\widetilde{A}=\pi_{m}(A)$ and
$\widetilde{B}=\pi_{m}(B)$ we have

$\operatorname*{\mathbb{E}}_{b\in
B\setminus\\{m\\}}\bigg{|}(A_{1}+b)\setminus\pi_{m}^{-1}(\widetilde{A})\bigg{|}\geqslant|A_{1}|\max\bigg{(}0,\frac{|\widetilde{B}|-|\widetilde{A}|}{|\widetilde{B}|}\bigg{)}.$

The next result follows easily from Lemma 5.

######  Lemma 6.

Let $A$ and $B$ be finite non-empty subsets of $\mathbb{Z}$, with $\min(B)=0$
and $\max(B)=m$. Suppose that $|B|-1=|\widetilde{B}|\geqslant
8|\widetilde{A}|$, where $\widetilde{A}=\pi_{m}(A)$ and
$\widetilde{B}=\pi_{m}(B)$. Then

$\operatorname*{\mathbb{E}}_{b_{2},b_{3}\in
B\setminus\\{m\\}}\bigg{|}A+\\{0,b_{2},b_{3}\\}\bigg{|}\geqslant 2.5|A|.$

The last result from [1] that we need is a strengthening of Theorem 1.

######  Theorem 7.

Let $A$ and $B$ be finite non-empty subsets of $\mathbb{Z}$ with $|A|=|B|$,
with $\min(B)=0$ and $\max(B)=m$. Then

$\operatorname*{\mathbb{E}}_{b\in
B\setminus\\{m\\}}\bigg{|}A+\\{0,b,m\\}\bigg{|}\geqslant|A|+|B|-1+\max\bigg{(}0,\frac{(2|\pi_{m}(A)|-m)(m-(|B|-1))-1}{|B|-1}\bigg{)}.$

##  3\. The Main Result

In this section we prove Theorem 2, our stability version of Theorem 1. As we
mentioned earlier, the dependence of the error terms on $\varepsilon$, being
linear, is of best possible order. It will turn out that a key ingredient is
actually the following weaker version of Theorem 2.

######  Theorem 8.

For any $\delta>0$ there exists $\varepsilon>0$ such that the following holds.
Let $A$ and $B$ be finite non-empty subsets of $\mathbb{Z}$ with $n=|A|=|B|$.
Suppose that

$\max_{b_{1},b_{2},b_{3},b_{4}\in
B}\bigg{|}A+\\{b_{1},b_{2},b_{3},b_{4}\\}\bigg{|}\leqslant 2n-1+\varepsilon
n.$ (4)

Then there exist arithmetic progressions $P$ and $Q$ in $\mathbb{Z}$ with the
same common difference and size $\lfloor(1+\delta)n\rfloor$ such that
$|A\setminus P|\leqslant\delta n\text{ and }B\subset Q.$

We will also need the following technical result.

######  Theorem 9.

For all sufficiently small $\alpha,\beta,\varepsilon>0$, taking
$\nu=(\varepsilon+\varepsilon^{2}(1-\alpha)^{-1})(1-4\alpha-\beta)^{-1}$ and
$\mu=2^{15}(\varepsilon+\beta)$ the following holds. Let $A$ and $B$ be finite
non-empty subsets of $\mathbb{Z}$ with $n=|A|=|B|$. Suppose that there exist
integer arithmetic progressions $P$ and $Q$ with the same common difference
$d$ and sizes $\lfloor(1+\alpha)n\rfloor$ and $\lfloor(1+\beta)n\rfloor$ such
that

$|A\setminus P|\leqslant\alpha n\text{ and }B\subset Q$ (5)

and

$\max_{b_{1},b_{2},b_{3},b_{4}\in
B}\bigg{|}A+\\{b_{1},b_{2},b_{3},b_{4}\\}\bigg{|}\leqslant 2n-1+\varepsilon
n.$ (6)

Then there exist integer arithmetic progressions $P^{\prime}$ and $Q^{\prime}$
with common difference $d$ and sizes $\lfloor(1+\mu)n\rfloor$ and
$\lfloor(1+\nu)n\rfloor$ such that $|A\setminus P^{\prime}|\leqslant\mu
n\text{ and }B\subset Q^{\prime}.$

###### Proof.

Fix $\alpha,\beta,\varepsilon>0$ sufficiently small. By Theorem 3, we may
assume that

$\varepsilon n\geqslant 1.$ (7)

Set $R=d\mathbb{Z}$, and assume without loss of generality that $P,Q\subset
R$. Form the partition $A=A_{1}\sqcup A_{2}$ given by $A_{1}=A\cap R\text{ and
}A_{2}=A\cap R^{c}$ and write $n_{1}=|A_{1}|\text{ and }n_{2}=|A_{2}|.$ By (5)
we have

$n\geqslant n_{1}\geqslant(1-\alpha)n\geqslant 9n_{2}.$ (8)

Assume that $\min(B)=0\text{ and }\max(B)=md.$ Take any subset $B_{1}\subset
B$ of size $n_{1}=|B_{1}|$ such that $\min(B_{1})=0\text{ and
}\max(B_{1})=md.$ On the one hand, by construction we have
$(A_{1}+B_{1})\cap(A_{2}+B_{1})=\emptyset.$ On the other hand, by (6) we have

${\mathbb{E}}_{b_{2},b_{3}\in
B_{1}\setminus\\{md\\}}\bigg{|}A+\\{0,b_{2},b_{3},md\\}\bigg{|}\leqslant
2n-1+\varepsilon n.$

The last two relations imply

${\mathbb{E}}_{b_{2}\in
B_{1}\setminus\\{md\\}}\bigg{|}A_{1}+\\{0,b_{2},md\\}\bigg{|}+{\mathbb{E}}_{b_{2},b_{3}\in
B_{1}\setminus\\{md\\}}\bigg{|}A_{2}+\\{0,b_{2},b_{3}\\}\bigg{|}\leqslant
2n-1+\varepsilon n.$

By Theorem 4, we have

${\mathbb{E}}_{b_{2}\in
B_{1}\setminus\\{md\\}}\bigg{|}A_{1}+\\{0,b_{2},md\\}\bigg{|}\geqslant
2n_{1}-1.$

Lemma 6 and (8) tell us that

${\mathbb{E}}_{b_{2},b_{3}\in
B_{1}\setminus\\{md\\}}\bigg{|}A_{2}+\\{0,b_{2},b_{3}\\}\bigg{|}\geqslant
2.5n_{2}.$

The last three inequalities imply

${\mathbb{E}}_{b_{2}\in
B_{1}\setminus\\{md\\}}\bigg{|}A_{1}+\\{0,b_{2},md\\}\bigg{|}\leqslant
2n_{1}-1+\varepsilon n_{1}.$ (9)

and also

$n_{2}\leqslant 2\varepsilon n\text{ i.e. }n_{1}\geqslant(1-2\varepsilon)n.$
(10)

By (6) and (10) we have

$\max_{b_{2},b_{3}\in
B_{1}\setminus\\{md\\}}\bigg{|}A_{1}+\\{0,b_{2},b_{3},md\\}\bigg{|}\leqslant
2n_{1}-1+8\varepsilon n_{1}.$ (11)

For the rest of the proof we focus on the sets $A_{1}$ and $B_{1}$ and thus we
may assume without loss of generality that $d=1.$

The construction of $Q^{\prime}$. By Theorem 7 we have

${\mathbb{E}}_{b_{2}\in
B_{1}\setminus\\{md\\}}\bigg{|}A_{1}+\\{0,b_{2},m\\}\bigg{|}\geqslant
2n_{1}-1+\frac{(2|\pi_{m}(A_{1})|-m)(m-(n_{1}-1))-1}{n_{1}-1}.$ (12)

By (5), we have $|\pi_{m}(A_{1})|\geqslant n-2\alpha n$ and also
$m\leqslant(1+\beta)n;$ consequently,

$2|\pi_{m}(A_{1})|-m\geqslant(1-4\alpha-\beta)n\geqslant(1-4\alpha-\beta)n_{1}.$
(13)

From (9), (12) and (13) we have

$\frac{(1-4\alpha-\beta)n_{1}(m+1-n_{1})-1}{n_{1}-1}\leqslant\varepsilon
n_{1},$ (14)

and so our bounds on the parameters imply

$\displaystyle m+1$ $\displaystyle\leqslant$ $\displaystyle
n_{1}+(1-4\alpha-\beta)^{-1}(\varepsilon(n_{1}-1)+\frac{1}{n_{1}})\leqslant
n+(1-4\alpha-\beta)^{-1}(\varepsilon n+\frac{(1-\alpha)^{-1}}{n})$
$\displaystyle\leqslant$ $\displaystyle n+(1-4\alpha-\beta)^{-1}(\varepsilon
n+\varepsilon^{2}(1-\alpha)^{-1}n)$
$\displaystyle=(1+(1-4\alpha-\beta)^{-1}(\varepsilon+\varepsilon^{2}(1-\alpha)^{-1}))n.$

Finally, we conclude the arithmetic progression
$Q^{\prime}=\\{0,d,\ldots,md\\}$ has common difference $d$ and size at most
$\lfloor(1+\nu)n\rfloor$ and contains $B$.

The construction of $P^{\prime}$. By translating $A_{1}$, we may assume that
the partition $A_{1}=A_{l}\sqcup A_{c}\sqcup A_{r}$ given by

$A_{l}=(-\infty,-m)\cap A_{1}\text{ , }A_{c}=[-m,0)\cap A_{1}\text{ ,
}A_{r}=[0,\infty)\cap A_{1}.$

satisfies

$|A_{r}|=k\text{ , }|A_{l}|=k-\tau\text{ , }|A_{c}|=n_{1}-2k+\tau,$ (15)

where $\tau\in\\{0,1\\}.$ By (5) and (8) we have $k\leqslant 2^{-10}n_{1}$,
and by (7) and (8) we have $2\varepsilon n_{1}\geqslant 1$. However, we may
assume that

$2^{-10}n_{1}\geqslant k\geqslant 2^{10}(\beta+\varepsilon)n_{1}\geqslant
2^{9},$ (16)

and so Theorem 4 implies

${\mathbb{E}}_{b_{2}\in
B_{1}\setminus\\{m\\}}\bigg{|}A_{c}+\\{0,b_{2},m\\}\bigg{|}\geqslant
2(n_{1}-2k+\tau)+(n_{1}-2k+\tau)\frac{2k-\tau-1}{n_{1}-1}.$

In particular, there exist $b_{2}\in B_{1}\setminus\\{m\\}$ and there exists a
partition $[-m,m)=Y\sqcup Y^{c}$ such that

$|Y|=2m-[2(n_{1}-2k+\tau)+(n_{1}-2k+\tau)\frac{2k-\tau-1}{n_{1}-1}]\geqslant
2k-\tau-1,$ $\displaystyle|Y^{c}|$ $\displaystyle=$ $\displaystyle
2(n_{1}-2k+\tau)+(n_{1}-2k+\tau)\frac{2k-\tau-1}{n_{1}-1}$ (17)
$\displaystyle\geqslant$ $\displaystyle
2n_{1}-1-2k+\tau-\frac{(2k-\tau-1)^{2}}{n_{1}-1},$ (18)

and

$Y^{c}\subset A_{c}\cup(A_{c}+m)\cup(A_{c}+b_{2}).$

We now break the argument into two cases.

Case 1:

$\bigg{|}[-m-k,-m)\cap A_{1}\bigg{|}\geqslant k/2\text{ and }\bigg{|}[0,k)\cap
A_{1}\bigg{|}\geqslant k/2.$ (19)

In this case, by (17) we get

$\bigg{|}[-m,0)\cap Y\bigg{|}\geqslant k-1\text{ or }\bigg{|}[0,m)\cap
Y\bigg{|}\geqslant k-1.$

Let $Z=Y\cap[-m,0).$ We may assume that $|Z|\geqslant k-1.$ By (16) we have

$|Z|\geqslant k/2.$ (20)

Claim A.

${\mathbb{E}}_{b_{3}\in[0,4k)\cap B_{1}}\bigg{|}(A_{1}+b_{3})\cap
Z\bigg{|}\geqslant k/32.$

In particular, there exists $b_{3}\in B_{1}$ such that

$\bigg{|}(A_{1}+b_{3})\cap Z\bigg{|}\geqslant k/32.$

###### Proof.

By (5), (10) and (16) we have

$\bigg{|}[0,4k)\setminus B_{1}\bigg{|}\leqslant\bigg{|}[0,m)\setminus
B\bigg{|}+|B_{2}|\leqslant\beta n+n_{2}\leqslant
4(\beta+\varepsilon)n_{1}\leqslant k/4.$ (21)

For $x\in[-m+3k,0)$, by (5), (10), (15) and (16) we have

$\displaystyle\bigg{|}(x-4k,x]\setminus A_{1}\bigg{|}$
$\displaystyle\leqslant$ $\displaystyle\bigg{|}(x-3k,x]\setminus
A_{1}\bigg{|}+k\leqslant\bigg{|}[-m,0)\setminus A_{1}\bigg{|}+k$ (22)
$\displaystyle\leqslant$ $\displaystyle m-(n_{1}-2k+\tau)+k\leqslant\beta
n+n_{2}+3k$ (23) $\displaystyle\leqslant$ $\displaystyle
4(\beta+\varepsilon)n_{1}+3k\leqslant 7k/2.$ (24)

For $x\in[-m,-m+3k)$, by (19) we get

$\bigg{|}(x-4k,x]\setminus A_{1}\bigg{|}\leqslant 7k/2.$ (25)

For $z\in[-m,0)$, by (21), (22), (25) we get

${\mathbb{P}}_{b_{3}\in[0,4k)\cap B_{1}}\bigg{(}z\in
A_{1}+b_{3}\bigg{)}\geqslant 1/16.$ (26)

Therefore, by (20) and (26) we conclude

${\mathbb{E}}_{b_{3}\in[0,4k)\cap B_{1}}\bigg{|}(A_{1}+b_{3})\cap
Z\bigg{|}=\sum_{z\in Z}{\mathbb{P}}_{b_{3}\in[0,4k)\cap B_{1}}\bigg{(}z\in
A_{1}+b_{3}\bigg{)}\geqslant k/32.$

This concludes the proof of Claim A. ∎

We now turn to the second case.

Case 2:

$\bigg{|}[-m-k,-m)\cap A_{1}\bigg{|}\leqslant k/2\text{ or }\bigg{|}[0,k)\cap
A_{1}\bigg{|}\leqslant k/2.$

In this case we may assume

$\bigg{|}[-m-k,-m)\cap A_{1}\bigg{|}\leqslant k/2\text{ and
}\bigg{|}[-\infty,-m-k)\cap A_{1}\bigg{|}\geqslant k/4.$ (27)

Put $Z=(-\infty,-m)\setminus A_{1}.$

Claim B.

${\mathbb{E}}_{b_{3}\in[0,k)\cap B_{1}}\bigg{|}(A_{1}+b_{3})\cap
Z\bigg{|}\geqslant k/32.$

In particular, there exists $b_{3}\in B_{1}$ such that
$\bigg{|}(A_{1}+b_{3})\cap Z\bigg{|}\geqslant k/32.$

###### Proof.

Let $S$ be set of the greatest $k/4$ elements of $[-\infty,-m-k)\cap A_{1}$.

For $x\in S$, by (27) we have

$\bigg{|}[x,x+k)\cap Z\bigg{|}\geqslant k/4.$ (28)

By (5), (10) and (16) we get

$\bigg{|}[0,k)\setminus B_{1}\bigg{|}\geqslant k-\bigg{|}[0,m)\setminus
B\bigg{|}-|B_{2}|\geqslant k-\beta n-n_{2}\geqslant
k-4(\beta+\varepsilon)n_{1}\geqslant 7k/8.$ (29)

For $x\in S$, by (28) and (29) we have ${\mathbb{P}}_{b_{3}\in[0,k)\cap
B_{1}}\bigg{(}x+b_{3}\in Z\bigg{)}\geqslant 1/8$, so

${\mathbb{E}}_{b_{3}\in[0,k)\cap B_{1}}\bigg{|}(A_{1}+b_{3})\cap
Z\bigg{|}=\sum_{x\in S}{\mathbb{P}}_{b_{3}\in[0,k)\cap
B_{1}}\bigg{(}x+b_{3}\in Z\bigg{)}\geqslant k/32.$

This ends the proof of Claim B. ∎

We now return to the proof of Theorem 9. By construction, we have

$A_{1}+\\{0,b_{2},b_{3},m\\}\supset$
$A_{l}\sqcup(A_{r}+m)\sqcup\bigg{(}[A_{c}\cup(A_{c}+b_{2})\cup(A_{c}+m)]\cap
Y^{c}\bigg{)}\sqcup\bigg{(}(A_{1}+b_{3})\cap Z\bigg{)}.$

So by Claim A and Claim B, together with (11), (15), (16) and (17), we obtain

$\displaystyle 2n_{1}-1+8\varepsilon n_{1}$ $\displaystyle\geqslant$
$\displaystyle
k+(k-\tau)+(2n_{1}-1-2k+\tau-\frac{(2k-\tau-1)^{2}}{n_{1}-1})+\frac{k}{32}$
$\displaystyle\geqslant$ $\displaystyle
2n_{1}-1+\frac{k}{32}-\frac{(2k-\tau-1)^{2}}{n_{1}-1}\geqslant
2n_{1}-1+\frac{k}{32}-\frac{4k^{2}}{n_{1}}$ $\displaystyle\geqslant$
$\displaystyle 2n_{1}-1+\frac{k}{64}.$

Therefore we have $k\leqslant 2^{9}\varepsilon n_{1}.$

Finally, we conclude the arithmetic progression
$P^{\prime}=\\{0,d,\ldots,md\\}$ with common difference $d$ and size at most
$\lfloor(1+\beta)n\rfloor\leqslant\lfloor(1+\mu)n\rfloor$ satisfies
$|A\setminus P^{\prime}|\leqslant n_{2}+2k\leqslant 2^{11}\varepsilon
n\leqslant\mu n.$

This finishes the proof of Theorem 9. ∎

We now prove Theorem 8.

###### Proof of Theorem 8.

Fix $\delta<2^{-10}$ and choose $\varepsilon=2^{-40}\delta^{8}$. By Theorem 3,
we may assume that $\varepsilon n\geqslant 1$. In particular, we have
$\varepsilon^{1/2}n\geqslant 2^{20}$ and $\varepsilon^{1/8}\leqslant 2^{-10}$.
We may also assume that $\min(B)=0$ and $\max(B)=m$.

The proof will proceed via the next three lemmas.

######  Lemma 10.

$|\pi_{m}(A)|\geqslant(1-4\varepsilon^{1/4})n.$

###### Proof.

The proof of this lemma is based on two claims. Suppose for a contradiction
that

$|\widetilde{A}|\leqslant(1-4\varepsilon^{1/4})n.$

Claim A. There exists $b_{1}\in B$ such that

$\bigg{|}A+\\{0,b_{1},m\\}\bigg{|}\geqslant 2n-1-2^{-1}\varepsilon^{1/2}n$

and

$\bigg{|}\pi_{m}[A+\\{0,b_{1},m\\}]\bigg{|}\leqslant\big{(}1-\varepsilon^{1/2}\big{)}n.$

###### Proof.

By Theorem 7 we have

${\mathbb{E}}_{b\in B\setminus\\{m\\}}\bigg{|}A+\\{0,b,m\\}\bigg{|}\geqslant
2n-1.$

By hypothesis we have

$\max_{b\in B}\bigg{|}A+\\{0,b,m\\}\bigg{|}\leqslant 2n-1+\varepsilon n.$

By Markov’s inequality, it follows that

${\mathbb{P}}_{b\in
B\setminus\\{m\\}}\bigg{(}\bigg{|}A+\\{0,b,m\\}\bigg{|}\geqslant
2n-1-2^{-1}\varepsilon^{1/2}n\bigg{)}>1-4\varepsilon^{1/2}.$ (30)

Now form the partition $A=A_{1}\sqcup A_{2}$ such that

$A_{1}^{x}=\begin{cases}A^{x}\text{ if }|A^{x}|\geqslant 2,\\\ \emptyset\text{
if }|A^{x}|\leqslant 1.\end{cases}\text{ and
}A_{2}^{x}=\begin{cases}A^{x}\text{ if }|A^{x}|\leqslant 1,\\\ \emptyset\text{
if }|A^{x}|\geqslant 2.\end{cases}$ (31)

From $|\widetilde{A}|\leqslant(1-4\varepsilon^{1/4})n$ we get
$|A_{1}|\geqslant 4\varepsilon^{1/4}n$. Lemma 5 gives

$\displaystyle{\mathbb{E}}_{b\in
B\setminus\\{m\\}}\bigg{|}(A_{1}+b)\setminus\pi^{-1}(\widetilde{A})\bigg{|}$
$\displaystyle\geqslant$
$\displaystyle|A_{1}|\max\bigg{(}0,\frac{|\widetilde{B}|-|\widetilde{A}|}{|\widetilde{B}|}\bigg{)}$
$\displaystyle\geqslant$ $\displaystyle
4\varepsilon^{1/4}n\frac{n-1-(1-4\varepsilon^{1/4})n}{n-1}\geqslant
8\varepsilon^{1/2}n.$

Trivially, we have

$\max_{b\in
B\setminus\\{m\\}}\bigg{|}(A_{1}+b)\setminus\pi^{-1}(\widetilde{A})\bigg{|}\leqslant
n.$

By Markov’s inequality, we deduce

${\mathbb{P}}_{b\in
B\setminus\\{m\\}}\bigg{(}\bigg{|}(A_{1}+b)\setminus\pi^{-1}(\widetilde{A})\bigg{|}\geqslant
4\varepsilon^{1/2}n\bigg{)}>4\varepsilon^{1/2}.$ (32)

By (30) and (32), it follows that there exists $b_{1}\in B\setminus\\{m\\}$
such that

$\bigg{|}A+\\{0,b_{1},m\\}\bigg{|}\geqslant 2n-1-2^{-1}\varepsilon^{1/2}n$

and

$\bigg{|}(A_{1}+b_{1})\setminus\pi^{-1}(\widetilde{A})\bigg{|}\geqslant
4\varepsilon^{1/2}n.$ (33)

By (1), together with (4), (31) and (33), it follows that

$\displaystyle 2n-1+\varepsilon n\geqslant\bigg{|}A+\\{0,b_{1},m\\}\bigg{|}$
$\displaystyle\geqslant$
$\displaystyle\bigg{|}A\cup(A+m)\bigg{|}+\bigg{|}[A+b_{1}]\setminus[A\cup(A+m)]\bigg{|}$
$\displaystyle\geqslant$
$\displaystyle|A|+|\widetilde{A}|+\bigg{|}(A+b_{1})\setminus\pi_{m}^{-1}(\widetilde{A})\bigg{|}$
$\displaystyle\geqslant$
$\displaystyle|A|+|\widetilde{A}|+\bigg{|}(\widetilde{A}+\widetilde{b}_{1})\setminus\widetilde{A}\bigg{|}+\frac{1}{2}\bigg{|}(A_{1}+b_{1})\setminus\pi_{m}^{-1}(\widetilde{A})\bigg{|}$
$\displaystyle\geqslant$
$\displaystyle(1+2\varepsilon^{1/2})n+\bigg{|}\widetilde{A}\cup(\widetilde{A}+\widetilde{b}_{1})\bigg{|}.$

Hence

$\bigg{|}\pi_{m}[A+\\{0,b_{1},m\\}]\bigg{|}=\bigg{|}\widetilde{A}\cup(\widetilde{A}+\widetilde{b}_{1})\bigg{|}\leqslant\big{(}1-\varepsilon^{1/2}\big{)}n.$

This establishes Claim A. ∎

Claim B.

${\mathbb{E}}_{b_{2}\in
B\setminus\\{m\\}}\bigg{|}A+\\{0,b_{1},b_{2},m\\}\bigg{|}>2n-1+\varepsilon n.$

###### Proof.

From the first part of Claim A we get

$\bigg{|}A+\\{0,b_{1},m\\}\bigg{|}\geqslant 2n-1-2^{-1}\varepsilon^{1/2}n$

From the second part of Claim A and Lemma 5 we get

$\displaystyle{\mathbb{E}}_{b_{2}\in
B\setminus\\{m\\}}\bigg{|}[A+b_{2}]\setminus[A+\\{0,b_{1},m\\}]\bigg{|}$
$\displaystyle\geqslant$ $\displaystyle{\mathbb{E}}_{b_{2}\in
B\setminus\\{m\\}}\bigg{|}[A+b_{2}]\setminus\pi_{m}^{-1}[\widetilde{A}\cup(\widetilde{A}+\widetilde{b}_{1})]\bigg{|}$
$\displaystyle\geqslant$
$\displaystyle|A|\max\bigg{(}0,\frac{|\widetilde{B}|-|\widetilde{A}\cup(\widetilde{A}+\widetilde{b}_{1})|}{|\widetilde{B}|}\bigg{)}$
$\displaystyle\geqslant$ $\displaystyle
n\max\bigg{(}0,\frac{n-1-(1-\varepsilon^{1/2})n}{n-1}\bigg{)}\geqslant\frac{3}{4}\varepsilon^{1/2}n.$

Combining the inequalities above, we obtain

${\mathbb{E}}_{b_{2}\in
B\setminus\\{m\\}}\bigg{|}A+\\{0,b_{1},b_{2},m\\}\bigg{|}\geqslant
2n-1+\frac{1}{4}\varepsilon^{1/2}n>2n-1+\varepsilon n.$

This proves Claim B. ∎

This completes the proof of Lemma 10, as we see that we have our desired
contradiction. ∎

We now move on to our second lemma.

######  Lemma 11.

There exists an arithmetic progression $Q$ of size
$\lfloor(1+32\varepsilon^{1/4})n\rfloor$ such that $B\subset Q$.

###### Proof.

The proof of this lemma is based on the following two claims.

Claim A. For every $\widetilde{c}\in\widetilde{B}+\widetilde{B}$ there exists
a set $\widetilde{A}^{\prime}\subset\widetilde{A}$ such that

$\widetilde{A}^{\prime}+\widetilde{c}\subset\widetilde{A}\text{ and
}|\widetilde{A}^{\prime}|\geqslant(1-10\varepsilon^{1/4})n.$

###### Proof.

Let $b_{1},b_{2}\in B$ such that
$\widetilde{c}=\widetilde{b}_{1}+\widetilde{b}_{2}$, and fix
$b\in\\{b_{1},b_{2}\\}$. By (4), (1) and Lemma 10 we have

$\displaystyle 2n-1+\varepsilon n$ $\displaystyle\geqslant$
$\displaystyle\bigg{|}A+\\{0,b,m\\}\bigg{|}\geqslant\bigg{|}A\cup(A+m)\bigg{|}+\bigg{|}[A+b]\setminus[A\cup(A+m)]\bigg{|}$
$\displaystyle\geqslant$
$\displaystyle|A|+|\widetilde{A}|+\bigg{|}(\widetilde{A}+\widetilde{b})\setminus\widetilde{A}\bigg{|}\geqslant(2-4\varepsilon^{1/4})n+\bigg{|}(\widetilde{A}+\widetilde{b})\setminus\widetilde{A}\bigg{|}.$

Therefore
$\bigg{|}(\widetilde{A}+\widetilde{b})\setminus\widetilde{A}\bigg{|}\leqslant
5\varepsilon^{1/4}n,$ and in particular, we have
$\bigg{|}(\widetilde{A}+\widetilde{c})\setminus\widetilde{A}\bigg{|}\leqslant
10\varepsilon^{1/4}n.$ We conclude that the set
$\widetilde{A}^{\prime}=\\{\widetilde{a}\in\widetilde{A}\text{ :
}\widetilde{a}+\widetilde{c}\in\widetilde{A}\\}$ has size
$|\widetilde{A}^{\prime}|\geqslant(1-10\varepsilon^{1/4})n$, so Claim A is
proved. ∎

Claim B.

$|\widetilde{B}+\widetilde{B}|\leqslant(1+32\varepsilon^{1/4})|\widetilde{B}|.$

###### Proof.

Recall that $|\widetilde{A}|\leqslant n\text{ and }|\widetilde{B}|=n-1.$
Consider the set

$E(\widetilde{A})=\\{(a_{1},a_{2},a_{3},a_{4})\in\widetilde{A}^{4}\text{ :
}a_{1}-a_{2}=a_{3}-a_{4}\\}.$

Trivially, $|E(\widetilde{A})|\leqslant n^{3}.$ On the other hand, by the
previous claim we have
$|E(\widetilde{A})|\geqslant(1-10\varepsilon^{1/4})^{2}n^{2}|\widetilde{B}+\widetilde{B}|.$
This completes the proof of Claim B. ∎

Returning to the proof of Lemma 11, by Claim B we have
$|\widetilde{B}+\widetilde{B}|\leqslant(1+32\varepsilon^{1/4})|\widetilde{B}|.$
Kneser’s inequality [9] now implies that $\widetilde{B}+\widetilde{B}$ is a
union of cosets of a subgroup $\widetilde{H}$ of $\mathbb{Z}_{m}$ with
$|\widetilde{H}|\geqslant(1-32\varepsilon^{1/4})|\widetilde{B}|.$ Because
$0\in\widetilde{B}$, it follows that
$\widetilde{B}+\widetilde{B}=\widetilde{H}$ where
$|\widetilde{H}|\leqslant(1+32\varepsilon^{1/4})|\widetilde{B}|$ and
$|\widetilde{B}\setminus\widetilde{H}|=0.$ If we let $Q$ be the unique
arithmetic progression in $\mathbb{Z}$ satisfying $\\{0,m\\}\subset
Q\subset[0,m]$ and $\pi_{m}(Q)=\widetilde{H}$ then we can conclude that
$|Q|=1+|\widetilde{H}|\leqslant(1+32\varepsilon^{1/4})n\text{ and }B\subset
Q.$ This finishes the proof of Lemma 11. ∎

Our final lemma is as follows.

######  Lemma 12.

There exists a translate $P$ of $Q$ such that $|A\setminus P|\leqslant
16\varepsilon^{1/8}n.$

###### Proof.

Let $X$ be the set of the first $\varepsilon^{1/8}n$ elements of $A$, and
assume that

$0=\min(B)=\min(Q)\text{ and }m=\max(B)=\max(Q).$

Suppose for a contradiction that for every $x\in X$ we have $|(x+Q)\cap
A|\leqslant(1-16\varepsilon^{1/8})n,$ so, in particular, $|(x+B)\cap
A|\leqslant(1-16\varepsilon^{1/8})n.$ On the one hand, from this assumption we
get

$\displaystyle{\mathbb{E}}_{b\in
B}\bigg{(}[X+b]\setminus[A\cup(A+m)]\bigg{)}=\sum_{x\in X}{\mathbb{P}}_{b\in
B}\bigg{(}x+b\not\in A\cup(A+m)\bigg{)}$ $\displaystyle=$
$\displaystyle\sum_{x\in X}{\mathbb{P}}_{b\in B}\bigg{(}x+b\not\in
A\cup(X+m)\bigg{)}=\sum_{x\in
X}\frac{\bigg{|}[x+B]\setminus[A\cup(X+m)]\bigg{|}}{|B|}$
$\displaystyle\geqslant$ $\displaystyle\sum_{x\in
X}\max\bigg{(}0,\frac{|B|-|(x+B)\cap A|-|X|}{|B|}\bigg{)}$
$\displaystyle\geqslant$
$\displaystyle\varepsilon^{1/8}n\max\bigg{(}0,\frac{n-(1-16\varepsilon^{1/8})n-\varepsilon^{1/8}n}{n}\bigg{)}=15\varepsilon^{1/4}n.$

On the other hand, from (4), (1) and Lemma 10 we have

$\displaystyle 2n-1+\varepsilon n\geqslant\max_{b\in
B}\bigg{|}A+\\{0,b,m\\}\bigg{|}$ $\displaystyle\geqslant$
$\displaystyle\bigg{|}A\cup(A+m)\bigg{|}+\max_{b\in
B}\bigg{|}[A+b]\setminus[A\cup(A+m)]\bigg{|}$ $\displaystyle\geqslant$
$\displaystyle|A|+|\widetilde{A}|+\max_{b\in
B}\bigg{|}[A+b]\setminus[A\cup(A+m)]\bigg{|}$ $\displaystyle\geqslant$
$\displaystyle(2-4\varepsilon^{1/4})n+\max_{b\in
B}\bigg{|}[A+b]\setminus[A\cup(A+m)]\bigg{|}.$

This is a contradiction, as desired, completing our proof. ∎

With this, we have proved Theorem 8, since it is implied by Lemma 11 and Lemma
12. ∎

To end this section, we prove Theorem 2.

###### Proof of Theorem 2.

The strategy is to first apply Theorem 8, and then apply Theorem 9 twice.
Consider the function $\delta(\varepsilon)$ given by Theorem 8, and the
functions $\nu(\alpha,\beta,\varepsilon),\mu(\alpha,\beta,\varepsilon)$ given
by Theorem 9. It is easy to check that $\delta\rightarrow 0\text{ as
}\varepsilon\rightarrow 0,$ and $\mu,\nu\rightarrow 0\text{ as
}\alpha,\beta,\varepsilon\rightarrow 0.$ It is also a simple computational
task to find $c>0$ such that
$\mu_{1}=\mu(\delta(\varepsilon),\delta(\varepsilon),\varepsilon)$,
$\nu_{1}=\nu(\delta(\varepsilon),\delta(\varepsilon),\varepsilon)$,
$\mu_{2}=\mu(\mu_{1},\nu_{1},\varepsilon)$ and
$\nu_{2}=\nu(\mu_{1},\nu_{1},\varepsilon)$ satisfy

$\mu_{2}\leqslant c\varepsilon\text{ and
}\nu_{2}\leqslant\varepsilon+c\varepsilon^{2}\text{ as }\varepsilon\rightarrow
0.$

The result follows from these estimates. ∎

To end the paper, we give one of the many possible conjectures.

Our inverse theorem about $\mathbb{Z}$, Theorem 2, involves taking four
elements from $B$ instead of three elements. We believe that a similar result
should hold with three elements. We state this as a conjecture in the weaker
form corresponding to Theorem 8 instead of Theorem 2, although we do believe
that the stronger form should be true as well.

######  Conjecture 13.

For every $\delta>0$ there exists $\varepsilon>0$ such that the following is
true. Suppose that $A$ and $B$ are finite subsets of ${\mathbb{Z}}$ of equal
size $n$ such that for any elements $b_{1},b_{2},b_{3}\in B$ we have

$|A+\\{b_{1},b_{2},b_{3}\\}|\leqslant(2+\varepsilon)n-1.$

Then there exist arithmetic progressions $P,Q$ in $\mathbb{Z}$ with the same
common difference such that

$B\subset Q\text{ and }|A\Delta P|,|B\Delta Q|\leqslant\delta n.$

We remark that if this conjecture is proved then, by virtue of Theorem 7, it
would actually yield a strengthening of itself in which $|B\Delta
Q|\leqslant(1+o(1))\varepsilon n$. However, as we remarked earlier, it is
important to note, for Conjecture 3, that the selection of three elements
cannot be done as in Theorem 1, by taking the maximum and minimum elements of
$B$ plus one more element.

## References

  * [1] Bollobás, B., I. Leader and M. Tiba, Large sumsets from small sumsets, arXiv:2204.07559, 52 pp.
  * [2] Breuillard, E., B. Green and T. Tao, Small doubling in groups, in Erdős Centennial, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013, pp. 129–151.
  * [3] Cauchy, A., Recherches sur les nombres, J. École Polytechnique 9 (1813) 99–116. Also de Cauchy, A.L., Recherches sur les nombres, Œuvres (2nd series, Paris, 1882), vol. 1, pp. 39–63.
  * [4] Davenport, H., On the addition of residue classes, J. London Math. Soc. 10 (1935) 30–32.
  * [5] Davenport, H., A historical note, J. London Math. Soc. 22 (1947) 100–101.
  * [6] Freǐman, G.A., The addition of finite sets I, Izv. Vysš. Učebn. Zaved. Matematika 6 (1959) 202–213. (in Russian)
  * [7] Freǐman, G.A., Inverse problems of additive number theory VI, On the addition of finite sets III, Izv. Vysš. Učebn. Zaved. Matematika 28 (1962) 151–157. (in Russian)
  * [8] Grynkiewicz, D. Structural additive theory. 30. Springer Science and Business Media, 2013, xii+426 pp.
  * [9] Kneser, M., Summenmengen in lokalkompakten abelschen Gruppen, Math. Z. 66 (1956) 88–110.
  * [10] Lev, V.F., and P.Y. Smeliansky, On addition of two distinct sets of integers, Acta Arith. 70 (1995) 85–91.
  * [11] Nathanson, M.B., Additive Number Theory. Inverse Problems and the Geometry of Sumsets, Graduate Texts in Mathematics 165, Springer-Verlag, New York, 1996, xiv+293 pp.
  * [12] Stanchescu, Y., On addition of two distinct sets of integers, Acta Arith. 75 (1996) 191–194.
  * [13] Tao, T. and V.H. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, Cambridge, 2006, xviii+512 pp.


# How Deep is the Feature Analysis underlying Rapid Visual Categorization?

Sven Eberhardt Jonah Cader††footnotemark:  Thomas Serre
Department of Cognitive Linguistic & Psychological Sciences
Brown Institute for Brain Sciences
Brown University
Providence, RI 02818
<EMAIL_ADDRESS>These authors contributed equally.

###### Abstract

Rapid categorization paradigms have a long history in experimental psychology:
Characterized by short presentation times and speedy behavioral responses,
these tasks highlight the efficiency with which our visual system processes
natural object categories. Previous studies have shown that feed-forward
hierarchical models of the visual cortex provide a good fit to human visual
decisions. At the same time, recent work in computer vision has demonstrated
significant gains in object recognition accuracy with increasingly deep
hierarchical architectures. But it is unclear how well these models account
for human visual decisions and what they may reveal about the underlying brain
processes.

We have conducted a large-scale psychophysics study to assess the correlation
between computational models and human participants on a rapid animal vs. non-
animal categorization task. We considered visual representations of varying
complexity by analyzing the output of different stages of processing in three
state-of-the-art deep networks. We found that recognition accuracy increases
with higher stages of visual processing (higher level stages indeed
outperforming human participants on the same task) but that human decisions
agree best with predictions from intermediate stages.

Overall, these results suggest that human participants may rely on visual
features of intermediate complexity and that the complexity of visual
representations afforded by modern deep network models may exceed those used
by human participants during rapid categorization.

##  1 Introduction

Our visual system is remarkably fast and accurate. The past decades of
research in visual neuroscience have demonstrated that visual categorization
is possible for complex natural scenes viewed in rapid tasks. Participants can
reliably detect and later remember visual scenes embedded in continuous
streams of images with exposure times as low as 100 ms [see Potter, 2012, for
review]. Observers can also reliably categorize animal vs. non-animal images
(and other classes of objects) even when flashed for 20 ms or less [see Fabre-
Thorpe, 2011, for review].

Unlike normal everyday vision which involves eye movements and shifts of
attention, rapid visual categorization is assumed to involve a single
feedforward sweep of visual information [see VanRullen, 2007, for review] and
engages our core object recognition system [reviewed in DiCarlo et al., 2012].
Incorrect responses during rapid categorization tasks are not uniformly
distributed across stimuli (as one would expect from random motor errors) but
tend to follow a specific pattern reflecting an underlying visual strategy
[Cauchoix et al., 2016]. Various computational models have been proposed to
describe the underlying feature analysis [see Crouzet and Serre, 2011, for
review]. In particular, a feedforward hierarchical model constrained by the
anatomy and the physiology of the visual cortex was shown to agree well with
human behavioral responses [Serre et al., 2007].

In recent years, however, the field of computer vision has championed the
development of increasingly deep and accurate models – pushing the state of
the art on a range of categorization problems from speech and music to text,
genome and image categorization [see LeCun et al., 2015, for a recent review].
From AlexNet [Krizhevsky et al., 2012] to VGG [Simonyan and Zisserman, 2014]
and Microsoft CNTK [He et al., 2015], over the years, the ImageNet Large Scale
Visual Recognition Challenge (ILSVRC) has been won by progressively deeper
architectures. Some of the ILSVRC best performing architectures now include
150 layers of processing [He et al., 2015] and even 1,000 layers for other
recognition challenges [He et al., 2016] – arguably orders of magnitude more
than the visual system (estimated to be $\mathcal{O}(10)$ [Serre et al.,
2007]). Despite the absence of neuroscience constraints on modern deep
learning networks, recent work has shown that these architectures explain
neural data better than earlier models [reviewed in Yamins and DiCarlo, 2016]
and are starting to match human level of accuracy for difficult object
categorization tasks [He et al., 2015].

It thus raises the question whether recent deeper network architectures better
account for speeded behavioral responses during rapid categorization tasks or
whether they have actually become too deep – instead deviating from human
results. Here, we describe a rapid animal vs. non-animal visual categorization
experiment that probes this question. We considered visual representations of
varying complexity by analyzing the output of different stages of processing
in state-of-the-art deep networks [Krizhevsky et al., 2012, Simonyan and
Zisserman, 2014]. We show that while recognition accuracy increases with
higher stages of visual processing (higher level stages indeed outperforming
human participants for the same task) human decisions agreed best with
predictions from intermediate stages.

##  2 Methods

### Image dataset

A large set of (target) animal and (distractor) non-animal stimuli was created
by sampling images from ImageNet [Deng et al., 2009]. We balanced the number
of images across basic categories from 14 high-level synsets, to curb biases
that are inherent in Internet images. (We used the invertebrate, bird,
amphibian, fish, reptile, mammal, domestic cat, dog, structure,
instrumentation, consumer goods, plant, geological formation, and natural
object subtrees.) To reduce the prominence of low-level visual cues, images
containing animals and objects on a white background were discarded. All
pictures were converted to grayscale and normalized for illumination. Images
less than 256 pixels in either dimension were similarly removed and all other
images were cropped to a square and scaled to 256 $\times$ 256 pixels. All
images were manually inspected and mislabeled images and images containing
humans were removed from the set ($\sim$ 17% of all images). Finally, we drew
stimuli uniformly (without replacement) from all basic categories to create
balanced sets of 300 images. Each set contained 150 target images (half mammal
and half non-mammal animal images) and 150 distractors (half artificial
objects and half natural scenes). We created 7 such sets for a total of 2,100
images used for the psychophysics experiment described below.

### Participants

Rapid visual categorization data was gathered from 281 participants using the
Amazon Mechanical Turk (AMT) platform (www.mturk.com). AMT is a powerful tool
that allows the recruitment of massive trials of anonymous workers screened
with a variety of criteria [Crump et al., 2001].

All participants provided informed consent electronically and were compensated
$4.00 for their time ($\sim$ 20–30 min per image set, 300 trials). The
protocol was approved by the University IRB and was carried out in accordance
with the provisions of the World Medical Association Declaration of Helsinki.

### Experimental procedure

On each trial, the experiment ran as follows: On a white background (1) a
fixation cross appeared for a variable time (1,100–1,600 ms); (2) a stimulus
was presented for 50 ms. The order of image presentations was randomized.
Participants were instructed to answer as fast and as accurately as possible
by pressing either the “S” or “L” key depending on whether they saw an animal
(target) or non-animal (distractor) image. Key assignment was randomized for
each participant.

Participants were forced to respond within 500 ms (a message was displayed in
the absence of a response past the response deadline). In past studies, this
has been shown to yield reliable behavioral data [e.g. Sofer et al., 2015]. We
have also run a control to verify that the maximum response time did not
affect qualitatively our results.

Figure 1: Experimental paradigm and stimulus set: (top) Each trial began with
a fixation cross (1,100–1,600 ms), followed by an image presentation ($\sim$
50 ms). Participants were forced to answer within 500 ms. A message appeared
when participants failed to respond in the allotted time. (bottom) Sample
stimuli from the balanced set of animal and non-animal images (n=2,100).

An illustration of the experimental paradigm is shown in Figure 1. At the end
of each block, participants received feedback about their accuracy. An
experiment started with a short practice during which participants were
familiarized with the task (stimulus presentation was slowed down and
participants were provided feedback on their response). No other feedback was
provided to participants during the experiment.

We used the psiTurk framework [McDonnell et al., 2012] combined with custom
javascript functions. Each trial (i.e., fixation cross followed by the
stimulus) was converted to a HTML5-compatible video format to provide the
fastest reliable presentation time possible in a web browser. Videos were
generated to include the initial fixation cross and the post-presentation
answer screen with the proper timing as described above. Videos were preloaded
before each trial to ensure reliable image presentation times over the
Internet.

We used a photo-diode to assess the reliability of the timing on different
machines including different OS, browsers and screens and found the timing to
be accurate to $\sim$ 10 ms. Images were shown at a resolution of 256$\times$
256\. We estimate this to a stimulus size between approximately $5^{o}-11^{o}$
visual angle depending on the participants’ screen size and specific seating
arrangement.

The subjects pool was limited to users connections from the United States
using either the Firefox or Chrome browser on a non-mobile device. Subjects
also needed to have a minimal average approval rating of 95% on past
Mechanical Turk tasks.

As stated above, we ran 7 experiments altogether for a total of 2,100 unique
images. Each experiment lasted 20-30 min and contained a total of 300 trials
divided into 6 blocks (50 image presentations / trials each). Six of the
experiments followed the standard experimental paradigm described above (1,800
images and 204 participants). The other 300 images and 77 participants were
reserved for a control experiment in which the maximum reaction time per block
was set to 500 ms, 1,000 ms, and 2,000 ms for two block each. (See below.)

Figure 2: Model decision scores: A classifier (linear SVM) is trained on
visual features corresponding to individual layers from representative deep
networks. The classifier learns a decision boundary (shown in red) that best
discriminates target/animal and distractor/non-animal images. Here, we
consider the signed distance from this decision boundary (blue dotted lines)
as a measure of the model’s confidence on the classification of individual
images. A larger distance indicates higher confidence. For example, while
images (a) and (b) are both correctly classified, the model’s confidence for
image (a) correctly classified as animal is higher than that of (b) correctly
classified as non-animal. Incorrectly classified images, such as (c) are
assigned negative scores corresponding to how far onto the wrong side of the
boundary they fall.

### Computational models

We tested the accuracy of individual layers from state-of-the-art deep
networks including AlexNet [Krizhevsky et al., 2012], VGG16 and VGG19
[Simonyan and Zisserman, 2014]. Feature responses were extracted from
different processing stages (Caffe implementation [Jia et al., 2014] using
pre-trained weights). For fully connected layers, features were taken as is;
for convolutional layers, a subset of 4,096 features was extracted via random
sampling. Model decisions were based on the output of a linear SVM (scikit-
learn [Pedregosa et al., 2011] implementation) trained on 80,000 ImageNet
images ($C$ regularization parameter optimized by cross-validation).
Qualitatively similar results were obtained with regularized logistic
regression. Feature layer accuracy was computed from SVM performance.

Model confidence for individual test stimuli was defined as the distance from
the decision boundary (see Figure 2). A similar confidence score was computed
for human participants by considering the fraction of correct responses for
individual images. Spearman’s rho rank-order correlations ($r_{s}$) was
computed between classifier confidence outputs and human decision scores.
Bootstrapped 95% confidence intervals (CIs) were calculated on human-model
correlation and human classification scores. Bootstrap runs (n=300) were based
on 180 participants sampled with replacement from the subject pool. CIs were
computed by considering the bottom 2.5% and top 97.5% values as upper and
lower bounds.

##  3 Results

We computed the accuracy of individual layers from commonly used deep
networks: AlexNet [Krizhevsky et al., 2012] as well as VGG16 and VGG19
[Simonyan and Zisserman, 2014]. The accuracy of individual layers for networks
pre-trained on the ILSVRC 2012 challenge (1,000 categories) is shown in Figure
3 (a). The depth of individual layers was normalized with respect to the
maximum depth as layer depth varies across models. In addition, we fine-tuned
VGG16 on the animal vs. non-animal categorization task at hand. Accuracy for
all models increased monotonically (near linearly) as a function of depth to
reach near perfect accuracy for the top layers for the best networks (VGG16).
Indeed, all models exceeded human accuracy on this rapid animal vs. non-animal
categorization task. Fine-tuning did improve test accuracy slightly from 95.0%
correct to 97.0% correct on VGG16 highest layer, but the performance of all
networks remained high in the absence of any fine-tuning.

To benchmark these models, we assessed human participants’ accuracy and
reaction times (RTs) on this animal vs. non-animal categorization task. On
average, participants responded correctly with an accuracy of 77.4% ($\pm$
1.4%). These corresponded to an average d’ of 1.06 ($\pm$ 0.06). Trials for
which participants failed to answer before the deadline were excluded from the
evaluation (13.7% of the total number of trials).

Figure 3: Comparison between models and human behavioral data: (a) Accuracy
and (b) correlation between decision scores derived from various networks and
human behavioral data plotted as a function of normalized layers depth
(normalized by the maximal depth of the corresponding deep net). (c)
Superimposed accuracy and correlation between decision scores derived from the
best performing network (VGG16 fine-tuned (_ft_) for animal categorization)
and human behavioral data plotted as a function of the raw layers depth. Lines
are fitted polynomials of 2nd (accuracy) and 3rd (correlation) degree order.
Shaded red background corresponds to 95% CI estimated via bootstrapping shown
for fine-tuned VGG16 model only for readability. Gray curve corresponds to
human accuracy (CIs shown with dashed lines).

The mean RT for correct responses was 429 ms ($\pm$ 103 ms standard
deviation). We computed the minimum reaction time _MinRT_ defined as the first
time bin for which correct responses start to significantly outnumber
incorrect responses [Fabre-Thorpe, 2011]. The MinRT is often considered a
floor limit for the entire visuo-motor sequence (feature analysis, decision
making, and motor response) and could be completed within a temporal window as
short as 370 ms $\pm$ 75 ms. We computed this using a binomial test (p < 0.05)
on classification accuracy from per-subject RT data sorted into 20 ms bins and
found the median value of the corresponding distribution.

Figure 4: Sample images where human participants and model (VGG16 layer fc7)
disagree. H: Average human decision score (% correct). M: Model decision score
(distance to decision boundary).

Confidence scores for each of the 1,800 (animal and non-animal) main
experiment images were calculated for human participants and all the
computational models. The resulting correlation coefficients are shown in
Figure 3 (b). Human inter-subject agreement, measured as Spearman’s rho
correlation between 1,000 randomly selected pairs of bootstrap runs, is at
$\rho=0.74$ ($\pm$ 0.05%). Unlike individual model layer accuracy which
increases monotonically, the correlation between these same model layers and
human participants picked for intermediate layers and decreased for deeper
layers. This drop-off is stable across all tested architectures and started
around at 70% of the relative model depth. For comparison, we re-plotted the
accuracy of the individual layers and correlation to human participants for
the best performing model (VGG16 fine-tuned) in Figure 3 (c). The drop-off in
correlation to human responses begins after layer conv5_2.

Example images in which humans and VGG16 top layer disagree are shown in
Figure 4. The model typically outperforms humans on elongated animals such as
snakes and worms, as well as camouflaged animals and when objects are
presented in an atypical context. Human participants outperform the model on
typical, iconic illustrations such as a cat looking directly at the camera.

We verified that the maximum response time (500 ms) allowed did not
qualitatively affect our results. We ran a control experiment (77
participants) on a set of 300 images where we systematically varied the
maximum response time available (500 ms, 1,000 ms and 2,000 ms). We evaluated
differences in categorization accuracy using a one-way ANOVA with Tukey’s HSD
for post-hoc correction. The accuracy increased significantly from 500 to
1,000 ms (from 74 % to 84 %; p < 0.01). However, no significant difference was
found between 1,000 and 2,000 ms (both $\pm$ 84%; p > 0.05). Overall, we found
no qualitative difference in the observed pattern of correlation between human
and model decision scores for longer response times (results not shown). We
found an overall slight upward trend for both intermediate and higher layers
for longer response times.

##  4 Discussion

The goal of this study was to perform a computational-level analysis aimed at
characterizing the visual representations underlying rapid visual
categorization.

To this end, we have conducted a large-scale psychophysics study using a fast-
paced animal vs. non-animal categorization task. This task is ecologically
significant and has been extensively used in previous psychophysics studies
[reviewed in Fabre-Thorpe, 2011]. We have considered 3 state-of-the-art deep
networks: AlexNet [Krizhevsky et al., 2012] as well as VGG16 and VGG19
[Simonyan and Zisserman, 2014]. We have performed a systematic analysis of the
accuracy of these models’ individual layers for the same animal/non-animal
categorization task. We have also assessed the agreement between model and
human decision scores for individual images.

Overall, we have found that the accuracy of individual layers consistently
increased as a function of depth for all models tested. This result confirms
the current trend in computer vision that better performance on recognition
challenges is typically achieved by deeper networks. However, the correlation
between model and human decision scores peaked at intermediate layers and
decreased for deeper layers. These results suggest that human participants may
rely on visual features of intermediate complexity and that the complexity of
visual representations afforded by modern deep network models may exceed those
used by human participants during rapid categorization. In particular, the
maximum correlation observed after $\sim$ 10 layers of processing in the best
performing network (VGG16) seems consistent with the number of processing
stages found in the ventral stream of the visual cortex Serre et al. [2007],
which has been implicated in the recognition of objects.

How then does the visual cortex achieve greater depth of processing when more
time is allowed for categorization? One possibility is that speeded
categorization reflects partial visual processing up to intermediate levels
while longer response times would allow for deeper processing in higher
stages. We compared the agreement between model and human decisions scores for
longer response times (500 ms, 1,000 ms and 2,000 ms). While the overall
correlation increased slightly for longer response times, this higher
correlation did not appear to differentially affect high- vs. mid-level
layers.

An alternative hypothesis is that greater depth of processing for longer
response times is achieved via recurrent circuits and that greater processing
depth is achieved through time. The fastest behavioral responses would thus
correspond to bottom-up / feedforward processing. This would be followed by
re-entrant and other top-down signals [Gilbert and Li, 2013] when more time is
available for visual processing.

## Acknowledgments

We would like to thank Matt Ricci for his early contribution to this work and
further discussions. This work was supported by NSF early career award [grant
number IIS-1252951] and DARPA young faculty award [grant number YFA
N66001-14-1-4037]. Additional support was provided by the Center for
Computation and Visualization (CCV).

## References

  * Cauchoix et al. [2016] M. Cauchoix, S. M. Crouzet, D. Fize, and T. Serre.  Fast ventral stream neural activity enables rapid visual categorization.  _Neuroimage_ , 125:280–290, 2016.  ISSN 10538119.  doi: 10.1016/j.neuroimage.2015.10.012.
  * Crouzet and Serre [2011] S. M. Crouzet and T. Serre.  What are the Visual Features Underlying Rapid Object Recognition?  _Front. Psychol._ , 2(November):326, jan 2011\.  ISSN 1664-1078.  doi: 10.3389/fpsyg.2011.00326.
  * Crump et al. [2001] M. J. C. Crump, J. V. McDonnell, and T. M. Gureckis.  Evaluating Amazon’s Mechanical Turk as a tool for experimental behavioral research.  _PLoS ONE,8(3)_ , 2001.
  * Deng et al. [2009] J. Deng, W. Dong, R. Socher, L. Li, K. Li, and L. Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on_ , pages 248–255. IEEE, 2009.
  * DiCarlo et al. [2012] J. J. DiCarlo, D. Zoccolan, and N. C. Rust.  How does the brain solve visual object recognition?  _Neuron, 73(104)_ , pages 415–434, 2012.
  * Fabre-Thorpe [2011] M. Fabre-Thorpe.  The characteristics and limits of rapid visual categorization.  _Front. Psychol._ , 2(October):243, jan 2011.  ISSN 1664-1078.  doi: 10.3389/fpsyg.2011.00243.
  * Gilbert and Li [2013] C. D. Gilbert and W. Li.  Top-down influences on visual processing.  _Nat. Rev. Neurosci._ , 14(5):350–63, may 2013\.  ISSN 1471-0048.  doi: 10.1038/nrn3476.
  * He et al. [2015] K. He, X. Zhang, S. Ren, and J. Sun.  Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification.  feb 2015.
  * He et al. [2016] K. He, X. Zhang, S. Ren, and J. Sun.  Identity mappings in deep residual networks.  _CoRR_ , abs/1603.05027, 2016.
  * Jia et al. [2014] Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, and T. Darrel.  Caffe: convolutional architecture for fast feature embedding.  In _Proceedings of the 2014 ACM Conference on Multimedia (MM 2014)_ , pages 10005–10014, 2014.
  * Krizhevsky et al. [2012] A. Krizhevsky, I. Sutskever, and G. E. Hinton.  ImageNet Classification with Deep Convolutional Neural Networks.  In _Advances in Neural Information Processing Systems 25 (NIPS 2012)_ , pages 1097–1105, 2012.
  * LeCun et al. [2015] Y. LeCun, Y. Bengio, and G. Hinton.  Deep Learning.  _Nature, 521_ , pages 436–444, 2015.
  * McDonnell et al. [2012] J. V. McDonnell, J. B. Martin, D. B. Markant, A. Coenen, A. S. Rich, and T. M. Gureckis.  psiturk (version 1.02)[software]. new york, ny: New york university. available from https://github.com/nyuccl/psiturk, 2012.
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine Learning in Python.  _J. Mach. Learn. Res._ , 12:2825–2830, 2011.
  * Potter [2012] M. C. Potter.  Recognition and memory for briefly presented scenes.  _Front. Psychol._ , 3:32, jan 2012.  ISSN 1664-1078.  doi: 10.3389/fpsyg.2012.00032.
  * Serre et al. [2007] T. Serre, A. Oliva, and T. Poggio.  A feedforward architecture accounts for rapid categorization.  _PNAS, 104(15)_ , pages 6424–6429, 2007.
  * Simonyan and Zisserman [2014] K. Simonyan and A. Zisserman.  Very Deep Convolutional Networks for Large-Scale Image Recognition.  Technical report, sep 2014.
  * Sofer et al. [2015] I. Sofer, S. M. Crouzet, and T. Serre.  Explaining the timing of natural scene understanding with a computational model of perceptual categorization.  _PLoS Comput Biol, 11(9)_ , page e1004456, 2015.
  * VanRullen [2007] R. VanRullen.  The power of the feed-forward sweep.  _Adv. Cogn. Psychol._ , 3(1-2):167–176, 2007\.
  * Yamins and DiCarlo [2016] D. L. K. Yamins and J. J. DiCarlo.  Using goal-driven deep learning models to understand sensory cortex.  _Nat. Neurosci._ , 19(3):356–365, feb 2016.  ISSN 1097-6256.  doi: 10.1038/nn.4244.