11institutetext: DENSO AUTOMOTIVE Deutschland GmbH, 85386 Eching, Germany
11email<EMAIL_ADDRESS>22institutetext: AIT Austrian Institute
of Technology GmbH, 1210 Vienna, Austria 22email:
<EMAIL_ADDRESS>
33institutetext: IMT School for Advanced Studies Lucca, 55100 Lucca, Italy
33email<EMAIL_ADDRESS>
# Specification-Guided Critical Scenario Identification for Automated Driving
††thanks:  This project has received funding from the European Union’s Horizon
2020 research and innovation programme under grant agreement No 956123.

Adam Molin 11 Edgar A. Aguilar 22 Dejan Ničković 22 Mengjia Zhu 33 Alberto
Bemporad 33 Hasan Esen 11

###### Abstract

To test automated driving systems, we present a case study for finding
critical scenarios in driving environments guided by formal specifications. To
that aim, we devise a framework for critical scenario identification, which we
base on open-source libraries that combine scenario specification, testing,
formal methods, and optimization.

###### Keywords:

Autonomous Vehicles Scenario Based Testing

##  1 Introduction

With the complexity of the automated driving (AD) system and its driving
environment, verification and validation (V&V) is regarded as one of the major
challenges of AD development [25]. _Scenario-based testing_ (SBT) was
introduced as an essential method for facilitating the overall safety
assurance of ADs. In SBT, the expected behavior of an AD system is described
by a representative set of scenarios that are relevant for its safe use. The
SBT paradigm facilitates shifting the AD testing from the physical to the
simulation environment. The use of virtual testing has manifold advantages –
more specifically it allows to: (1) explore efficiently a large number of
situations originating from the catalog of relevant scenarios, (2) reproduce
environment conditions (fog, night, rain, etc.) that are hard to enforce in a
physical environment, and (3) play dangerous scenarios without risk to humans,
other vehicles or infrastructure.

Despite significant advances in research and standardization of SBT, there are
still remaining open issues. One of them is to determine the critical
scenarios among the virtually infinite number of scenarios with an abundance
of influential factors ranging from weather or road conditions, to the
behaviors of surrounding road users. A first attempt to keep the number of
scenarios manageable is to restrict the operational design domain (ODD) of the
AD system. According to [20], the ODD is defined as the operating conditions
under which a given AD system is specifically designed to function. However,
there are some factors, including the dynamic behavior of the road users,
which cannot be controlled in the ODD. Thus, efficient methods are needed to
identify the critical scenarios from the scenario space within the ODD. An
extensive survey study on finding critical scenarios has been conducted in
[25]. With regard to specification-guided critical scenario identification,
our work is closely related to [8, 21, 23, 24].

In this paper, we present a specification-driven framework for critical
scenario identification (CSI) entirely based on open-source software libraries
and demonstrate its benefits with an automated emergency break case study. The
proposed framework, based on the falsification testing paradigm [18], uses
optimization-based methods for finding critical scenarios. We first describe
the vanilla workflow and show how to tailor it with custom test generation and
monitoring strategies. Hence, our aim is to share our experience in combining
existing methods into a flexible and efficient SBT framework. To innovate the
methodology for SBT within the framework, we investigate the separation
between the AD system and the other road users, modeling their interplay with
Assume/Guarantee (A/G) contracts. By using A/G contracts, we can improve the
search for meaningful scenarios, assign responsibility for critical situations
and distinguish between invalid behaviors originating from the AD system and
from its environment. In that way, we can detect the violation of environment
assumptions in the simulation execution, and discard the test run. By sharing
our experience in SBT, we intend to nurture the innovation of prospective CSI
methods that are based on specification-guided strategies.

##  2 Specification-Driven Scenario-Based Testing

###  2.1 Traffic scenario description

Figure 1: Scenario abstraction types according to [17].

In the operational domain in which the ADS will be deployed, it is exposed to
a potentially infinite number of traffic scenarios. As a consequence, it is
impractical to conduct testing - even in simulation - directly on these
traffic scenarios. A first step towards a successful application of scenario-
based testing to assure the correct behavior of an ADS within its ODD is the
abstraction of traffic scenarios. While the argumentation for quality
assurance is done on a higher level of abstraction, the creation of evidence
is performed on simulating a variety of concrete traffic scenarios derived
from the abstract ones. The PEGASUS project “for the establishment of
generally accepted quality criteria, tools and methods as well as scenarios
and situations for the release of highly-automated driving functions”,
introduced three abstraction types: functional, logical, concrete scenarios
[16]. In this paper, we use an extended classification proposed in [17], see
Fig. 1. Functional scenarios are defined as behavior-based, non-formal
descriptions of traffic scenarios in natural language. Abstract scenarios are
a formalization of functional scenarios using a declarative way to describe
the scenario. Logical scenarios are defined as a parameterized set of traffic
scenarios, while concrete scenarios are instances of a logical scenario with
fixed parameters. They have a fixed scenery and road user behavior, that is
based on the ego-vehicle movement. Abstract, logical, and concrete scenarios
are machine-readable, and various realizations of traffic scenario description
formats exist for simulation.

Table 1: Supported types and properties of scenario description formats  |  OSC1.2 |  OSC2.0 |  SCENIC
---|---|---|---
Scenario types |  |  |
Functional |  $\times$ |  $\times$ |  $\times$
Abstract |  $\times$ |  ✓ |  ✓
Logical |  ✓ |  ✓ |  ✓
Concrete |  ✓ |  ✓ |  ✓
Properties |  |  |
Syntax format |  XML111Extensible Markup Language |  DSL222Domain-specific language, pythonic |  DSL, pythonic
Language paradigm |  imperative |  mostly declarative |  declarative/ imperative
Map-agnostic scenario definition |  $\times$ |  ✓ |  ✓

In the following, we give a comparison between three non-proprietary, and
openly available scenario description formats: OpenSCENARIO®1.2 (OSC1.2) [3],
OpenSCENARIO®2.0 (OSC2.0) [4], and Scenic [12], see Tab. 1. With regard to the
overall traffic scenario, their focus is on the initial placement and the
dynamic behavior of the actors. The description of the scenery, such as the
map, is defined outside these formats. OSC1.2 is mainly used for describing
concrete traffic scenarios that can be directly run by the simulator. The
actors’ placement and behavior are defined in an imperative fashion using
pairs of actions and triggers that evoke these actions. OSC2.0’s and Scenic’s
main intent is to define abstract scenarios, which can be concretized by a
dedicated scenario generation engine. OSC2.0’s description is mostly
declarative by constraining the road users’ behavior. The probabilistic
programming language Scenic is declarative in the initial actor placement with
a rich instruction set for relationships between entities, and uses an
imperative description for behaviors. All three languages support
parameterization of scenario parameters to describe logical scenarios. A
distinctive feature of OSC2.0 and Scenic compared to OSC1.2 is that the
location of the scenario does not need to be specified within the scenario
definition. Instead, the scenario generation engine will find a suitable
segment on the road map, on which the scenario can be executed with all actors
in the simulator.

Based on the scenario format, a database of abstract/logical scenarios needs
to be created that covers all the relevant features in the considered ODD of
the AD function. In this paper, we selected Scenic as our scenario format, due
to both its flexibility in expressing abstract scenarios and the availability
of an open-source testing framework [9] that is provided for Scenic.

###  2.2 Critical scenario identification

This section introduces the test framework to find critical concrete scenario
instances within a specified abstract scenario efficiently and in a flexible
manner. The framework depicted in Fig. 2 indicating the overall workflow is
based on open-source software components highlighted in bold. It assumes two
inputs, the abstract scenario given in the Scenic format, and a formal
specification of the AD system defined in signal temporal logic (STL), that we
use as a test oracle. The technical details on the formal specification are
introduced in Sec. 2.3.

Figure 2: Critical scenario identification framework with tool architecture.

#### Workflow

The test execution framework is based on Berkeley’s VerifAI [9]. By applying a
sampling strategy, VerifAI generates concrete scenarios from the Scenic
scenario that are executed in the CARLA simulator [7]. To evaluate the
resulting trajectories, we integrated RTAMT - an STL monitoring library [19]
\- into the VerifAI-based testing framework. RTAMT provides the automated
generation of robustness monitors from STL specifications and therefore
facilitates checking simulation traces against the formal specification. The
robustness measure is then fed back as a criticality indicator to the scenario
sampler that determines new test parameters that constitute the next concrete
scenario to be simulated. Depending on the sampling strategy, the scenario
search can be of explorative or exploitative nature. Instead of using the
sampling strategies provided by VerifAI, we integrated an external sampling
strategy, that is based on the global optimizer GLIS [5]. The details about
GLIS are outlined in Sec. 2.4.

###  2.3 Formal Specifications

Concrete scenarios are typically evaluated against requirements. These
requirements can cover various aspects, including safety, legal, comfort and
ethical considerations. In order to avoid ambiguities and facilitate their
evaluation, there is a need to formulate requirements using a formal
specification language. In this paper, we adopt signal temporal logic (STL)
[15] as our specification formalism. There are several motivations to choose
STL for requirement formalization: (1) an existing body of work already
captures AD system requirements using STL, (2) STL admits quantitative
semantics that can be used to guide the search for critical scenarios, and (3)
there are runtime verification tools that enable evaluation of STL properties.
The syntax of STL is given by the grammar

$\displaystyle\varphi::=\top\mid
f(R)>0\mid\lnot\varphi\mid\varphi_{1}\lor\varphi_{2}\mid\varphi_{1}\operatorname{\mathcal{U}}_{I}\varphi_{2}\mid\varphi_{1}\operatorname{\mathcal{S}}_{I}\varphi
2\,,$

where $f(R)$ are terms in $\Theta$ and $I$ are real intervals with bounds in
$\mathbb{Q}_{\geq 0}\cup\\{\infty\\}$. As customary we use
$\operatorname{\lozenge}_{I}\varphi\equiv\top\operatorname{\mathcal{U}}_{I}\varphi$
for _eventually_ ,
$\operatorname{\Box}_{I}\varphi\equiv\lnot\operatorname{\lozenge}_{I}\lnot\varphi$
for _always_ , $\operatorname{\hbox{\zmsy\char
81\relax}}_{I}\varphi\equiv\top\operatorname{\mathcal{S}}_{I}\varphi$ for
_once_ and $\operatorname{\hbox{\zmsy\char
96\relax}}_{I}\varphi\equiv\lnot\operatorname{\hbox{\zmsy\char
81\relax}}_{I}\lnot\varphi$ for _historically_. The timing interval $I$ may be
omitted when $I=[0,\infty)$ or $I=(0,\infty)$. STL can be naturally equipped
with _quantitative semantics_ based on the infinity norm [6] that measure how
far is the observed behavior from satisfying or violating a requirement.

The evaluation of an AD system cannot be performed in isolation from its
environment. For instance, an AD system cannot guarantee safety requirements,
such as RSS, in presence of other road users that do not behave in a
reasonable manner. The relation of the AD system and the environment under
which it operates can be formalized in terms of a _contract_
$C=(\varphi,\psi)$, a pair of properties where $\varphi$ represents the
assumptions on the environment and $\psi$ guarantees of the system under these
assumptions. This classical interpretation of $C$ is given by the temporal
logic formula

$\operatorname{\Box}\varphi\to\operatorname{\Box}\psi.$

According to the above formula, any violation of the assumption by the
environment results in the (vacuous) satisfaction of the contract, even if the
system also violates its guarantee. However, this definition neglects that
these two violations may not be causally related – the violation of $\psi$ by
the system at time $t$ before the violation of $\varphi$ by the environment at
time $t^{\prime}>t$ still results in the satisfaction of the contract. To
address this situation, we propose a more refined notion of a contract that
takes the intended temporal causality between the environment and the AD
system into account. We denote our refined contract by $\hat{C}$ and capture
its meaning using the formula:

$\operatorname{\Box}((\operatorname{\hbox{\zmsy\char
96\relax}}_{[0,T]}\varphi)\to\psi)$

where $T$ specifies the maximum duration within which we consider the
violation of $\varphi$ to be causally related to the violation of $\psi$.

###  2.4 Sampling Strategy

Different sampling strategies may be used to identify the parameters of the
next concrete scenario to simulate. These strategies can be broadly divided
into naïve (passive) and guided search (active) sampling strategies [25]. The
naïve search strategies, such as random sampling, involve the independent
selection of test parameters. In contrast, the guided search, such as
optimization [11, 10], make the selection based on a specific selection
criterion and the information of existing samples. Naïve search sampling
strategies are useful if the simulation is computationally cheap to run since
parallelization of the procedure is possible due to the independence among
testing samples. On the other hand, when the test case simulation is
computationally expensive to run and/or when the test cases interested
(critical test cases in this case) are in a small region of the search domain,
the guided search sampling strategies can be more sample efficient.

For the current study, guided-search sampling strategies such as surrogate-
based black-box optimization methods are appropriate to efficiently identify
relevant critical concrete scenarios for the AD system. It is because a
closed-form expression of the KPI in terms of the test parameters is often
unavailable. Specifically, we use the global optimization algorithm GLIS
(Global optimization via Inverse distance weighting and Surrogate radial basis
functions) [5] as the active guided-search sampler to identify the next test
parameters of a concrete scenario for testing. The procedure of GLIS includes
an initial sampling stage and an active learning stage. In the initial
sampling stage, $N_{\rm initial}$ different test parameters are randomly
selected within the search domain, and the corresponding concrete scenarios
are simulated. The resulting quantitative evaluation of each test parameter
from RTAMT monitors is fed back to GLIS (c.f. Fig. 2). A surrogate radial
basis interpolation function (RBF) representing the correlation between the
test parameters and the KPI is fitted to the initial samples. In the active
learning phase, at each iteration, we identify a new test parameter, simulate
the corresponding concrete scenario, and refit the surrogate function by
including the newly identified test parameter and its KPI. The new test
parameter is obtained by optimizing an acquisition function, which trades off
the exploitation of the fitted RBF surrogate and exploration of an inverse
distance weighting (IDW) function. IDW is a distance-based exploration
function that promotes visiting points far away from the existing samples,
which helps prevent the solver from being trapped in the local optima. GLIS
terminates when the maximum allowed iteration is reached, or another user-
defined criterion is met.

GLIS is chosen for this study, as it easily incorporates constraints and has a
low computing cost [5]. If the computing cost is reasonable, GLIS may be
replaced by other surrogate-based active samplers, such as Bayesian
optimization.

##  3 Automatic Emergency Braking Case Study

To illustrate the methodology, we focus on testing a simple Automatic
Emergency Braking (AEB) functionality using a highway scenario.

#### Scenario description

The functional scenario is an ego vehicle following a leading vehicle on a
highway, when suddenly the leading vehicle brakes abruptly. The ego vehicle is
equipped with a simplistic distance-based AEB function which is activated when
the ego is less than safeDist meters from the leading vehicle. Figure 3 shows
a snapshot of the scenario running in CARLA v9.10.

(a)

(b)

Figure 3: (left) Snapshot of CARLA simulator running the AEB function test on
a highway. (right) Example of telemetric data collected from all actors.

The abstract scenario, depicted in Listing 1, is formulated using Scenic333The
shown scenario is simplified to facilitate presentation.. The scenario first
specifies the sampler and the map used to generate concrete simulations (lines
1 and 2). Then, it defines parameter variables that we partition into: (1) the
_constant_ variables (lines 3-4) that do not change across concrete scenarios
and (2) the _optimization_ variables (lines 6-7) that are fed to an external
(VerifAI) sampler in order to find critical scenarios in a controlled fashion.
There are also what we call _implicit_ variables that are not explicitly part
of the Scenic abstract scenario but still need to have a concrete value in the
simulator. For example, the weather conditions, the exact starting position
and orientation of each vehicle, the vehicle model, etc. In this case study,
there are more than $25$ implicit parameters. The scenario also defines the
behavior of the ego (lines 9-12) and of the lead vehicle (lines 14-18). Both
the ego and the lead vehicle follow the lane with some target speed as their
default behavior. However, the lead vehicle abruptly breaks at regular
intervals, while the ego breaks when it approaches any object at some minimum
distance. The two vehicles are spawned at some uniformly chosen part of the
map (line 20) that is sufficiently far away from an intersection (line 25).
The lead car is initialized at some pre-defined distance in front of the ego
vehicle (lines 22-23).

⬇

1param verifaiSamplerType = ‘glis’ # specify sampler

2param carla_map = ‘Town04’ # specify map to use

3initDist = 30 # constant

4leadSpeed = 10

5

6safeDist = VerifaiRange(25,45) # optimization variable

7egoSpeed = VerifaiRange(9,11) # optimization variable

8

9behavior AEB_Behavior: # define ego behavior

10 try:

11 FollowLaneBehavior(egoSpeed)

12 interrupt when withinDistanceToObjsInLane(self, safeDist): take
SetBrakeAction(1), SetThrottleAction(0)

13

14behavior Brake_Behavior: # define behavior of lead car

15 try:

16 FollowLaneBehavior(leadSpeed)

17 interrupt when simulation().currentTime > delay:

18 take SetBrakeAction(1), SetThrottleAction(0)

19

20spawnPt = Uniform(*HighwayRoads) # Highway part of map

21

22ego = Car at spawnPt, with AEB_Behavior} # spawn ego

23leadCar = Car at spawnPt + initDist, with Brake_Behavior # lead

24

25require (distance from leadCar to intersection > 50)

26# extra requirements for rejection sampling

Listing 1: AEB highway scenario in Scenic

#### Formalized Requirements

We illustrate the formalization of the requirements with the contract
$C=(\varphi,\psi)$, which captures the assumption $\varphi$ about the maximum
allowed deceleration of the lead vehicle and the guarantee $\psi$ as the
Responsibility-Sensitive Safety (RSS) property of the ego vehicle. The
assumption $\varphi$ originates from the IEEE Standard 2846-2022 [1], that
describes the minimal set of assumptions on the road users for safety-related
models of AD. From the assumptions described in the standard, we focus on the
maximum deceleration specification

$\varphi=\beta\leq\beta_{\emph{max}}.$

The Responsibility-Sensitive Safety (RSS) rule specifies, under minimal
assumptions, what longitudinal and lateral distances the ego vehicle must keep
from other road users to ensure no collisions [22]. The RSS rules were
formalized into temporal logic by [2] [14]. We adopt the STL specification
from [2] for an ego vehicle (back) to keep a safe longitudinal distance to
another vehicle (front):

$\displaystyle\operatorname{\Box}\left(v_{\text{front}}\geq 0\wedge
v_{\text{back}}\geq 0\right)$
$\displaystyle\operatorname{\Box}\left(a_{\text{front}}\in[a_{\text{max-
Br}},a_{\text{max-Acc}}]\wedge a_{\text{back}}\in[a_{\text{max-
Br}},a_{\text{max-Acc}}]\right)$
$\displaystyle\operatorname{\Box}\left(d(\text{front,
back})<d_{\text{safe}}\rightarrow a_{\text{back}}\in[a_{\text{max-
Br}},a_{\text{min-Br}}]\right)$

where $a,v$ are correspondingly acceleration and velocity. Similarly
$a_{\text{max-Acc}}$, $a_{\text{max-Br}}$, $a_{\text{min-Br}}$ are assumed
maximum acceleration, maximum braking, and minimum braking acceleration.
Finally, $d_{\text{safe}}$ is determined dynamically depending on the
velocities of both vehicles, and the reaction time $\tau$ of the ego vehicle:

$d_{\text{safe}}=\left(v_{\text{back}}\tau+\frac{a_{\text{max-
Acc}}\tau^{2}}{2}+\frac{(v_{\text{back}}+a_{\text{max-
Acc}}\tau)^{2}}{2a_{\text{min-Br}}}-\frac{v_{\text{front}}^{2}}{2a_{\text{max-
Br}}}\right).$

The safety distance is calculated in order to ensure that a collision is
avoided as long as the ego vehicle is sufficiently far away from the leading
vehicle. If it is momentarily closer than $d_{\text{safe}}$ then a collision
will still be avoided if the ego is reacting appropriately (by braking with at
least $a_{\text{min-Br}}$).

###  3.1 Simulation Results

In this section we present our evaluation outcomes. Fig. 4 shows the results
from simulating the abstract scenario $70$ times using the described tool
chain. Each point in the scatter plots represents a simulated concrete
scenario, where the RSS longitudinal distance was monitored. If the ego
vehicle managed to react adequately by braking in time, then this is
represented as a blue circle, otherwise (if the specification was violated) it
is represented by a red cross (the intensity of the color represents the
robustness degree).

(a)

(b)

Figure 4:  Comparison between Halton sampling (left) and GLIS sampling
[5](right) for $70$ concrete scenarios. The GLIS parameters are: $\alpha=1$,
$\delta=0.5$, $\varepsilon_{\text{SVD}}=0.01$, and an inverse-quadratic basis
function with $\epsilon=0.2$ was used.

Furthermore, we compare two different sampling strategies to find critical
scenarios. In this case, we compare a passive sampling strategy (i.e. agnostic
to feedback) which is based on Halton sequences [13], to an active strategy
based on the GLIS optimization sampling. As expected, sampling scenarios with
GLIS leads to the discovery of more critical scenarios ($11$ compared to $2$
with Halton), and suggests variable regions which should be further
investigated. In our example, the optimizer clearly was trying to exploit
around the region of higher egoSpeed, and lower safeDist (as expected). In
practice, both strategies are used to obtain a clear picture of the
performance of the ADAS functionality.

Figure 5: Evaluation with A/G contracts.

In Fig. 5, we illustrate the discrepancy between the classical and the refined
interpretation of A/G contracts. The figure depicts two simulations showing
the deceleration $\beta$ of the lead vehicle and the maximum allowed
deceleration threshold $\beta_{\emph{max}}=2m/s^{2}$ (top) and the distance
between the ego and the lead vehicle, as well as the safe distance between
them (bottom). We see that in the two simulations both the assumption
$\varphi$ and the guarantee $\psi$ are violated (purple and red stipes,
respectively). In the first simulation (left), there is a clear causality
between the abrupt breaking of the lead vehicle and the longitudinal RSS
violation – it follows that the contract is satisfied under both the classical
and the refined interpretation. In the second simulation (right), the
violation of the longitudinal RSS requirement happens before the lead vehicle
breaks. Intuitively, we expect the contract to be violated since the behavior
of the lead vehicle did not cause this critical scenario. However, under the
classical contract interpretation, the contract is satisfied because the lead
vehicle does violate the assumption at a later stage. On the other hand, the
refined contract rightly indicates the contract falsification.

###  3.2 Lessons Learned

In this section, we share our experience about the scenario-based testing
framework and collected during the case study evaluation.

#### Passive vs. active sampling

Both passive and active sampling have their merits in testing AD systems.
Passive sampling methods such as Halton provide a coverage of the parameter
space, facilitate detecting interesting patterns, if any, and help identifying
parameter regions that are interesting to further explore. In contrast, active
sampling methods such as GLIS can accelerate the detection of critical
scenarios.

#### Level of scenario abstraction

Balance between keeping a scenario abstract, and letting the tools sample
different variables, and having consistent concrete scenarios. If too many
variables are left unspecified, drawing meaningful conclusions from the
experiments is difficult, but if too many parameters are specified, there is a
risk of missing out on potential critical scenarios that are relevant (and it
also needs more development time).

#### Optimization with implicit variables

It is interesting to note that from the point of view of the optimizer, the
robustness function the of concrete scenario is non-deterministic. That is,
there are many different concrete scenarios that result from having the same
egoSpeed and safeDist which result in different robustness values. This is
mostly due to different implicit parameters impacting the robustness, which
the optimizer does not directly see (e.g. road geometry).

## References

  * [1] IEEE Standard for Assumptions in Safety-Related Models for Automated Driving Systems. IEEE Std 2846-2022 pp. 1–59 (2022). https://doi.org/10.1109/IEEESTD.2022.9761121
  * [2] Aréchiga, N.: Specifying safety of autonomous vehicles in signal temporal logic. In: 2019 IEEE Intelligent Vehicles Symposium (IV). pp. 58–63 (2019). https://doi.org/10.1109/IVS.2019.8813875
  * [3] Association for Standardization of Automation and Measuring Systems: ASAM OpenSCENARIO V1.2.0. Standard, Munich, Germany (2022), https://www.asam.net/standards/detail/openscenario/
  * [4] Association for Standardization of Automation and Measuring Systems: ASAM OpenSCENARIO V2.0.0. Standard, Munich, Germany (2022), https://www.asam.net/standards/detail/openscenario/v200/
  * [5] Bemporad, A.: Global optimization via inverse distance weighting and radial basis functions. Computational Optimization and Applications 77, 571–595 (2020), code available at http://cse.lab.imtlucca.it/~bemporad/glis
  * [6] Donzé, A., Maler, O.: Robust satisfaction of temporal logic over real-valued signals. In: Formal Modeling and Analysis of Timed Systems - 8th International Conference, FORMATS 2010, Klosterneuburg, Austria, September 8-10, 2010. Proceedings. pp. 92–106 (2010)
  * [7] Dosovitskiy, A., Ros, G., Codevilla, F., Lopez, A., Koltun, V.: CARLA: An open urban driving simulator. In: Proceedings of the 1st Annual Conference on Robot Learning. pp. 1–16 (2017)
  * [8] Dreossi, T., Donzé, A., Seshia, S.A.: Compositional falsification of cyber-physical systems with machine learning components. J. Autom. Reason. 63(4), 1031–1053 (2019). https://doi.org/10.1007/s10817-018-09509-5, https://doi.org/10.1007/s10817-018-09509-5
  * [9] Dreossi, T., Fremont, D.J., Ghosh, S., Kim, E., Ravanbakhsh, H., Vazquez-Chanlatte, M., Seshia, S.A.: VerifAI: A toolkit for the formal design and analysis of artificial intelligence-based systems. In: 31st International Conference on Computer Aided Verification (CAV) (Jul 2019)
  * [10] Feng, S., Feng, Y., Sun, H., Bao, S., Zhang, Y., Liu, H.X.: Testing scenario library generation for connected and automated vehicles, part ii: Case studies. IEEE Transactions on Intelligent Transportation Systems 22(9), 5635–5647 (2020)
  * [11] Feng, S., Feng, Y., Yu, C., Zhang, Y., Liu, H.X.: Testing scenario library generation for connected and automated vehicles, part i: Methodology. IEEE Transactions on Intelligent Transportation Systems 22(3), 1573–1582 (2020)
  * [12] Fremont, D.J., Dreossi, T., Ghosh, S., Yue, X., Sangiovanni-Vincentelli, A.L., Seshia, S.A.: Scenic: a language for scenario specification and scene generation. In: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. 63–78 (2019)
  * [13] Halton, J.H., Smith, G.B.: Algorithm 247: Radical-inverse quasi-random point sequence. Commun. ACM 7(12), 701–702 (1964). https://doi.org/10.1145/355588.365104, https://doi.org/10.1145/355588.365104
  * [14] Hekmatnejad, M., Yaghoubi, S., Dokhanchi, A., Amor, H.B., Shrivastava, A., Karam, L., Fainekos, G.: Encoding and monitoring responsibility sensitive safety rules for automated vehicles in signal temporal logic. In: Proceedings of the 17th ACM-IEEE International Conference on Formal Methods and Models for System Design. MEMOCODE ’19 (2019). https://doi.org/10.1145/3359986.3361203, https://doi.org/10.1145/3359986.3361203
  * [15] Maler, O., Nickovic, D.: Monitoring temporal properties of continuous signals. In: Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems, Joint International Conferences on Formal Modelling and Analysis of Timed Systems, FORMATS 2004 and Formal Techniques in Real-Time and Fault-Tolerant Systems, FTRTFT 2004, Grenoble, France, September 22-24, 2004, Proceedings. pp. 152–166 (2004)
  * [16] Menzel, T., Bagschik, G., Maurer, M.: Scenarios for development, test and validation of automated vehicles. In: 2018 IEEE Intelligent Vehicles Symposium (IV). pp. 1821–1827. IEEE (2018)
  * [17] Neurohr, C., Westhofen, L., Butz, M., Bollmann, M.H., Eberle, U., Galbas, R.: Criticality analysis for the verification and validation of automated vehicles. IEEE Access 9, 18016–18041 (2021)
  * [18] Nghiem, T., Sankaranarayanan, S., Fainekos, G., Ivancic, F., Gupta, A., Pappas, G.J.: Monte-carlo techniques for falsification of temporal properties of non-linear hybrid systems. In: Proceedings of the 13th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2010, Stockholm, Sweden, April 12-15, 2010. pp. 211–220 (2010)
  * [19] Ničković, D., Yamaguchi, T.: Rtamt: Online robustness monitors from stl. In: International Symposium on Automated Technology for Verification and Analysis. pp. 564–571. Springer (2020)
  * [20] On-Road Automated Driving (ORAD) committee: J3016 Taxonomy and Definitions for Terms Related to Driving Automation Systems for On-Road Motor Vehicles. Tech. rep. (2021), https://www.sae.org/standards/content/j3016_202104/
  * [21] Qin, X., Aréchiga, N., Best, A., Deshmukh, J.: Automatic testing with reusable adversarial agents. arXiv preprint arXiv:1910.13645 (2019)
  * [22] Shalev-Shwartz, S., Shammah, S., Shashua, A.: On a Formal Model of Safe and Scalable Self-driving Cars. arXiv e-prints arXiv:1708.06374 (Aug 2017)
  * [23] Tuncali, C.E., Fainekos, G., Prokhorov, D., Ito, H., Kapinski, J.: Requirements-driven test generation for autonomous vehicles with machine learning components. IEEE Transactions on Intelligent Vehicles 5(2), 265–280 (2019)
  * [24] Tuncali, C.E., Pavlic, T.P., Fainekos, G.: Utilizing s-taliro as an automatic test generation framework for autonomous vehicles. In: 19th IEEE International Conference on Intelligent Transportation Systems, ITSC 2016, Rio de Janeiro, Brazil, November 1-4, 2016. pp. 1470–1475 (2016)
  * [25] Zhang, X., Tao, J., Tan, K., Törngren, M., Sanchez, J.M.G., Ramli, M.R., Tao, X., Gyllenhammar, M., Wotawa, F., Mohan, N., et al.: Finding critical scenarios for automated driving systems: A systematic mapping study. IEEE Transactions on Software Engineering (2022)


# Kemperman’s inequality and Freiman’s lemma via few translates

Yifan Jing  Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK
<EMAIL_ADDRESS>and  Akshat Mudgal  Mathematical Institute, University of
Oxford, Oxford OX2 6GG, UK<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a connected compact group equipped with the normalised Haar measure
$\mu$. Our first result shows that given $\alpha,\beta>0$, there is a constant
$c=c(\alpha,\beta)>0$ such that for any compact sets $A,B\subseteq G$ with

$\alpha\mu(B)\geq\mu(A)\geq\mu(B)\ \ \text{and}\ \ \mu(A)+\mu(B)\leq 1-\beta,$

there exist $b_{1},\dots b_{c}\in B$ such that

$\mu(A\cdot\\{b_{1},\dots,b_{c}\\})\geq\mu(A)+\mu(B).$

A special case of this, that is, when $G=\mathbb{T}^{d}$, confirms a recent
conjecture of Bollobás, Leader and Tiba.

We also prove a quantitatively stronger version of such a result in the
discrete setting of $\mathbb{R}^{d}$. Thus, given $d\in\mathbb{N}$, we show
that there exists $c=c(d)>0$ such that for any finite, non-empty set
$A\subseteq\mathbb{R}^{d}$ which is not contained in a translate of a
hyperplane, one can find $a_{1},\dots,a_{c}\in A$ satisfying

$|A+\\{a_{1},\dots,a_{c}\\}|\geq(d+1)|A|-O_{d}(1).$

The main term here is optimal and recovers the bounds given by Freiman’s lemma
up to the $O_{d}(1)$ error term.

###### Key words and phrases:

Kemperman’s inequality, Freiman’s lemma, Inverse theorems

###### 2020 Mathematics Subject Classification:

11B30, 22C05

YJ and AM are supported by Ben Green’s Simons Investigator Grant, ID:376201.

##  1\. Introduction

Given finite, non-empty sets $A,B$ of integers, a classical result in additive
number theory implies that the sumset

$A+B=\\{a+b:a\in A,b\in B\\}$

satisfies

$|A+B|\geq|A|+|B|-1.$ (1.1)

This has been since generalised to a variety of settings, including the case
when $A,B$ are subsets of some connected, compact group $G$ as well as when
$A,B$ are finite subsets of $\mathbb{R}^{d}$. In order to elucidate upon the
former, we describe some notation, and so, whenever we write $G$ to be a
compact, connected group, we will associate with $G$ the group operation
$\cdot$ and the normalised Haar measure $\mu$ satisfying $\mu(G)=1$. In this
setting, a fundamental result of Kemperman [15] implies that whenever
$A,B\subseteq G$ are non-empty compact sets, then the product set

$A\cdot B=\\{a\cdot b:a\in A,b\in B\\}$

satisfies

$\mu(A\cdot B)\geq\min\\{\mu(A)+\mu(B),1\\}.$ (1.2)

When $G$ is abelian, this is also known as Kneser’s inequality [16]. Moving
now from the continuous case to the discrete setting, we note that analysis of
finite sumsets in $\mathbb{R}^{d}$ arose from work of Freiman [9] and has
played an important role in additive combinatorics, specially due to its
connections to Freiman’s theorem and the sum-product problem, see, for
instance, [5, 11]. In particular, denoting $\dim(A)$ to be the dimension of
the affine span of $A$ for any finite, non-empty $A\subseteq\mathbb{R}^{d}$,
the well-known Freiman’s lemma (see [9, Section 1.14] or [24, Lemma 5.13])
implies that whenever $\dim(A)=d$, then

$|A+A|\geq(d+1)|A|-d(d+1)/2.$ (1.3)

Both the aforementioned inequalities can be seen to be sharp, for example, one
can observe that (1.2) is optimal by considering the case when $G=\mathbb{T}$
is the torus and $A,B$ are sufficiently small intervals in $\mathbb{T}$.
Similarly, (1.3) is sharp as evinced by the case when
$A\subseteq\mathbb{R}^{d}$ satisfies

$A=\\{0,e_{1},\dots,e_{d-1}\\}\times\\{1,2,\dots,N\\},$ (1.4)

where $\\{e_{1},\dots,e_{d}\\}$ form the canonical basis of $\mathbb{R}^{d}$.

In a recent paper, Bollobás, Leader, and Tiba [1] considered a different
perspective towards (1.1), wherein, they showed that whenever
$A,B\subseteq\mathbb{Z}$ are finite sets with $|A|\geq|B|\geq 1$, then there
exist $b_{1},b_{2},b_{3}\in B$ such that

$|A+\\{b_{1},b_{2},b_{3}\\}|\geq|A|+|B|-1.$ (1.5)

They proved some similar results when $A,B$ are subsets of $\mathbb{F}_{p}$
and $\mathbb{T}$, with various restrictions on the sizes of $A,B$. They
further conjectured that an analogous phenomenon should hold in the higher
dimensional torus $\mathbb{T}^{d}$, that is, writing $G$ to be
$\mathbb{T}^{d}$, there exists some $c>0$ such that for any compact, non-empty
sets $A,B\subseteq G$ with $\mu(A)=\mu(B)=1/3$, one can find
$b_{1},\dots,b_{c}\in B$ such that

$\mu(A\cdot\\{b_{1},\dots,b_{c}\\})\geq\mu(A)+\mu(B).$

Here, since $G=\mathbb{T}^{d}$, the group operation $\cdot$ denotes the
additive group operation in $\mathbb{T}^{d}$.

Our first result confirms a much more general version of their conjecture.

######  Theorem 1.1.

Given $\alpha,\beta>0$, there exists some constant $c=c(\alpha,\beta)>0$ such
that the following holds. Let $G$ be a connected compact group and let
$A,B\subseteq G$ be compact sets with

$\alpha\mu(B)\geq\mu(A)\geq\mu(B)\ \ \text{and}\ \ \mu(A)+\mu(B)\leq 1-\beta.$

Then there exist $b_{1},\dots,b_{c}\in B$ such that

$\mu(A\cdot\\{b_{1},\dots,b_{c}\\})\geq\mu(A)+\mu(B).$

Hence, we prove their conjecture for all connected, compact groups, including
the cases when $G$ is possibly nonabelian. Moreover, our constant $c$ is
independent of $G$. One way to interpret our result is that given suitable
sets $A,B\subseteq G$, one can recover the lower bound (1.2) for $\mu(A\cdot
B)$ by just considering few translates $A\cdot b_{1},\dots,A\cdot b_{c}$ of
$A$. For instance, a conclusion akin to that of Theorem 1.1 holds for any
$K$-approximate group $A$ of $G$, that is, symmetric sets $A\subseteq G$
containing the identity for which $A\cdot A\subseteq X\cdot A$ for some
$X\subseteq G$ with $|X|\leq K$. Indeed in our setting, we may apply (1.2) to
deduce that

$2\mu(A)\leq\mu(A\cdot A)\leq\mu(A\cdot\\{x_{1},\dots,x_{c}\\}),$

where $\\{x_{1},\dots,x_{c}\\}=X^{-1}\subseteq G$. On the other hand, a
celebrated result of Breuillard, Green, and Tao [3] shows that approximate
groups are highly structured objects that essentially only come from nilpotent
groups. Despite the rarity of such objects, Theorem 1.1 suggests that one can
in fact recover the above inequality for any compact set $A\subseteq G$ with
$\mu(A)\leq 1-\beta$ and $c=c(\beta)$.

In the discrete setting, it is worth noting that the main result of [1]
already implies (1.5) for finite, non-empty sets $A,B\subseteq\mathbb{R}^{d}$
by considering Freiman isomorphisms from $A\cup B$ to sets of integers. On the
other hand, noting Freiman’s lemma, it is natural to ask whether one can also
recover bounds akin to (1.3) by just considering $O_{d}(1)$ translates of $A$.
This is precisely the content of our next result.

######  Theorem 1.2.

Given $d\in\mathbb{N}$, there exists some constant $c=c(d)>0$ such that for
every finite, non-empty set $A\subseteq\mathbb{R}^{d}$ with $\dim(A)=d$, there
exist $a_{1},\dots,a_{c}\in A$ satisfying

$|A+\\{a_{1},\dots,a_{c}\\}|\geq(d+1)|A|-5(d+1)^{3}.$

The main term in the above lower bound matches the main term in (1.3) provided
by Freiman’s lemma, and as before, can be seen to be sharp by considering the
sets represented in (1.4). A similar setup has been analysed in the recent
work of Fox, Luo, Pham and Zhou [8], wherein, the authors showed that for
every $d,\varepsilon>0$, there exist constants $C=C(d,\varepsilon)\geq 1$ and
$c=c(d,\varepsilon)\geq 1$ such that any finite set
$A\subseteq\mathbb{R}^{d}$, which is not contained in $C$ translates of any
hyperplane, contains elements $a_{1},\dots,a_{c}$ satisfying

$|A+\\{a_{1},\dots,a_{c}\\}|\geq(2^{d}-\varepsilon)|A|.$

Thus, while they obtain a stronger lower bound for
$|A+\\{a_{1},\dots,a_{c}\\}|/|A|$, they must restrict to relatively less
structured sets $A$, that is, sets $A$ which can not be covered by $C$
translates of any hyperplane. Moreover, the quantitative dependence of $C$ on
$d,\varepsilon$ is slightly weak, since this arises from an application of the
Freiman–Bilu theorem (see [11]). In comparison, Theorem 1.2 provides lower
bounds for $|A+\\{a_{1},\dots,a_{c}\\}|/|A|$ that grow linearly with $d$ but
hold for any $d$-dimensional subset $A\subseteq\mathbb{R}^{d}$, essentially
allowing us to obtain optimal estimates when $C=1$.

We now turn to a related philosophy of considering inverse results for small
sumsets. This forms a large collection of results in additive combinatorics,
with the central theorem being Freiman’s inverse theorem, which suggests that
sets $A\subseteq\mathbb{Z}$ with $|A+A|\leq K|A|$ must be contained
efficiently in very additively structured sets known as generalised arithmetic
progressions. Moreover, obtaining quantitatively optimal versions of this
result as $K$ becomes large is a key open problem in the area, see [20]. On
the other hand, when $K$ is very small, say $K<3$, then we have very sharp
characterisations. This is the content of Freiman’s $3k-4$ theorem (see [24,
Theorem 5.11]) which implies that any finite set $A\subseteq\mathbb{Z}$ with
$|A+A|\leq 3|A|-4$ is contained in an arithmetic progression $P$ of length
$|A+A|-|A|+1$. Such types of results have been extended to a variety of
settings including the case of finite fields and $\mathbb{Z}^{d}$, see [4, 22]
and the references therein.

More recently, it was shown in [2] that one can obtain an analogue of
Freiman’s $3k-4$ theorem for sumsets akin to (1.5), that is, instead of
assuming upper bounds for $|A+A|$ with $A\subseteq\mathbb{Z}$, one can assume
that $|A+A^{\prime}|\leq(2+\varepsilon)|A|$ for every $A^{\prime}\subseteq A$
with $|A^{\prime}|=4$ and with $\varepsilon$ being sufficiently small,
whereupon, one may deduce that $A$ is contained in an arithmetic progression
$P$ of size $(1+\varepsilon+O(\varepsilon^{2}))|A|$. In our paper, we are also
able to prove these type of inverse theorems in the settings of Theorems 1.1
and 1.2, and we present the first of these below.

######  Theorem 1.3.

Given $\varepsilon,\alpha,\beta>0$, there exist constants $c,\eta$ depending
only on $\varepsilon,\alpha,\beta$, such that the following holds. Let $G$ be
a connected compact group, let $A,B\subseteq G$ be compact sets such that
$\mu(A)+\mu(B)<1-\beta$, and $\alpha^{-1}\mu(B)\leq\mu(A)\leq\alpha\mu(B)$.
Moreover, suppose that for every $b_{1},\dots,b_{c}\in B$, we have

$\mu(A\cdot\\{b_{1},\dots,b_{c}\\})\leq\mu(A)+\mu(B)+\eta\min\\{\mu(A),\mu(B)\\}.$

Then there is a surjective group homomorphism $\chi:G\to\mathbb{T}$ and two
compact intervals $I,J\subseteq\mathbb{T}$, with $\lambda$ being the
normalised Lebesgue measure on $\mathbb{T}$, such that

$\lambda(I)\leq(1+\varepsilon)\mu(A)\ \ \text{and}\ \
\lambda(J)\leq(1+\varepsilon)\mu(B)\ \ \text{and}\ \ A\subseteq\chi^{-1}(I)\ \
\text{and}\ \ B\subseteq\chi^{-1}(J).$

Here, if one replaces the assumption that $\mu(A\cdot\\{b_{1},\dots,b_{c}\\})$
is small from Theorem 1.3 by the hypothesis that the entire product set
$\mu(A\cdot B)$ is small, then the corresponding inverse theorem was obtained
by the first author and Tran in [14], and when $G$ is abelian, it was first
proven by Tao [23], see also [6] for a quantitatively better bound. This
asserts that sets with doubling close to $2$ in connected compact groups are
dominated by a one-dimensional torus, and, in particular, when $G$ is compact
semisimple, the doubling constant of any small subset should be away from $2$.
Theorem 1.3 is a strengthening of this phenomenon, and we have the following
immediate corollary.

######  Corollary 1.4.

There are absolute constants $c,\eta>0$ such that the following holds. Let $G$
be a compact semisimple Lie group, and let $A\subseteq G$ satisfy $\mu(A)\leq
1/3$. Then there exist $a_{1},\dots,a_{c}\in A$ such that

$\mu(A\cdot\\{a_{1},\dots,a_{c}\\})>(2+\eta)\mu(A).$

Returning to the discrete setting, Stanchescu [22] showed that whenever a
large set $A\subseteq\mathbb{Z}^{d}$ with $\dim(A)=d$ has its sumset close in
size to the lower bound in (1.3), then $A$ is contained in a union of $d$
parallel lines, that is, $A\subseteq T+l=\cup_{t\in T}(t+l),$ where
$T\subseteq\mathbb{Z}^{d}$ is a set satisfying $|T|\leq d$ and $l$ is some one
dimensional subspace, consequently making progress towards a problem raised by
Freiman [10]. An asymmetric version of the above conclusion for sets
$A,B\subseteq\mathbb{R}^{d}$ may be derived by combining ideas from [17] and
[18], see, for instance, the proof of Lemma 5.1. Both these results seem to
capture the extremality of the example presented in (1.4). Using our methods,
we are able to obtain an analogous conclusion under a weaker hypothesis, that
is, instead of assuming upper bounds for the entire sumset $A+A$, we operate
under the assumption that for any $A^{\prime}\subseteq A$ with
$|A^{\prime}|\ll_{d}1$, the sumset $A+A^{\prime}$ is close in size to the
estimates provided by Theorem 1.2. We record this inverse result below.

######  Theorem 1.5.

Given $d\in\mathbb{N}$, there exists some constant $c=c(d)>0$ such that the
following holds true. Let $A\subseteq\mathbb{R}^{d}$ be a finite, non-empty
set with $\dim(A)=d$, such that for any $a_{1},\dots,a_{c}\in A$, we have

$|A+\\{a_{1},\dots,a_{c}\\}|\leq(d+1+1/16)|A|.$

Then either $|A|\ll_{d}1$ or $A\subseteq T+l$, where $l$ is a one dimensional
subspace of $\mathbb{R}^{d}$ and $T\subseteq\mathbb{R}^{d}$ satisfies
$|T|\leq(d+1)^{2}$.

We point out that we have not chosen to optimise the constant $1/16$ in the
above result, and this can be quantitatively improved, potentially at the cost
of slightly increasing the upper bound for $|T|$. It would also be interesting
to show a variant of the above result where one obtains $|T|\leq d$, akin to
the results in [18, 22] as well as Lemma 5.1 in §5.

We now provide a brief outline of the paper. We utilise §2 to record various
preliminary definitions and results that we will require throughout our paper.
These include a variety of inverse and structural results from additive
combinatorics along with some standard lemmata like the Plünnecke-Ruzsa
inequality. We employ §3 to present the proofs of Theorems 1.1 and 1.3. The
key lemma in the section is Lemma 3.1, which deal with the case when $G$ has a
torus quotient and the sets are close to $1$-dimensional Bohr sets. The proofs
of Theorems 1.1 and 1.3 is that either we are in the situation to apply Lemma
3.1, or a random selection argument works. Our main aim of §4 will be to prove
Lemma 4.1, which can be interpreted as a variant of Theorem 1.2 in the case
when our set $A\subseteq\mathbb{R}^{d}$ can be covered by few translates of a
line. This will require a combination of combinatorial geometric and additive
combinatorial methods. Moreover, Lemma 4.1 will then naturally combine with
Theorem 1.5 to deliver the proof of Theorem 1.2. Finally, in §5, we record the
proof of Theorem 1.5.

Notation. In this paper, we use Vinogradov notation, that is, we write
$X\gg_{z}Y$, or equivalently $Y\ll_{z}X$, to mean $|X|\geq C_{z}|Y|$ where $C$
is some positive constant depending on the parameter $z$. Moreover, we write
$X=O_{z}(Y)$ to mean $X\ll_{z}Y$. Given a group $G$ and a set $A\subseteq G$,
we use $\mathbbm{1}_{A}$ to denote the indicator function of the set $A$, that
is, $\mathbbm{1}_{A}(g)=1$ when $g\in A$, and $\mathbbm{1}_{A}(g)=0$ when
$g\in G\setminus A$.

Acknowledgements. We would like to thank Marcelo Campos and Zach Hunter for
useful comments. We are also grateful to Zach for help in improving the
presentation of our paper.

##  2\. Preliminaries

A locally compact group $G$ is a group equipped with a locally compact and
Hausdorff topology on its underlying set such that the group multiplication
and inversion maps are continuous. We say that a measure $\mu$ on the
collection of Borel subsets of $G$ is a left Haar measure if it satisfies the
following properties:

  1. (1)

(nonzero) $\mu(X)>0$ for all open $X\subseteq G$;

  2. (2)

(left-invariant) $\mu(X)=\mu(a\cdot X)$ for all $a\in G$ and all measurable
sets $X\subseteq G$;

  3. (3)

(inner regular) when $X$ is open, $\mu(X)=\sup\mu(K)$ with $K$ ranging over
compact subsets of $X$;

  4. (4)

(outer regular) when $X$ is Borel, $\mu(X)=\inf\mu(U)$ and $U$ ranging over
open subsets of $G$ containing $X$;

  5. (5)

(compactly finite) $\mu$ takes finite measure on compact subsets of $G$.

When $G$ is a locally compact topological group, a famous theorem of Haar
asserts that $G$ has a unique (up to a constant factor) left-invariant Haar
measure, denoted by $\mu$. When $G$ is compact, $\mu$ is also right-invariant
(that is for a measureable $X$ we also have $\mu(X\cdot g)=\mu(X)$ for all
$g\in G$). We say $\mu$ is normalised if $\mu(G)=1$.

In our proof of Theorem 1.1, it will sometimes be more convenient to study the
popular product set defined as follows. Given $0\leq
t\leq\min\\{\mu(A),\mu(B)\\}$, we denote the popular product set

$A\cdot_{t}B=\\{x\in G\mid\mathbbm{1}_{A}*\mathbbm{1}_{B}(x)\geq t\\},$

where, given any $f,g:G\to\mathbb{R}$, we define the convolution function
$f*g:G\to\mathbb{R}$ as

$f*g(x)=\int_{G}f(y)g(y^{-1}x)\,\mathrm{d}\mu(y)$

for every $x\in G$. Note that when $G$ is compact, we also have

$f*g(x)=\int_{G}f(xy^{-1})g(y)\,\mathrm{d}\mu(y)$

for every $x\in G$, since $\mu$ is bi-invariant. Noting these definitions, one
can further see that

$\lim_{t\to
0}A\cdot_{t}B=\mathrm{supp}(\mathbbm{1}_{A}*\mathbbm{1}_{B})\subseteq A\cdot
B.$

We now state the well-known quotient integral formula, see, for example, [7,
Theorem 2.49].

######  Lemma 2.1.

Let $G$ be a locally compact group and $H\leq G$ be a closed normal subgroup.
Let $\mu_{G}$ and $\mu_{H}$ be left invariant Haar measures on $G$ and $H$
respectively. Then there is a unique left invariant Haar measure $\mu_{G/H}$
on $G/H$ such that for every compactly supported continuous function
$f:G\to\mathbb{C}$,

$\int_{G}f(g)\,\mathrm{d}\mu_{G}(g)=\int_{G/H}\int_{H}f(xh)\,\mathrm{d}\mu_{H}(h)\,\mathrm{d}\mu_{G/H}(xH).$

A locally compact group $G$ is called connected if it is connected as a
topological space. In particular, it does not have any open subgroups. Recall
that open subgroups are closed, and closed subgroups of finite indices are
open, hence all the closed subgroups of a connected group have measure $0$.

We now recall Kemperman’s inequality as presented in (1.2), which can be seen
as an extension of Kneser’s inequality [16], which in turn, is a
generalisation of the Cauchy–Davenport inequality. We remark that the latter
can further generalised to all locally compact groups see [13]. Moreover, one
can prove various inverse theorems for when the lower bound in such
inequalities is close to being sharp. In our proof of Theorem 1.1, we will
make use of one such inverse theorem which can be derived from the work of the
first author and Tran in [14]; a generalised version of which is also stated
in the forthcoming work [12]. The abelian case of this theorem (with a weaker
quantitative bound, in particular, with $\eta=o(1)$) was first obtained by Tao
[23], with a further result by Christ–Iliopoulou [6] which dispensed a sharp
exponent bound.

######  Theorem 2.2.

Given $\varepsilon,\alpha>0$, there is $\eta>0$ such that the following hold.
Let $G$ be a connected compact group equipped with the normalised Haar measure
$\mu$ and let $A,B\subseteq G$ be compact sets such that
$\alpha\mu(B)\geq\mu(A)\geq\mu(B)$. If

$\mu(A\cdot_{\eta\mu(B)}B)\leq\mu(A)+\mu(B)+\eta\mu(B)<1,$

then there is a continuous surjective homomorphism $\chi:G\to\mathbb{T}$, and
two compact intervals $I,J\subseteq\mathbb{T}$ such that with $\lambda$ the
normalised Lebesgue measure on $\mathbb{T}$ we have

$\lambda(I)\leq(1+\varepsilon)\mu(A),\qquad\lambda(J)\leq(1+\varepsilon)\mu(B),$

and $A\subseteq\chi^{-1}(I)$, $B\subseteq\chi^{-1}(J)$.

We now move to the discrete setting, where the ambient group is
$\mathbb{R}^{d}$ and $A\subseteq\mathbb{R}^{d}$ is a finite set. Our first
preliminary lemma in this setting will be the following inverse theorem for
sumsets in higher dimensions from [17].

######  Lemma 2.3.

Given $d\in\mathbb{N}$ and $K\geq 1$ and a finite set
$A\subseteq\mathbb{R}^{d}$ with $|A+A|\leq K|A|$, there exist parallel lines
$l_{1},\dots,l_{r}$ in $\mathbb{R}^{d}$ and a constant $0<\sigma\leq 1/2$
depending only on $K$, such that

$|A\cap l_{1}|\geq\dots|A\cap l_{r}|\geq|A\cap l_{1}|^{1/2}\gg|A|^{\sigma}$

and

$|A\setminus(l_{1}\cup\dots\cup l_{r})|\ll K|A|^{1-\sigma}.$

Thus if $A\subseteq\mathbb{R}^{d}$ has a small sumset, then one can
efficiently cover $A$ with translates of a one dimensional subspace. We will
combine this with the following asymmetric variant of Freiman’s lemma from the
second author’s work in [18].

######  Lemma 2.4.

Let $d\geq 2$ be an integer, let $A,B\subseteq\mathbb{R}^{d}$ be finite sets
such that $|A|\geq|B|$ and $\dim(A)=d$. Suppose that
$l_{1},\dots,l_{r},m_{1},\dots,m_{q}$ are parallel lines such that

$A\subseteq l_{1}\cup\dots\cup l_{r}\ \ \text{and}\ \ B\subseteq
m_{1}\cup\dots\cup m_{q},$

with $|A\cap l_{i}|,|B\cap m_{j}|\geq 1$ for every $1\leq i\leq r$ and $1\leq
j\leq q.$ Then we have that

$|A+B|\geq|A|+\Big{(}d+1-\frac{1}{r-d+2}-\frac{1}{q-c+2}\Big{)}|B|-(d-1)(r+q),$

where $c=d$ when $\dim(B)=d$ and $c=\dim(B)$ when $\dim(B)<d$.

Next, we will require the following modified version of [1, Theorem 8’] for
our proof of Theorem 1.5.

######  Lemma 2.5.

For all $K$ and $\varepsilon>0$, there exists $c=c(K,\varepsilon)>0$ such that
the following holds true. Given a finite subset $A$ of some abelian group $G$,
there exists a set $A^{*}\subseteq A$ with $|A^{*}|\geq(1-\varepsilon)|A|$
such that if we select $a_{1},\dots,a_{c}$ uniformly at random from $A^{*}$
then

$\mathbb{E}_{a_{1},\dots,a_{c}\in
A^{*}}|A^{*}+\\{a_{1},\dots,a_{c}\\}|\geq\min\\{(1-\varepsilon)|A^{*}+A^{*}|,K|A^{*}|\\}.$

This may be obtained by applying the following corollary of [21, Theorem 1.1]
in the proof of [1, Theorem 8’], instead of the original version of [21,
Theorem 1.1].

######  Lemma 2.6.

Given $\varepsilon>0$ and $K\geq 1$, the following is true for all $\delta>0$
sufficiently small in terms of $\varepsilon,K$. Let $A$ be a finite subset of
some abelian group $G$ and let $\Gamma\subseteq A\times A$, with
$|\Gamma|\geq(1-\delta)|A|^{2}$. Writing $S=\\{a+b:(a,b)\in\Gamma\\}$, suppose
that $|S|\leq K|A|$. Then there exists $A^{\prime\prime}\subseteq A$ such that

$|A^{\prime\prime}|\geq(1-\varepsilon)|A|\ \ \text{and}\ \
|A^{\prime\prime}+A^{\prime\prime}|\leq|S|+\varepsilon|A|.$

Lemma 2.6 follows from a straightforward manner from [21, Theorem 1.1] by
setting $A^{\prime\prime}=A^{\prime}\cap B^{\prime}$ in the conclusion of [21,
Theorem 1.1] and rescaling $\varepsilon$ appropriately.

We now record a standard result in additive combinatorics known as the
Plünnecke-Ruzsa inequality [24, Corollary 6.29], which, in the situation when
$|A+B|\leq K|B|$, allows us to efficiently bound many-fold sumsets of $A$.

######  Lemma 2.7.

Let $A,B$ be finite, non-empty subsets of some abelian group $G$ satisfying
$|A+B|\leq K|B|$. Then for every $k\in\mathbb{N}$, we have that

$|\\{a_{1}+\dots+a_{k}:a_{1},\dots a_{k}\in A\\}|\leq K^{k}|B|.$

We end this section by recalling that (1.5), when combined with the theory of
Freiman isomorphisms, implies that for any finite $A,B\subseteq\mathbb{R}^{d}$
with $|A|\geq|B|,$ one may find elements $b_{1},b_{2},b_{3}\in B$ such that

$|A+\\{b_{1},b_{2},b_{3}\\}|\geq|A|+|B|-1.$ (2.1)

##  3\. Proof of Theorems 1.1 and 1.3

We begin this section by proving the following lemma that can be seen to
provide a stronger version of the conclusion from Theorem 1.1, but in the more
specific setting where $A,B\subseteq G$ can be mapped surjectively to large
subsets of some intervals in $\mathbb{T}$.

######  Lemma 3.1.

Let $G$ be a connected compact group with $\mu$ being the normalised Haar
measure on $G$, and let $A,B$ be two compact sets in $G$ with
$\mu(A)\geq\mu(B)$. Suppose that $\chi:G\to\mathbb{T}$ is a surjective compact
group homomorphism and $I,J$ are two compact intervals in $\mathbb{T}$ with

$\lambda(I)+\lambda(J)<1,\ \text{and}\ A\subseteq\chi^{-1}(I)\ \text{and}\
B\subseteq\chi^{-1}(J),$

where $\lambda$ is the normalised Lebesgue measure on $\mathbb{T}$. Then there
exist $b_{1},b_{2},b_{3}\in B$ such that

$\mu(A\cdot\\{b_{1},b_{2},b_{3}\\})\geq\mu(A)+\mu(B).$

###### Proof.

By replacing $A$ and $B$ with $a^{-1}\cdot A$ and $B\cdot b^{-1}$ for some
$a\in A$ and $b\in B$ respectively, we may assume that $0$ is the left end
point for both $I$ and $J$. By the compactness assumption on $A$ and $B$ we
may further assume that

$\chi^{-1}(0)\cap A\neq\varnothing,\quad\chi^{-1}(0)\cap
B\neq\varnothing,\quad\chi^{-1}(\lambda(I))\cap
A\neq\varnothing,\quad\chi^{-1}(\lambda(J))\cap B\neq\varnothing.$

Note that as $G$ is compact and hence unimodular, such translations would not
affect the measure of the product set $A\cdot B$.

Let us now consider the following short exact sequence

$1\to H:=\ker\chi\to G\xrightarrow{\chi}\mathbb{T}\to 1,$

and note that $H$ is a connected compact group, write $\mu_{H}$ to denote the
normalised Haar measure on $H$. As $\lambda(I)+\lambda(J)<1$, observe that the
natural embedding $\phi:\mathbb{T}\to\mathbb{R}$ with $\phi(\mathbb{T})=[0,1)$
preserves the measure of the sumset

$I+J=\\{i+j:i\in I,j\in J\\}.$

For clarity of exposition, we note that here, and throughout the proof of
Lemma 3.1, we will use $+$ to denote the additive operation in the abelian
group $\mathbb{T}$. Next, defining $\psi=\phi\circ\chi$, which maps $G$ to
$\mathbb{R}$, we will abuse some notation and write $I$, $J$ (instead of
$\phi(I)$,$\phi(J)$) for the compact intervals in $\mathbb{R}$. Note that we
still have

$\psi^{-1}(0)\cap A\neq\varnothing,\quad\psi^{-1}(0)\cap
B\neq\varnothing,\quad\psi^{-1}(\lambda(I))\cap
A\neq\varnothing,\quad\psi^{-1}(\lambda(J))\cap B\neq\varnothing,$

where we now view $\lambda$ as its pushforward in $\mathbb{R}$. Let

$b_{1}\in\psi^{-1}(0)\cap B\ \ \text{and}\ \ b_{2}\in\psi^{-1}(\lambda(J))\cap
B,$

and let

$X=A\cdot\\{b_{1},b_{2}\\}=(A\cdot b_{1})\cup(A\cdot b_{2}).$

We may assume that $\lambda(I)\geq\lambda(J)$, because otherwise we would have

$\mu(X)\geq 2\mu(A)\geq\mu(A)+\mu(B),$

in which case, we would be done. For every element $x$ in $\mathbb{R}$ and for
every set $S\subseteq G$, let us consider the fiber function with respect to
$A$ defined as

$f_{A}(x)=\mu_{H}(([\psi^{-1}(x)]^{-1}\cdot A)\cap H)\ \ \ \text{for every}\
x\in\psi(A),$

where $[xH]$ denotes the representative element that lives on the coset $xH$.
Moreover, we write $f_{A}(x)=0$ for every $x\in\mathbb{R}\setminus\psi(A)$. We
define the fiber functions for $B$ and $X$ in the same way. We further set

$\pi(X):=\int_{0}^{\lambda(J)}\max_{y\in
x+\lambda(J)\mathbb{Z}}f_{X}(y)\,\mathrm{d}\lambda.$

This can be viewed as the size of some sort of a “maximum projection” of $X$
onto $[0,\lambda(J))$. It is worth pointing out that in the above definition
while we are considering, for every $x\in[0,\lambda(J))$, the maximum over all
$y\in x+\lambda(J)\mathbb{Z}$, in practice, this maximum only considers
finitely many values of $y$ since the function $f_{X}$ is only supported on
the set $[0,\lambda(J)+\lambda(I)]$.

Our first aim is to show that

$\mu(X)\geq\mu(A)+\pi(X).$ (3.1)

We proceed by observing that

$f_{X}(x)=f_{A}(x)\ \text{for}\ x\in[0,\lambda(J))\ \ \text{and}\ \
f_{X}(x)=f_{A}(x-\lambda(J))\ \text{for all}\ x>\lambda(I),$

and so, we may apply Lemma 2.1 to discern that

$\mu(X)=\int_{\lambda(I)-\lambda(J)}^{\lambda(I)}f_{A}(x)\,\mathrm{d}\lambda(x)+\int_{0}^{\lambda(I)}f_{X}(x)\,\mathrm{d}\lambda(x),$

which, in turn, gives us

$\mu(X)-\mu(A)=\int_{0}^{\lambda(I)}(f_{X}(x)-f_{A}(x-\lambda(J)))\,\mathrm{d}\lambda(x).$

Note that in the above expression, $f_{A}(x-\lambda(J))=0$ for every
$x\in[0,\lambda(J))$. Splitting the integral from $[0,\lambda(I)]$ over
periods of length $\lambda(J)$, we may now deduce that

$\mu(X)-\mu(A)=\int_{0}^{\lambda(J)}\sum_{k=0}^{\infty}(f_{X}(x+k\lambda(J))-f_{A}(x+(k-1)\lambda(J)))\,\mathrm{d}\lambda(x).$
(3.2)

While for expository purposes we are taking the sum above over all
$k\in\mathbb{N}\cup\\{0\\}$, we remark that as before, it is, in practice, a
finite sum since for all $k>2\lceil\lambda(I)/\lambda(J)\rceil$ we have

$f_{X}(x+k\lambda(J))=f_{A}(x+(k-1)\lambda(J))=0$

as $X,A\subseteq[0,\lambda(I)+\lambda(J)]$. Now, fixing
$x_{0}\in[0,\lambda(J))$, we let $k_{0}=k_{0}(x_{0})\in\mathbb{N}\cup\\{0\\}$
satisfy

$f_{X}(x_{0}+k_{0}\lambda(J))=\max_{y\in x+\lambda(J)\mathbb{Z}}f_{X}(y).$

Since

$f_{X}(x)\geq\max\\{f_{A}(x),f_{A}(x-\lambda(J))\\}$

for every $x\in\mathbb{R}$ and $f_{A}(x-\lambda(J))=0$ for every
$x<\lambda(J)$, we see that

$\displaystyle\sum_{k=0}^{\infty}(f_{X}(x_{0}+k\lambda(J))$ $\displaystyle-
f_{A}(x_{0}+(k-1)\lambda(J)))\geq\sum_{k=0}^{k_{0}}(f_{X}(x_{0}+k\lambda(J))-f_{A}(x_{0}+(k-1)\lambda(J)))$
$\displaystyle=f_{X}(x_{0}+k_{0}\lambda(J))+\sum_{k=0}^{k_{0}-1}((f_{X}(x_{0}+k\lambda(J))-f_{A}(x_{0}+k\lambda(J))$
$\displaystyle\geq f_{X}(x_{0}+k_{0}\lambda(J)).$

Integrating the above for all $x_{0}\in[0,\lambda(J))$ and noting (3.2), we
obtain the claimed estimate

$\mu(X)-\mu(A)\geq\int_{0}^{\lambda(J)}\max_{y\in
x+\lambda(J)\mathbb{Z}}f_{X}(y)=\pi(X).$

In the rest of the proof we will assume that $\pi(X)<\mu(B)$ as otherwise we
are done by applying (3.1). Note that for every $a\in A$, we have

$\displaystyle\mu((a\cdot B)\setminus X)$ $\displaystyle\geq\max\\{\mu(a\cdot
B)-\mu(X\cap\psi^{-1}([\psi(a),\psi(a)+\lambda(J)])),0\\}$
$\displaystyle\geq\max\\{\mu(B)-\pi(X),0\\}.$

By the assumption that $\pi(X)<\mu(B)$, we have, for every $a\in A$, the
inequality

$\mu((a\cdot B)\setminus X)\geq\mu(B)-\pi(X).$

Let us now choose $b_{3}\in B$ uniformly at random with respect to $\mu$. Then
by Fubini’s theorem and the above inequality, we find that

$\displaystyle\mathbb{E}(\mu((A\cdot b_{3})\setminus X))$
$\displaystyle=\frac{1}{\mu(B)}\int_{G}\mathbbm{1}_{A}(a)\int_{G}\mathbbm{1}_{B}(b)\mathbbm{1}_{G\setminus
X}(a\cdot b)\,\mathrm{d}\mu(b)\,\mathrm{d}\mu(a)$
$\displaystyle=\frac{1}{\mu(B)}\int_{G}\mathbbm{1}_{A}(a)\mu((a\cdot
B)\setminus X)\,\mathrm{d}\mu(a)$
$\displaystyle\geq\frac{\mu(A)(\mu(B)-\pi(X))}{\mu(B)}.$

Therefore there exists $b_{3}\in B$ such that

$\mu((A\cdot b_{3})\setminus
X)\geq\frac{\mu(A)(\mu(B)-\pi(X))}{\mu(B)}\geq\mu(B)-\pi(X),$

where we have used the hypothesis that $\mu(B)\leq\mu(A)$. Combining this with
(3.1), we get that

$\mu(A\cdot\\{b_{1},b_{2},b_{3}\\})=\mu(X)+\mu((A\cdot b_{3})\setminus
X)\geq\mu(A)+\mu(B),$

which concludes the proof of Lemma 3.1 . ∎

With this in hand, we will now essentially divide our proof of Theorem 1.1
into two cases, the first being the setting when the set of popular products
$A\cdot_{\delta}B$, for some appropriate choice of $\delta$, is somewhat
large, wherein, probabilistic methods suffice to dispense the desired result.
The second case is when the set of popular products is small. Here, we will
first apply an inverse theorem to show that our sets $A,B$ can be mapped
surjectively to large subsets of some intervals in $\mathbb{T}$, whereupon, we
will apply Lemma 3.1 to deduce the claimed estimate. We now present the
deduction of our main result in the first of the above two cases.

######  Lemma 3.2.

Let $G$ be a connected, compact group, let $A,B\subseteq G$ be compact sets
and let $0<\delta<\min\\{\mu(A),\mu(B)\\}$ be a real number. Then for every
$c\geq(\mu(B)/\delta)^{2}$, there exist $b_{1},\dots,b_{c}\in B$ such that

$\mu(A\cdot\\{b_{1},\dots,b_{c}\\})\geq(1-O(\exp(-c^{1/2})))\mu(A\cdot_{\delta}B).$

###### Proof.

We choose a set with $c$ elements $B_{c}:=\\{b_{1},\dots,b_{c}\\}$ from $B$
uniformly at random. Note that an element $g$ is in $A\cdot B_{c}$ if and only
if at least one of $b_{i}$ in $b_{1},\ldots,b_{c}$ satisfies that
$b_{i}^{-1}\in g^{-1}A$. Thus, the probability that $g\in A\cdot B_{c}$ is

$1-\left(1-\frac{\mu(B\cap
A^{-1}g)}{\mu(B)}\right)^{c}=1-\left(1-\frac{\mathbbm{1}_{A}*\mathbbm{1}_{B}(g)}{\mu(B)}\right)^{c},$

and so, whenever $g\in A\cdot_{\delta}B$, then the probability that $g\in
A\cdot B_{c}$ is at least $1-(1-\delta/\mu(B))^{c}$. Since
$c\geq(\mu(B)/\delta)^{2}$, we may deduce that

$\left(1-\frac{\delta}{\mu(B)}\right)^{c}\leq\exp\left(-\frac{c\delta}{\mu(B)}\right)\ll\exp(-c^{1/2}),$

with the first inequality above following from the fact that for every
$x\in(0,1)$, one has $1-x\leq\exp(-x)$. Thus by Markov’s inequality, there
exists a choice of $\\{b_{1},b_{2},\dots,b_{c}\\}$ such that

$\mu((A\cdot_{\delta}B)\setminus(A\cdot\\{b_{1},b_{2},\dots,b_{c}\\}))\ll\exp(-c^{1/2})\mu(A\cdot_{\delta}B).$

This, in turn, implies that

$\displaystyle\mu(A\cdot\\{b_{1},b_{2},\dots,b_{c}\\})\geq(1-O(\exp(-c^{1/2})))\mu(A\cdot_{\delta}B),$

as desired. ∎

We are now ready to prove Theorem 1.1.

###### Proof of Theorem 1.1.

Given $\varepsilon>0$ and let $\eta=\eta(\varepsilon)$ be as in Theorem 2.2.
Let us first consider the case when

$\mu(A\cdot_{\eta\mu(B)}B)\leq\mu(A)+\mu(B)+\eta\mu(B).$

As $\mu(A)+\mu(B)\leq 1-\beta$ with some $\beta>0$, by letting $\varepsilon$
sufficiently small we may assume the right hand side of the above inequality
is smaller than $1$. Thus by Theorem 2.2, there is a continuous surjective
group homomorphism $\chi:G\to\mathbb{T}$, and two compact intervals
$I,J\subseteq\mathbb{T}$, so that with $\lambda$ the normalised Lebesgue
measure on $\mathbb{T}$,

$\lambda(I)\leq(1+\varepsilon)\mu(A),\qquad\lambda(J)\leq(1+\varepsilon)\mu(B),$

and $A\subseteq\chi^{-1}(I)$, $B\subseteq\chi^{-1}(J)$. By choosing a
sufficiently small $\varepsilon$, we may assume $\lambda(I)+\lambda(J)<1$.
Then by Lemma 3.1, there are $b_{1},b_{2},b_{3}\in B$ such that

$\mu(A\cdot\\{b_{1},b_{2},b_{3}\\})\geq\mu(A)+\mu(B).$

It remains to consider the case when

$\mu(A\cdot_{\eta\mu(B)}B)>\mu(A)+\mu(B)+\eta\mu(B).$

By Lemma 3.2, for every $c\geq\eta^{-2}$ there exist $b_{1},\dots,b_{c}$ from
$B$ such that

$\displaystyle\mu(A\cdot\\{b_{1},\dots,b_{c}\\})$
$\displaystyle\geq(1-O(\exp(-c^{1/2})))\mu(A\cdot_{\eta\mu(B)}B)$
$\displaystyle>(1-O(\exp(-c^{1/2})))(\mu(A)+\mu(B)+\eta\mu(B))$
$\displaystyle\geq\mu(A)+\mu(B),$

where the latter inequality follows by choosing $c$ to be sufficiently large
compared to $\alpha$ so as to ensure that

$\frac{\eta\mu(B)}{2}\geq\frac{\eta\alpha\mu(A)}{2}\gg\exp(-c^{1/2})\mu(A).$

This finishes the proof of Theorem 1.1. ∎

We conclude this section by notation that our inverse result Theorem 1.3
follows immediately from a combination of Theorem 2.2 and Lemma 3.2.

###### Proof of Theorem 1.3.

We will proceed by showing that the contra-positive statement holds true.
Thus, given $\varepsilon,\beta>0$, suppose that the conclusion of Theorem 1.3
does not hold. Applying Theorem 2.2, we may find $\eta^{\prime}>0$ such that

$\mu(A\cdot_{\eta^{\prime}\mu(B)}B)>\mu(A)+\mu(B)+\eta^{\prime}\min\\{\mu(A),\mu(B)\\}.$

Now by Lemma 3.2, for every $c\geq(\eta^{\prime})^{-1}$, there exist
$b_{1},\dots,b_{c}$ in $B$ such that

$\mu(A\cdot\\{b_{1},\dots,b_{c}\\})>(1-O(\exp(-c)))(\mu(A)+\mu(B)+\eta^{\prime}\min\\{\mu(A),\mu(B)\\}).$

As $\mu(B)>\alpha\mu(A)$, we may now set $\eta=\eta^{\prime}/2$ and note that
whenever $c$ is large enough, we will get

$\mu(A\cdot\\{b_{1},\dots,b_{c}\\})>\mu(A)+\mu(B)+\eta\min\\{\mu(A),\mu(B)\\}.$

This finishes the proof of Theorem 1.3. ∎

##  4\. Proof of Theorem 1.2

In this section, we will present the proof of Theorem 1.2 and we begin by
recording the following weaker version of Theorem 1.2 where we allow the
parameter $c=c(d)$ to also depend on the number of translates of a one
dimensional subspace that we would require to cover $A$.

######  Lemma 4.1.

For every $d,r\in\mathbb{N}$ with $d\leq r$, there exists $s\in\mathbb{N}$
with $s\leq 3dr^{2}$ such that the following holds true. Let $A$ be a finite,
non-empty subset of $\mathbb{Z}^{d}$ such that $\dim(A)=d$ and $A\subseteq
l_{1}\cup\dots\cup l_{r}$, where $l_{1},\dots,l_{r}$ are parallel lines such
that

$|A\cap l_{i}|\geq 2$

for each $1\leq i\leq r$. Then there exist $a_{1},\dots,a_{s}\in A$ such that

$|A+\\{a_{1},\dots,a_{s}\\}|\geq(d+1)|A|-3dr.$

We note that Lemma 4.1 and Theorem 1.5 combine together to deliver Theorem 1.2
in a straightforward manner.

###### Proof of Theorem 1.2.

Let $A\subseteq\mathbb{R}^{d}$ be a finite, non-empty set with $\dim(A)=d$.
Applying Theorem 1.5, we can either find $a_{1},\dots,a_{c}\in A$ such that

$|A+\\{a_{1},\dots,a_{c}\\}|\geq(d+1+1/16)|A|,$

or we have that $|A|\ll_{d}1$ or $A$ is contained in at most $(d+1)^{2}$
translates of some line $l$. We are done in the first case, and so, suppose
that $|A|\ll_{d}1$. In this case, we may take $\\{a_{1},\dots,a_{c}\\}=A$ and
apply (1.3) to deduce that

$|A+\\{a_{1},\dots,a_{c}\\}|=|A+A|\geq(d+1)|A|-d(d+1)/2,$

which is better than the desired bound. Thus, we now consider the final case
where $A$ is contained is at most $(d+1)^{2}$ translates of some line $l$.
Here, we may remove at most $2(d+1)^{2}$ many elements from $A$ to further
assume that $A$ is covered by translates $l_{1},\dots,l_{r}$ of $l$ with
$r\leq(d+1)^{2}$, such that $|A\cap l_{i}|\geq 2$ for every $1\leq i\leq r$.
In this setting, we may now apply Lemma 4.1 to obtain the desired bound in a
straightforward manner. ∎

Thus, our aim for the rest of this section is to prove Lemma 4.1.

###### Proof of Lemma 4.1.

We will prove this lemma by induction, and thus, note that when $d=1$, this
follows from (2.1). We may now assume that $d\geq 2$, in which case, we denote
$H$ to be the $(d-1)$-dimensional subspace orthogonal to $l_{1}$ and we let
$\pi:\mathbb{R}^{d}\to H$ be the natural projection map. We write $p_{i}=A\cap
l_{i}$ and $x_{i}=\pi(p_{i})$ for every $1\leq i\leq r$ as well as
$x^{\pi}=\pi^{-1}(x)\cap A$ for every $x\in H$. This allows us to define
$X=\pi(A)=\\{x_{1},\dots,x_{r}\\}$. Note that since $\dim(A)=d$, we have that
$\dim(X)=d-1$. Let $\mathcal{C}$ be the convex hull of $X$ and without loss of
generality, let $x_{r}\in X$ be an extreme point of $X$, that is, let $x_{r}$
be a vertex on the convex hull $\mathcal{C}$ of X. We now consider the set
$X^{\prime}=X\setminus\\{x_{r}\\}$ and its preimage $A^{\prime}=\\{a\in
A:\pi(a)\in X^{\prime}\\}$.

Noting that $d-2\leq\dim(X^{\prime})\leq d-1$, we divide our proof into two
cases, the first being when $\dim(X^{\prime})=d-2$. In this case, since
$\dim(X)=d-1$, we see that $x$ does not lie in the affine span of
$X^{\prime}$, whence, the sets

$\\{2x_{r}\\},X^{\prime}+\\{x_{r}\\}\ \ \text{and}\ \ X^{\prime}+X^{\prime}$

are pairwise disjoint. This, in turn, implies that the sets

$x_{r}^{\pi}+x_{r}^{\pi},x_{r}^{\pi}+x_{1}^{\pi},\dots,x_{r}^{\pi}+x_{r-1}^{\pi},A^{\prime}+A^{\prime}$

are pairwise disjoint. We may now apply the inductive hypothesis for
$A^{\prime}$ to deduce that there exist $a_{1},\dots,a_{s^{\prime}}\in
A^{\prime}$, with $s^{\prime}\leq 3(d-1)(r-1)^{2}$, such that

$|A^{\prime}+\\{a_{1},\dots,a_{s^{\prime}}\\}|\geq d|A^{\prime}|-3(d-1)(r-1).$
(4.1)

Let $I_{1}=\\{1\leq i\leq r:|x_{r}^{\pi}|\geq|x_{i}^{\pi}|\\}$ and let
$I_{2}=\\{1,\dots,r\\}\setminus I_{1}$. Given $i\in I_{1}$, we can apply (2.1)
for the sumset $x_{r}^{\pi}+x_{i}^{\pi}$ to obtain elements
$a_{i,1},\dots,a_{i,3}\in x_{i}^{\pi}$ such that

$|x_{r}^{\pi}+\\{a_{i,1},\dots,a_{i,3}\\}|\geq|x_{r}^{\pi}|+|x_{i}^{\pi}|-1.$

Similarly, for every $i\in I_{2}$, we can apply (2.1) for the sumset
$x_{r}^{\pi}+x_{i}^{\pi}$ to obtain elements $a_{i,1},\dots,a_{i,3}\in
x_{r}^{\pi}$ such that

$|x_{i}^{\pi}+\\{a_{i,1},\dots,a_{i,3}\\}|\geq|x_{r}^{\pi}|+|x_{i}^{\pi}|-1.$

Putting these two together along with (4.1), we obtain a set

$B=\\{a_{1,1},\dots,a_{r,3},a_{1},\dots,a_{s^{\prime}}\\}\subseteq A$

with $|B|\leq s^{\prime}+3r$ such that

$\displaystyle|A+B|$
$\displaystyle\geq|A^{\prime}+\\{a_{1},\dots,a_{s^{\prime}}\\}|+\sum_{i\in
I_{1}}|x_{r}^{\pi}+\\{a_{i,1},\dots,a_{i,3}\\}|+\sum_{i\in
I_{2}}|x_{i}^{\pi}+\\{a_{i,1},\dots,a_{i,3}\\}|$ $\displaystyle\geq
d|A^{\prime}|-3(d-1)(r-1)+\sum_{1\leq i\leq r}(|x_{r}^{\pi}|+|x_{i}^{\pi}|-1)$
$\displaystyle\geq(d+1)|A^{\prime}|+(r+1)|x_{r}^{\pi}|-r-3(d-1)(r-1)$
$\displaystyle\geq(d+1)|A|-3dr.$

Moreover, by the inductive hypothesis, we have

$|B|\leq s^{\prime}+3r\leq 3(d-1)(r-1)^{2}+3r\leq 3dr^{2},$

and consequently, we obtain the required conclusion in this case.

We now consider the case when $\dim(X^{\prime})=d-1$. In this case, we analyse
the convex hull $\mathcal{C}^{\prime}$ of $X^{\prime}$. Here, since
$\dim(X^{\prime})=d-1$ and since $x_{r}$ is an extreme point of $\mathcal{C}$,
we find elements $y_{1},\dots,y_{d-1}\in X^{\prime}$ such that

$\\{x_{r},(x_{r}+y_{1})/2,\dots,(x_{r}+y_{d-1})/2\\}\cap\mathcal{C}^{\prime}=\varnothing.$

This implies that the sumsets

$x_{r}^{\pi}+x_{r}^{\pi},x_{r}^{\pi}+y_{1}^{\pi},\dots,x_{r}^{\pi}+y_{d-1}^{\pi},A^{\prime}+A^{\prime}$

are pairwise disjoint. We see that $\dim(A^{\prime})=d$ because
$\dim(X^{\prime})=d-1$, and that $A^{\prime}$ is contained in $r-1$ parallel
lines. Thus, we may apply the inductive hypothesis for $A^{\prime}$ to obtain
$a_{1},\dots,a_{s^{\prime}}\in A^{\prime}$, with $s^{\prime}\leq 3d(r-1)^{2}$,
such that

$|A^{\prime}+\\{a_{1},\dots,a_{s^{\prime}}\\}|\geq(d+1)|A^{\prime}|-3d(r-1).$

Moreover, for every $1\leq i\leq d-1$, we fix an element $b_{i}\in
y_{i}^{\pi}$. Furthermore, we apply (2.1) for the set
$x_{r}^{\pi}+x_{r}^{\pi}$ to obtain elements $b_{d},b_{d+1},b_{d+2}\in
x_{r}^{\pi}$ satisfying

$|x_{r}^{\pi}+\\{b_{d},b_{d+1},b_{d+2}\\}|\geq 2|x_{r}^{\pi}|-1.$

As in the previous case, we see that the set
$B=\\{a_{1},\dots,a_{s^{\prime}},b_{1},\dots,b_{d+2}\\}\subseteq A$ satisfies

$\displaystyle|A+B|$
$\displaystyle\geq|A^{\prime}+\\{a_{1},\dots,a_{s}\\}|+|x_{r}^{\pi}+\\{b_{d},b_{d+1},b_{d+2}\\}|+\sum_{1\leq
i\leq d-1}|x_{r}^{\pi}+\\{b_{i}\\}|$
$\displaystyle\geq(d+1)|A^{\prime}|-3d(r-1)+2|x_{r}^{\pi}|-1+(d-1)|x_{r}^{\pi}|$
$\displaystyle\geq(d+1)|A|-3dr.$

Moreover, by the inductive hypothesis, we have that

$|B|\leq s^{\prime}+d+2\leq 3d(r-1)^{2}+3d\leq 3dr^{2},$

and so, we finish our proof of Lemma 4.1. ∎

##  5\. Proof of Theorem 1.5

Our goal in this section is to present the proof of Theorem 1.5. We begin by
noting the following asymmetric generalisation of Freiman’s lemma which was
given by Ruzsa [19]. Thus, whenever $A,B\subseteq\mathbb{R}^{d}$ are finite
sets with $\dim(A)=d$ and $|A|\geq|B|$, then

$|A+B|\geq|A|+d|B|-d(d+1)/2.$

Our first objective in this section is to show that in a slightly more
specific version of this setting, whenever $A+B$ is close to the above lower
bound, then both $A$ and $B$ can be efficiently covered by translates of a one
dimensional subspace, which, in turn, implies that both $A$ and $B$ have dense
subsets lying on translates of the same line.

######  Lemma 5.1.

Let $A,B\subseteq\mathbb{R}^{d}$ be finite sets with $\dim(A)=d$ and $|A|=|B|$
and

$|A+B|\leq|A|+(d+1/7)|B|-O_{d}(1).$

Then either $|A|\ll_{d}1$ or there exists some line $l$ and some
$x,y\in\mathbb{R}^{d}$ such that

$|A\cap(x+l)|\geq|A|/d\ \ \text{and}\ \ |B\cap(y+l)|\geq|B|/d.$

###### Proof.

This is true trivially when $A,B\subseteq\mathbb{R}$, whence, we may assume
that $d\geq 2$. Applying Lemma 2.7 with $k=2$, we may deduce that

$|A+A|\leq(d+8/7)^{2}|A|.$

We may now apply Lemma 2.3 to obtain parallel lines $l_{1},\dots,l_{r}$, with
$r\ll_{d}|A|^{1-\sigma}$ for some $\sigma\in(0,1/2]$ that only depends on $d$,
such that $A\subseteq l_{1}\cup\dots\cup l_{r}$ and

$|l_{1}\cap A|\gg_{d}|A|^{\sigma}.$

We now cover $B$ with lines that are parallel to $l_{1}$, and so, let
$q\in\mathbb{N}$ be the minimal natural number such that $B\subseteq
m_{1}\cup\dots\cup m_{q}$, where $m_{1},\dots,m_{q}$ are lines parallel to
$l_{1}$. Note that $q\ll_{d}|A|^{1-\sigma}$, since

$(d+8/7)|A|\geq|A+B|\geq\sum_{i=1}^{q}|l_{1}+m_{i}|\geq
q|l_{1}|\gg_{d}q|A|^{\sigma}.$

This allows us to apply Lemma 2.4, whence, we have

$|A+B|\geq|A|+\Big{(}d+1-\frac{1}{r-d+2}-\frac{1}{q-c+2}\Big{)}|B|-(d-1)(r+q),$

where $c=\min\\{d,\dim(B)\\}$. Here, since $r,q\ll_{d}|A|^{1-\sigma}$, we may
combine this with the hypothesis of Lemma 5.1 to see that

$\Big{(}\ \frac{6}{7}-\frac{1}{r-d+2}-\frac{1}{q-c+2}\
\Big{)}|B|\ll_{d}r+q\ll_{d}|A|^{1-\sigma}.$

Note that if $r>d$ or $q>c$, then

$1/(r-d+2)+1/(q-c+2)\leq 1/2+1/3=5/6,$

which combines with the above inequality to gives us $|A|=|B|\ll_{d}1$. On the
other hand, when $r=d$ and $q=c$, then we must have some $1\leq i\leq r$ and
$1\leq j\leq q$ such that

$|A\cap l_{i}|\geq|A|/r=|A|/d\ \ \text{and}\ \ |B\cap
m_{j}|\geq|B|/q=|B|/c\geq|B|/d.$

Thus, we conclude our proof of Lemma 5.1. ∎

With this in hand, we will now proceed with our proof of Theorem 1.5.

###### Proof of Theorem 1.5.

Our aim is to show that given a finite, non-empty set
$A\subseteq\mathbb{R}^{d}$ such that $\dim(A)=d$, we either have $|A|\ll_{d}1$
or $A$ is covered by at most $(d+1)^{2}$ translates of some line or we can
find elements $a_{1},\dots,a_{c}\in A$ such that

$|A+\\{a_{1},\dots,a_{c}\\}|\geq(d+1+1/16)|A|.$

Setting $K=(d+1+1/10)$ and $\varepsilon=100^{-d^{2}}$, we apply Lemma 2.5 to
obtain $c=c(d)>0$ and a set $A^{*}\subseteq A$ such that
$|A^{*}|\geq(1-100^{-d^{2}})|A|$ and such that if we select
$a_{1},\dots,a_{c}\in A^{*}$ uniformly at random from $A^{*}$, then

$\mathbb{E}_{a_{1},\dots,a_{c}\in
A^{*}}|A^{*}+\\{a_{1},\dots,a_{c}\\}|\geq\min\\{(1-100^{-d^{2}})|A^{*}+A^{*}|,(d+1+1/10)|A^{*}|\\}.$

Here, if

$(1-100^{-d^{2}})|A^{*}+A^{*}|\geq(d+1+1/10)|A^{*}|,$ (5.1)

then we have that

$\displaystyle\mathbb{E}_{a_{1},\dots,a_{c}\in
A^{*}}|A^{*}+\\{a_{1},\dots,a_{c}\\}|$
$\displaystyle\geq(1-100^{-d^{2}})(d+1+1/10)|A|$
$\displaystyle\geq(d+1+1/12)|A|,$

whence, we are done. Thus, we may assume that (5.1) does not hold true, in
which case, we obtain elements $a_{1},\dots,a_{c}\in A^{*}$ such that

$|A^{*}+\\{a_{1},\dots,a_{c}\\}|\geq(1-100^{-d^{2}})|A^{*}+A^{*}|.$ (5.2)

We now suppose that $\dim(A^{*})=m$ for some $1\leq m\leq d$. We first
consider the subcase when

$|A^{*}+A^{*}|\geq(m+1+1/10)|A^{*}|-m(m+1)/2.$ (5.3)

Here, since $\dim(A)=d$, we see that there exist elements
$b_{m+1},\dots,b_{d}\in A\setminus A^{*}$ which are linearly independent and
are not contained in the affine span of $A^{*}$. Thus, we may now set
$A^{\prime}=\\{a_{1},\dots,a_{c}\\}\cup\\{b_{m+1},\dots,b_{d}\\}$ to see that

$\displaystyle|A+A^{\prime}|$
$\displaystyle\geq|A^{*}+A^{\prime}|=|A^{*}+\\{a_{1},\dots,a_{c}\\}|+\sum_{i=m+1}^{d}|A^{*}+\\{b_{i}\\}|$
$\displaystyle\geq(1-100^{-d^{2}})|A^{*}+A^{*}|+(d-m)|A^{*}|$
$\displaystyle\geq(1-100^{-d^{2}})(m+1+1/10)|A^{*}|+(d-m)|A^{*}|-m(m+1)/2$
$\displaystyle\geq(d+1+1/15)|A^{*}|-m(m+1)/2$
$\displaystyle\geq(d+1+2/31)|A|-d(d+1),$

where the second and third inequalities utilise (5.2) and (5.3) respectively.
Thus we either have that

$|A+A^{\prime}|\geq(d+1+1/16)|A|$

or $|A|\ll_{d}1$, and so, we are done in this subcase.

Noting the above, we may now assume that (5.3) does not hold true. After
applying suitable affine transformations, we may employ Lemma 5.1 to show that
either $|A|\ll_{m}1$ or there exists some line $l$ in $\mathbb{R}^{d}$ such
that

$|A\cap l|\geq|A^{*}\cap l|\geq|A^{*}|/m\geq|A|(1-100^{-d^{2}})/d.$ (5.4)

Since $m\leq d$ we are done in the setting when $|A|\ll_{m}1$, and so, we may
assume that some $l$ exists such that (5.4) holds. We now cover $A$ with
translates of the line $l$, and so, let $l_{1},\dots,l_{r}$ be lines parallel
to $l$ such that

$A\subseteq l_{1}\cup\dots\cup l_{r},$

and $r$ is minimal. We may assume that $r\geq(d+1)^{2}+1$, since otherwise, we
are done. Moreover, writing $p_{i}=A\cap l_{i}$ for every $1\leq i\leq r$, we
may assume that

$|p_{1}|\geq\dots\geq|p_{r}|,$

and so,

$|p_{1}|\geq|A\cap l|\geq|A|(1-100^{-d^{2}})/d.$

Writing $r_{0}=(d+1)^{2}+1$, observe that the sumsets

$p_{1}+p_{1},\dots,p_{1}+p_{r_{0}}$

are pairwise disjoint, and so, we may apply (2.1) for each such sumset to
procure elements $a_{i,1},a_{i,2},a_{i,3}\in p_{i}$, for every $1\leq i\leq
r_{0}$, such that

$\displaystyle|A+\\{a_{1,1},\dots,a_{r_{0},3}\\}|$
$\displaystyle\geq\sum_{i=1}^{r_{0}}|p_{1}+\\{a_{i,1},\dots,a_{i,3}\\}|$
$\displaystyle\geq\sum_{i=1}^{r_{0}}(|p_{1}|+|p_{i}|-1)\geq r_{0}|p_{1}|$
$\displaystyle>(d+1)^{2}|A|(1-100^{-d^{2}})/d$ $\displaystyle\geq(d+2)|A|,$

This implies the desired bound, and consequently, we conclude the proof of
Theorem 1.5. ∎

## References

  * [1] Béla Bollobás, Imre Leader, and Marius Tiba, _Large sumsets from small subsets_ , arXiv:2204.07559 (2022).
  * [2] by same author, _A strengthening of Freiman’s $3k-4$ theorem_, arXiv:2204.09816, to appear in Bulletin of the LMS (2022).
  * [3] Emmanuel Breuillard, Ben Green, and Terence Tao, _The structure of approximate groups_ , Publ. Math. Inst. Hautes Études Sci. 116 (2012), 115–221.
  * [4] Pablo Candela, Oriol Serra, and Christoph Spiegel, _A step beyond Freiman’s theorem for set addition modulo a prime_ , J. Théor. Nombres Bordeaux 32 (2020), no. 1, 275–289.
  * [5] Mei-Chu Chang, _The Erdős-Szemerédi problem on sum set and product set_ , Ann. of Math. 157 (2003), no. 3, 939–957.
  * [6] Michael Christ and Marina Iliopoulou, _Inequalities of Riesz-Sobolev type for compact connected abelian groups_ , Amer. J. Math. 144 (2022), no. 5, 1367–1435.
  * [7] Gerald B. Folland, _A course in abstract harmonic analysis_ , Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1995.
  * [8] Jacob Fox, Sammy Luo, Huy Tuan Pham, and Yunkun Zhou, _Small subsets with large sumset: Beyond the Cauchy–Davenport bound_ , arXiv:2210.07196 (2022).
  * [9] Gregory Freiman, _Foundations of a structural theory of set addition_ , Translated from the Russian. Translations of Mathematical Monographs 37 (1973), American Mathematical Society, Providence, R. I., 1973. vii+108 pp.
  * [10] by same author, _Structure theory of set addition_ , Astérisque 258 (1999), 1–33.
  * [11] Ben Green and Terence Tao, _Compressions, convex geometry and the Freiman-Bilu theorem_ , Q. J. Math. 57 (2006), no. 4, 495–504.
  * [12] Yifan Jing, _The Riesz rearrangement inequality and its inverse theorem over compact groups_ , in preparation (2023).
  * [13] Yifan Jing and Chieu-Minh Tran, _A Cauchy–Davenport theorem for locally compact groups_ , arXiv:2106.02924 (2021).
  * [14] by same author, _Measure growth gap in compact semisimple Lie groups and the Kemperman inverse problem_ , arXiv:2303.15628 (2023).
  * [15] Johannes Kemperman, _On products of sets in a locally compact group_ , Fund. Math. 56 (1964), 51–68.
  * [16] Martin Kneser, _Summenmengen in lokalkompakten abelschen Gruppen_ , Math. Z. 66 (1956), 88–110.
  * [17] Akshat Mudgal, _Sums of linear transformations in higher dimensions_ , Q. J. Math. 70 (2019), no. 3, 965–984.
  * [18] by same author, _New lower bounds for cardinalities of higher dimensional difference sets and sumsets_ , Discrete Analysis (2022), Paper no. 15, 19pp.
  * [19] Imre Ruzsa, _Sum of sets in several dimensions_ , Combinatorica 14 (1994), no. 4, 485–490.
  * [20] Tom Sanders, _The structure theory of set addition revisited_ , Bull. Amer. Math. Soc. (N.S.) 50 (2013), no. 1, 93–127.
  * [21] Xuancheng Shao, _On an almost all version of the Balog-Szemerédi-Gowers theorem._ , Discrete Analysis (2019), Paper No. 12, 18 pp.
  * [22] Yonutz V. Stanchescu, _The structure of d-dimensional sets with small sumset_ , J. Number Theory 130 (2010), no. 2, 289–303.
  * [23] Terence Tao, _An inverse theorem for an inequality of Kneser_ , Proc. Steklov Inst. Math. 303 (2018), no. 1, 193–219.
  * [24] Terence Tao and Van Vu, _Additive combinatorics_ , Cambridge Studies in Advanced Mathematics 105 (2006), Cambridge University Press, Cambridge.