---
abstract: 'For $\delta>0$ sufficiently small and $A\subset \mathbb{Z}^k$ with $|A+A|\le (2^k+\delta)|A|$, we show either $A$ is covered by $m_k(\delta)$ parallel hyperplanes, or satisfies $|{\widehat{\operatorname{co}}}(A)\setminus A|\le c_k\delta |A|$, where ${\widehat{\operatorname{co}}}(A)$ is the smallest convex progression (convex set intersected with a sublattice) containing $A$. This generalizes the Freiman-Bilu $2^k$ theorem, Freiman’s $3|A|-4$ theorem, and recent sharp stability results of the present authors for sumsets in $\mathbb{R}^k$ conjectured by Figalli and Jerison.'
author:
- 'Peter van Hintum, Hunter Spink, Marius Tiba'
bibliography:
- 'references.bib'
title: 'Sets in $\mathbb{Z}^k$ with doubling $2^k+\delta$ are near convex progressions'
---

Introduction
============

One of the central questions in additive combinatorics is the inverse sumset problem of characterizing the finite subsets $A$ of abelian groups with small *doubling constant* $|A+A|\cdot|A|^{-1} \le \lambda $ for fixed $\lambda>0$. In this paper, we will consider the inverse sumset problem in torsion-free abelian groups $\mathbb{Z}^k$, which has been studied from a variety of perspectives by Freiman [@Freiman], Green and Tao [@GreenTao], Chang [@Chang], and Sanders [@Revisited] among others. For $A \subset \mathbb{Z}^k$, define the convex progression ${\widehat{\operatorname{co}}}(A)$ to be the intersection of the real convex hull $\widetilde{{\operatorname{co}}}(A)$ with the affine sub-lattice $\Lambda_A$ spanned by $A$. An $r$-dimensional generalized arithmetic progression in $\mathbb{Z}^k$ is a subset of the form $B(n_1,\ldots,n_r;v_1,\ldots,v_r;b):=\left\{b+\sum_{i=1}^r\ell_iv_i: 0 \le \ell_i < n_i\right\}.$

Motivated by the fact that for $\widetilde{A}\subset \mathbb{R}^k$ the doubling constant (with respect to volume) is at least $2^k$, we define $d_k(A)=|A+A|-2^k|A|$ for $A\subset \mathbb{Z}^k$. Our main result describes the structure of $A\subset \mathbb{Z}^k$ with $d_k(A)\le \Delta_k|A|$, i.e. $|A+A|\le (2^k+\Delta_k)|A|$.

\[mainthm\]\[quant\]

a)  For $k\geq 1$, there are constants $\Delta_k, m_k,\epsilon_k,$ such that for $A\subset \mathbb{Z}^k$ with $d_k(A)\leq \Delta_k|A|$, either $A$ is covered by $m_k$ parallel hyperplanes, or $A$ lies in some $B=B(n_1,\ldots,n_k;v_1,\ldots,v_k;b)$ with $v_1,\ldots,v_k$ linearly independent and $|A|\ge \epsilon_k |B|$.

b)  For $k\geq 1$, there are constants $c_k< (4k)^{5k}$, and constants $ \Delta_k(\epsilon_0), g_k(\epsilon_0)$ for all $\epsilon_0>0$, such that for $A\subset \mathbb{Z}^k$ with $d_k(A) \le \Delta_k(\epsilon_0)|A|$, if $A$ lies in some $B=B(n_1,\ldots,n_k;v_1,\ldots,v_k;b)$ with $v_1,\ldots,v_k$ linearly independent and $|A|\ge \epsilon_0 |B|$, then $$|{\widehat{\operatorname{co}}}(A)\setminus A|\le c_kd_k(A)+g_k(\epsilon_0)\min\{n_i\}^{-\frac{1}{1+\frac{1}{2}(k-1)\lfloor k/2 \rfloor}}|A|.$$

\[maincor\] There are constants $c_k< (4k)^{5k}$, $\Delta_k$, $m_k(\delta)$ such that for $\delta\in (0,\Delta_k]$ and $A\subset \mathbb{Z}^k$ with $d_k(A)\leq \delta |A|$, either $A$ is covered by $m_k(\delta)$ parallel hyperplanes, or $$|{\widehat{\operatorname{co}}}(A)\setminus A|\le c_k\delta |A|.$$

\[mainfigalli\] There are constants $c_k< (4k)^{5k}, \Delta_k$ such that for $\widetilde{A} \subset \mathbb{R}^k$ of positive measure with $|\widetilde{A} +\widetilde{A} | \le (2^k+\Delta_k)|\widetilde{A} |$, we have $ |{\widetilde{\operatorname{co}}}(\widetilde{A}) \setminus \widetilde{A}| \le c_k (|\widetilde{A} +\widetilde{A} | - 2^k|\widetilde{A} |).$ Here $|\cdot|$ denotes the outer Lebesgue measure.

directly generalizes the Freiman-Bilu $2^k$ theorem [@Freiman; @Bilu] (as improved by Green and Tao [@GreenTao]), Freiman’s $3|A|-4$ theorem [@Freiman] for $A\subset \mathbb{Z}$, and the sharp stability of the Brunn-Minkowski inequality for equal sets in $\mathbb{R}^k$, conjectured by Figalli and Jerison [@Semisum], and recently proved by the authors of the present paper [@HomoBM].

As a consequence of a) and we have that for $A\subset \mathbb{Z}^k$ not contained in a bounded (in terms of $\delta$) number of parallel hyperplanes, the fact that $d_k(A)\le O(\delta)|A|$ is the same as the fact that $A$ satisfies $|{\widehat{\operatorname{co}}}(A)\setminus A|\le O(\delta)|A|$ and has density at least $\epsilon_k$ in a $k$-dimensional generalized arithmetic progression. We note that for a set $A$ symmetric about a lattice point, the discrete John’s theorem of Tao and Vu [@TAOVu] implies ${\widehat{\operatorname{co}}}(A)$ has positive density in a $k$-dimensional generalized arithmetic progression, so in this case the density condition is superfluous.

The reverse implication in the previous paragraph follows from a weak converse to b), that if $A\subset B=B(n_1,\ldots,n_k;v_1,\ldots,v_k;b)$, $|A| \ge \epsilon_0 |B|$ and $|{\widehat{\operatorname{co}}}(A)\setminus A|\leq \delta' |A|$ then $d_k(A)\le (2^k\delta' + O(\min\{n_i\})^{-1})|A|$ (see and ), and $A$ is covered by $\min\{n_i\}$ parallel hyperplanes.

, conjectured by Figalli and Jerison [@Semisum] and recently resolved by the authors of the present paper [@HomoBM] without any digression to the discrete setting, follows by standard approximation techniques from . This result similarly yields a characterization of positive measure $\widetilde{A}\subset \mathbb{R}^k$ with $d_k(\widetilde{A}) \le O(\delta)|\widetilde{A}|$ as equivalently having $|\widetilde{{\operatorname{co}}}(\widetilde{A})\setminus \widetilde{A}| \le O(\delta)|\widetilde{A}|$.

First, we recall Green and Tao’s improvement [@GreenTao] to the classical Freiman-Bilu $2^k$-theorem.

\[mainbilu\] Given $\delta>0$, there is a constant $m_k(\delta)$ such that if $A\subset \mathbb{Z}^k$ has $|A+A|\le (2^k-\delta)|A|$, then $A$ is covered by $m_k(\delta)$ parallel hyperplanes.

The Freiman-Bilu theorem shows that the correct notion of degeneracy in $\mathbb{Z}^k$ is being covered by a bounded number of parallel hyperplanes, and non-degenerate sets $A$ have doubling constant bounded below by roughly $2^k$. This reflects the continuous analogue for measurable $\widetilde{A}\subset \mathbb{R}^k$. formally implies the Freiman-Bilu theorem, and extends the scope of the theorem beyond the $2^k$ threshold.

Next, we recall Freiman’s $3|A|-4$ theorem, which marked the beginning of the study of inverse problems in additive combinatorics.

\[3A-4\] Let $A\subset \mathbb{Z}$ be a subset of the integers with $d_1(A)\le |A|-4$. Then $|{\widehat{\operatorname{co}}}(A)\setminus A| \le d_1(A)+1$.

This result is sharp, both in the linear bound on $d_1(A)$ in terms of $|A|$ (there are examples of sets $A$ with fixed $d_1(A)=|A|-3$ and $|{\widehat{\operatorname{co}}}(A)\setminus A|$ arbitrarily large in terms of $|A|$), and in the linear bound on $|{\widehat{\operatorname{co}}}(A)\setminus A|$ in terms of $d_1(A)$.

is a direct generalization of Freiman’s $3|A|-4$ theorem to arbitrary dimension. The bound $c_k\delta$ is optimal up to the constant $c_k$. The bound $\Delta_k$ on $\delta$ is necessary as before. The additional condition of not being covered by $m_k(\delta)$ hyperplanes is also necessary, and has no analogue when $k=1$ (as subsets $A\subset \mathbb{Z}$ cannot exhibit lower dimensional degeneracies). Consider for example the set $A=(\{1,\ldots,n_0\}\times\{1,\ldots,2n\}^{k-1}) \cup \{(-1,1,1,\ldots,1)\}$, where $n_0$ is constant and $n\gg n_0$, which has $d_k(A)<0$ and $|{\operatorname{co}}(A) \setminus A| =   \frac{|A|-1}{2^{k-1} n_0}$.

Furthermore, is the first result for $A\subset \mathbb{Z}^k$ with doubling constant beyond the $2^k$ threshold besides the coarse characterizations given by Freiman’s general theorem on sets with small doubling [@Freiman] and subsequent optimizations (see the beginning of ). To our knowledge even a weaker result with $c_k\delta$ replaced with a function $\omega(\delta)$ with $\omega(\delta) \rightarrow 0$ as $\delta \to 0$ was not previously known. As it turns out, much of the work in proving the quantitative statement of is devoted to proving the following qualitative statement.

\[quali\]\[qual\] Given $\epsilon_0,\delta>0$ and $k\geq 1$, there exist $n_k(\epsilon_0,\delta)$ and $\omega(\epsilon_0,\delta)$ where for fixed $\epsilon_0$ we have $\omega(\epsilon_0,\delta)\to 0$ as $\delta \to 0$ such that the following is true. If $A$ lies in some $B=B(n_1,\ldots,n_k;v_1,\ldots,v_k;b)$ with $v_1,\ldots,v_k$ linearly independent and $n_1,\ldots,n_k \ge n_k(\epsilon_0,\delta)$ ,such that $|A|\ge \epsilon_0 |B|$ and $d_{k}(A)\le \delta |A|$, then $|{\widehat{\operatorname{co}}}(A)\setminus A|\le \omega(\epsilon_0,\delta)|A|.$

A continuous analogue of proved by Christ [@Christ] and strengthened by Figalli and Jerison [@FigJerJems] was a key step in the study of stability results for the Brunn-Minkowski inequality. However, our methods are largely different from [@Christ] and [@FigJerJems], especially because of phenomena which occur in the discrete setting which have no continuous analogue.

We mention a particularly nice intermediate result we show during the proof of . For a real-valued function $f$ on a convex progression $A={\widehat{\operatorname{co}}}(A)$, we define the *infimum-convolution* (see e.g. Strömberg’s extensive survey [@Infconvsurvey]) $f^{\square}:A+A\to \mathbb{R}$ by $$f^{\square}(z)=\min_{x+y=z}\{f(x)+f(y)\}.$$

\[squarepropintro\] There exist constants $c_{k+1}'$ and $g_{k+1}'(\epsilon_0)>0$ for $\epsilon_0>0$ such that the following is true. Let $A={\widehat{\operatorname{co}}}(A)\subset B(n_1,\ldots,n_k;v_1,\ldots,v_k;b)$ with $v_1,\ldots,v_k$ linearly independent, $|A|\ge \epsilon_0|B|$, and $f:A\to [0,1]$ a function. Then with $\widehat{f}:A\to [0,1]$ the lower convex hull function, $$\sum_{x\in A}(f-\widehat{f})(x)\le c'_{k+1}\left( 2^{k+1}\sum_{x\in A}f(x)-\sum_{x'\in A+A} f^{\square}(x')\right)+g_{k+1}'(\epsilon_0)\min\{n_i\}^{-\frac{1}{1+\frac{1}{2}k\lfloor(k+1)/2\rfloor}}|A|.$$

follows from our main results applied to the epigraph $A'_{f,N,M}=\{(a,x):a\in A,x \in [Nf(a),M]\}\subset A\times [0,M]$ for $1 \ll N \ll M$ large constants for fixed $A$ (note that the choice of $M$ allows us to avoid having the condition given by $\Delta_{k+1}$). (used in the proof of ) is essentially this statement for $A$ a simplex with a smaller error term $g_{k+1}'(\epsilon_0)\min\{n_i\}^{-1}|A|$ (and with $c_k'\mapsto c_k'^{-1}$).

We remark that the constant $c_k$ in (as well as the constants from and ) can be taken to be less than $(4k)^{5k}$ (which was the constant found in [@HomoBM]), and the constant $c_k'$ can be taken to be at most $c_k$. We have the lower bound $c_k \ge \frac{2^k}{k}$, attained for example by the set $A$ with $ \frac{1}{n}A:=((\widetilde{T} \times [-2,0]) \cup (V(\widetilde{T}) \times \{1\})) \cap (\frac{1}{n}\mathbb{Z})^k$, where $\widetilde{T}\subset \mathbb{R}^{k-1}$ is a fixed simplex with vertices $V(\widetilde{T})\subset \mathbb{Z}^{k-1}$ and $n$ sufficiently large. We also have $c_k'\ge \frac{2^k}{k}$ by taking the functional version of this example, namely with $f:(n\widetilde{T}\cap \mathbb{Z}^k)\to [0,1]$ whose value is $0$ at the vertices and $1$ elsewhere. We believe that the optimal values of $c_k,c_k'$ lie closer to the lower bound $\frac{2^k}{k}$.

What are the optimal values of $c_k$ and $c_k'$?

Finally, we remark on the exponent $-\frac{1}{1+(k-1)\lfloor k/2\rfloor}$ in . Our proof of reduces the case that ${\widetilde{\operatorname{co}}}(A)$ is a simplex. For a general $A$ we first approximate ${\widetilde{\operatorname{co}}}(A)$ from within by a polytope $\widetilde{P}$, and then triangulate $\widetilde{P}$ into simplices via a triangulation of $\partial \widetilde{P}$. To approximate the volume of ${\widetilde{\operatorname{co}}}(A)$ by a polytope $\widetilde{P}$ with $|\widetilde{P}|\ge(1-\alpha)|{\widetilde{\operatorname{co}}}(A)|$ requires $\ell=O(\alpha^{-\frac{2}{k-1}})$ vertices by Gordon, Meyer, and Reisner [@BestApproximation], and the proof of the upper bound conjecture by Stanley [@Stanley] implies that a triangulation of $\partial \widetilde{P}$ has at most $O(\ell^{\lfloor k/2 \rfloor})$ simplicies. These two bounds end up giving the exponent in .

Prior Work {#PriorWork}
----------

Freiman’s theorem [@Freiman] on sets with small doubling says there are constants $b_1(\lambda),b_2(\lambda),b_3(\lambda)$ such that any finite subset $A\subset \mathbb{Z}^k$ with doubling constant less than $\lambda$ can be covered by $b_1(\lambda)$ translates of a generalized arithmetic progression of size at most $b_2(\lambda)|A|$, and of dimension at most $b_3(\lambda)$. Freiman originally formulated his theorem in terms of convex progressions (images of sets of the form ${\widehat{\operatorname{co}}}(A')$ under affine linear maps) instead of generalized arithmetic progressions, and much of the literature focuses on this formulation. Generalizations of convex progressions were used implicitly by Bourgain [@Bourgain], and Green-Sanders [@GreenSanders] (see Sander’s extensive survey [@Revisited] for more information). We note that many authors require convex progressions to be symmetric, but in this paper we impose no such assumptions.

Although we focus on subsets of $\mathbb{Z}^k$, we remark briefly that Freiman’s theorem has been generalized to arbitrary abelian groups by Green and Ruzsa [@GreenRusza], and the recent literature on approximate groups seeks to describe analogous characterizations in non-abelian groups (see for example the seminal work of Breuillard, Green and Tao [@ApproxGroup]).

The constants $b_1(\lambda)$, $b_2(\lambda)$, and $\exp(b_3(\lambda))$ cannot all be brought down to polynomial as shown by Lovett and Regev [@counterexample], but the analogous question reformulated in terms of (symmetric) convex progressions is open (the *polynomial Freiman-Ruzsa conjecture*). Green and Ruzsa [@GreenRusza], Chang [@Chang], Bourgain [@Bourgain], and Green and Tao [@GreenTao2] showed the constants could be reduced to $b_1(\lambda)=b_2(\lambda)=\exp(b_3(\lambda))=\exp(O(\lambda^C))$ for some constant $C$, improved by Schoen [@Schoen] to $\exp(\exp(O(\sqrt{\log(\lambda)}))$, and finally improved by Sanders [@Revisited] to $\exp(O(\log^{3+o(1)}\lambda))$.

For $\mathbb{Z}^k$, Green and Tao [@GreenTao] showed we can obtain optimal bounds for the dimension and sizes of these generalized arithmetic progressions, at the cost of the number of translates. In particular, for $\lambda\in [2^k,2^{k+1})$ we may take $b_2(\lambda)=1$ and $b_3(\lambda)=k$. Our a) shows that when $\lambda \le 2^k+\Delta_k$, then under the non-degeneracy hypothesis that $A$ is not covered by $m_k$ parallel hyperplanes, we can take $b_1(\lambda)=1,b_3(\lambda)=k$.

The “thickness” of a subset $A\subset \mathbb{Z}^k$, is the minimum number of parallel hyperplanes required to cover $A$. The central result relating the doubling of a set $A$ to its thickness is the Freiman-Bilu $2^k$-theorem [@Bilu; @Freiman; @GreenTao], . There is a large literature of classifications of subsets $A\subset \mathbb{Z}^k$ with doubling at most $2^k-\delta$ (see e.g. Fishburn [@Fishburn], Freiman [@Freiman], Grynkiewicz and Serra [@Grynkiewicz], and Stanchescu [@Stanchescu1; @Stanchescu1.5; @Stanchescu2; @Stanchescu3]). For $k=1$ Freiman’s $3|A|-4$ theorem [@Freiman], , and subsequent improvements by Jin [@Jin] go beyond this threshold, but even for $k=2$ there do not appear to have been any such results beyond $2^k-\delta$.

Without thickness assumptions, Gardner and Gronchi [@Gardner] proved for $A,C\subset \mathbb{Z}^{k}$ not lying in hyperplanes an optimal lower bound for $|A+C|$, but the bound is far worse than $(|A|^{\frac{1}{k}}+|C|^{\frac{1}{k}})^{k}$ predicted by the Brunn-Minkowski inequality for measurable sets in $\mathbb{R}^k$. Under thickness assumptions, the situation is better. For example, by a result of Green and Tao [@GreenTao] (following an approach of Bollobás and Leader [@Bollobas]), if $A,C \subset B(n_1,\ldots,n_k;v_1,\ldots,v_k;b)$ and $|A|,|C| \ge \epsilon |B|$ then $|A+C|\ge (2^k + O(\epsilon\min(n_i))^{-1})\min(|A|,|C|)$. Showing a general form of the Brunn-Minkowski inequality for thick sets is open (see [@Ruzsa Conjecture 3.10.12]), though progress in this direction has been made by Cifre, María, and Iglesias [@Cifre].

The sharp stability result for the Brunn-Minkowski inequality for equal sets, conjectured by Figalli and Jerison [@Semisum], was recently resolved by the authors of the present paper in [@HomoBM]. Our is a discrete analogue of this continuous stability result, and in fact implies it as mentioned earlier. A crucial component used in [@HomoBM] was having a “qualitative result” which shows that $|{\widetilde{\operatorname{co}}}(A)\setminus \widetilde{A}| |\widetilde{A}|^{-1}\to 0$ as $|\widetilde{A}+\widetilde{A}|\cdot |\widetilde{A}|^{-1}\to 2^k$. Such a result was first proved by Christ [@Christ] and later with explicit constants by Figalli and Jerison [@FigJerJems].

Proving discrete analogues of stability results for the Brunn-Minkowski inequality for thick subsets $A,C \subset \mathbb{Z}^k$, such as that of Christ [@Christ] and Figalli and Jerison [@FigJerAdv] for general sets, or sharp stability results such as Barchiesi and Julin [@Barchiesi] for one of the sets being convex and the present authors [@1911.11945] for arbitrary two-dimensional sets, would be extremely interesting, and we believe would be a worthwhile goal to pursue.

Outline of the Paper {#outlineofpaper}
--------------------

As mentioned before, most of the work is devoted to proving . The strategy is to construct in stages a highly structured set $A_{\star}$ from $A$ with the properties that $|A \Delta A_{\star}| =o_{\epsilon_0}(1) |A|$ and $d_k(A_{\star}) =o_{\epsilon_0}(1)|A_{\star}|=o_{\epsilon_0}(1)|A|$ (where for fixed $\epsilon_0$ we have $o_{\epsilon_0}(1)\to 0$ as $\delta \to 0$). The additional structure of $A_{\star}$ enables us to conclude that $|{\widehat{\operatorname{co}}}(A_{\star}) \setminus A_{\star}| =o_{\epsilon_0}(1)|A_{\star}|$, which finally implies that $|{\widehat{\operatorname{co}}}(A) \setminus A| =o_{\epsilon_0}(1)|A|$.

At each stage we produce a new set $A_{\text{new}}$ from an existing set $A_{\text{old}}$ which satisfies $|A\Delta A_{old}|=o_{\epsilon_0}(1)|A|$ and $d_k(A_{old})=o_{\epsilon_0}(1)|A|$. With a single exception, this is done by throwing away rows $R_x$ in the first coordinate direction which are are in some sense unstructured. If we can show $|A_{old}\setminus A_{new}|=o_{\epsilon_0}(1)|A|$, then $|A\Delta A_{new}|=o_{\epsilon_0}(1)|A|$ and hence we have $d_k(A_{new})=o_{\epsilon_0}(1)|A|$.

To bound $|A_{\text{old}} \setminus A_{\text{new}}|$ from above, we introduce an operation $(+)$ in order to create a “reference set” $A_{\text{old}}(+)A_{\text{old}}\subset A_{\text{old}}+A_{\text{old}}$, whose size we can guarantee to be approximately $2^k|A_{\text{old}}|$. For one dimensional sets $X, Y$ we define $X(+)Y:= (X+\min Y)\cup (Y+ \max X) \subset X+Y$; in general, we define $A_{\text{old}}(+)A_{\text{old}}:=\bigsqcup_{\vec{v}\in \{0,1\}^{k-1}}\bigsqcup_{x}R_x(+)R_{x+\vec{v}} \subset A_{\text{old}}+A_{\text{old}}$.

In order to control the size of the unstructured rows $U:=\bigsqcup_{x\text{ - unstructured}}R_x$, we construct a set $D \subset U+A_{\text{old}} \subset A_{\text{old}}+A_{\text{old}} $ of comparable size to $U$, disjoint from $A_{\text{old}}(+)A_{\text{old}}$. Then, we will obtain $|A_{\text{old}} \setminus A_{\text{new}}|=|U| \approx |D| \le |A_{\text{old}}+A_{\text{old}}| - |A_{\text{old}}(+)A_{\text{old}}| \approx d_k(A_{\text{old}})=o_{\epsilon_0}(1)|A|$.

For the last step in the proof of and for the proof of b), we use two versions of an argument inspired by the one used in [@HomoBM]. For the last part of , we prove that functions on convex domains with small infimum-convolution are close to their convex hulls (which is essentially ). For b), we proceed as follows. By choosing an appropriately small $\Delta_k(\epsilon_0),$ ensures $|{\widehat{\operatorname{co}}}(A)\setminus A|\cdot |A|^{-1}$ is as small as we like. This guarantees a large interior region of ${\widehat{\operatorname{co}}}(A+A)$ is contained in $A+A$. We control the size of ${\widehat{\operatorname{co}}}(A)\setminus A$ by inductively controlling the size of ${\widehat{\operatorname{co}}}(A)\setminus A$ restricted to certain homothetic copies of $\widetilde{{\operatorname{co}}}(A)$ used to cover a thickened boundary of $\widetilde{{\operatorname{co}}}(A)$. This will allow us to show that $|{\widehat{\operatorname{co}}}(A+A)\setminus (A+A)|\leq (2^k-c_k')|{\widehat{\operatorname{co}}}(A)\setminus A|+o_{\epsilon_0}(1)|B|$ for some constant $c_k'$, which allows us to conclude b).

Finally, for a), we will start with a result of Green and Tao [@GreenTao] that $A$ is covered by a bounded number of generalized arithmetic progressions of dimension $k$ and size at most $|A|$, and show that we can reduce to a single generalized arithmetic progression of size $O(|A|)$.

In Section 2, we make some initial definitions, conventions and observations, which will be used throughout the paper. In Sections 3 and 4, we prove and b) with a simultaneous induction on dimension. In Section 5, we prove a), whose proof is independent of Sections 3 and 4. Finally, for completeness, we include in Appendix A a proof of and from .

Definitions, Conventions, and Observations
==========================================

In this section, we introduce our definitions and conventions, as well as observations we will be using throughout the remaining sections.

Definitions and Conventions
---------------------------

For $A'\subset \mathbb{Z}^k$, we denote by

-   $\widetilde{{\operatorname{co}}}(A')\subset \mathbb{R}^k$ for the convex hull,

-   ${\operatorname{co}}(A')=\widetilde{{\operatorname{co}}}(A')\cap \mathbb{Z}^k$,

-   $\Lambda_{A'}=\langle A'-a\rangle+a\subset \mathbb{Z}^k$ for any $a\in A'$, the affine sublattice of $\mathbb{Z}^k$ spanned by $A'$, and

-   ${\widehat{\operatorname{co}}}(A')={\operatorname{co}}(A')\cap \Lambda_{A'}$, the smallest convex progression containing $A'$.

We say that $A'$ is *reduced* if $\Lambda_{A'}=\mathbb{Z}^k$, or equivalently ${\operatorname{co}}(A')={\widehat{\operatorname{co}}}(A')$ and $A'$ is not contained in a hyperplane.

We will typically denote regions of $\mathbb{R}^k$ with a tilde such as $\widetilde{A'}\subset \mathbb{R}^k$. By abuse of notation, we will use $|\cdot |$ to refer both to cardinality of sets, and for volumes of sets. It will be clear with the tilde notation whether we intend to use discrete or continuous volume, and from context what dimension we are considering.

When we define a polytope or affine subspace $\widetilde{P}\subset \mathbb{R}^k$, we let $P=\widetilde{P}\cap \mathbb{Z}^k$.

Given numbers $n_1,\ldots,n_k$, we define the discrete box $$B(n_1,\ldots,n_k)=\prod_{i=1}^k \{1,\ldots,n_i\}.$$ We write $B$ instead of $B(n_1,\ldots,n_k)$ when $n_1,\ldots,n_k$ are clear from context.

In and b), we shall assume without loss of generality that the vectors $v_i$ coincide with basis vectors $e_i$ of $\mathbb{R}^k$ and $b=\vec{1}$, writing the generalized arithmetic progression $B=B(n_1,\ldots,n_k;v_1,\ldots,v_k;b)=B(n_1,\ldots,n_k)$.

\[redconv\] In the proofs of and b), we shall assume $A$ is reduced, as allowed by below.

We define the projection $$\pi:\mathbb{Z}^k=\mathbb{Z}\times\mathbb{Z}^{k-1}\to \{0\}\times\mathbb{Z}^{k-1}$$ to be the projection away from the first coordinate.

For $\widetilde{A'}\subset \mathbb{R}^k$ a subset such that ${\widetilde{\operatorname{co}}}(\widetilde{A'})$ is a polytope with integral vertices, we define $V(\widetilde{A'})\subset \mathbb{Z}^{k}$ to be the vertices of ${\widetilde{\operatorname{co}}}(\widetilde{A}')$, and $V_\pi(\widetilde{A'}):=\pi(V(\widetilde{A}'))\subset \{0\}\times \mathbb{Z}^{k-1}$.

A *row* of $A'\subset \mathbb{Z}^k$ is $R_x=\pi^{-1}(x)\cap A'$ for some $x\in \{0\}\times \mathbb{Z}^{k-1}$.

When talking about the rows of a set $A'$, we will use the notation $R_x$ without further clarification. It will always be clear from context which set $A'$ is being referred to.

For $X,Y\subset \mathbb{Z}$, define $X(+)Y:=(X+\min Y)\cup (Y+\max X)\subset X+Y$ if $X,Y$ are both nonempty, and $\emptyset$ otherwise. For $A'\subset \mathbb{Z}^k$, we define $$A'(+)A':=\sum_{\vec{v}\in \{0\}\times\{0,1\}^{k-1}}\sum_{x\in \{0\}\times \mathbb{Z}^{k-1}}R_x(+)R_{x+\vec{v}}\subset A'+A'.$$

In , by choosing $\omega(\epsilon_0,\delta)=1$ for large values of $\delta$, we may assume $\delta$ is sufficiently small and $n_k(\epsilon_0,\delta)$ is sufficiently large to make all statements true without actually specifying the exact bounds.

\[nkconv\] We omit the sentence “for all $\delta$ sufficiently small and $n_k(\delta,\epsilon_0)$ sufficiently large” from the end of all of our statements, unless stated otherwise.

The big and little o notations $O(1)$ and $o(1)$ are with respect to fixed $\epsilon_0$ as $\delta \to 0$ throughout.

Finally, we introduce a small constant which we will use to absorb errors into exponents through the paper.

\[cdef\] We let $c=10^{-10}$.

Observations
------------

The first observation guarantees that hyperplanes $\widetilde{H}$ have small intersections with discrete boxes. In particular, large subsets of $B$ cannot be covered by few hyperplanes.

\[hypboxsmall\] Given a hyperplane $\widetilde{H}$ and a box $B=B(n_1,\ldots,n_k)$, we have $$|\widetilde{H}\cap B|\le \min\{n_i\}^{-1}|B|.$$ In particular, a subset $A'\subset B$ with $|A'|>m\min\{n_1\}^{-1}|B|$ cannot be covered by $m$ hyperplanes.

If coordinate basis vector $e_i$ is not parallel to $\widetilde{H}$, then the projection of $\widetilde{H}\cap B$ away from the $i$th coordinate injects into the same projection for $B$, and therefore $|\widetilde{H}\cap B|\le n_i^{-1}|B|$.

The next observation is used to assume $A$ is reduced so holds.

\[nonreduced\] For all $\epsilon_0>0$, the following holds. Given $n_i$ sufficiently large in terms of $\epsilon_0$, for a subset $A'\subset B=B(n_1,\ldots,n_k)$ with $|A'|\geq \epsilon_0|B|$, we can find a subset $A''\subset B(2^kn_1,\ldots,2^kn_k)$ such that $A''$ is reduced, $|A'|=|A''|$, $d_k(A')=d_k(A'')$, and $|{\widehat{\operatorname{co}}}(A')\setminus A'|=|{\operatorname{co}}(A'')\setminus A''|$.

We first note that $A'$ is not contained inside a hyperplane by . Take some $a\in A'$, then $A'-a\in C:=\prod_{i=1}^k \{-n_i+1,\ldots,n_i-1\}$ and the affine sub-lattice $\Lambda_{A'-a}$ is actually a subgroup $\langle v_1, \hdots, v_k\rangle\subset \mathbb{Z}^k$ generated by linearly independent vectors $v_i=(v_{i,1}, \hdots, v_{i,k})$.

Without loss of generality, suppose $n_1\le \ldots \le n_k$. By the Euclidean algorithm we may assume that $|v_{j, i}| = 0$ for all $j>i$, and $|v_{j,i}| \le |v_{i,i}|$ for all $j \le i$. Because $v_1,\ldots,v_i$ are linearly independent, we have $v_{i,i}\ne 0$. Consider a point $p=p_1v_1 + \hdots + p_kv_k \in C$. We will show by induction on $i$ that $|p_i|\le 2^{i-1}(n_i-1)$. Indeed, by considering the $i$th coordinate, we have that $$|p_1 v_{1,i} + p_2 v_{2,i}+ \hdots +p_i v_{i,i}| \le n_{i}-1$$ and hence $$|p_i| |v_{i,i}| \le |p_1| |v_{1,i}| + \ldots + |p_{i-1}| |v_{i-1,i}| + n_{i}-1 \le (|p_1|+ \ldots + |p_{i-1}| + n_{i}-1)|v_{i,i}|.$$ This shows that $A'-a\subset \{p_1 v_1 + \ldots p_kv_k \text{ : } |p_i| \le 2^{i-1}(n_{i}-1)  \}$. If we let $$A''':=\{(p_1, \hdots p_k) \text{ : } p_1v_1 + \hdots p_kv_k \in A'-a \}\subset \prod_{i=1}^k \{-2^{i-1}(n_i-1),\ldots,2^{i-1}(n_i-1)\},$$ then $A'''$ is reduced in $\mathbb{Z}^k$, and is obtained from $A'$ by applying an element of $GL_n(\mathbb{Q})$ followed by a translation, so $|A'|=|A'''|$, $d_k(A''')=d_k(A')$, and $|{\operatorname{co}}(A''') \setminus A'''| =|{\widehat{\operatorname{co}}}(A')\setminus A'|.$ We conclude by taking $A''$ a suitable translation of $A'''$.

We now prove an observation lower bounding $d_k$ for subsets of boxes, an easy corollary of a Lemma of Green and Tao [@GreenTao].

\[negdk\] For any subsets $X\subset B=B(n_1,\ldots,n_k)$ and $Y\subset \pi(B)$ we have $$d_{k}(X) \ge -2^{2k}\min\{n_i\}^{-1}|B|\text{, and }d_{k-1}(Y) \ge -2^{2(k-1)}\min\{n_i\}^{-1}n_1^{-1}|B|.$$ More generally, for $X_1,X_2\subset B$ and $Y_1,Y_2\subset \pi(B)$ we have $$\begin{aligned}
|X_1+X_2|&\ge 2^{k}\min(|X_1|,|X_2|)- 2^{2k}\min\{n_i\}^{-1}|B|\text{, and}\\
|Y_1+Y_2|&\ge 2^{k-1}\min(|Y_1|,|Y_2|) -2^{2(k-1)}\min\{n_i\}^{-1}n_1^{-1}|B|.\end{aligned}$$

Because $B$ and $\pi(B)$ are downsets, the result follows from [@GreenTao Lemma 2.8], and the trivial estimates that the size of each coordinate projection of $B+B$ and $\pi(B)+\pi(B)$ have sizes at most $2^k\min\{n_i\}^{-1}|B|$ and $2^{k-1}\min\{n_i\}^{-1}n_1^{-1}|B|$, respectively.

We frequently need the following observation when considering $A'(+)A'$ to show it has size roughly $2^k|A'|$ as described in .

\[Surfobs\] Let $Y\subset \pi(B)$ with $B=B(n_1,\ldots,n_k)$, and let $0\ne \vec{v}\in \{0\}\times\{0,1\}^{k-1}$. Then $$\left|\{x \in \mathbb{Z}^{k-1} : |\{x,x+\vec{v}\}\cap {\operatorname{co}}(Y)|=1\}\right| \le 2(k-1) \min\{n_i\}^{-1}n_1^{-1}|B|.$$

Consider all lines in the direction $\vec{v}$ intersecting $\pi(B)$. On each such line there are at most 2 values of $x$ such that $|\{x,x+\vec{v}\}\cap {\operatorname{co}}(Y)|=1$, and there are at most $(k-1) \min\{n_i\}^{-1} |\pi(B)|$ such lines which intersect $\pi(B)$.

The next observation relates $d_k$ between sets and subsets. In particular, it allows us to guarantee that all auxiliary sets we construct in the proof of are reduced and have similar $d_k$ solely because they are close in symmetric difference to the original set $A$.

\[dkobs\] If $X\subset Y$, then $$\begin{aligned}
\label{dk}d_k(X)\le d_k(Y)+2^k|Y\setminus X|.\end{aligned}$$ In particular, for reduced $A\subset B=B(n_1,\ldots,n_k)$ with $|A|\ge \epsilon_0|B|$, $d_k(A)\le \delta |B|$, $\delta$ sufficiently small in terms of $\epsilon_0$, and $n_1,\ldots,n_k$ sufficiently large in terms of $\epsilon_0,\delta$, if $A'\subset B$ has $$\begin{aligned}
\label{redcond}|A\Delta A'|\le 2^{-(k+1)}\epsilon_0|B|\end{aligned}$$ then $A'$ is reduced.

For , we have $$d_k(X)=|X+X|-2^k|X|\le |Y+Y|-2^k|Y|+2^k|Y\setminus X|=d_k(Y)+2^k|Y\setminus X|.$$ For , it suffices to show $A\cap A'$ is reduced, so we may assume $A'\subset A$. Assume for the sake of contradiction that $A'$ is not reduced. Then there is an $a\in A$, such that $a+A'$ is disjoint from $A'+A'$. Hence, we have $|A+A|\ge |A'+A'|+|A'|$, and in particular $$\delta |B| \ge d_k(A)\ge d_k(A')-(2^k+1)|A\setminus A'|+|A| \ge \left(-2^{2k}\min \{n_i\}^{-1}+\left(\frac{1}{2}-\frac{1}{2^{k+1}}\right)\epsilon_0\right)|B|,$$ a contradiction.

We next have an observation which allows us to transition between convex sets and reduced convex progressions with a loss proportional to the surface area of a containing box.

\[contdisc\] Let $B=B(n_1,\ldots,n_k)$, and suppose we have a convex polytope $\widetilde{P}\subset {\widetilde{\operatorname{co}}}(B)$. Then with $P=\widetilde{P}\cap \mathbb{Z}^k$, we have $\left||\widetilde{P}|-|P|\right|\leq 2k(k+1) \min\{n_i\}^{-1}|B|$. This is more generally true for any subset $\widetilde{P}\subset{\widetilde{\operatorname{co}}}(B)$ given as the intersection of finitely many open and closed half-spaces.

By perturbing the defining half-spaces slightly, we may replace $\widetilde{P}$ with a polytope without changing $P$, so we assume $\widetilde{P}$ is a polytope from now on.

Consider the set $X:=\left\{z\in \mathbb{Z}^k: (z+[0,1]^k)\cap \partial\widetilde{P}\neq \emptyset\right\}.$ We first show $|X|$ is small.

$|X|\leq 2k(k+1)\min\{n_i\}^{-1}|B|$

For $1\le i \le k$, let $\pi_i:\mathbb{Z}^k\to\mathbb{Z}^{i-1}\times \{0\}\times \mathbb{Z}^{k-i}$ be the projection away from the $i$th coordinate. Let $f_i^+,f_i^{-}:\pi_i(X) \to \mathbb{Z}$ be defined by $$\begin{aligned}
    f_i^+:x \mapsto \max(\pi_i^{-1}(x)\cap X)\qquad f_i^{-}:x \mapsto \min(\pi_i^{-1}(x)\cap X),\end{aligned}$$ and for every $x=(x_1,\ldots,x_{i-1},0,x_{i+1},\ldots,x_k)\in \pi_i(X)$, let $$\begin{aligned}
X^+_{i,x}&=\{(x_1,\dots,x_{i-1},j,x_{i+1},\dots,x_k):f^+_i(x)-k\leq j\leq f^+_i(x)\}\\ X^-_{i,x}&=\{(x_1,\dots,x_{i-1},j,x_{i+1},\dots,x_k):f^-_i(x)\leq j\leq f^-_i(x)+k\}\end{aligned}$$ be the $k+1$ elements of $\mathbb{Z}^k$ in the $x$-row in direction $i$ of $X$ below the maximum element and above the minimum element respectively. From these definitions it is immediate that $$\left|\bigcup_{i=1}^k X_{i,x}^+\cup X_{i,x}^-\right|\leq 2k(k+1)\min\{n_i\}^{-1}|B|,$$ so it suffices to show that $X\subset\bigcup X_{i,x}^+\cup X_{i,x}^-$.

Suppose for the sake of contradiction that there is some $z\in X\setminus\left(\bigcup X_{i,x}^+\cup X_{i,x}^-\right)$. Then $$f^+_i(\pi_i(z))\geq z_i+k+1, \text{ and }f_i^-(\pi_i(z))\leq z_i-k-1$$ for all $i$, so there are $r_i^+,r_i^- \ge k+1$ such that $ z+r_i^+e_i+[0,1]^k$ and $z-r_i^-e_i+[0,1]^k$ intersect $\widetilde{P}$. As $z+[0,1]^k$ intersects $\widetilde{P}$, by convexity of $\widetilde{P}$ for all $i\in [k]$ there are points $$y^+_i\in (z+(k+1)e_i+[0,1]^k)\cap \widetilde{P},\qquad y^-_i\in (z-(k+1)e_i+[0,1]^k)\cap \widetilde{P}.$$

We claim that $$z+[0,1]^k\subset int(\widetilde{co}(\{y^+_1,\dots,y^+_k,y^-_1,\dots,y^-_k\}))\subset int (\widetilde{P}).$$ Write $y_i^+=z+(\frac{1}{2},\ldots,\frac{1}{2})+p_i^+$ and $ y_i^-=z+(\frac{1}{2},\ldots,\frac{1}{2})+p_i^-$ where $p_i^+= (k+1)e_i+\epsilon_i^+$ and $p_i^-= -(k+1)e_i+\epsilon_i^-$ with $\epsilon_i^{\pm}\in [-\frac{1}{2},\frac{1}{2}]^k$. Then this is equivalent to showing $$\left[-\frac{1}{2},\frac{1}{2}\right]^k\subset int(\widetilde{{\operatorname{co}}}(\{p_1^+,\ldots,p_k^+,p_1^-,\ldots,p_k^-\})).$$ We will show that ${\widetilde{\operatorname{co}}}(\{p_1^+,\ldots,p_k^+,p_1^-,\ldots,p_k^-\})$ has facets ${\widetilde{\operatorname{co}}}(p_1^{\pm},\ldots,p_k^{\pm})$ for the $2^k$ choices of $\pm$, and $\left[-\frac{1}{2},\frac{1}{2}\right]^k$ lies on the same side of these facets as ${\widetilde{\operatorname{co}}}(\{p_1^+,\ldots,p_k^+,p_1^-,\ldots,p_k^-\})$. To show this, let $\epsilon\in [-\frac{1}{2},\frac{1}{2}]^k$. We claim that it suffices to show that $\epsilon$ and $p_1^-$ lie on the same side of the hyperplane $\widetilde{H}$ through $p_1^+,\ldots,p_k^+$. Indeed, if this is the case, then by symmetry all vertices lie on the same side of $\widetilde{H}$, which implies that ${\widetilde{\operatorname{co}}}(\{p_1^+,\ldots,p_k^+\})$ is a facet, and ${\widetilde{\operatorname{co}}}(\{p_1^+,\ldots,p_k^+,p_1^-,\ldots,p_k^-\})$ lies on the same side of this facet as $\epsilon$. This is equivalent in turn to showing that for $w\in \{p_1^-,\epsilon\}$, the determinants of the matrices whose columns are $p_i^+-w$ for $1 \le i \le k$ have the same signs. We will in fact show that this sign is positive for both.

For $w=\epsilon$, the matrix we are considering is $M+(k+1)I$ where $M$ has as its $i$th column $\epsilon_i^+-\epsilon$. Note that $M$ has entries of magnitude at most $1$, so the spectral radius of $M$ is at most $k$. But if $\det(M+(k+1)I)\le 0$, then as $\det(M+\lambda I) \to \infty$ as $\lambda \to \infty$ there must exist $\lambda\ge k+1$ with $\det(M+\lambda I)=0$, a contradiction as $|-\lambda|>k$. Hence $\det(M+(k+1)I)>0$ as desired.

For $w=p_1^-$, note that we have already shown that $\epsilon_1^-$ lies on the positive side of $\widetilde{H}$, and $p_1^-\in \epsilon_1^-+\mathbb{R}_{\le 0}e_1$. Hence it suffices to show that the point $\epsilon_1^+-Ne_1$ lies on the positive side of $\widetilde{H}$ for all $N>0$ sufficiently large. This is equivalent to saying that the matrix $M_N$ whose $i$th column is $p_i^++Ne_1-\epsilon_1^-$ has positive determinant for all $N> 0$ sufficiently large. Subtracting the first column from all subsequent columns and then considering the coefficient of $N$ in $\det(M_N)$, this follows from an identical argument.

Hence we have $z+[0,1]^k\subset int(\widetilde{P})$, contradicting $(z+[0,1]^k)\cap \partial \widetilde{P}\ne \emptyset$.

Returning to the proof of , consider the translates of $[0,1]^k$ by $P$, i.e. $P+[0,1]^k$. Each of these translates is either contained in $\widetilde{P}$ or intersects $\partial{\widetilde{P}}$. Hence, $|P|\leq |\widetilde{P}|+|X|$. On the other hand, consider the set of all integer translates of $[0,1]^k$ intersecting $\widetilde{P}$. All of these translates intersect $\partial{\widetilde{P}}$ or are of the form $a+[0,1]^k$ with $a\in P$. As these clearly cover $\widetilde{P}$, we find $|\widetilde{P}|\leq |P|+|X|$.

Finally, the following observation implies $A'$ being close to its convex hull implies $d_k(A')$ is small, which as mentioned in the introduction yields a weak converse to b).

\[cvxsd\] Given a set $A'\subset B=B(n_1,\ldots,n_k)$, we have $$d_k(A')\leq 2^k|{\operatorname{co}}(A')\setminus A'|+2^{k+2}k(k+1)\min\{n_i\}^{-1}|B|$$

By , we only need to show $d_k({\operatorname{co}}(A'))\le 2^{k+2}k(k+1)\min\{n_i\}^{-1}|B|$. This follows as by we have $$\begin{aligned}
d_k({\operatorname{co}}(A'))&= |{\operatorname{co}}(A')+{\operatorname{co}}(A')|-2^k |{\operatorname{co}}(A')|\\
&\leq |({\widetilde{\operatorname{co}}}(A')+{\widetilde{\operatorname{co}}}(A'))\cap \mathbb{Z}^k|-2^k |{\operatorname{co}}(A')|\\
&\leq |{\widetilde{\operatorname{co}}}(A')+{\widetilde{\operatorname{co}}}(A')|-2^k |{\operatorname{co}}(A')|+2^{k+1}k(k+1) \min\{n_i\}^{-1}|B|\\
&= 2^k|{\widetilde{\operatorname{co}}}(A')|-2^k |{\operatorname{co}}(A')|+2^{k+1}k(k+1) \min\{n_i\}^{-1}|B|\\
&\leq 2^{k+2}k(k+1) \min\{n_i\}^{-1}|B|.\end{aligned}$$

Proof of for $k$ given b) for $k-1$ {#1.6section}
===================================

For $k=1$, and are implied by Freiman’s $3|A|-4$ theorem [@Freiman], , so we suppose from now on that $k\ge 2$. In this section, we prove for dimension $k$ given b) for dimension $k-1$. We recall by that we will assume that $A$ is reduced. Define $\epsilon\ge \epsilon_0$ to be the density of $A$ in $B$, so we have $$\begin{aligned}
\label{Ainfo}|A|=\epsilon|B|\text{,  and }d_k(A)\le \delta |B|.\end{aligned}$$

Outline of the proof
--------------------

We will create sets $$A\supset A_1\supset A_2\supset A_3\supset A_4\supset A_5\subset A_+\supset A_\star$$ (note that $A_5\subset A_+$) such that $|A\Delta A_\star|$ is small, and $A_\star$ has a large number of properties which allow us to show that $A_\star$ is close to ${\operatorname{co}}(A_\star)$. From this we will be able to conclude that $A$ is close to ${\operatorname{co}}(A)$.

In , we derive a general reduction to sets for which the projection under $\pi$ satisfies the induction hypothesis.

In , we construct $A\supset A_1\supset A_2\supset A_3$ such that $A_3$ is reduced, has large rows $R_x$ close to ${\widehat{\operatorname{co}}}(R_x)$, and has $\pi(A_3)$ close to ${\operatorname{co}}(\pi(A_3))$.

In , we construct $A_3\supset A_4\supset A_5$ such that $A_5$ has the same properties as $A_3$ and the arithmetic progressions ${\widehat{\operatorname{co}}}(R_x)$ have the same step size $d$.

In , we show that $d=1$, i.e. ${\widehat{\operatorname{co}}}(R_x)={\operatorname{co}}(R_x)$ is an interval for all rows $R_x$ of $A_5$.

In , we show that filling in the rows of $A_5$ to make a set $A_+\supset A_5$ preserves the properties that $A_5$ had (this is the only step we deviate from throwing away a subset of rows).

In , we show that we can approximate $A_+$ with a subset $A_\star\subset A_+$ which has simultaneously

1.  Few vertices on $\widetilde{{\operatorname{co}}}(A_\star)$

2.  $\pi(A_\star)$ close to ${\operatorname{co}}(\pi(A_\star))$

3.  The technical condition .

Up to this point, we were able to show that $|A\Delta A_+| \le \delta^{O(1)}|A|$. However obtaining $A_\star$ involves a double recursion, and we are only able to show $|A\Delta A_\star|=o(1)|A|$ where $o(1)\to 0$ as $\delta \to 0$.

In , we show that $A_\star$ is close to its convex hull. The key step is to convert the problem to one of bounding the size of the epigraph of a certain infimum-convolution of a function by the size of the epigraph of the original function.

Finally, in we finish the proof of by showing that $A_\star$ being close to its convex hull implies $A$ is close to its convex hull.

Exploiting the inductive hypothesis {#inductiveh}
-----------------------------------

In this section we prove a result, relying on the inductive hypothesis, which we will frequently apply that allows us to remove a small number of rows from a set $A'$ to ensure that the projection $\pi(A')$ is close to ${\widehat{\operatorname{co}}}(\pi(A'))$. Recall we introduced in a small constant $c$.

\[alphaprop’\] Let $\sigma=\sigma(\delta)$ be a function with $\sigma \to 0$ as $\delta \to 0$ and let $\lambda>\alpha>0$. Let $A'\subset B$ with $|A'|=\epsilon'|B|\ge \frac{\epsilon_0}{2}|B|$ and $d_k(A')\le \sigma^{\lambda}|B|$. Then there exists $A''\subset A'$ formed as a union of rows $R_x$ of $A'$ with $$\begin{aligned}
 |{\widehat{\operatorname{co}}}(\pi(A''))\setminus \pi(A'')| \le\sigma^{\alpha} |\pi(B)|,\quad |A'\setminus A''| \le \sigma^{\lambda-\alpha-c}|B|.\end{aligned}$$ Furthermore, if $A'$ is reduced then $A''$ is reduced and in particular ${\widehat{\operatorname{co}}}(\pi(A''))={\operatorname{co}}(\pi(A''))$.

\[alphaproprmk\] For a fixed function $\sigma(\delta)$ and for fixed parameters $\lambda$ and $\alpha$, the proof of requires us to impose certain bounds on $\sigma$ and $n_k(\epsilon_0, \delta)$ so that for example $\sigma<1$. However, by we have an implicit bound on $n_k(\epsilon_0,\delta)$ and on $\delta$ depending on $\sigma$ (and hence in particular a bound on $\sigma(\delta)$). We shall not make remarks about in any subsequent statement.

We can take $A''=\emptyset$ if $\lambda \le \alpha+c$, so suppose $\lambda > \alpha+c$. Let $$\begin{aligned}
E_i=\{x\in \pi(A') : |\pi^{-1}(x)\cap A'| \ge i\},\qquad F_i=\{x \in \pi(A'+A') : |\pi^{-1}(x)\cap (A'+A')| \ge i\}.\end{aligned}$$ Note that $E_1\supset E_2 \supset \ldots$ and $F_1 \supset F_2 \supset \ldots$, and we have $$\begin{aligned}
\label{EiFiequation}
    |A'|=\sum_{i=1}^{n_1} |E_i|,\text{ and }|A'+A'|=\sum_{i=1}^{2n_1-1} |F_i|.\end{aligned}$$ We note that $E_i+E_i \subset F_{2i-1},F_{2i-2}$, so we have $$\begin{aligned}
|A'+A'| &\ge -2^{k-1}n_1^{-1}|B|+ 2\sum_{i=1}^{n_1} |E_i+E_i|\\&\ge -\sigma^{\lambda}|B|+2\sum_{i=1}^{n_1}|E_i+E_i|.\end{aligned}$$ Subtracting $2^k|A'|=2\sum_{i=1}^{n_1} 2^{k-1}|E_i|$, we obtain $d_k(A') \ge -\sigma^{\lambda}|B|+2\sum_{i=1}^{n_1} d_{k-1}(E_i),$ so by the hypothesis $\sigma^{\lambda}|B|\ge d_k(A')$ we see that $$\begin{aligned}
\label{sigmalambdagreaterEi}
\sigma^\lambda|B| \ge \sum_{i=1}^{n_1}d_{k-1}(E_i).\end{aligned}$$ Let $i_0$ be the first index with $d_{k-1}(E_{i_0})\le \sigma^{\alpha+c/2} |E_{i_0}|$, which exists as otherwise by ,, $$\sigma^{\lambda}|B|\ge\sigma^{\alpha+c/2}|A'|\ge \sigma^{\alpha+c/2}\frac{\epsilon_0}{2}|B|>\sigma^{\lambda}|B|.$$ Let $A'':=\pi^{-1}(E_{i_0})\cap A'\subset A'$ be the union of all rows of size at least $i_0$. By construction, $$\begin{aligned}
\label{dk-1A''small}
d_{k-1}(\pi(A''))=d_{k-1}(E_{i_0})\le \sigma^{\alpha+c/2}|E_{i_0}|= \sigma^{\alpha+c/2}|\pi(A'')|.\end{aligned}$$ Also as $|E_i|$ is decreasing in $i$, $\sum_{i=1}^{i_0-1} |E_i|\ge \frac{i_0-1}{n}|A'|$ by . Thus by and , $$\begin{aligned}
\sigma^{\lambda}|B| \ge\sum_{i=1}^{n_1} d_{k-1}(E_i)\ge& \sigma^{\alpha+c/2}\frac{i_0-1}{n_1}|A'|-n_12^{2(k-1)}n_{k}(\epsilon_0,\delta)^{-1}n_1^{-1}|B|\\
\ge& \sigma^{\alpha+c/2}\frac{i_0-1}{n_1}\cdot\frac{\epsilon_0}{2}|B|-\sigma^{\lambda}|B|.\end{aligned}$$ Thus we obtain $$i_0-1 \le 4\sigma^{\lambda-\alpha-c/2} \epsilon_0^{-1}n_1\le \sigma^{\lambda-\alpha-c}n_1.$$ As the $|\pi(A'\setminus A'')|\le |\pi(B')|=n_1^{-1}|B|$ nonempty rows in $A'\setminus A''$ have size at most $\sigma^{\lambda-\alpha-c}n_1$, we have $$|A'\setminus A''| \le \sigma^{\lambda-\alpha-c}|B|.$$

We have $|A'\setminus A''|\le 2^{-(k+1)}\epsilon_0|B|$ so $A''$ is reduced by , and $|A''|\ge \frac{\epsilon_0}{4}|B|$. In particular, $\pi(A'')$ is reduced and $|\pi(A'')|\ge \frac{\epsilon_0}{4}|\pi(B)|$. The set $\pi(A'')$ has $d_{k-1}(\pi(A''))\le \sigma^{\alpha+c/2}|\pi(A'')|$ by , and has density at least $\frac{\epsilon_0}{4}$ in $\pi(B)$, which has side lengths at least $n_k(\epsilon_0,\delta)$. By , the number of parallel hyperplanes needed to cover $\pi(A'')$ is at least $\frac{\epsilon_0}{4}n_k(\epsilon_0,\delta)>m_{k-1}(\sigma^{\alpha+c/2})$, so by for dimension $k-1$ we deduce that $$|{\operatorname{co}}(\pi(A''))\setminus \pi(A'')|=|{\widehat{\operatorname{co}}}(\pi(A''))\setminus \pi(A'')|\le c_{k-1}\sigma^{\alpha+c/2}|\pi(B)|\le \sigma^{\alpha}|\pi(B)|.$$

\[alphaprop\]

Let $\lambda> \alpha >0$. Let $A'\subset B$ with $|A'|=\epsilon'|B|\ge \frac{\epsilon_0}{2}|B|$ and $d_k(A')\le \delta^{\lambda}|B|$. Then there is an $A''\subset A'$ formed by a union of rows of $A'$ with $$\begin{aligned}
|{\widehat{\operatorname{co}}}(\pi(A''))\setminus \pi(A'')|\le\delta^{\alpha} |\pi(B)|,\quad |A'\setminus A''| \le \delta^{\lambda-\alpha-c}|B|.\end{aligned}$$ Furthermore, if $A'$ is reduced then $A''$ is reduced and in particular ${\widehat{\operatorname{co}}}(\pi(A''))={\operatorname{co}}(\pi(A''))$.

Reductions Part 1: All rows are dense in large APs {#prelimreductions}
--------------------------------------------------

We start by constructing in a sequence of steps a set $A_3\subset A$ such that $|A\setminus A_3|$ is small, $\pi(A_3)$ is close to ${\operatorname{co}}(\pi(A_3))$ and the rows $R_x$ of $A_3$ are large and close to ${\widehat{\operatorname{co}}}(R_x)$. In the continuous setting, a similar preliminary reduction was carried out at the beginning of [@FigJerJems].

### $A_1\subset A$ has $\pi(A_1)$ close to its convex progression: Construction 

Apply to $A$ with $\alpha=\frac{1}{2}$, $\lambda=1$ and $\epsilon'=\epsilon \ge \frac{\epsilon_0}{2}$ (by ) to obtain a reduced set $A_1\subset A$ with $$\begin{aligned}
\label{A1info}|{\operatorname{co}}(\pi(A_1))\setminus \pi(A_1)| \le \delta^{\frac{1}{2}} |\pi(B)|,\quad|A\setminus A_1|\le \delta^{\frac{1}{2}-c}|B|.\end{aligned}$$ By , we have $$\begin{aligned}
\label{A1dk}d_k(A_1)\le \delta |B|+2^k\delta^{\frac{1}{2}-c}|B|\le \delta^{\frac{1}{2}-2c}|B|.\end{aligned}$$

### $A_2$ has large rows close to their convex progressions: Setup 

We show that assuming ${\operatorname{co}}(\pi(A'))\setminus \pi(A')$ is small, we can create a subset $A''\subset A'$ by deleting rows with big doubling or small size without changing the size of $A'$ too much.

\[betaprop\] Let $\lambda>\alpha>\beta>0$, $\gamma>0$ and $A'\subset B$ with $$\begin{aligned}
d_k(A')
\le \delta^{\lambda} |B|,\qquad
|{\operatorname{co}}(\pi(A'))\setminus \pi(A')|\le \delta^{\alpha}|\pi(B)|. \end{aligned}$$ If $A''\subset A'$ is the union all rows $R_x$ which satisfy $d_1(R_x)\le \delta^{\beta} n_1$ and $|R_x|\geq \delta^{\gamma} n_1$, then $$|A'\setminus A''|\le (\delta^{\alpha-\beta-c}+\delta^{\gamma})|B|.$$

Let $A'''$ be the union all rows $R_x$ of $A'$ which satisfy $d_1(R_x)\le \delta^{\beta} n_1$. For $0\ne\vec{v}\in \{0\}\times\{0,1\}^{k-1}$ and $x\in \{0\}\times \mathbb{Z}^{k-1}$, we have $$|R_x+R_{x+\vec{v}}|-|R_x|-|R_{x+\vec{v}}|\ge \begin{cases}0&|\{x,x+\vec{v}\}\cap \pi(A')|=0\\-n_1 & |\{x,x+\vec{v}\}\cap \pi(A')|=1\\-1 & |\{x,x+\vec{v}\}\cap \pi(A')|= 2\end{cases}$$ From $|{\operatorname{co}}(\pi(A'))\setminus \pi(A')|\le\delta^{\alpha}n_1^{-1}|B|$ and , we have $$\begin{aligned}
\left|\left\{x\in\{0\}\times \mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A')|=1\right\}\right|&\le 2\left|{\operatorname{co}}(\pi(A'))\setminus \pi(A')\right|+2(k-1)n_1^{-1}n_k(\epsilon_0,\delta)^{-1}|B|\\
&\le \delta^{\alpha-c/4}n_1^{-1}|B|\end{aligned}$$ and $$\begin{aligned}
|\{x\in \{0\}\times\mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A')|=2\}|\le |\pi(B)|\le n_k(\epsilon_0,\delta)^{-1}|B|\le \delta^{\alpha-c/4}|B|.\end{aligned}$$

Hence, as $\sum_{x\in\{0\}\times \mathbb{Z}^{k-1}}|R_x|=|A'|$, we have (taking $\vec{v}\in \{0\}\times \{0,1\}^{k-1}$ and $x\in \{0\}\times \mathbb{Z}^{k-1}$) $$\begin{aligned}
    |A'+A'| \ge& \sum_{\vec{v}}\sum_{x}|R_x+R_{x+\vec{v}}|\\
    =&\left(\sum_{j=0}^2\sum_{0\ne\vec{v}}\sum_{|\{x,x+\vec{v}\}\cap \pi(A')|=j}|R_x+R_{x+\vec{v}}|\right)+\sum_{x\in \pi(A')}|R_x+R_{x}|\\
    \ge& \left(\sum_{0\ne \vec{v}}\sum_{x}|R_{x}|+|R_{x+\vec{v}}|\right)-2(2^{k-1}-1)\delta^{\alpha-c/4}|B|+\sum_{x\in \pi(A')}|R_x+R_{x}|\\
    \geq&(2^{k}-2)|A'|-\delta^{\alpha-c/2}|B|+\sum_{x\in \pi(A')}|R_x+R_x|.\end{aligned}$$ In particular, as $\sum_{x \in \pi(A')}|R_x|=|A'|$ and $d_1(R_x)\ge -1$ for all $x$, we have $$\begin{aligned}
\delta^{\lambda}|B|\ge d_k(A')\ge& -\delta^{\alpha-c/2}|B|+\sum_{x\in \pi(A')}d_1(R_x)\\\ge&-\delta^{\alpha-c/2}|B|-n_k(\delta,\epsilon_0)^{-1}|B|+ \sum_{x\in \pi(A'\setminus A''')}d_1(R_x)\\
\ge&-\delta^{\alpha-3c/4}|B|+|\pi(A'\setminus A''')|\delta^{\beta} n_1,\end{aligned}$$ so $$|A'\setminus A'''|\le n_1|\pi(A'\setminus A''')|\le (\delta^{\alpha-\beta-3c/4}+\delta^{\lambda-\beta})|B|\le \delta^{\alpha-\beta-c}|B|.$$ Finally note that $A''\subset A'''$ satisfies $|A'''\setminus A''|\leq \delta^{\gamma}n_1|\pi(B)|\leq \delta^{\gamma}|B|$, from which the conclusion follows.

### $A_2$ has large rows close to their convex progression: Construction 

Let $A_2\subset A_1$ be the set obtained from applied to $A_1$ with $\lambda=\frac{1}{2}-2c$, $\alpha=\frac{1}{2}-3c$, $\beta=\frac{3}{10}$, and $\gamma=\frac{1}{5}$ (by ,). Then for all rows $R_x\subset A_2$, we have $$\begin{aligned}
\label{A2betagamma}d_1(R_x)\le \delta^{\frac{3}{10}} n_1,\quad|R_x|\ge \delta^{\frac{1}{5}} n_1,\end{aligned}$$ and by we additionally have $$\begin{aligned}
\label{AA2}|A\setminus A_2|\le |A\setminus A_1|+|A_1\setminus A_2|\le \left(\delta^{\frac{1}{2}-c}+\delta^{\frac{1}{5}-4c}+\delta^{\frac{1}{5}}\right)|B|\le \delta^{\frac{1}{5}-5c}|B|.\end{aligned}$$ By , we have $A_2$ is reduced and $$\begin{aligned}
\label{A2dk}
    d_k(A_2)\le \left(\delta+2^k\delta^{\frac{1}{5}-5c}\right)|B|\le \delta^{\frac{1}{5}-6c}|B|.\end{aligned}$$ Freiman’s $3k-4$ theorem [@Freiman], , says that for any $R\subset \mathbb{Z}$, we have $$d_1(R)\ge \min(|R|-3,|{\widehat{\operatorname{co}}}(R)\setminus R|-1).$$ Therefore, because $\delta^{\frac{3}{10}} n_1 <\delta^{\frac{1}{5}} n_1-3$, we have by that every row $R_x$ of $A_2$ satisfies $$\begin{aligned}
\label{coint}\text{ }|{\widehat{\operatorname{co}}}(R_x)\setminus R_x|\le \delta^{\frac{3}{10}}n_1+1\le \delta^{\frac{1}{10}}|R_x|+1\le 2\delta^{\frac{1}{10}}|R_x|.\end{aligned}$$

\[dxrmk\] In particular, this means that for each non-empty row $R_x$ we have $|R_x|>\left\lceil \frac{|{\widehat{\operatorname{co}}}(R_x)|}{2}\right\rceil$, so there exist two elements $z_1, z_2 \in R_x$ with $z_1-z_2=(d_x, 0, 0 \hdots, 0)$, where $d_x$ is the common difference in the arithmetic progression ${\widehat{\operatorname{co}}}(R_x)$.

### $A_3\subset A_2$ has $\pi(A_3)$ close to its convex progression: Construction 

Apply to $A_2$ with $\alpha=\frac{1}{10}$, $\epsilon'\ge\epsilon-\delta^{\frac{1}{5}-5c}\ge \frac{\epsilon_0}{2}$ and $\lambda=\frac{1}{5}-6c$ (by ,) to obtain a reduced set $A_3\subset A_2$ with $$\begin{aligned}
\label{A3info}|{\operatorname{co}}(\pi(A_3))\setminus A_3|\le \delta^{\frac{1}{10}}|\pi(B)|, \qquad |A_2\setminus A_3|\le \delta^{\frac{1}{10}-7c}|B|.\end{aligned}$$ By and , we have $$\begin{aligned}
\label{AA3}|A\setminus A_3|\le |A\setminus A_2|+|A_2\setminus A_3|\le \left(\delta^{\frac{1}{5}-5c}+\delta^{\frac{1}{10}-7c}\right)|B|\le \delta^{\frac{1}{10}-8c}|B|,\end{aligned}$$ and by , we have $$\begin{aligned}
\label{A3dk}d_k(A_3)\le \left(\delta+2^k\delta^{\frac{1}{10}-8c}\right)|B|\le \delta^{\frac{1}{10}-9c}|B|.\end{aligned}$$ Finally, as the rows of $A_3$ are a subset of the rows of $A_2$, by and , we have $$\begin{aligned}
\label{A3beta}
    |R_x|\ge \delta^{\frac{1}{5}}n_1,\qquad |{\widehat{\operatorname{co}}}(R_x)\setminus R_x|\le 2\delta^{\frac{1}{10}}|R_x|.\end{aligned}$$

Reductions Part 2: All rows are in APs of the same step size {#reductionssamesize}
------------------------------------------------------------

We now find a set $A_5\subset A_3$ which has the same properties as $A_3$, and furthermore has the property that for each row $R_x$, the arithmetic progressions ${\widehat{\operatorname{co}}}(R_x)$ have the same step sizes. To do this, we carefully analyze a discrete analogue of Voronoi cells.

Let $d_x$ be the smallest consecutive difference between two consecutive elements in $R_x$, which as noted in is also the common difference of ${\widehat{\operatorname{co}}}(R_x)$, and let $d=\min d_x$.

### $A_4\subset A_3$ has all rows in same step size APs: Setup

We now show that the rows with $d_x>d$ carry small weight.

\[approp\] Let $\lambda>\alpha>0$ and $A'\subset B$ with $d_k(A')\le \delta^{\lambda}|B|$ and $|{\operatorname{co}}(\pi(A'))\setminus \pi(A')|\le \delta^{\alpha}|\pi(B)|$. Let $d_x$ be the smallest consecutive difference between two elements of row $R_x\subset A'$, and let $d=\min d_x$. If $A''\subset A'$ is the subset of rows $R_x$ with $d_x=d$, then $$|A'\setminus A''|\le \delta^{\alpha-c}|B|.$$

Before starting the proof of , we need to prove some claims. shows that $|R_x+R_y|$ is large if $d_x \ne d_y$, and creates a large set of disjoint row sums of this form. is used to prove , which shows that this set of disjoint row sums has small intersection with $A'(+)A'$. Finally, shows $A'(+)A'$ is large, and we can carry out the proof outline described in .

\[dxdy\] Let $X,Y \subset \mathbb{Z}$ with $|X| \ge 2$ such that the smallest differences $d_X,d_Y$ between consecutive elements of $X$ and $Y$ respectively satisfy $d_X<d_Y$. Then $$|X+Y| \ge |X|+2|Y|-2.$$

Consider elements $x,x' \in X$ such that $x'-x=d_X$. Let $X_{<x}$ be the set of elements less than $x$ in $X$ and analogously $X_{>x'}$ those elements greater than $x'$. Then the following four sets $$X_{<x}+\min(Y), (Y+x),  (Y+x'),X_{> x'}+\max(Y),$$ are disjoint subsets of $X+Y$.

Now, we define $$f:\pi(A')\setminus \pi(A'')\to \pi(A'')$$ by letting $f(x)\in \pi(A'')$ be a closest point to $x$ in Euclidean distance (breaking ties arbitrarily). Fibers of $f$ should be thought of as a discrete analogue of Voronoi cells associated to $\pi(A'')$.

\[xfnotyf\] We have $x+f(x)\ne y+f(y)\text{ for distinct }x,y\in \pi(A')\setminus \pi(A'')$. In particular, $$Z_1:=\bigsqcup_{x_1\in \pi(A')\setminus \pi(A'')}R_{x_1}+R_{f(x_1)}\subset A'+A'$$ is a disjoint union.

Indeed, otherwise $x,y,f(x),f(y)$ form a parallelogram with distinct vertices with diagonals $xf(x)$ and $yf(y)$. However, in any parallelogram (even degenerated as long as the vertices are distinct), the longest diagonal is longer than all sides. Hence, if say $xf(x)$ is the longest diagonal, then $|x-f(x)|>|x-f(y)|$, a contradiction.

Let $$Z:=A'(+)A'=\bigsqcup_{\vec{v}\in \{0\} \times \{0,1\}^{k-1}}\bigsqcup_{x_2\in \{0\} \times \mathbb{Z}^{k-1}}R_{x_2}(+)R_{x_2+\vec{v}}\subset A'+A'.$$ We now analyze when $R_{x_1}+R_{f(x_1)}$ and $R_{x_2}(+)R_{x_2+\vec{v}}$ can intersect.

\[diagonal\] If $x_1\in \pi(A')\setminus \pi(A'')$, $x_2\in\{0\}\times \mathbb{Z}^{k-1}$, $\vec{v}\in\{0\}\times \{0,1\}^{k-1}$ are such that $R_{x_1}+R_{f(x_1)} \cap R_{x_2}(+)R_{x_2+\vec{v}} \not= \emptyset$, then either $\{x_1,f(x_1)\}=\{x_2,x_2+\vec{v}\}$ or $x_2,x_2+\vec{v}\in \pi(A') \setminus \pi(A'')$.

The points $x_1, x_2, f(x_1), x_2+\vec{v}$ form a parallelogram with diagonals $x_1f(x_1)$ and $x_2(x_2+\vec{v})$. Assuming that $\{x_1,f(x_1)\}\not=\{x_2,x_2+\vec{v}\}$, this parallelogram has distinct vertices.

The number of odd coordinates of $x_1-f(x_1)$ is the same as the number of odd coordinates of $x_1+f(x_1)=2x_2+\vec{v}$, which is the same as the number of non-zero coordinates of $v$. Hence, $|x_1-f(x_1)|\ge |\vec{v}|$, or equivalently $|x_1-f(x_1)|\ge |x_2-(x_2+\vec{v})|$. Therefore, $x_1f(x_1)$ is the longest diagonal of the above parallelogram. As in a parallelogram (even degenerated as long as the vertices are distinct) the largest diagonal is strictly longer than all sides, we deduce that the diagonal $x_1f(x_1)$ is strictly longer than $x_1x_2$ and $x_1(x_2+\vec{v})$. By definition of $f(x_1)$ this implies $x_2,x_2+\vec{v}\not\in  \pi(A'')$. As $R_{x_2},R_{x_2+\vec{v}}$ are nonempty we also have $x_2,x_2+\vec{v}\in \pi(A')$ and the result follows.

\[diagonal2\] For any $x_1\in \pi(A') \setminus \pi(A'')$ we have $$|(R_{x_1}+R_{f(x_1)})\setminus Z|\ge |R_{x_1}|-1.$$

We have $|(R_{x_1}+R_{f(x_1)})\setminus Z|=|(R_{x_1}+R_{f(x_1)})\setminus (R_{x_2}+R_{x_2+\vec{v}})|$ for the unique $x_2\in \{0\}\times \mathbb{Z}^{k-1}$ and $\vec{v}\in \{0\}\times \{0,1\}^{k-1}$ such that $x_1+f(x_1)=x_2+(x_2+\vec{v})$. Clearly $|(R_{x_1}+R_{f(x_1)})|\ge |R_{x_1}|-1$, so assume $(R_{x_1}+R_{f(x_1)}) \cap (R_{x_2}(+)R_{x_2+\vec{v}}) \not= \emptyset$. By we have that $\text{either  }\{x_1,f(x_1)\}=\{x_2,x_2+\vec{v}\} \text{ or }x_2,x_2+\vec{v}\in \pi(A') \setminus \pi(A'')$. In the former case, by we have that $$|(R_{x_1}+R_{f(x_1)}) \setminus (R_{x_2}(+)R_{x_2+\vec{v}})|=|R_{x_1}+R_{f(x_1)}|-|R_{x_1}|-|R_{f(x_1)}|+1\ge |R_{x_1}|-1.$$ Assume now we are in the latter case. Let $z_1,z_2\in R_{f(x_1)}$ such that $z_1-z_2=(d,0,\ldots,0)$. As the smallest difference in $R_{x_2}(+)R_{x_2+\vec{v}}$ is strictly larger than $d$, for every element $z\in R_{x_1}$ either $z+z_1$ or $z+z_2$ is not in $R_{x_2}(+)R_{x_2+\vec{v}}$, and if there were $z,z'\in R_{x_1}$ with $z+z_1=z'+z_2$ then $z'-z=(d,0,\dots,0)$ contradicting $x_1\not\in \pi(A'')$. Hence $$|(R_{x_1}+R_{f(x_1)}) \setminus (R_{x_2}(+)R_{x_2+\vec{v}})|\ge |R_{x_1}|>|R_{x_1}|-1.$$

\[rs\] We have $|Z| \ge 2^k|A'| - 2^k\delta^{\alpha-c/2}|B|$.

Note that for $x_2\in \{0\}\times \mathbb{Z}^{k-1}$, $0\ne\vec{v} \in \{0\}\times \{0,1\}^{k-1}$, we have $$|R_{x_2}(+)R_{{x_2}+\vec{v}}|-|R_{x_2}|-|R_{x_2+\vec{v}}|\ge\begin{cases}0 & |\{x_2,x_2+\vec{v}\}\cap \pi(A')|=0\\ -n_1 & |\{x_2,x_2+\vec{v}\}\cap \pi(A')|=1\\ -1& |\{x_2,x_2+\vec{v}\}\cap \pi(A')|=2.\end{cases}$$ From $|{\operatorname{co}}(\pi(A'))\setminus \pi(A')|\le\delta^{\alpha}n_1^{-1}|B|$ and , we have $$\begin{aligned}
|\{x\in \{0\}\times\mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A')|=1\}|&\le 2|{\operatorname{co}}(\pi(A'))\setminus \pi(A')|+2(k-1)n_1^{-1}n_k(\epsilon_0,\delta)^{-1}|B|\\
&\le \delta^{\alpha-c/4}n_1^{-1}|B|\end{aligned}$$ and $$\begin{aligned}
|\{x\in \{0\}\times\mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A')|=2\}|\le |\pi(B)|\le n_k(\epsilon_0,\delta)^{-1}|B|\le \delta^{\alpha-c/4}|B|.\end{aligned}$$

As $\sum_{x\in\{0\}\times \mathbb{Z}^{k-1}}|R_x|=|A'|$, we have (taking $\vec{v}\in \{0\}\times \{0,1\}^{k-1}$ and $x\in \{0\}\times \mathbb{Z}^{k-1}$) $$\begin{aligned}
    |Z| =& \sum_{\vec{v}}\sum_{x}|R_x(+)R_{x+\vec{v}}|\\
    =&\left(\sum_{j=0}^2\sum_{0\ne\vec{v}}\sum_{|\{x,x+\vec{v}\}\cap \pi(A')|=j}|R_x(+)R_{x+\vec{v}}|\right)+\sum_{x\in \pi(A')}|R_x(+)R_x|\\
    \ge& -2(2^{k-1}-1)\delta^{\alpha-c/4}|B|-n_k(\epsilon_0,\delta)^{-1}|B|+\sum_{\vec{v} }\sum_{x}|R_{x}|+|R_{x+\vec{v}}|\\
    \geq&2^{k}|A'|-2^k\delta^{\alpha-c/2}|B|.\end{aligned}$$

Note that $$|\pi(A')\setminus \pi(A'')|\le |\pi(B)|\le n_k(\epsilon_0,\delta)^{-1}|B|\le \delta^{\alpha-c/2}|B|.$$ Thus, by , , and , we have

$$\begin{aligned}
|A'+A'|&\ge |Z\cup Z_1|\\
&=|Z|+\sum_{x_1\in \pi(A')\setminus \pi(A'')}|(R_{x_1}+R_{f(x_1)})\setminus Z|\\
&\ge2^k|A'| -2^k\delta^{\alpha-c/2}|B| +\sum_{x_1\in \pi(A')\setminus \pi(A'')}(|R_{x_1}|-1)\\
&\ge2^k|A'|-\delta^{\alpha-3c/4}|B|+|A'\setminus A''|.\end{aligned}$$

We conclude $$|A'\setminus A''| \le d_k(A')+\delta^{\alpha-3c/4}|B|\le \delta^{\lambda} |B|+\delta^{\alpha-3c/4}|B|\le \delta^{\alpha-c}|B|.$$

### $A_4\subset A_3$ has all rows in same step size APs: Construction

Let $A_4\subset A_3$ be the set given by applied to $A_3$ with $\lambda=\frac{1}{10}-9c$ $\alpha=\frac{1}{10}-10c$ (by ,). Then we have $$\begin{aligned}
\label{A4info}
    |A_3\setminus A_4|\le \delta^{\frac{1}{10}-11c}|B|,\end{aligned}$$ and thus by and , $$\begin{aligned}
\label{AA4}
    |A\setminus A_4|\le |A\setminus A_3|+|A_3\setminus A_4|\le (\delta^{\frac{1}{10}-8c}+\delta^{\frac{1}{10}-11c})|B|\le \delta^{\frac{1}{10}-12c}|B|.\end{aligned}$$ By , $A_4$ is reduced and we have $$\begin{aligned}
\label{A4dk}
    d_k(A_4)\le (\delta+2^k\delta^{\frac{1}{10}-12c})|B|\le \delta^{\frac{1}{10}-13c}|B|.\end{aligned}$$ By construction and , ${\widehat{\operatorname{co}}}(R_x)$ has the same step size $d$ for all rows $R_x$ of $A_4$. Finally, by , we have $$\begin{aligned}
\label{A4beta}
    |R_x|\ge \delta^{\frac{1}{5}}n_1,\qquad |{\widehat{\operatorname{co}}}(R_x)\setminus R_x|\le 2\delta^{\frac{1}{10}}|R_x|.\end{aligned}$$

### $A_5\subset A_4$ with $\pi(A_5)$ close to its convex progression: Construction

Apply to $A_4$ with $\lambda=\frac{1}{10}-13c$, $\alpha=\frac{1}{20}$ and $\epsilon'\ge \epsilon-\delta^{\frac{1}{10}-12c}\ge \frac{\epsilon_0}{2}$ (by ,) to obtain a reduced set $A_5\subset A_4$ with $$\begin{aligned}
\label{A5daggerinfo}
 |{\operatorname{co}}(\pi(A_5))\setminus \pi(A_5)|\le \delta^{\frac{1}{20}}|\pi(B)|\qquad
    |A_4\setminus A_5|\le \delta^{\frac{1}{20}-14c}|B|.\end{aligned}$$ By and , we have $$\begin{aligned}
\label{AA5dagger}
    |A\setminus A_5|\le |A\setminus A_4|+|A_4\setminus A_5|\le (\delta^{\frac{1}{10}-12c}+\delta^{\frac{1}{20}-14c})|B|\le \delta^{\frac{1}{20}-15c}|B|,\end{aligned}$$ and by , we have $$\begin{aligned}
\label{A5dk}
    d_k(A_5)\le (\delta+2^k\delta^{\frac{1}{20}-15c})|B|\le \delta^{\frac{1}{20}-16c}|B|.\end{aligned}$$ Furthermore, all rows of $A_5$ are also rows of $A_4$, so have the same step size $d$ and satisfy , so $$\begin{aligned}
\label{A5beta}
       |R_x|\ge \delta^{\frac{1}{5}}n_1,\qquad |{\widehat{\operatorname{co}}}(R_x)\setminus R_x|\le 2\delta^{\frac{1}{10}}|R_x|.\end{aligned}$$

Reductions Part 3: Showing the rows of $A_5$ are almost intervals {#almostintervals}
-----------------------------------------------------------------

We now show that the arithmetic progressions ${\widehat{\operatorname{co}}}(R_x)$ containing the rows $R_x$ of $A_5$ are in fact intervals i.e. ${\widehat{\operatorname{co}}}(R_x)={\operatorname{co}}(R_x)$.

We suppose by way of contradiction that the rows $R_x$ have convex progression ${\widehat{\operatorname{co}}}(R_x)$ with the same step size $d\ne 1$.

Let $\pi':\mathbb{Z}^k\to \mathbb{Z}$ be the projection onto the second coordinate. For a set $A'\subset \mathbb{Z}^k$, we let a “hyperplane” $H_y$ be $\pi'^{-1}(y)\cap A'$.

We shall make a series of temporary reductions in order to arrive at a contradiction, and we shall notate sets used in this proof by contradiction with the dagger symbol $\dagger$.

The hyperplanes $H_y$ of a set $A'$ are unions of rows $R_x$.

### $A_6^{\dagger}\subset A_5$ has big hyperplanes with small doubling: Setup

First, we show that assuming ${\operatorname{co}}(\pi(A'))\setminus \pi(A')$ is small, we can create a subset $A''\subset A'$ by deleting hyperplanes with big doubling or small size without changing the size of $A'$ too much. This is analogous to for rows.

\[hypbetaprop\] Let $\lambda>\alpha>\beta >0, \gamma>0$ and let $A'\subset B$ with $$d_k(A')\le \delta^{\lambda}|B|,\qquad |{\operatorname{co}}(\pi(A'))\setminus \pi(A')|\le \delta^{\alpha}|\pi(B)|.$$ If $A''\subset A'$ is the union of all hyperplanes $H_y$ with $d_{k-1}(H_y)\le \delta^{\beta} n_2^{-1}|B|$ and $|H_y|\ge \delta^{\gamma}n_2^{-1}|B|$, then $$|A'\setminus A''|\le (\delta^{\alpha-\beta-c}+\delta^{\gamma})|B|.$$

Let $A'''\subset A'$ be the union of the hyperplanes $H_y$ with $d_{k-1}(H_y)\le \delta^{\beta}n_2^{-1}|B|$. For $0\ne \vec{v}\in \{0\}\times\{1\}\times \{0,1\}^{k-2}$ we have $$|R_x+R_{x+\vec{v}}|-|R_x|-|R_{x+\vec{v}}|\ge \begin{cases}0&|\{x,x+\vec{v}\}\cap \pi(A')|=0\\-n_1 & |\{x,x+\vec{v}\}\cap \pi(A')|=1\\-1 & |\{x,x+\vec{v}\}\cap \pi(A')|= 2\end{cases}$$ From $|{\operatorname{co}}(\pi(A'))\setminus \pi(A')|\le \delta^{\alpha}n_1^{-1}|B|$ and , we have $$\begin{aligned}
|\{x\in\{0\}\times \mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A')|=1\}|&\le 2|{\operatorname{co}}(\pi(A'))\setminus \pi(A')|+2(k-1)n_1^{-1}n_k(\epsilon_0,\delta)^{-1}|B|\\
&\le \delta^{\alpha-c/4}n_1^{-1}|B|\end{aligned}$$ and $$\begin{aligned}
|\{x\in\{0\}\times \mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A')|=2\}|\le |\pi(B)|\le n_k(\epsilon_0,\delta)^{-1}|B|\le \delta^{\alpha-c/4}|B|.\end{aligned}$$ Hence as $\sum_{x \in \{0\}\times \mathbb{Z}^{k-1}}|R_x|=|A'|$, we have (taking $\vec{v}\in \{0\}\times \{1\}\times \{0,1\}^{k-2}$ and $x\in \{0\}\times \mathbb{Z}^{k-1}$) $$\begin{aligned}
|A'+A'|\ge& \left(\sum_{y\in \mathbb{Z}} |H_y+H_y|\right)+\sum_{j=0}^2\sum_{\vec{v}}\sum_{|\{x,x+\vec{v}\}\cap \pi(A')|=j}|R_x+R_{x+\vec{v}}|\\
\ge& \left(\sum_{y \in \mathbb{Z}}|H_y+H_y|\right)+\left(\sum_{\vec{v}}\sum_{x}|R_x|+|R_{x+\vec{v}}|\right) -2\cdot 2^{k-2}\delta^{\alpha-c/4}|B|\\
\ge&\left(\sum_{y\in \mathbb{Z}}|H_y+H_y|\right)+2^{k-1}|A'|-\delta^{\alpha-c/2}|B|.\end{aligned}$$

Now, as $\sum_{y \in \mathbb{Z}}|H_y|=|A'|$, by with $H_y$ and the box $\pi'^{-1}(y)\cap B$, we have $$\begin{aligned}
    \delta^{\lambda}|B|\ge d_k(A')\ge& \left(\sum_{y\in \pi'(A')}d_{k-1}(H_y)\right)-\delta^{\alpha-c/2}|B|\\
    \ge& \left(\sum_{y\in \pi'(A')\setminus \pi'(A''')}d_{k-1}(H_y)\right)-n_2\cdot 2^{2(k-1)}n_k(\epsilon_0,\delta)^{-1}n_2^{-1}|B|-\delta^{\alpha-c/2}|B|\\
    \ge& |\pi'(A'\setminus A''')|\cdot \delta^{\beta} n_2^{-1}|B|-\delta^{\alpha-3c/4}|B|\\
    \ge&\delta^{\beta} |A'\setminus A'''|-\delta^{\alpha-3c/4}|B|.\end{aligned}$$ Therefore, $$|A'\setminus A'''| \le (\delta^{\lambda-\beta}+\delta^{\alpha-\beta-3c/4})|B|\le \delta^{\alpha-\beta-c}|B|.$$ Finally, note that $A''\subset A'''$ satisfies $|A'''\setminus A''|\le n_2\delta^{\gamma}n_2^{-1}|B|=\delta^{\gamma}|B|$, from which the conclusion follows.

### $A_6^{\dagger}\subset A_5$ has big hyperplanes with small doubling: Construction 

Applying to $A_5$ with $\lambda=\frac{1}{20}-16c$, $\alpha=\frac{1}{40}$, $\beta=\frac{1}{80}$, and $\gamma=\frac{1}{160}-c$, we obtain $$\begin{aligned}
\label{A6daggerinfo}|A_5\setminus A_6^{\dagger}|\le (\delta^{\frac{1}{80}-c}+\delta^{\frac{1}{160}-c})|B|\le \delta^{\frac{1}{160}-2c} |B|\end{aligned}$$ and for every hyperplane $H_y\subset A_6^{\dagger}$ we have $$\begin{aligned}
\label{hypdoub}d_{k-1}(H_y)\le \delta^{\frac{1}{80}}n_2^{-1}|B|, \qquad |H_y|\ge \delta^{\frac{1}{160}-c} n_2^{-1}|B|.\end{aligned}$$ We also have by and that $$\begin{aligned}
\label{AA6dagger}
    |A\setminus A_6^{\dagger}|\le |A\setminus A_5|+|A_5\setminus A_6^{\dagger}|\le (\delta^{\frac{1}{20}-15c}+\delta^{\frac{1}{160}-2c})|B|\le \delta^{\frac{1}{160}-3c}|B|,\end{aligned}$$ and by we have $A_6^{\dagger}$ is reduced and $$\begin{aligned}
\label{A6dk}
    d_k(A_6^{\dagger})\le (\delta+2^k\delta^{\frac{1}{160}-3c})|B|\le \delta^{\frac{1}{160}-4c}|B|.\end{aligned}$$ Consider the set $H_y$ contained inside a box $B_y:=\pi'^{-1}(y)\cap B$ with sides at least $n_k(\epsilon_0,\delta)$. We have $|H_y| \ge \delta^{\frac{1}{160}-c} |B_y|$ and $d_{k-1}(H_y) \le \delta^{\frac{1}{160}+c}|H_y|$. By , the number of parallel hyperplanes needed to cover $H_y$ is at least $n_k(\epsilon_0,\delta)\delta^{\frac{1}{160}-c}>m_{k-1}(\delta^{\frac{1}{160}+c})$. Hence by for dimension $k-1$, we deduce that $$\begin{aligned}
\label{convhyp}|{\widehat{\operatorname{co}}}(H_y)\setminus H_y|\le c_{k-1}\delta^{\frac{1}{160}+c}|B_y|\le\delta^{\frac{1}{160}}|B_y|.\end{aligned}$$

\[stepsize\] For a hyperplane $H_y\subset A_6^{\dagger}$, the smallest affine sublattice $\Lambda_{H_y}\subset \pi'^{-1}(y)=\mathbb{Z}\times \{y\}\times \mathbb{Z}^{k-2}$ containing $H_y$ has the property that the nonempty rows of $\Lambda_{H_y}$ have step size $d$.

For each row $R_x$ contained in a hyperplane $H_y$, the arithmetic progression ${\widehat{\operatorname{co}}}(R_x)$ has step size $d$. Let $d'$ be the uniform step size of the nonempty rows of $\Lambda_{H_y}$ (which exists by Lagrange’s theorem), and hence of the nonempty rows of ${\widehat{\operatorname{co}}}(H_y)$. Assume for the sake of contradiction $d'\not=d$. As $d'$ divides $d$, for every row $R_x$ of $H_y$ and corresponding row $R_x'$ of ${\widehat{\operatorname{co}}}(H_y)$, we have $|R_x'\setminus R_x|\ge \frac{1}{2}|R_x|$ (as each row $R_x$ has at least $2$ elements by ). Adding this over all rows $R_x$ of $H_y$, we obtain from $$|{\widehat{\operatorname{co}}}(H_y)\setminus H_y| \ge \frac{1}{2}|H_y|\ge \frac{1}{2}\delta^{\frac{1}{160}-c} |B_y|$$ contradicting that $\delta^{\frac{1}{160}}|B_y|\ge |{\widehat{\operatorname{co}}}(H_y)\setminus H_y|.$

### $A_7^{\dagger}\subset A_6^{\dagger}$ with $\pi(A_7^{\dagger})$ close to its convex progression: Construction

Apply to $A_{6}^{\dagger}$ with $\lambda=\frac{1}{160}-4c$, $\alpha=\frac{1}{320}$, $\epsilon'\ge\epsilon-\delta^{\frac{1}{160}-3c}\ge \frac{\epsilon_0}{2}$ (by ,) to obtain a reduced set $A_7^{\dagger}\subset A_6^{\dagger}$ with $$\begin{aligned}
\label{A7daggerinfo}
 |A_6^{\dagger}\setminus A_7^{\dagger}|\le \delta^{\frac{1}{320}-5c}|B|,\qquad |{\operatorname{co}}(\pi(A_7^{\dagger}))\setminus \pi(A_7^{\dagger})|\le \delta^{\frac{1}{320}}|\pi(B)|.\end{aligned}$$ By and , we have $$\begin{aligned}
\label{AA7dagger}
    |A\setminus A_7^{\dagger}|\le |A\setminus A_6^{\dagger}|+|A_6^{\dagger}\setminus A_7^{\dagger}| \le (\delta^{\frac{1}{160}-3c}+\delta^{\frac{1}{320}-5c})|B|\le \delta^{\frac{1}{320}-6c}|B|,\end{aligned}$$ and by we have $$\begin{aligned}
\label{A7daggerdk}
    d_k(A_7^{\dagger})\le (\delta+2^k\delta^{\frac{1}{320}-6c})|B|\le \delta^{\frac{1}{320}-7c}|B|.\end{aligned}$$ As we pass from $A_6^{\dagger}$ to $A_7^{\dagger}$, the affine sub-lattice $\Lambda_{H_y}$ shrinks, so by the nonempty rows of $\Lambda_{H_y}$ have step size at least $d$. As the nonempty rows of $A_7^{\dagger}$ have step size $d$, this forces the nonempty rows of $\Lambda_{H_y}$ to have step size exactly $d$.

We note that we do not know that the hyperplanes of $A_7^{\dagger}$ have big size or small doubling.

### $A_8^{\dagger}\subset A_7^{\dagger}$ has $\pi(H)$ reduced for all hyperplanes $H$: Construction 

Let $A_8^{\dagger}\subset A_7^{\dagger}$ be the union of all hyperplanes $H_y$ such that $\pi(H_y)$ is reduced in $\{0\}\times \{y\}\times \mathbb{Z}^{k-2}$. Recall we let $B_y=\pi'^{-1}(y)\cap B$, so $H_y\subset B_y$.

If $\pi(H_y)$ is not reduced inside $\{0\}\times\{y\}\times \mathbb{Z}^{k-2}$, then there is a direction $e_j$ with $j\in \{3,\hdots, k\}$ such that $\pi(H_y)\cap(\pi(H_y)+e_j)=\emptyset$. Hence, letting $\pi_j:\mathbb{Z}^k\to \mathbb{Z}^{k-1}$ be the projection away from the $j$th coordinate and $S_x=\pi_j^{-1}(x)\cap \pi(H_y)$, we have $|{\operatorname{co}}(S_x)\setminus S_x| \ge \frac{1}{2}(|S_x|-1)$. Summing the above inequality over all $x\in \pi_j(\pi(H_y))\subset \pi_j(\pi(B_y))$, we deduce $$|{\operatorname{co}}(\pi(H_y))\setminus \pi(H_y)|\ge \sum_{x\in \pi_j(\pi(H_y))}|{\operatorname{co}}(S_x)\setminus S_x| \ge \frac{1}{2}(|\pi(H_y)|-n_k(\epsilon_0,\delta)^{-1}|\pi(B_y)|).$$ Adding this over all $y$ with $\pi(H_y)$ not reduced, we obtain by that $$\begin{aligned}
\nonumber|\pi(A_7^{\dagger}\setminus A_8^{\dagger})|&\le n_k(\epsilon_0,\delta)^{-1}|\pi(B)|+2\sum_{\pi(H_y)\text{ not reduced}}|{\operatorname{co}}(\pi(H_y))\setminus \pi(H_y)|\\\label{piA7A8}&\le n_k(\epsilon_0,\delta)^{-1}|\pi(B)|+2|{\operatorname{co}}(\pi(A_7^{\dagger}))\setminus \pi(A_7^{\dagger})|\le 3\delta^{\frac{1}{320}}|\pi(B)|\le \delta^{\frac{1}{320}-c}|\pi(B)|,\end{aligned}$$ so in particular we have $$|A_7^{\dagger}\setminus A_8^{\dagger}|\le \delta^{\frac{1}{320}-c}|B|.$$ Hence by we have $$\begin{aligned}
\label{AA8dagger}
    |A\setminus A_8^{\dagger}|\le |A\setminus A_7^{\dagger}|+|A_7^{\dagger}\setminus A_8^{\dagger}|\le  \left(\delta^{\frac{1}{320}-6c}+\delta^{\frac{1}{320}-c}\right)|B|\le \delta^{\frac{1}{320}-7c}|B|,\end{aligned}$$ and by we have $A_8^{\dagger}$ is reduced and $$\begin{aligned}
\label{A8dk}d_k(A_8^{\dagger})\le \left(\delta+2^k\delta^{\frac{1}{320}-7c}\right)|B|\le \delta^{\frac{1}{320}-8c}|B|.\end{aligned}$$ Note that $|{\operatorname{co}}(\pi(A_8^{\dagger}))\setminus \pi(A_8^{\dagger})|\le |{\operatorname{co}}(\pi(A_7^{\dagger}))\setminus \pi(A_7^{\dagger})|+|\pi(A_7^{\dagger}\setminus A_8^{\dagger})|$, so we have by , that $$\begin{aligned}
\label{copiA8dagger}|{\operatorname{co}}(\pi(A_8^{\dagger}))\setminus \pi(A_8^{\dagger})|\le \left(\delta^{\frac{1}{320}}+\delta^{\frac{1}{320}-c}\right)|\pi(B)|\le \delta^{\frac{1}{320}-2c}|\pi(B)|.\end{aligned}$$ As we pass from $A_7^{\dagger}$ to $A_8^{\dagger}$, the affine sub-lattice $\Lambda_{H_y}$ shrinks, so the nonempty rows of $\Lambda_{H_y}$ have step size at least $d$. As the nonempty rows of $A_8^{\dagger}$ have step size $d$, this forces the nonempty rows of $\Lambda_{H_y}$ to have step size exactly $d$. Furthermore, the reducedness of $\pi(H_y)$ implies $\pi(\Lambda_{H_y})=\{0\}\times \{y\}\times\mathbb{Z}^{k-2}$.

### Contradiction

We now derive a contradiction. Let $H_{y_1},\ldots,H_{y_\ell}$ be the nonempty hyperplanes of $A_8^{\dagger}$ with $y_1<\ldots<y_\ell$, and for notational convenience set $H_{i}:=H_{y_i}$ and $\Lambda_i:=\Lambda_{H_{y_i}}$. Let $$\Phi_i:\pi(\Lambda_{i})=\{0\}\times\{y_i\}\times \mathbb{Z}^{k-2}\to \mathbb{Z}/d\mathbb{Z}$$ be the affine-linear function defined by taking $\Phi_i(0,y_i,z)=z'\mod d$ where $(z'+d\mathbb{Z},y_i,z)$ is a row in $\Lambda_{i}$.

We create $r$ subintervals $I_i\subset \{1,\ldots,\ell\}$ satisfying the following properties.

-   $1\in I_1$

-   $\bigsqcup_{j\in I_i}H_j$ is not reduced in $\mathbb{Z}^k$, and $H_{1+\max I_i}\sqcup\bigsqcup_{j \in I_i}H_j$ is reduced, for $1\leq i\le r-1$.

-   $\min I_{i+1}=\max I_i+\begin{cases} 0 & H_{\max I_i}\sqcup H_{1+\max I_{i}}\text{ is not reduced.}\\1 & H_{\max I_i}\sqcup H_{1+\max I_i}\text{ is reduced.}
        \end{cases}$

These conditions uniquely determine intervals $I_1,\ldots,I_r$ which cover $\{1,\ldots,\ell\}$, and as $A_8^{\dagger}$ is reduced we have $r\ge 2$.

\[minmaxrmk\] If $\max I_i=\min I_{i+1}$ then $|I_i|\ge 2$. If instead $\max I_i+1=\min I_{i+1}$, then with $j=\max I_i$ we have $y_{j}+1=y_{j+1}$, and $\Phi_j(w)-\Phi_{j+1}(w+e_2): \{0\}\times \{y_{j}\}\times \mathbb{Z}^{k-2}\to \mathbb{Z}$ is non-constant.

For $1\le i \le r-1$, let $z_i\in H_{1+\max I_i}$ be a point not in the affine sub-lattice containing $\bigsqcup_{j \in I_i}  H_{j}$. Let $$f:\bigsqcup_{j\in [1,\min I_r-1]}H_j\to A_8^{\dagger}$$ be defined by setting $$f\left(\bigsqcup_{j \in [\min I_i,\min I_{i+1}-1]}H_j\right)=z_i.$$

If $z',z''\in \bigsqcup_{j\in[1,\min I_r-1]}H_j$ are distinct, then we have $$z'+f(z')\ne z''+f(z'').$$

Indeed, if they were equal then $$\pi'(z')+\pi'(f(z'))=\pi'(z'')+\pi'(f(z'')),$$ and if without loss of generality $\pi'(z')\le \pi'(z'')$, then $\pi'(f(z'))\le \pi'(f(z''))$, so we must have $\pi'(z')=\pi'(z'')$. Therefore $f(z')=f(z')$, so $z'=z''$, a contradiction.

Hence the set $$Z_1=\bigsqcup_{i=1}^{r-1}\bigsqcup_{j\in [\min I_i,\max I_{i}-1]}(H_j+z_i)\subset A_8^{\dagger}+A_8^{\dagger}$$ is a disjoint union as $[\min I_{i},\max I_i-1]\subset [\min I_i,\min I_{i+1}-1]$.

For $ \vec{v}\in \{0\}\times\{0,1\}^{k-1}$ and $x\in \{0\}\times \mathbb{Z}^{k-1}$, and $z\in H_t$ with $t\in [\min I_i, \max I_{i}-1]$ for some $1\le i \le r-1$, we have $$z+f(z)\not \in R_x + R_{x+\vec{v}}.$$

Assume to the contrary that $z+f(z)\in R_x+R_{x+\vec{v}}$. First note that $\pi'(x)\ge y_{\min I_i}$ since $$2y_{\min I_i}\le \pi'(z)+\pi'(f(z))=\pi'(x)+\pi'(x+\vec{v})\le 2\pi'(x)+1.$$ Next, we note that $\pi'(x+\vec{v})\le y_{\max I_i}$. Indeed, if $\pi'(x+\vec{v})>y_{\max I_i}$, then as $R_x$ and $R_{x+\vec{v}}$ are non-empty, we have $\pi'(x+\vec{v})\geq y_{1+\max I_i}$ and $\pi'(x)\geq y_{\max I_i}$. However, then $$\pi'(x+\vec{v})+\pi'(x)\geq y_{1+\max I_i}+y_{\max I_i}>\pi'(f(z))+\pi'(z),$$ a contradiction. Hence, $z,R_x,R_{x+\vec{v}}$ are all contained in the affine sub-lattice containing $\sqcup_{j \in I_i}H_j$, and $f(z)$ is not in this affine sub-lattice by construction, contradicting $z+f(z)\in R_x+R_{x+\vec{v}}$.

Hence the sets $$Z:=A_8^{\dagger}(+)A_8^{\dagger}= \bigsqcup_{\vec{v}\in \{0\}\times \{0,1\}^{k-1}}\bigsqcup_{x\in \{0\}\times\mathbb{Z}^{k-1}}R_x(+)R_{x+\vec{v}}\subset A_8^{\dagger}+A_8^{\dagger}$$ and $Z_1$ are disjoint.

The set of indices $\mathcal{I}=[1,\min I_{r}-1]\setminus \bigcup_{i=1}^{r-1} [\min I_i,\max I_{i}-1]$ whose corresponding hyperplanes $H_j$ were not accounted for by $Z_1$ are precisely those indices $j$ such that there exists $1 \le i\le r-1$ with $j=\max I_i=\min I_{i+1}-1$. We will now find a third set $Z_2$ disjoint from $Z$, and $Z_1$ which accounts for the hyperplanes with indices in $\mathcal{I}$.

Consider two consecutive hyperplanes $H_j$, and $H_{j+1}$ with $j\in \mathcal{I}$, and let $i$ be such that $j=\max I_i$ and $j+1=\min I_{i+1}$. Note that by , we have $y_j+1=y_{j+1}$ and the affine-linear function $\Phi_j(w)-\Phi_{j+1}(w+e_2):\{0\}\times \{y_j\}\times \mathbb{Z}^{k-2}\to \mathbb{Z}/d\mathbb{Z}$ is non-constant. In particular, there is an index $s_j\in \{3,\ldots,k\}$ so that the standard basis vector $e_{s_j}$ satisfies $\Phi_j(w+e_{s_j})-\Phi_{j+1}(w+e_{s_j}+e_2)\ne \Phi_j(w)-\Phi_{j+1}(w+e_2)$ for all $w$. Rearranging, $$\Phi_j(w+e_{s_j})+\Phi_{j+1}(w+e_2)\ne \Phi_j(w)+\Phi_{j+1}(w+e_{s_j}+e_2)$$ for all $w$. Hence we have $$\left(R_{w+e_2}+R_{w+e_{s_j}}\right) \cap \left(R_{w}+R_{w+e_2+e_{s_j}}\right) = \emptyset$$ for all $w$ since they lie in different translated $d\mathbb{Z}$-progressions.

For $w\in \{0\}\times \{y_j\}\times \mathbb{Z}^{k-2}$, we have $$(R_{w+e_2}+R_{w+e_{s_j}})\cap Z=\emptyset.$$

If $(w+e_2)+(w+e_{s_j})=x+(x+\vec{v})$ for some $x\in \{0\}\times \mathbb{Z}^{k-1}$ and $\vec{v}\in \{0\}\times \{0,1\}^{k-1}$, then by looking at the odd coordinates we see that $\vec{v}=e_2+e_{s_j}$ and hence $x=w$. But then $$(R_{w+e_2}+R_{w+e_{s_j}})\cap Z=(R_{w+e_2}+R_{w+e_{s_j}})\cap (R_{w}(+)R_{w+e_2+e_{s_j}})=\emptyset.$$

Hence the disjoint union $$Z_2:=\bigsqcup_{j\in \mathcal{I}}\bigsqcup_{w \in \{0\}\times \{y_j\}\times \mathbb{Z}^{k-2}}R_{w+e_2}(+)R_{w+e_{s_j}}$$ is disjoint from $Z$. Finally, we prove a claim which implies $Z_1$ is disjoint from $Z_2$.

For any $1 \le s \le r-1$ and for any $z\in H_t$ with $t \in [\min I_s, \max I_s-1]$ and for any $w\in \{0\}\times \{y_j\}\times \mathbb{Z}^{k-2}$ with $j \in \mathcal{I}$, we have $$z+f(z)\not \in R_{w+e_2}+R_{w+e_{s_j}}.$$

Assume for the sake of contradiction that $z+f(z)\in R_{w+e_2}+R_{w+e_{s_j}}$. Let $i$ be such that $j=\max I_i=\min I_{i+1}-1$. First, suppose that $\pi'(z)=y_t\le y_j-1$. Then $s \le i$ as if $i<s$ then $j=\min I_{i+1}-1< \min I_s\leq t$, and therefore $y_j<y_t$, a contradiction. Therefore $\pi'(f(z))= y_{\max I_s +1}\le y_{\max I_i +1}= y_{j+1}=y_j+1$ by , so we obtain the contradiction $$\pi'(z+f(z))\le y_j-1+(y_j+1)<2y_j+1=\pi'(w+e_2)+\pi'(w+e_{s_j}).$$ Next, suppose $\pi'(z)=y_t=y_j$. Then $j=t$, contradicting that $\mathcal{I}$ is disjoint from $[\min I_s,\max I_s-1]$ by construction of $\mathcal{I}$. Finally, suppose that $\pi'(z)=y_t\ge y_j+1$. Then as $\pi'(f(z))> \pi'(z)$, we have the contradiction $$\pi'(z+f(z))> 2y_j+2>2y_j+1=\pi'(w+e_2)+\pi'(w+e_{s_j}).$$

Hence $Z,Z_1$ and $Z_2$ are disjoint subsets of $A_8^\dagger+A_8^\dagger$. Note that for $x_1\ne x_2$ we have $$|R_{x_1}(+)R_{x_2}|-|R_{x_1}|-|R_{x_2}|\ge \begin{cases}0&|\{x_1,x_2\}\cap \pi(A')|=0\\-n_1 & |\{x_1,x_2\}\cap \pi(A')|=1\\-1 & |\{x_1,x_2\}\cap \pi(A')|= 2\end{cases}$$

For $0\ne\vec{v}\in \{-1,0,1\}^k$ we have from and , $$\begin{aligned}
|\{x\in \mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A^\dagger_8)|=1\}|&\le 2|{\operatorname{co}}(\pi(A^\dagger_8))\setminus \pi(A^\dagger_8)|+2(k-1)n_1^{-1}n_k(\epsilon_0,\delta)^{-1}|B|\\
&\le \delta^{\frac{1}{320}-3c}n_1^{-1}|B|\end{aligned}$$ and $$\begin{aligned}
|\{x\in \mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A^\dagger_8)|=2\}|\le |\pi(B)|\le n_k(\epsilon_0,\delta)^{-1}|B|\le \delta^{\frac{1}{320}-3c}|B|.\end{aligned}$$

Therefore, we have (taking $\vec{v}\in \{0\}\times \{0,1\}^{k-1}$ and $x\in \{0\}\times \mathbb{Z}^{k-1}$) $$\begin{aligned}
|A_8^{\dagger}+A_8^{\dagger}| \ge& |Z| + |Z_1| + |Z_2|\\
=&\left(\sum_{\vec{v}}\sum_{x} |R_x(+)R_{x+\vec{v}}|\right)+\sum_{i=1}^{r-1}\sum_{j\in [\min I_i,\max I_{i+1}-1]}|H_j|\\&+\sum_{j \in \mathcal{I}}\sum_{w\in \{0\}\times \{y_j\}\times \mathbb{Z}^{k-2}}|R_{w+e_2}(+)R_{w+e_{s_j}}|\\
\ge&\left(\sum_{\vec{v}}\sum_{x} |R_x|+|R_{x+\vec{v}}|\right)+\sum_{i=1}^{r-1}\sum_{j\in [\min I_i,\max I_{i+1}-1]}|H_j|\\&+\left(\sum_{j \in \mathcal{I}}\sum_{w\in \{0\}\times \{y_j\}\times \mathbb{Z}^{k-2}}|R_{w+e_{s_j}}|\right)-\delta^{\frac{1}{320}-4c}|B|\\
=&2^k|A_8^{\dagger}|+\left(\sum_{j\in [1,\min I_{r}-1]}|H_j|\right)-\delta^{\frac{1}{320}-4c}|B|.\end{aligned}$$

If we consider the same process ran in reverse, we produce another collection of intervals $I'_1, \hdots I'_{r'}\subset \{1,\ldots \ell\}$ with $\ell\in I_1'$ such that $$|A_8^{\dagger}+A_8^{\dagger}| \ge 2^k|A_8^{\dagger}|+\left(\sum_{j\in [\max I'_{r'}+1,l]}|H_j|\right)-\delta^{\frac{1}{320}-4c}|B|.$$

As $A_8^{\dagger}$ is reduced, we have that $r'\ge 2$. As $\sqcup_{i \in I_r} H_{i}$ is not reduced, we have that $I_r \subset I_1'\subset [\max I_r'+1,\ell]$. Averaging the two inequalities we get by that $$d_k(A_8^{\dagger})\ge \frac{1}{2}|A_8^{\dagger}|-\delta^{\frac{1}{320}-4c}|B|\ge \frac{\epsilon_0}{4}|B|,$$ contradicting that $d_k(A_8^{\dagger})\le \delta^{\frac{1}{320}-8c}|B|$. The conclusion follows.

Reductions Part 4: Filling in the rows to create $A_+\supset A_5$ {#reductionAplus}
-----------------------------------------------------------------

We recall that we have just shown that all rows $R_x$ of $A_5$ satisfy ${\operatorname{co}}(R_x)={\widehat{\operatorname{co}}}(R_x)$. We now show that filling in all of the rows of $A_5$ does not change the size of $A_5$ or $d_k(A_5)$ too much.

### $A_+ \supset A_5$ with all rows filled in

Let $A_+ \supset A_5$ be obtained by replacing each row $R_x$ of $A_5$ with ${\operatorname{co}}(R_x)$. We have $A_+$ is reduced as $A_5$ is reduced. Also by and we have $$\begin{aligned}
\label{AA+}|A \Delta A_+|\le |A\setminus A_5|+|A_+\setminus A_5|\le \delta^{\frac{1}{20}-15c}|B|+2\delta^{\frac{1}{10}}|A_5|\le \delta^{\frac{1}{20}-16c}|B|.\end{aligned}$$ Furthermore, $\pi(A_+)=\pi(A_5)$, so by we have $$|{\operatorname{co}}(\pi(A_+))\setminus \pi(A_+)|=|{\operatorname{co}}(\pi(A_5))\setminus \pi(A_5)|\le \delta^{\frac{1}{20}}|\pi(B)|.$$

$d_k(A_+)\leq \delta^{\frac{1}{20}-17c}|B|.$

We begin the proof with the following general claim.

\[disjointunion\] Given a finite family of finite subsets $Z_i\subset \mathbb{Z}$ and a parameter $\rho$ such that $|{\operatorname{co}}(Z_i)| \le (1+\rho)|Z_i|$, we have $$\left|\bigcup {\operatorname{co}}(Z_i)\right| \le (1+2\rho)\left|\bigcup Z_i\right|.$$

Let $\mathcal{F}, \mathcal{G}$ be families of indices such that $\bigcup {\operatorname{co}}(Z_i)=(\bigsqcup_{i \in \mathcal{F}} {\operatorname{co}}(Z_i))\cup (\bigsqcup_{i \in \mathcal{G}}{\operatorname{co}}(Z_i))$, where both are disjoint unions. Then $$\left|\bigcup {\operatorname{co}}(Z_i)\setminus \bigcup Z_i\right| \le \sum_{i\in \mathcal{F}\cup \mathcal{G}} |{\operatorname{co}}(Z_i)\setminus Z_i| \le \sum_{i\in \mathcal{F}\cup \mathcal{G}} \rho|Z_i|\le 2\rho\left|\bigcup Z_i\right|.$$

Now, for nonempty rows $R_{x_{1}},R_{x_{2}}$ of $A_5$, we have by that $|{\operatorname{co}}(R_{x_{1}})|\le (1+2\delta^{\frac{1}{10}})|R_{x_{1}}|$ and $|{\operatorname{co}}(R_{x_{2}})| \le (1+2\delta^{\frac{1}{10}})|R_{x_{2}}|$, so $$|{\operatorname{co}}(R_{x_{1}}+R_{x_{2}})|=|{\operatorname{co}}(R_{x_{1}})|+|{\operatorname{co}}(R_{x_{2}})|-1 \le (1+2\delta^{\frac{1}{10}})(|R_{x_{1}}|+|R_{x_{2}}|)-1\le (1+4\delta^{\frac{1}{10}})|R_{x_{1}}+R_{x_{2}}|.$$ Taking the sets $Z_i$ to be the pairwise row sums $R_{x_{1}}+R_{x_{2}}$ with $x_1+x_2=x$ fixed, and summing the inequality in over all $x\in\{0\}\times\mathbb{Z}^{k-1}$, we obtain $$|A_++A_+| \le (1+8\delta^{\frac{1}{10}})|A_5+A_5|.$$ Hence by , we thus have $$\begin{aligned}
d_k(A_+) &\le (1+8\delta^{\frac{1}{10}})d_k(A_5)+2^k\cdot8\delta^{\frac{1}{10}}|A_5|\\
&\le \delta^{\frac{1}{20}-17c}|B|.\end{aligned}$$

Reductions Part 5: Approximating $A_+$ by $A_\star\subset A_+$ with few vertices in ${\operatorname{co}}(A_\star)$ and an extra technical condition {#sectionAstarapprox}
---------------------------------------------------------------------------------------------------------------------------------------------------

We now construct a set $A_\star\subset A_+$ with $|A_+\setminus A_\star|=o(1)|B|$, which has simultaneously

1.  $|V(A_\star)|$, which we recall is the number of vertices of ${\widetilde{\operatorname{co}}}(A_\star)$, is bounded by a function of $\delta$

2.  $|{\operatorname{co}}(\pi(A_\star))\setminus \pi(A_\star)|=o(1)|\pi(B)|$

3.  The technical condition holds.

We show this using a double recursion, and the bounds we obtain will no longer be powers of $\delta$.

In , we prove , which shows that we can ensure that 1 holds. This is accomplished by showing an analogous approximation result for (continuous) polytopes, and then transitioning to the discrete setting using .

In , we prove , which shows that we can ensure that both 1 and 2 hold. by itself shows that 2 holds, so we alternate applications of and , and show that at some point both 1 and 2 hold simultaneously.

In , we prove , which shows that we can ensure that all of 1,2,3 hold. To do this, we show , which shows that we can ensure 1 and 3 hold. Similarly to the proof of , we alternate applications of and , and show that at some point 1,2,3 hold simultaneously.

Finally, in , we apply to $A_+$ to construct $A_\star$.

### $A_\star\subset A_+$ with $|V(A_\star)|$ small: Setup Part 1 {#AstarPart1}

\[polyapprox\] For any $\alpha\ge 16 \epsilon_0^{-1} k(k+1) \min\{n_i\}^{-1}$, there exists an $\ell=\ell(\alpha)$ such that the following is true. For any set of points $C\subset B$ with $|{\operatorname{co}}(C)|\ge \frac{\epsilon_0}{2}|B|$, there exists $Q={\operatorname{co}}(Q)\cap C\subset C$ with $|V(Q)|\le \ell$ and $V(Q)\subset V(C)$, such that $|{\operatorname{co}}(Q)|\ge (1-\alpha)|{\operatorname{co}}(C)|$, and if $C$ has all rows intervals then $Q$ has all rows intervals. There exists a constant $\tau_k$ such that for $n_i$ sufficiently large and $\alpha=\min\{n_i\}^{-\frac{2}{(k-1)\lfloor k/2\rfloor+2}}$, we can take $\ell=\tau_k\min\{n_i\}^{\frac{k-1}{(k-1)\lfloor k/2\rfloor+2}}$.

To do this, we first consider a continuous analogue, which was proved constructively by Gordon, Meyer, and Reisner [@BestApproximation].

\[contpolyapprox\] For any $\alpha>0$, there exists $\ell'=\ell'(\alpha)$ such that the following is true. For any polytope $\widetilde{C}$, there is a polytope $\widetilde{Q}$ which is the convex hull of at most $\ell'$ vertices of $\widetilde{C}$ with $|\widetilde{Q}|\ge (1-\alpha)|\widetilde{C}|$. There is an absolute constant $\tau$ independent of $k$ such that for $\alpha$ sufficiently small in terms of $k$ we can take $\ell'=(\frac{\tau}{k}\alpha)^{-\frac{k-1}{2}}$.

It is enough to find such a polytope $\widetilde{Q}$ with vertices contained inside $\widetilde{C}$. Indeed, a simple convexity argument shows that as we vary the vertices of $\widetilde{Q}$ the maximum volume is attained when all vertices of $\widetilde{Q}$ are among the vertices of $\widetilde{C}$. The result then follows from [@BestApproximation Theorem 3].

Let $\widetilde{C}={\widetilde{\operatorname{co}}}(C)$ be the continuous convex hull of $C$. By , there exists a polytope $\widetilde{P}$ with $|V(\widetilde{P})|\le \ell'(\frac{\alpha}{2})$, $V(\widetilde{P})\subset V(\widetilde{C})=V(C)$, and $|\widetilde{P}|\ge (1-\frac{\alpha}{2})|\widetilde{C}|$. Let $Q=\widetilde{P}\cap C$, and note that ${\widetilde{\operatorname{co}}}(Q)=\widetilde{P}$.

We thus have by that $$\begin{aligned}
|{\operatorname{co}}(Q)|&\ge |\widetilde{P}|-2k(k+1)\min\{n_i\}^{-1}|B|\\
&\ge \left(1-\frac{\alpha}{2}\right)|\widetilde{C}|-2k(k+1)\min\{n_i\}^{-1}|B|\\
&\ge \left(1-\frac{\alpha}{2}\right)|{\operatorname{co}}(C)|-4k(k+1)\min\{n_i\}^{-1}|B|\\
&\ge (1-\alpha)|{\operatorname{co}}(C)|.\end{aligned}$$ For $\alpha=\min\{n_i\}^{-\frac{2}{(k-1)\lfloor k/2\rfloor+2}}$ (sufficiently small in terms of $k$ as $n_i$ is sufficiently large) we see that $\ell=\ell'(\frac{\alpha}{2})$, yielding $\ell=\tau_k\min\{n_i\}^{\frac{k-1}{(k-1)\lfloor k/2\rfloor+2}}$.

### $A_\star\subset A_+$ with $|V(A_\star)|$ and $|{\operatorname{co}}(\pi(A_\star))\setminus \pi(A_\star)|$ small: Setup part 2 {#AstarPart2}

At this point in the proof, we will lose polynomial control over the doubling constant, so for convenience we will work with purely qualitative statements from now on. The following proposition is the qualitative analogue of and . Crucially, this qualitative version holds for all $\delta>0$, rather than for $\delta$ sufficiently small.

\[qualalphaprop\] There are functions $h_{1}(t),h_{2}(t)$ with $h_{1},h_{2}\to 0$ as $t \to 0$ such that for any function $f=f(\delta)$ with $f\to 0$ as $\delta \to 0$ the following is true. For every $\delta>0$, if $A'\subset B$ and $|A'|\ge \frac{\epsilon_0}{2}$ with $d_k(A')\le f|B|$, then there is a subset of the rows $A''\subset A'$ such that $$|A'\setminus A''|\le h_{1}(f)|B|,\qquad|{\operatorname{co}}(\pi(A''))\setminus \pi(A'')|\le h_{2}(f)|\pi(B)|.$$

According to , the first sentence of should be read as follows. Given $\epsilon_0$ there are increasing functions $h_{1}(t),h_{2}(t)$ with $h_{1},h_{2}\to 0$ as $t \to 0$ such that given a function $f(\delta)$ with $f\to 0$ as $\delta \to 0$, there exist a function $n_k(\delta, \epsilon_0)$ such that following is true. We shall omit this type clarification in the rest of the document.

Let $\Delta'(\epsilon_0)$ denote the implicit bound on $f(\delta)$ required to apply with $\sigma=f$, $\lambda=1$ and $\alpha=\frac12$. Note under , yields a bound on $\delta$ which may depend on $\sigma$ rather than a bound on $\sigma(\delta)$, but in we note that the proof works with a bound on $\sigma(\delta)$ instead. For $t\geq \Delta'(\epsilon_0)$, set $h_1(t)=h_2(t)=1$ and for $f<\Delta'(\epsilon_0)$ gives the result with $h_1(t)=t^{\frac{1}{2}-c}$ and $h_2(t)=t^{\frac{1}{2}}$.

\[firstit\] There are functions $h_3(t),h_4(t)\to 0$ as $t \to 0$ such that for any function $f=f(\delta)\to 0$ as $\delta \to 0$ the following is true. For every $\delta>0$, if $A'\subset B$ has all rows intervals, $|A'|\ge \frac{2\epsilon_0}{3}|B|$ and $d_k(A')\le f|B|$, then there exists a subset $A''\subset A'$ with each row an interval, such that

1.  $|{\operatorname{co}}(\pi(A''))\setminus \pi(A'')|\le h_3(f)|\pi(B)|$

2.  $|A'\setminus A''|\le h_4(f)|B|$

3.  $V(A'')\le \ell(f)$ with $\ell$ as in .

We start by giving a high level outline of how the proof will work. Starting with $A'=A_0'$, we will create a nested sequence of sets $A_0'\supset A_0''\supset A_1'\supset A_1''\supset \ldots \supset A_{\gamma(f)}'$, where $\gamma$ is some function, $A_i''\subset A_i'$ is obtained through an application of , and $A_{i+1}'\subset A_i''$ is obtained through an application of . All $A_{i}',A_{i}''$ automatically satisfy the second point, and all of the $A_i'$ automatically satisfy the third point, so it suffices to show there is an $A_i'$ which satisfies the first point. But $|{\operatorname{co}}(\pi(A_{i-1}''))\setminus \pi(A_{i-1}'')|$ is always extremely small by construction, so if $|{\operatorname{co}}(\pi(A_i'))\setminus \pi(A_i'))|>h_3(f)|\pi(B)|$, then $|\pi(A_{i-1}'')\setminus \pi(A_i')|$ must be at least roughly $h_3(f)|\pi(B)|$. This inequality can only happen approximately $h_3(f)^{-1}$ times however before the $A_i'$ become empty, which is smaller than $\gamma(f)$.

Let $h_1,h_2$ be as in . We recursively define functions with $g_0(t)=t$ and $$g_{i}(t)=g_{i-1}(t)+2^k h_1(g_{i-1}(t))+2^kt.$$ For fixed $i$ we have $g_i(t)\to 0$ as $t \to 0$.

We define a decreasing sequence of real numbers $r_1,r_2,\ldots \to 0$ with the properties

&\_[t(0,r\_i\]]{}+\_[j=0]{}\^[i-1]{}h\_2(g\_j(t))0,i ,&\[h1h2cond0\]\
\[h1h2cond1\]&\_[t(0,r\_i\]]{}it+\_[j=0]{}\^[i-1]{}h\_1(g\_j(t))0,i\
\[h1h2cond2\]&\_[t(0,r\_i\]]{} i t+\_[j=0]{}\^[i-1]{}h\_1(g\_j(t)).

For $t\le r_1$ define $\gamma(t)=\max\{i:t\leq r_i\}$, and note $t \in (0,r_{\gamma(t)}]$, and $\gamma(t) \rightarrow \infty$ as $ t \rightarrow 0$. Let $$h_3(t):=\begin{cases}\frac{2}{\gamma(t)}+\sum_{j=0}^{\gamma(t)-1}h_2(g_{j}(t)) & \text{if } t \le r_1 \\1& \text{if } t > r_1\end{cases},\quad h_4(t):=\begin{cases}\gamma(t)t+\sum_{j=0}^{\gamma(t)-1}h_1(g_j(t)) & \text{if } t \le r_1 \\ 1 & \text{if } t>r_1\end{cases},$$ and note that $h_3, h_4 \rightarrow 0$ as $t\rightarrow 0$ by ,.

If $f>r_1$, then the conclusion trivially holds with $A''=\emptyset$. Otherwise, if $f\le r_1$, we will see that we can iterate the below construction $\gamma(f)$ times while always satisfying the conditions in and that the corresponding set under consideration has size at least $\frac{\epsilon_0}{2}|B|$.

We will now recursively construct sets $A'=A'_0\supset A'_1\supset \ldots \supset A_{\gamma(f)}'$ with all rows intervals such that $$\begin{aligned}
\label{RecursiveAi}d_k(A'_{i})\le g_{i}(f)|B|,\qquad |A'\setminus A'_{i}|\leq \left[i f+\sum_{j=0}^{i-1}h_1(g_j(f))\right]|B|.\end{aligned}$$ Suppose that for some $i\leq \gamma(f)$, we have constructed $A'_{i-1}$, we will now construct $A'_i$. By for $i-1$, for $i=\gamma(f)$, and the fact that $f\le r_{\gamma(f)}$, we have $$\begin{aligned}
|A'\setminus A_{i-1}'|\le \left[(i-1)f+\sum_{j=0}^{i-2}h_1(g_j(f))\right]|B| \le \left[\gamma(f)f+\sum_{j=0}^{\gamma(f)-1}h_1(g_j(f))\right] |B| \le \frac{\epsilon_0}{6}|B|,\end{aligned}$$ so $|A_{i-1}'|\ge (\frac{2}{3}-\frac{1}{6})\epsilon_0|B|=\frac{\epsilon_0}{2}|B|$. Applying to $A'_{i-1}$ we obtain $A''_i\subset A'_{i-1}$ with all rows intervals such that $$\begin{aligned}
\label{Ai-1'Ai''1}|A'_{i-1}\setminus A''_i|\le h_1(g_{i-1}(f))|B|,\qquad |{\operatorname{co}}(\pi(A''_i))\setminus \pi(A''_i)|\le h_2(g_{i-1}(f))|\pi(B)|.\end{aligned}$$ An identical proof shows $|A''_{i}|\geq (\frac23-\frac16) \epsilon_0 |B| \ge \frac{\epsilon_0}{2} |B|$. We now apply with $\alpha=f$, to find a subset $A'_i\subset A''_i$ with all rows intervals such that $|V(A'_i)|\le \ell(f)$ and $A_i'={\operatorname{co}}(A_i')\cap A_i''$, with the property that $$\begin{aligned}
\label{Ai''Ai'1}|A_i''\setminus A_i'|=|A_i''\setminus {\operatorname{co}}(A_i')|\le \left|{\operatorname{co}}(A''_i)\setminus {\operatorname{co}}(A'_i)\right|\le f|{\operatorname{co}}(A'_i)|\le f|B|,\end{aligned}$$ so together with for $i-1$ and , we deduce $$\begin{aligned}
|A'\setminus A'_i|\leq \left[(i-1) f+\sum_{j=0}^{i-2}h_1(g_j(f))+f+h_1(g_{i-1}(f))\right]|B|=\left[if+\sum_{j=0}^{i-1}h_1(g_j(f))\right]|B|.\end{aligned}$$ By for $i-1$, ,, and , $$d_k(A_i')\le d_k(A_{i-1}')+2^k(h_1(g_{i-1}(f))+f)|B|\le (g_{i-1}(f)+2^k h_1(g_{i-1}(f))+2^kf)|B|=g_i(f)|B|,$$ verifying for $A_i'$.

Writing $\gamma$ for $\gamma(f)$, we have $|A'\setminus A_{\gamma}'|\le (\gamma f+\sum_{j=0}^{\gamma-1}h_1(g_j(f)))|B|=h_4(f)|B|$. If all of $A_1',\ldots,A_{\gamma}'$ have the property that $|{\operatorname{co}}(\pi(A_i'))\setminus \pi(A_i')| > h_3(f)|\pi(B)|$, then noting that because $\pi(A_i')\subset \pi(A_i'')$ we have $|{\operatorname{co}}(\pi(A_i'))\setminus \pi(A_i')|-|{\operatorname{co}}(\pi(A_i''))\setminus \pi(A_i'')|=|\pi(A_i'')\setminus \pi(A_i')|-|{\operatorname{co}}(\pi(A_i'))\setminus {\operatorname{co}}(\pi(A_i''))|$, we deduce $$\begin{aligned}
|{\operatorname{co}}(\pi(A_1'))\setminus \pi(A'_\gamma)|&\ge |{\operatorname{co}}(\pi(A_1'))\setminus \pi(A_1')|+\sum_{i=2}^\gamma |\pi(A_i'')\setminus \pi(A_i')|\\&\geq \sum_{i=1}^\gamma |{\operatorname{co}}(\pi(A'_i))\setminus\pi(A'_i)|-|{\operatorname{co}}(\pi(A''_i))\setminus\pi(A''_i)|\\
&\geq \sum_{i=1}^{\gamma}(h_3(f)-h_2(g_{i-1}(f)))|\pi(B)|\\
&=2|\pi(B)|,\end{aligned}$$a contradiction. Let $1\le i_0\leq \gamma$ be an index such that $|{\operatorname{co}}(\pi(A'_{i_0}))\setminus \pi(A'_{i_0})|\leq h_3(f)|\pi(B)|$. Then, as $i_0\leq \gamma$, we have by and the definition of $h_4$ that $|A'\setminus A'_{i_0}|\leq |A'\setminus A'_\gamma|\leq h_4(f)|B|.$ Moreover, $|V(A'_{i_0})|\le \ell(f)$ vertices. We thus conclude by setting $A''=A'_{i_0}$.

### $A_\star\subset A_+$ with $|V(A_\star)|$ and $|{\operatorname{co}}(\pi(A_\star))\setminus \pi(A_\star)|$ small and one further technical condition: Setup part 3 {#AstarPart3}

For every $A'\subset B$, let $\mathcal{T}^+(A')$ (resp. $\mathcal{T}^-(A')$) be a triangulation of the upper (resp. lower) convex hull of ${\widetilde{\operatorname{co}}}(A')$ with respect to the $e_1$ direction, projected under $\pi$ to $\{0\}\times\mathbb{R}^{k-1}$, so in particular every $\widetilde{T}\in\mathcal{T}^+(A')$ has $\widetilde{T}\subset \{0\}\times\mathbb{R}^{k-1}$. We ensure that if ${\widetilde{\operatorname{co}}}(A'_1)={\widetilde{\operatorname{co}}}(A'_2)$, then $\mathcal{T}^+(A'_1)=\mathcal{T}^+(A'_2)$ and $\mathcal{T}^-(A'_1)=\mathcal{T}^-(A'_2)$.

For a simplex $\widetilde{T}\subset \{0\}\times \mathbb{R}^{k-1}$, we will write $$T:=\widetilde{T}\cap \{0\}\times \mathbb{Z}^{k-1},\text{ and }T^o:=\widetilde{T}^o\cap (\{0\}\times \mathbb{Z}^{k-1})$$ where $\widetilde{T}^o$ is the interior of $\widetilde{T}$.

\[YofT\] Given $\widetilde{T} \subset \{0\}\times \mathbb{R}^{k-1}$ with integral vertices, and a set $\mathcal{W} \subset \{0\}\times \mathbb{Z}^{k-1}$, for every $x\in T$ we define the set $$Y_{\mathcal{W}}(x):=((x+\mathcal{W})\cap T)\cup V(T)\subset T.$$

\[overpulling\] Let $\nu>0$, $A'\subset B$ with $|A'|\ge \frac{2\epsilon_0}{3}|B|$, $d_k(A')\le f_1(\delta)|B|$, $|{\operatorname{co}}(\pi(A'))\setminus \pi(A')|\le f_2(\delta)|\pi(B)|$. Suppose we have sets $\mathcal{W}_T\subset \{0\}\times \mathbb{Z}^{k-1}$ with $|\mathcal{W}_T| \le \nu$ for every $\widetilde{T} \in\mathcal{T}^+(A')\cup\mathcal{T}^{-}(A')$. Then there exists a subset of rows $A''\subset A'$ such that $$|A'\setminus A''|\le (2\nu+2)(f_1(\delta)+2^{k+1}f_2(\delta))|B|$$ which satisfies the following additional properties.

1.  ${\operatorname{co}}(A'')={\operatorname{co}}(A')$.

2.  For every $\widetilde{T}\in \mathcal{T}^+(A')\cup \mathcal{T}^-(A')=\mathcal{T}^+(A'') \cup \mathcal{T}^-(A'')$, if $x\in T^o \setminus V_\pi(A'')$, $y\in Y_{\mathcal{W}_T}(x)$, $z \in \pi(B)$ and $\vec{v}\in\{0\}\times\{0,1\}^{k-1}$ with $x+y=z+z+\vec{v}$ and $R_{x}+R_{y}, R_{z}+R_{z+\vec{v}}$ nonempty, then $(R_{x}+R_{y})\cap (R_{z}+R_{z+\vec{v}})\ne \emptyset$.

For every $\widetilde{T} $, write $\mathcal{W}_T:=\{\vec{w}_{T,i} : 1\le i \le \nu \}$. Let $X_{T,i}\subset T^o\setminus V_\pi(A')$ be those $x$ such $x+\vec{w}_{T,i}\in Y_{\mathcal{W}_T}(x)$, and writing $x+x+\vec{w}_{T,i}=z+z+\vec{v}$ with $\vec{v}\in\{0\}\times\{0,1\}^{k-1}$, we have $$R_{x}+R_{x+\vec{w}_{T,i}},R_{z}+R_{z+\vec{v}}\text{ nonempty and }(R_{x}+R_{x+\vec{w}_{T,i}}) \cap (R_{z}+R_{z+\vec{v}}) = \emptyset.$$ For $\star\in \{+,-\}$, let $X^\star_i:=\bigsqcup_{\widetilde{T}\in \mathcal{T}^\star(A')} X_{T,i}$, let $y_i^\star$ be defined on $X_i^\star$ by setting $y^\star_i(x)=x+\vec{w}_{T,i}$ for $x\in X_{T,i}$, and set the disjoint union $$Z^\star_i:=\bigsqcup_{\widetilde{T}\in \mathcal{T}^\star(A') }\bigsqcup_{x\in X_{T,i}} R_x+R_{y^\star_i(x)}\subset A'+A'.$$ Here we note the union is disjoint as $\frac{1}{2}(x+y_i^\star(x))\in \widetilde{T}^{\circ}$, which are disjoint for distinct $\widetilde{T}$, and for a given $\widetilde{T}$ we have $\{2x+\vec{w}_{T,i}\}_{x\in T}$ are distinct.

For $\star \in \{+,-\}$ let $X^\star_0\subset \pi(B)\setminus V_\pi(A')$ be those $x$ such that there exists $\widetilde{T}\in\mathcal{T}^\star(A')$ with $x\in T^o$ and $y^\star_0(x)\in V(T)$, such that writing $x+y^\star_0(x)=z+z+\vec{v}$ with $\vec{v}\in\{0\}\times\{0,1\}^{k-1}$, $$R_{x},R_{z}+R_{z+\vec{v}}\text{ nonempty, and }(R_{x}+R_{y^\star_0(x)}) \cap (R_{z}+R_{z+\vec{v}})= \emptyset.$$ Set the disjoint union $$Z^{\star}_0:=\bigsqcup_{x\in X^{\star}_0} R_x+R_{y^\star_0(x)}\subset A'+A'.$$ Here, the union is disjoint because $\frac{1}{2}(x+y_0^\star(x))\in \widetilde{T}^{\circ}$, which are disjoint for distinct $\widetilde{T}$, and for a given $\widetilde{T}$ we have $\{\frac{1}{2}(\widetilde{T}^{\circ}+y)\}_{y\in V(T)}$ are disjoint.

Finally, set $X:=\bigcup_{(\star,i) \in \{+,-\}\times \{0,\ldots,\nu\}}X^\star_i$, and let $A''=A'\setminus \bigsqcup_{x\in X} R_x$, so that $|A'\setminus A''|=\sum_{x \in X}|R_x|$. By construction $A''$ satisfies the properties 1 and 2, so it suffices to show $|A'\setminus A''|\le (2\nu+2)(f_1(\delta)+2^{k+1}f_2(\delta))|B|$.

Set the disjoint union $$Z:=A'(+)A'=\bigsqcup_{\vec{v}\in \{0\}\times \{0,1\}^{k-1}}\bigsqcup_{x\in \{0\}\times\mathbb{Z}^{k-1}}R_x(+)R_{x+\vec{v}}\subset A'+A',$$ and note that by construction $Z\cap Z^\star_i=\emptyset$ for all $\star,i$. Choose $(\star,i)\in \{+,-\}\cup \{0,\ldots,\nu\}$ so that $$|A'\setminus A''|=\sum_{x \in X}|R_x| \le (2\nu+2) \sum_{x \in X^{\star}_i}|R_x|.$$

Note that for $0\ne \vec{v}\in \{0\}\times \{0,1\}^{k-1}$ and $x\in \{0\}\times \mathbb{Z}^{k-1}$ we have $$|R_{x}(+)R_{x+\vec{v}}|-|R_{x}|-|R_{x+\vec{v}}|\ge \begin{cases}0&|\{x_1,x_2\}\cap \pi(A')|=0\\-n_1 & |\{x_1,x_2\}\cap \pi(A')|=1\\-1 & |\{x_1,x_2\}\cap \pi(A')|= 2\end{cases}$$ By , we have for $0\ne \vec{v}\in \{0\}\times\{0,1\}^{k-1}$ that $$\begin{aligned}
|\{x\in \{0\}\times\mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A')|=1\}|&\le 2|{\operatorname{co}}(\pi(A'))\setminus \pi(A')|+2(k-1)n_1^{-1}n_k(\epsilon_0,\delta)^{-1}|B|\\
&\le 3f_2(\delta)n_1^{-1}|B|\end{aligned}$$ and $$\begin{aligned}
|\{x\in \{0\}\times\mathbb{Z}^{k-1}: |\{x,x+\vec{v}\}\cap \pi(A')|=2\}|\le |\pi(B)|\le n_k(\epsilon_0,\delta)^{-1}|B|\le f_2(\delta)|B|.\end{aligned}$$ We therefore have (taking $\vec{v}\in \{0\}\times \{0,1\}^{k-1}$ and $x\in \{0\}\times \mathbb{Z}^{k-1}$) $$\begin{aligned}
|A'+A'| \ge& |Z| + |Z^\star_i| \\
=&\left(\sum_{\vec{v}}\sum_{x} |R_x(+)R_{x+\vec{v}}|\right)+\sum_{x\in X^\star_i}|R_x+R_{y^\star_i(x)}|\\
\ge&2^k|A'|-(2^{k-1}-1)(3f_2(\delta)+f_2(\delta))|B|-|\pi(B)|+\sum_{x\in X^\star_i}|R_x|\\\ge& 2^k|A'|-2^{k+1}f_2(\delta)|B|+\frac{1}{2\nu+2}|A'\setminus A''|.\end{aligned}$$ Hence, $$|A'\setminus A''|\leq (2\nu+2)( d_k(A')+2^{k+1}f_2(\delta)|B|)\leq (2\nu+2)(f_1(\delta)+2^{k+1}f_2(\delta))|B|.$$

\[Astarreduction\] There exist functions $h_5(t), h_6(t), H_7(t)$ such that $h_5, h_6,\rightarrow 0$ as $t \rightarrow 0$ and $H_7(t)\to \infty$ as $t \to 0$ such that for any function $e:=e(\delta)$ such that $e \rightarrow 0$ as $\delta \rightarrow 0$ the following is true. For every $\delta$, if $A'\subset B$ has all rows intervals and $|A'|\ge \frac{3\epsilon_0}{4}|B|$, $d_k(A')\le e|B|$, and if for every simplex $\widetilde{T}\subset \{0\}\times \mathbb{R}^{k-1}$ with integral vertices we have a set $\mathcal{W}_T\subset \{0\}\times \mathbb{Z}^{k-1}$ with $|\mathcal{W}_T| \le \nu$ for a constant $\nu=\nu(k)$, then there exists $A''\subset A'$ with all rows intervals and $$|A'\setminus A''|\le h_5(e)|B|,\qquad|{\operatorname{co}}(\pi(A''))\setminus \pi(A'')|\le h_6(e)|\pi(B)|$$ which satisfies the following additional properties.

1.  $V(A'')\le H_7(e)$

2.  We have for every $\widetilde{T}\in\mathcal{T}^+(A'')\cup\mathcal{T}^{-}(A'')$, if $x\in T^o \setminus V_\pi(A'')$, $y\in Y_{\mathcal{W}_T}(x)$, $z \in \pi(B)$ and $\vec{v}\in\{0\}\times\{0,1\}^{k-1}$ with $x+y=z+z+\vec{v}$ and $R_{x}+R_{y}, R_{z}+R_{z+\vec{v}}$ nonempty, that $(R_{x}+R_{y}) \cap (R_{z}+R_{z+\vec{v}}) \ne \emptyset$.

The high level overview of this proof is identical to that given at the start of the proof of , except with $h_3$ replaced with $h_6$, replaced with and replaced with .

We recursively define functions $g_0(t)=t$ and $$g_i(t)=(2\nu+2)\left[\left(2^k+\frac{1}{2\nu+2}\right)g_{i-1}(t)+\left(2^{2k}+\frac{2^k}{2\nu+2}\right)h_4(g_{i-1}(t))+2^{2k+1}h_3(g_{i-1}(t))\right]$$ For fixed $i$ we have $g_i(t)\to 0$ as $t \to 0$.

We define a decreasing sequence of real numbers $r_1,r_2,\ldots \to 0$ with the following properties:

\[h3h4cond0\]&\_[t(0,r\_i\]]{}+\_[j=0]{}\^[i-1]{}h\_3(g\_[j]{}(t))0i&\
\[h3h4cond1\]&\_[t(0,r\_i\]]{}(2+2)0i\
\[h3h4cond2\]&\_[t(0,r\_i\]]{}(2+2)\_0.

For $t\le r_1$ set $\gamma(t)=\max\{i: t\leq r_i\}$. Note that $t \in (0,r_{\gamma(t)}]$ and that $\gamma(t) \rightarrow \infty$ as $ t \rightarrow 0$. Set $$h_5(t):=\begin{cases}(2\nu+2)\left[\sum_{j=0}^{\gamma(t)-1} g_{j}(t)+\left(2^k+\frac{1}{2\nu+2}\right)h_4(g_{j}(t))+2^{k+1}h_3(g_{j}(t))\right] & \text{if } t \le r_1 \\ 1 & \text{if } t>r_1 \end{cases},$$ $$h_6(t):=\begin{cases}\frac{2}{\gamma(t)}+\sum_{j=0}^{\gamma(t)-1}h_3(g_j(t))  & \text{if } t \le r_1 \\ 1 & \text{if } t>r_1 \end{cases},$$ and with $\ell$ as in $$H_7(t):=\max_{0 \le j \le \gamma(t)-1}(\ell(g_{j}(t))$$ and note that $h_5, h_6 \rightarrow 0$ as $t\rightarrow 0$ by ,.

If $e>r_1$, then the conclusion trivially holds with $A''=\emptyset$. Otherwise, if $e\le r_1$, we will see that we can iterate the below construction $\gamma(e)$ times while always satisfying the conditions in and that the corresponding set under consideration has size at least $\frac{2\epsilon_0}{3}|B|$.

We will now recursively construct sets $A'=A_0'\supset  A_1'\supset \ldots\supset  A'_{\gamma(e)}$ with all rows intervals, such that $$\begin{aligned}
\label{dkAi-1'}d_k(A'_{i})&\leq g_{i}(e)|B|,\\\label{A'Ai-1'}|A'\setminus A'_{i}|&\leq (2\nu+2)\left[\sum_{j=0}^{i-1} g_{j}(e)+\left(2^k+\frac{1}{2\nu+2}\right)h_4(g_{j}(e))+2^{k+1}h_3(g_{j}(e))\right]|B|.\end{aligned}$$ Suppose that for some $i\le \gamma(e)$, we have constructed $A'_{i-1}$, we will now construct $A_i'$. By for $i-1$, for $i=\gamma(e)$, and the fact that $e\le r_{\gamma(e)}$, we have $|A'_{i-1}|\geq (\frac34-\frac{1}{12})\epsilon_0 |B|=\frac23 \epsilon_0|B|$. Applying to $A'_{i-1}$, we find $A''_{i}$ with all rows intervals, $|V(A_i'')|\le \ell(g_{i-1}(e))$, and $$\begin{aligned}
\label{A'i-1A''i2}|A'_{i-1}\setminus A''_i|\leq h_4(g_{i-1}(e)) |B|,\qquad |{\operatorname{co}}(\pi(A''_i))\setminus \pi(A''_i)|\leq h_3(g_{i-1}(e))|\pi(B)|.\end{aligned}$$ By for $i-1$,, and , we have $$\begin{aligned}
\label{dkA''i}d_k(A''_i)\leq \left[g_{i-1}(e)+2^kh_4(g_{i-1}(e))\right]|B|.\end{aligned}$$ An identical proof shows $|A''_i|\geq(\frac34-\frac{1}{12})\epsilon_0 |B|=\frac23 \epsilon_0|B|$. Now by and , applying to $A''_i$ gives a set $A'_i\subset A''_i$ with all rows intervals, ${\operatorname{co}}(A'_i)={\operatorname{co}}(A''_i)$, property 2 with $A'=A_i'$, and $$\begin{aligned}
\label{Ai'Ai''2}|A''_{i}\setminus A'_i|\leq (2\nu+2)\left[g_{i-1}(e)+2^kh_4(g_{i-1}(e))+2^{k+1}h_3(g_{i-1}(e))\right] |B|,\end{aligned}$$ so together with for $i-1$ and , we deduce $$\begin{aligned}
|A'\setminus A'_i|\leq (2\nu+2)\left[\sum_{j=0}^{i-1} g_{j}(e)+\left(2^k+\frac{1}{2\nu+2}\right)h_4(g_{j}(e))+2^{k+1}h_3(g_{j}(e))\right] |B|.\end{aligned}$$ By , and , we have $$\begin{aligned}
d_k(A'_i)&\leq (2\nu+2)\left[\left(2^k+\frac{1}{2\nu+2}\right)g_{i-1}(e)+\left(2^{2k}+\frac{2^k}{2\nu+2}\right)h_4(g_{i-1}(e))+2^{2k+1}h_3(g_{i-1}(e))\right]|B|\\&=g_i(e)|B|.\end{aligned}$$ Write $\gamma$ for $\gamma(e)$. If for $1 \le i \le \gamma$ we have $|{\operatorname{co}}(\pi(A'_i))\setminus \pi(A'_i)|>h_6(e)|\pi(B)|$, then we have removed at least $$\begin{aligned}
|{\operatorname{co}}(\pi(A_1'))\setminus \pi(A'_\gamma)|&\ge |{\operatorname{co}}(\pi(A_1'))\setminus \pi(A_1')|+\sum_{j=2}^{\gamma}|\pi(A_j'')\setminus \pi(A_j')|\\&\geq  \sum_{j=1}^\gamma |{\operatorname{co}}(\pi(A'_j))\setminus\pi(A'_j)|-|{\operatorname{co}}(\pi(A''_j))\setminus\pi(A''_j)|\\
&\geq \sum_{j=1}^{\gamma}(h_6(e)-h_3(g_{j-1}(e)))|\pi(B)|\\
&=2|\pi(B)|\end{aligned}$$rows in $\pi(B)$, a contradiction. Let $1 \le i_0\leq \gamma$ be an index such that $|{\operatorname{co}}(\pi(A'_{i_0}))\setminus \pi(A'_{i_0})|\leq h_6(e)|\pi(B)|$. As $i_0\leq \gamma$, we have by and the definition of $h_5$ that $$\begin{aligned}
|A'\setminus A'_{i_0}|\leq |A'\setminus A'_\gamma|\le h_5(e)|B|.\end{aligned}$$ Moreover, $V(A'_{i_0})=V(A''_{i_0})\le \ell(g_{i_0-1}(e))\leq H_7(e)$, and as remarked earlier, $A'_{i_0}$ satisfies property 2. We thus conclude by setting $A''=A'_{i_0}$.

### $A_\star\subset A_+$ with $|V(A_\star)|$ and $|{\operatorname{co}}(\pi(A_\star))\setminus \pi(A_\star)|$ small and one further technical condition: Construction {#AstarConstruction}

Before we proceed we need to introduce the following definition.

\[sij\] Given a simplex $\widetilde{T}\subset \mathbb{R}^k$ with vertices $x_0, \hdots, x_k$ construct inductively a dense family of translates of $\frac{1}{2^i}\widetilde{T}$ inside $\widetilde{T}$ as follows. Set $$\begin{aligned}
\mathcal{S}_{i,0}(\widetilde{T})&:= \left\{\left(1-\frac{1}{2^i}\right)x_r+ \frac{1}{2^i}\widetilde{T} : 0\le r \le k \right\}\\
\mathcal{S}_{i,j+1}(\widetilde{T})&:= \left\{ \frac{\widetilde{S}_1+ \widetilde{S}_2}{2}: \widetilde{S}_1, \widetilde{S}_2 \in \mathcal{S}_{i,j} \right\}\end{aligned}$$

Given a simplex $\widetilde{T}\subset \mathbb{R}^k$ we define $$\begin{aligned}
\mathcal{U}_{i,j}({\widetilde{T}}):=\{\vec{u}:\exists \widetilde{S}_1,\widetilde{S}_2\in \mathcal{S}_{i,j}\text{ with }\widetilde{S}_1+\vec{u}=\widetilde{S}_2\}.\end{aligned}$$

Before preceeding, we remark that we will now need a future result, , to define certain constants $\mu_1$ and $\mu_2$ depending only on $k$. The proof is entirely self-contained, and while we could include the result and its proof at this point, we feel it is better to defer them.

\[VofT\] We define constants $\mu_1=\mu_1(k), \mu_2=\mu_2(k)$ as those produced by . Given a simplex $\widetilde{T}$ we set $$\mathcal{W}_T:= \bigcup_{\vec{u}\in \mathcal{U}_{\mu_1, \mu_2}(\widetilde{T})} \mathcal{R}(\vec{u})\cup (-\mathcal{R}(\vec{u})),$$ where $\mathcal{R}(\vec{u})=\lfloor \vec{u} \rfloor + \{0\} \times \{0,1\}^{k-1} $. This satisfies $|\mathcal{W}_T| \le \nu$ for $\nu=\nu(k)$ the constant $2^k|\mathcal{U}_{\mu_1,\mu_2}|$, which is independent of the simplex $\widetilde{T}$. Note that $0\in\mathcal{U}_{\mu_1, \mu_2}(\widetilde{T})$ so $\{0\}\times \{0,1\}^{k-1}\subset \mathcal{W}_T$, and $\mathcal{W}_T=-\mathcal{W}_T$.

With this construction we apply , obtaining a subset $A_\star\subset A_+$ with all rows intervals satisfying the following properties. By , we have $$\begin{aligned}
\label{AAstar}|A\Delta A_\star|\le|A\Delta A_{+}|+|A_+\setminus A_\star|\le (\delta^{\frac{1}{20}-16c}+h_5(\delta^{\frac{1}{20}-17c}))|B|=:h_8(\delta)|B|,\end{aligned}$$ and by , we have $A_\star$ is reduced and $$\begin{aligned}
\label{dkAstar}d_k(A_{\star}) \le (\delta^{\frac{1}{20}-17c} + 2^kh_8(\delta) )|B| = :h_9(\delta)|B|.\end{aligned}$$ Also, $$\begin{aligned}
\label{copiAstar}|{\operatorname{co}}(\pi(A_{\star})) \setminus \pi(A_{\star})|&\le h_6(\delta^{\frac{1}{20}-17c})|\pi(B)|,\text{ and }\\
\label{Astarfewvert}V(A_\star)&\le H_7(\delta^{\frac{1}{20}-17c}).\end{aligned}$$ Here, $h_6,h_8,h_9 \rightarrow 0$ as $\delta \rightarrow 0$.

\[pullover\] Finally, we have for every $\widetilde{T}\in\mathcal{T}^+(A_\star)\cup\mathcal{T}^{-}(A_\star)$, if $x\in T^o \setminus V_\pi(A_\star)$, $y\in Y_{\mathcal{W}_T}(x)$, $z \in \pi(B)$ and $\vec{v}\in\{0\}\times\{0,1\}^{k-1}$ with $x+y=z+z+\vec{v}$ and $R_{x}+R_{y}, R_{z}+R_{z+\vec{v}}$ nonempty, then $(R_{x}+R_{y}) \cap (R_{z}+R_{z+\vec{v}}) \ne \emptyset$.

$A_\star$ is close to ${\operatorname{co}}(A_\star)$ {#Astarclosetoco}
----------------------------------------------------

In this section, we show that $|{\operatorname{co}}(A_\star)\setminus A_\star|= o(1)|B|$. It is easy to show that $2^k|{\operatorname{co}}(A_\star)\setminus A_\star|\le |{\operatorname{co}}(A_\star+A_\star)\setminus (A_\star+A_\star)|+o(1)|B|$, so it will suffice to show that $$\begin{aligned}
\label{vaguedescription2kck}|{\operatorname{co}}(A_\star+A_\star)\setminus (A_\star+A_\star)|\le (2^k-c_k')|{\operatorname{co}}(A_\star)\setminus A_\star|+o(1)|B|\end{aligned}$$ for some constant $c_k'$. We now give a motivating outline.

For $\widetilde{T}\in \mathcal{T}^+(A_\star)\cup \mathcal{T}^-(A_\star)$, we will define functions $g_{T}^+,g_T^-:T\to [0,n_1]$ (actually we will need $[0,2n_1]$ for technical reasons), which encode the distances from the nonempty rows of $A_\star$ in $T$ to the upper and lower convex hulls of $A_\star$ respectively. Then we can estimate $$\begin{aligned}
\label{vaguedesc1}|{\operatorname{co}}(A_\star)\setminus A_\star|=o(1)|B|+\sum_{\ast \in \{+,-\}}\sum_{\widetilde{T}\in \mathcal{T}^\ast} \sum_{x\in T}g_T^\ast(x).\end{aligned}$$ Moreover, we will define functions $g^{+\square}_T,g^{-\square}_T$ as certain restricted infimum convolutions of $g^+_T$ and $g^-_T$ with themselves. These will encode the distance between the rows of a certain subset of $A_\star+A_\star$ (which we will guarantee to be intervals by ) to the upper and lower convex hulls of $A_\star+A_\star$ respectively. This subset accounts for almost all rows. Then we can similarly estimate $$\begin{aligned}
\label{vaguedesc2}|{\operatorname{co}}(A_\star+A_\star)\setminus (A_\star+A_\star)| \le o(1)|B|+\sum_{\ast \in \{+,-\}}\sum_{\widetilde{T}\in \mathcal{T}^\ast}\sum_{x'\in 2\widetilde{T}\cap \{0\}\times \mathbb{Z}^{k-1}} g^{\ast\square}_{T}(x').\end{aligned}$$ To prove the inequality, it will therefore suffice to show for every $\ast \in \{+,-\}$ and $\widetilde{T}\in \mathcal{T}^\ast$, given a function $g:T\to [0,2n_1]$ which is $0$ at the vertices of $T$, that $$\begin{aligned}
\label{vaguedesc3}\sum_{x\in T}g(x) \le o(1)|B|+ (2^k-c_k')\sum_{x'\in 2\widetilde{T}\cap \{0\}\times \mathbb{Z}^{k-1}}g^{\square}(x').\end{aligned}$$

In , we properly define the functions $g^\ast_T(x)$ and $g^{\ast \square}_T(x)$ and show in and in , thus reducing the problem to showing .

In , we prove in .

Finally, in , we combine these results and conclude in .

### Transitioning from $A_\star$ to functions and their infimum convolutions {#Transitioningsubsection}

We focus on the gaps in the $e_1$-direction between $A_\star$ and the convex hull of $A_\star$ via functions on $\pi(A_\star)$.

We denote by $V_\pi=V_\pi(A_\star)$ the projection of the vertices of ${\widetilde{\operatorname{co}}}(A_{\star})$ under $\pi$ to $\{0\}\times \mathbb{Z}^{k-1}$. We denote the empty rows by $E:={\operatorname{co}}(\pi(A_\star))\setminus \pi(A_\star).$ Finally, we write $\mathcal{T}^+:=\mathcal{T}^+(A_\star)$ and $\mathcal{T}^-:=\mathcal{T}^-(A_\star)$.

Recall that for a simplex $\widetilde{T}\subset {\widetilde{\operatorname{co}}}(\pi(B))$, we denote $T=\widetilde{T}\cap  \mathbb{Z}^{k}=\widetilde{T}\cap (\{0\}\times \mathbb{Z}^{k-1})$.

\[gplusgminusdefn\] Denoting $\Psi_{A_\star}^+,\Psi_{A_\star}^-:{\widetilde{\operatorname{co}}}(\pi(A_\star))\to \mathbb{R}$ the upper and lower convex hull function of $A_\star$ in the $e_1$-direction respectively, we define for $\widetilde{T}^+\in \mathcal{T}^+$ and $\widetilde{T}^-\in \mathcal{T}^-$ the functions $$g^+_{T^+}:T^+\to [0,2n_1],\qquad g^-_{T^-}:T^-\to [0,2n_1]$$ according to the formulas $$g^+_{T^+}(x)=\begin{cases}\Psi_{A^\star}^+(x)-\max R_x & \text{if }x\in  V(T^+)\text{ or }x\not\in V_\pi\cup E\\
2n_1 & \text{otherwise}.\end{cases},$$ and $$g^-_{T^-}(x)=\begin{cases}\min R_x-\Psi_{A^\star}^-(x) & \text{if }x\in  V(T^-)\text{ or }x\not\in V_\pi\cup E\\
2n_1 & \text{otherwise.}\end{cases}.$$

\[gplusgminusrmk\] For $x\in V(T^\ast)$ or $x\not\in V_{\pi}\cup E$, $g^\ast_{T^\ast}(x)\in [0,n_1-1]$ is the distance in the $e_1$-direction from the row $R_x$ to the upper convex hull of $A_\star$ for $\ast=+$ and lower convex hull of $A_\star$ for $\ast=-$, and we always have $g^\ast_{T^\ast}(x)\le 2n_1$. In particular, for $x\in V(T^\ast)$ we note that $g^\ast_{T^\ast}(x)=0$.

\[gsimple\] We have the following estimate for some function $h_{10}(\delta)\to 0$ as $\delta\to 0$ that $$\begin{aligned}
\left(\sum_{\ast \in \{+,-\}}\sum_{\widetilde{T}^\ast\in\mathcal{T}^\ast}\sum_{x\in T^\ast}g^\ast_{T^\ast}(x)\right)-|{\operatorname{co}}(A_\star)\setminus A_\star|\le h_{10}(\delta)|B|.\end{aligned}$$

Writing $|{\operatorname{co}}(A_\star)\setminus A_\star|=\sum_{x\in {\operatorname{co}}(\pi(A_\star))}|({\operatorname{co}}(A_\star)\setminus A_\star)\cap \pi^{-1}(x)|$, we upper bound the contribution separately on the left hand side for each $x\in {\operatorname{co}}(\pi(A_\star))$.

-   We estimate the contribution of $x\in \partial\widetilde{T}^+$ for some $\widetilde{T}^+\in \mathcal{T}^+$ or with $x\in\partial\widetilde{T}^-$ for some $\widetilde{T}^-\in \mathcal{T}^-$. There are at most $\binom{|V_\pi|}{k}$ simplices, each with $k$ facets, with each facet having at most $n_k(\delta,\epsilon_0)^{-1}|\pi(B)|$ integral points by , each of which can in turn contribute $2n_1+2n_1$ to the left hand side.

-   We estimate the contribution of $x \in V_\pi\cup E$ that lie in the interior of at most one simplex in $\mathcal{T}^+$ and at most one simplex in $\mathcal{T}^-$. There are at most $|E|+|V_\pi|$ of these points, each of which can in turn contribute $2n_1+2n_1$ to the left hand side.

-   Finally, each remaining $x$ lies in a unique simplex of $\widetilde{T}^+\in\mathcal{T}^+$ and $\widetilde{T}^-\in\mathcal{T}^-$, and $x\not \in V_\pi\cup E$. For such $x$, we have $|({\operatorname{co}}(A_\star)\setminus A_\star)\cap R_x|=\lfloor g^+_{T^+}(x)\rfloor + \lfloor g^-_{T^-}(x) \rfloor$. This discrepancy with $g^+_{T^+}(x)+g^-_{T^-}(x)$ is crudely bounded by $2|\pi(B)|$ for each of the at most $\binom{|V_\pi|}{k}$ simplices.

Combining these errors, and noting that $|E|$ and $|V_\pi|$ are bounded by and , we conclude by choosing $h_{10}(\delta)$ so that $$4k\binom{|V_\pi|}{k}n_k(\delta,\epsilon_0)^{-1}|B|+(|E|+|V_\pi|)4n_1+2\binom{|V_\pi|}{k}|\pi(B)|\le h_{10}(\delta)|B|.$$

Recall in , we introduced for a simplex $\widetilde{T}\subset \{0\}\times \mathbb{R}^{k-1}$ with integral vertices and a subset $\mathcal{W}\subset \{0\}\times \mathbb{Z}^{k-1}$ the notation $Y_{\mathcal{W}}(x)=((x+\mathcal{W})\cap T)\cup V(T)$. We now define a restricted infimum convolution with respect to $\mathcal{W}$.

\[infconv\] Given a simplex $\widetilde{T}\subset \{0\}\times \mathbb{R}^{k-1}$ with integral vertices, a subset $\mathcal{W}\subset \{0\}\times \mathbb{Z}^{k-1}$, and a function $g : T \rightarrow \mathbb{R}_{\ge 0}$, we define the restricted infimum convolution $g^{\square}_{\mathcal{W}}:T+T\to \mathbb{R}_{\ge 0}$ by $$g^{\square}_{\mathcal{W}}(x)=\begin{cases}\min\{g(x_1)+g(x_2)\}& \text{over all }x_1+x_2=x \text{ with } x_1\in T^{\circ}\text{ and }x_2 \in Y_{\mathcal{W}}(x_1)\\
0& \text{no such $x_1,x_2$ exist.}
\end{cases}$$

For $g=g^\ast_{T^\ast}$ for some $\ast\in \{+,-\}$, we will always take $\mathcal{W}=\mathcal{W}_T$ as defined in in the infimum convolution $g^{\ast\square}_{T^\ast,\mathcal{W}}$. We will always omit the subscript $\mathcal{W}$, writing $g^{\ast\square}_{T^\ast}$ instead.

\[gsquare\] We have the following estimate for some function $h_{11}(\delta)\to 0$ as $\delta\to 0$ that $$\begin{aligned}
|{\operatorname{co}}(A_\star+A_\star)\setminus (A_\star+A_\star)|-\sum_{\ast\in \{+,-\}} \sum_{\widetilde{T}^\ast\in\mathcal{T}^\ast}\sum_{x'\in (T^\ast+T^\ast)}g_{T^\ast}^{\ast\square}(x')\le h_{11}(\delta)|B|.\end{aligned}$$

Writing $|{\operatorname{co}}(A_\star+A_\star)\setminus (A_\star+A_\star)|=\sum_{x'\in {\operatorname{co}}(\pi(A_\star+A_\star))}|({\operatorname{co}}(A_\star+A_\star)\setminus (A_\star+A_\star))\cap \pi^{-1}(x')|$, we upper bound the contribution for each $x'\in {\operatorname{co}}(\pi(A_\star+A_\star))$, which we express uniquely as $x'=x+x+\vec{v}$ with $\vec{v}\in\{0\}\times\{0,1\}^{k-1}, x \in\{0\}\times\mathbb{Z}^{k-1}$.

Fix $x'=x+x+\vec{v}$ as above. Suppose for each $\ast \in \{+,-\}$ there exists $\widetilde{T}^\ast\in \mathcal{T}^\ast$ with $x,x+\vec{v}\in T^{\ast o}\setminus (V_\pi\cup E)$. Then $$|{\operatorname{co}}(A_\star+A_\star)\cap \pi^{-1}(x')|\le g_{T^+}^{+\square}(x')+g_{T^-}^{-\square}(x').$$

Note that we can write $x'=x+(x+\vec{v})$, with $x\in T^{\circ}$ and $x+\vec{v}\in Y_{\mathcal{W}_{T^\ast}}(x)$ since $\vec{v}\in \mathcal{W}_{T^{\ast}}$. Hence by there exists $x_1^*\in T^{\ast o}$ and $x_2^*\in Y_{\mathcal{W}_{T^\ast}}(x_1^\ast)$ so that $x_1^\ast+x_2^\ast=x'$ and $g^{\ast\square}_{T^\ast}(x')=g_{T^\ast}^\ast(x_1^\ast)+g_{T^\ast}^\ast(x_2^\ast)$. If either $x_1^\ast$ or $x_2^\ast$ are in $(V_\pi\cup E)\setminus V(T^\ast)$, the corresponding term on the right hand side is at least $2n_1$ and the inequality is trivially true. Hence, we may assume $x_1^*,x_2^*\not \in (V_\pi\cup E)\setminus V(T^\ast)$. In particular, we have $x_1^*\in T^{\ast\circ}\setminus V_\pi$ and both $x_1^\ast,x_2^\ast\not\in E$. Let $\Psi_{A_\star+A_\star}^+,\Psi_{A_\star+A_\star}^-:{\widetilde{\operatorname{co}}}(\pi(A_\star+A_\star))\to \mathbb{R}$ be the upper and lower convex hull function on $A_\star+A_\star$ in the $e_1$-direction respectively. We have $$\begin{aligned}
    \Psi^+_{A_\star+A_\star}(x')-\max (R_{x_1^+}+R_{x_2^+})&=\Psi_{A_\star}(x_1^+)+\Psi_{A_\star}(x_2^+)-\max R_{x_1^+}-\max R_{x_2^+}\\
    &=g_{T^+}^+(x_1^+)+g_{T^+}^+(x_2^+)=g^{+\square}_{T^+}(x')\end{aligned}$$ and $$\begin{aligned}
        \min (R_{x_1^-}+R_{x_2^-})-\Psi^-_{A_\star+A_\star}(x')&=\min R_{x_1^-}+\min R_{x_2^-}-\Psi_{A_\star}(x_1^-)-\Psi_{A_\star}(x_2^-)\\
    &=g_{T^-}^-(x_1^-)+g_{T^-}^-(x_2^-)=g^{-\square}_{T^-}(x').\end{aligned}$$ By , as $x_1^*\in T^\circ\setminus V_\pi$, $x_2^\ast\in Y_{\mathcal{W}_{T^\ast}}(x_1^\ast)$, and $x_1^\ast,x_2^\ast,x,x+\vec{v}\not\in E$, the intervals $R_{x_1^+}+R_{x_2^+}$ and $R_{x_1^-}+R_{x_2^-}$ both overlap $R_x+R_{x+\vec{v}}$, so $$I_{x'}:=(R_{x_1^-}+R_{x_2^-})\cup (R_{x}+R_{x+\vec{v}})\cup (R_{x_1^+}+R_{x_2^+})$$ is an interval. Therefore $$\begin{aligned}
&|({\operatorname{co}}(A_\star+A_\star)\setminus (A_\star+A_\star))\cap \pi^{-1}(x')|\\\le &|({\operatorname{co}}(A_\star+A_\star)\cap \pi^{-1}(x'))\setminus I_{x'}|\\
 \le&\lfloor \Psi^+_{A_\star+A_\star}(x')\rfloor-\max (R_{x_1^+}+R_{x_2^+})+\min (R_{x_1^-}+R_{x_2^-})-\lceil \Psi^-_{A_\star+A_\star}(x')\rceil\\
 \le& g^{+\square}_{T^+}(x')+g^{-\square}_{T^-}(x').\end{aligned}$$

Returning to the proof of , we have the following estimates. Recall that we uniquely write $x'=x+x+\vec{v}$ with $x'\in {\operatorname{co}}(\pi(A_\star+A_\star))$, $x\in \{0\}\times \mathbb{Z}^{k-1}$ and $\vec{v}\in \{0\}\times \{0,1\}^{k-1}$.

-   We estimate the contribution of $x,\vec{v}$ such that for some $\ast \in \{+,-\}$, there is no $\widetilde{T}^\ast\in \mathcal{T}^\ast$ with $x,x+\vec{v}\in T^{\ast\circ}$. For the simplex $\widetilde{T}^\ast$ containing $\frac{1}{2}(x+(x+\vec{v}))=\frac{1}{2}x'\in \pi({\widetilde{\operatorname{co}}}(A_\star))$, there is a hyperplane $\widetilde{H}$ containing a facet of $\widetilde{T}^\ast$ that separates (or contains one of) $x$ and $x+\vec{v}$. For each $\vec{v}$, there are at most $\binom{|V_\pi|}{k}$ simplices, each with $k$ facets, and each facet separating (or containing) at most $2$ such $x,x+\vec{v}$ pairs on each of the at most $(k-1)n_k(\epsilon_0,\delta)^{-1}|\pi(B)|$ $\vec{v}$-fibers of $\pi(B)$, and each such $x,\vec{v}$ contributes at most $2n_1$ to the left hand side.

-   We now estimate the contribution for those $x,\vec{v}$ such that one of $x,x+\vec{v}$ lies in $V_\pi\cup E$. There are $2^{k-1}$ choices of $v$, and for each of these choices there are at most $2(|V_\pi|+|E|)$ such values of $x$, each of which contributes at most $2n_1$ to the right hand side.

-   The remaining $x,\vec{v}$ have $x,x+\vec{v}\in T^{+o}\setminus (V_\pi\cup E), T^{-o}\setminus (V_\pi\cup E)$ for unique simplices $\widetilde{T}^+\in \mathcal{T}^+$ and $\widetilde{T}^-\in \mathcal{T}^-$. But the above claim shows that the contribution of such $x'$ is non-positive.

Combining these errors, and noting that $|E|$ and $|V_\pi|$ are bounded by and , we conclude by taking $h_{11}(\delta)$ so that $$\begin{aligned}
2^{k+1}(k-1)\binom{|V_\pi|}{k} n_k(\epsilon_0,\delta)^{-1}|B|+2^{k+1}(|V_\pi|+|E|)n_1\le h_{11}(\delta)|B|.\end{aligned}$$

### Infimum convolution of functions {#infconvolutionsubsection}

In this section we prove a general result about the infimum convolution (see ) of functions, related to the fact that small doubling implies being close to the convex hull.

\[squareprop\] There exist constants $c_k',c_k''>0$ such that the following is true. Let $T\subset \pi(B)$ be a discrete simplex with integral vertices $x_0,\ldots,x_{k-1}\in \{0\}\times\mathbb{Z}^{k-1}$, and let $g:T\to [0,2n_1]$ with $g(x_i)=0$ for all $i$. Then $$\sum_{x' \in T+T}g_{\mathcal{W}_T}^{\square}(x')\le (2^k-c_k')\sum_{x \in T}g(x)+c_k''\min\{n_i\}^{-1}|B|$$

We omit the subscript $\mathcal{W}_T$ from now on. Throughout the entire proof we shall consider the sets $\mathcal{S}_{i,j}=\mathcal{S}_{i,j}(\widetilde{T})$ in with parameters $i,j$ bounded above by $\mu_1,\mu_2$, respectively.

For a subset $\widetilde{P} \subset \widetilde{T}$, we define $g(\widetilde{P})= \sum_{x \in \widetilde{P}\cap T} g(x)$, and for a subset $\widetilde{Q}\subset \widetilde{T}+\widetilde{T}$, define $g^{\square}(\widetilde{Q})=\sum_{x\in \widetilde{Q}\cap (T+T)}g^{\square}(\widetilde{Q})$.

For a subset $\widetilde{P} \subset \widetilde{T}$, we define $d'_k(\widetilde{P})=-g^{\square}(\widetilde{P}+\widetilde{P})+2^kg(\widetilde{P})$.

\[dk’obs\] For a polytope $\widetilde{P} \subset \widetilde{T}$, we have $d'_k(\widetilde{P}) \ge -2^{2k+5}\min\{n_i\}^{-1}|B|$. In particular, with $P=\widetilde{P}\cap (\{0\}\times\mathbb{Z}^{k-1})$ we have $d'_k(P) \ge -2^{2k+5}\min\{n_i\}^{-1}|B|$. More generally, the same conclusion holds for any region $\widetilde{P}\subset \widetilde{T}$ defined as the intersection of open and closed half-spaces.

Note that if $\widetilde{P}\subset \widetilde{T}$ is defined as the intersection of open and closed half-spaces, then we can perturb the open half-spaces to closed ones without changing the lattice points in $\widetilde{P}$ or $\widetilde{P}+\widetilde{P}$, so we may assume that $\widetilde{P}$ is a polytope. Recall that $\{0\}\times \{0,1\}^{k-1} \subset \mathcal{W}_T$. Note that if we write $z\in (\widetilde{P}+\widetilde{P})\cap T=2\widetilde{P}\cap T$ as $z=x+(x+\vec{v})$ with $\vec{v}\in \{0\}\times \{0,1\}^{k-1}$, then as $\widetilde{P}$ is convex, either $x,x+\vec{v}\in P^o$ or the segment $[x,x+\vec{v}]$ intersects $\partial\widetilde{P}$. Therefore with $\vec{v}$ ranging over $\{0\}\times\{0,1\}^{k-1}$ we have $$\begin{aligned}
    d'_k(\widetilde{P})&= 2^kg(\widetilde{P})-g^{\square}(\widetilde{P}+\widetilde{P}) \nonumber\\
    &\ge 2^k\sum_{x\in P} g(x) - \sum_{\vec{v}}\sum_{x,x+\vec{v}\in P^o}g^{\square}(x+x+\vec{v}) - \sum_{\vec{v}}\sum_{[x,x+\vec{v}]\cap\partial \widetilde{P}\ne \emptyset}g^{\square}(x+x+\vec{v})\nonumber\\\label{3.44line3}
    &\ge 2^k\sum_{x\in P} g(x) - \sum_{\vec{v}}\sum_{x,x+\vec{v} \in P^o  }g(x)+g(x+\vec{v})- \sum_{\vec{v}}\sum_{[x,x+\vec{v}]\cap\partial \widetilde{P}\ne \emptyset}4n_1\\
    &\ge-\sum_{\vec{v}}\sum_{[x,x+\vec{v}]\cap\partial \widetilde{P}\ne \emptyset}4n_1 \nonumber\\
    &\ge  -8n_1\sum_{\vec{v}}|(\widetilde{P} \Delta (\widetilde{P}-\vec{v})) \cap \{0\}\times\mathbb{Z}^{k-1}|  \nonumber\\
    &\ge -8n_1\sum_{\vec{v}}|(\widetilde{P} \Delta (\widetilde{P}-\vec{v}))|  -8n_12^{k-1}\cdot 3\cdot 2(k-1)k \min\{n_i\}^{-1} |\pi(B)|  \label{3.44line6}\\
    &\ge -8n_1\sum_{\vec{v}}|\vec{v}||\partial\widetilde{P}|  -3\cdot 2^{k+3}(k-1)k \min\{n_i\}^{-1} |B|   \nonumber\\
    &\ge -8n_12^{k-1}\sqrt{k-1}\cdot2(k-1)\min\{n_i\}^{-1} |\pi(B)| -3\cdot 2^{k+3}(k-1)k \min\{n_i\}^{-1} |B| \label{3.44line8}\\
    &\ge -2^{2k+5}\min\{n_i\}^{-1}|B|.\nonumber\end{aligned}$$

In we used the fact that $\vec{v}\in \mathcal{W}_T$ so $x+\vec{v}\in Y_{\mathcal{W}_T}(x)$, and $g^{\square}\le 2\max g \le 4n_1$. In we have used to upper bound $$|(\widetilde{P} \Delta (\widetilde{P}-\vec{v})) \cap \{0\}\times\mathbb{Z}^{k-1}|=|\widetilde{P}\cap \{0\}\times\mathbb{Z}^{k-1}|+|(\widetilde{P}-\vec{v})\cap \{0\}\times\mathbb{Z}^{k-1}|-|(\widetilde{P}\cap(\widetilde{P}-\vec{v}))\cap \{0\}\times\mathbb{Z}^{k-1}|,$$ and in the fact that $|\partial \widetilde{P}|\le |\partial \widetilde{\pi(B)}|\le 2(k-1)\min\{n_i\}^{-1}|\pi(B)|$.

For a vertex $x\in V(\widetilde{T})$ and simplices $\widetilde{S}=(1-2^{-i})x+2^{-i}\widetilde{T} \in \mathcal{S}_{i,0}$ and $\widetilde{S}'=\frac{1}{2}(x+\widetilde{S}) \in \mathcal{S}_{i+1,0}$, we have $$g(S')\leq 2^{-k} g(S)+2^{-k}d_k'(T) +2^{k+6}\min\{n_i\}^{-1}|B|$$

By we have (letting $\widetilde{S}'^c$ be the complement of $\widetilde{S}'$ inside $\widetilde{T}$) that $$\begin{aligned}
    \nonumber d_k'(T)\ge d_k'(\widetilde{T})&=2^k g(\widetilde{T})-g^\square(\widetilde{T}+\widetilde{T})\\\nonumber
    &\ge 2^k g(\widetilde{S}')-g^\square(\widetilde{S}'+\widetilde{S}') + 2^k g(\widetilde{S}'^c)-g^\square(\widetilde{S}'^c+\widetilde{S}'^c)\\\nonumber
    &= 2^k g(\widetilde{S}')-g^\square(\widetilde{S}'+\widetilde{S}') + d_k'(\widetilde{S}'^c)\\\nonumber
    &\ge  2^k g(\widetilde{S}')-g^\square(\widetilde{S}'+\widetilde{S}')-2^{2k+5}\min\{n_i\}^{-1}|B|\\\nonumber
    &\ge  2^k g(\widetilde{S}')-g^\square(\widetilde{S}^{\circ}+x)-g^{\square}(\partial\widetilde{S}+x)-2^{2k+5}\min\{n_i\}^{-1}|B|\\\label{3.49line6}
    &\ge 2^k g(\widetilde{S}')-g(\widetilde{S}^{\circ})-k(4n_1)\min\{n_i\}^{-1}|\pi(B)|-2^{2k+5}\min\{n_i\}^{-1}|B|\\\nonumber
    &\ge2^k g(S')-g(S)-2^{2k+6}\min\{n_i\}^{-1}|B|.\end{aligned}$$ where in we used that $x\in Y_{\mathcal{W}_T}(y)$ for all $y\in \widetilde{T}^{\circ}$, to estimate the number of lattice points on each facet of $\widetilde{S}$, and the fact that $\max g^{\square}\le 4n_1$.

For $\widetilde{S}'\in\mathcal{S}_{i,0}$, we have $$\begin{aligned}
g(S'')&\leq 2^{-ik} g(T)+\max\left(0,\frac{1}{2^k-1} d_k'(T)\right)+ \frac{2^k}{2^k-1}2^{k+6}\min\{n_i\}^{-1}|B|\\&\le 2^{-ik} g(T)+\frac{1}{2^k-1} d_k'(T)+2^{2k+6}\min\{n_i\}^{-1}|B|\end{aligned}$$

\[averageg\] Let $i\leq \mu_1$ and $j\leq \mu_2-1$. For $\widetilde{S}'_1,\widetilde{S}'_2\in\mathcal{S}_{i,j}$ and $\widetilde{S}''=\frac12(\widetilde{S}'_1+\widetilde{S}'_2)\in\mathcal{S}_{i,j+1}$, we have $$g(S'')\leq \frac12( g(S'_1)+g(S'_2))+2^{-k}d_k'(T)+ 2^{5k}\min\{n_i\}^{-1}|B|$$

Let $\vec{u}$ be the vector such that $\widetilde{S}'_1+\vec{u}=\widetilde{S}'_2$. Then by , we have $\mathcal{R}(\vec{u})=\lfloor \vec{u} \rfloor +\{0\}\times\{0,1\}^{k-1}\subset \mathcal{W}_{T}$. Let $$\widetilde{S}''^{c}=\widetilde{P}_1\sqcup\dots\sqcup \widetilde{P}_{k}$$ be a partition into convex regions, the intersection of open and closed half-spaces. Indeed this can be obtained by taking the defining equations $x \cdot \vec{c}_i\le \vec{b}_i$ for $1 \le i \le k$ of $\widetilde{S}''$, and defining $\widetilde{P}_j$ by setting $x \cdot \vec{c}_i\le\vec{b}_i$ for $1 \le i <j$ and $x \cdot \vec{w}_j > \vec{b}_j$ inside $\widetilde{T}$. Hence, by we find $$\begin{aligned}
    d_k'(T)\ge d_k'(\widetilde{T})=2^k g(\widetilde{T})-g^\square(\widetilde{T}+\widetilde{T})
    &=2^kg(\widetilde{S}'')-g^\square(\widetilde{S}''+\widetilde{S}'')+ \sum_j 2^kg( \widetilde{P}_{j})-g^\square( \widetilde{P}_{j}+\widetilde{P}_{j})\\
    &=2^kg(\widetilde{S}'')-g^\square(\widetilde{S}_1'+\widetilde{S}_2')+ \sum_jd_k'(\widetilde{P}_{j})\\
    &\ge 2^kg(\widetilde{S}'')-g^\square(\widetilde{S}_1'+\widetilde{S}_2')  -k2^{2k+5}\min\{n_i\}^{-1}|B|.\end{aligned}$$

Note that every point $x' \in (\widetilde{S}_1'+\widetilde{S}_2') \cap \{0\}\times\mathbb{Z}^{k-1}$ we can write uniquely as $x'=x+x+\vec{w}$ for some $\vec{w}\in \mathcal{R}(\vec{u})$ (this is true in fact for every $x' \in \{0\}\times \mathbb{Z}^{k-1}$), and for this $\vec{w}$ (in fact for any $\vec{w}\in \mathcal{R}(u)$) we have $\vec{w}-\vec{u}\in\{0\}\times (-1,1]^{k-1}$. We have $\vec{u}\in \{0\}\times \prod_{i=2}^k[-n_i+1,n_i-1]$ and $x'\in (\pi(\widetilde{B})+\pi(\widetilde{B}))\cap \{0\}\times \mathbb{Z}^{k-1}=\{0\}\times \prod_{i=2}^k \{2,\ldots,2n_i\}$, so $$x=\left\lfloor \frac{x'-\lfloor\vec{u}\rfloor}{2}\right\rfloor\in B':=\{0\}\times\prod_{i=2}^k \left\{\left\lfloor\frac{3-n_{i}}{2}\right\rfloor,\ldots,\left\lfloor\frac{3n_i-1}{2}\right\rfloor\right\},$$ where $B'$ is a translate of $B(2n_2-1,\ldots,2n_k-1)$. Also, as the midpoint $\frac{1}{2}(x+(x+(\vec{w}-\vec{u})))$ lies in $\widetilde{S}'_1$, either $x\in \widetilde{S}_1'$ and $x+(\vec{w}-\vec{u}) \in \widetilde{S}_1'$ (equivalently $x+\vec{w}\in \widetilde{S}_2'$), or $x$ and $x+(\vec{w}-\vec{u})$ are separated by some hyperplane $\widetilde{H}$ containing one of the $k$ facets of $\widetilde{S}_1'$.

Given $\vec{w}\in \mathcal{R}(\vec{u})$ and a hyperplane $\widetilde{H}$, there are at most $2^{2k}\min\{n_i\}^{-1}|\pi(B)|$ many choices of $x \in B'$ with $x,x+(\vec{w}-\vec{u})$ separated by $\widetilde{H}$. Indeed, set $\widetilde{G}_{\vec{w},\widetilde{H}}$ to be the convex region of the box $\widetilde{B'}$ between the hyperplanes $\widetilde{H}$ and $\widetilde{H}-(\vec{w}-\vec{u})$. Note that $$|\widetilde{G}_{\vec{w},\widetilde{H}}|\le |\vec{w}-\vec{u}|\cdot|\partial \widetilde{B'}|\le (k-1)^{\frac{1}{2}} 2(k-1)2^{k-2}\min\{n_i\}^{-1}|\pi(B)|\le 2^{2k-1}\min\{n_i\}^{-1}|\pi(B)|.$$ By applied to $B'$, $$\begin{aligned}
\label{discGsize}|\widetilde{G}_{\vec{w},\widetilde{H}}\cap (\{0\}\times \mathbb{Z}^{k-1})|\le (2^{2k-1}  + 2(k-1)k2^{k-2})\min\{n_i\}^{-1}|\pi(B)| \le 2^{2k}\min\{n_i\}^{-1}|\pi(B)|.\end{aligned}$$

From the above discussion, if $x+x+\vec{w}\in \widetilde{S}_1'+\widetilde{S}_2'$, and either $x\not \in \widetilde{S}_1'$ or $x+\vec{w}\not\in \widetilde{S}_2'$, then $x\in \widetilde{G}_{\vec{w},\widetilde{H}}$ for some $\widetilde{H}$ containing a facet of $\widetilde{S_1}'$. Hence from (taking $\vec{w}\in \mathcal{R}(\vec{u})$ and $x\in \{0\}\times\mathbb{Z}^{k-1}$) we deduce $$\sum_{\vec{w}}\sum_{\substack{x+x+\vec{w} \in \widetilde{S}_1'+\widetilde{S}_2'  \\ x \not\in \widetilde{S}_1' \text{ or }x+\vec{w} \not\in \widetilde{S}_2' }} g^{\square}(x+x+\vec{w}) \le 2^{k-1}k2^{2k}\min\{n_i\}^{-1}|\pi(B)|\max g^{\square} \le k2^{3k+1}\min\{n_i\}^{-1}|B|.$$ Also, as $\mathcal{R}(u) \subset \mathcal{W}_T$ and $\max g^{\square}\le 4n_1$, we have $$\begin{aligned}
\sum_{\vec{w}}\sum_{\substack{x+x+\vec{w} \in \widetilde{S}_1'+\widetilde{S}_2'  \\ x \in \widetilde{S}_1' \text{ and }x+\vec{w} \in \widetilde{S}_2' }} g^{\square}(x+x+\vec{w}) &\le \sum_{\vec{w}}\sum_{\substack{x+x+\vec{w} \in \widetilde{S}_1'+\widetilde{S}_2'\nonumber  \\ x \in (\widetilde{S}_1')^{\circ} \text{ and }x+\vec{w} \in \widetilde{S}_2' }} (g(x)+g(x+\vec{w}))+\sum_{x\in \partial \widetilde{S}_1'}4n_1\\ &\le 2^{k-1}(g(\widetilde{S}_1')+ g(\widetilde{S}_2'))+4k\min\{n_i\}^{-1}|B|\label{3.51},\end{aligned}$$ where in we used on each of the facets of $\widetilde{S}_1'$. Putting it all together, $$\begin{aligned}
    d_k'(T)\ge d_k'(\widetilde{T})\ge& 2^kg(\widetilde{S}'')-k2^{2k+5}\min\{n_i\}^{-1}|B|\\&-\sum_{\substack{x+x+\vec{w} \in \widetilde{S}_1'+\widetilde{S}_2'  \\ x \in \widetilde{S}_1' \text{ and }x+\vec{w} \in \widetilde{S}_2' }} g^{\square}(x+x+\vec{w})- \sum_{\substack{x+x+\vec{w} \in \widetilde{S}_1'+\widetilde{S}_2'  \\ x \not\in \widetilde{S}_1' \text{ or }x+\vec{w} \not\in \widetilde{S}_2' }} g^{\square}(x+x+\vec{w})\\
    \ge& 2^{k}g(\widetilde{S}'')-2^{k-1}(g(\widetilde{S}_1')+ g(\widetilde{S}_2'))-(4k+k2^{2k+5}+k2^{3k+1})\min\{n_i\}^{-1}|B|\\
    \ge& 2^{k}g(S'')-2^{k-1}(g(S_1')+ g(S_2'))-2^{6k}\min\{n_i\}^{-1}|B|.\end{aligned}$$

\[mu1mu2\] For $\widetilde{S}'\in\mathcal{S}_{\mu_1,\mu_2}$ we have $$g(S')\leq 2^{-\mu_1 k} g(T)+\left(\frac{1}{2^k-1}+ \mu_22^{-k}\right)d_k'(T)+(2^{2k+6}+\mu_22^{5k})\min\{n_i\}^{-1}|B|$$

Finally, before we prove , we prove the following result which as mentioned before constructs the constants $\mu_1,\mu_2$.

\[coveringfamily\] There exist $\mu_1=\mu_1(k)$ and $\mu_2=\mu_2(k)$ and a family $\mathcal{F}\subset \mathcal{S}_{\mu_1,\mu_2}(\widetilde{T})$ such that $\widetilde{T}\subset \bigcup_{\widetilde{S}\in \mathcal{F}}\widetilde{S}$ and $\sum_{\widetilde{S}\in \mathcal{F}} |\widetilde{S}|\leq 2^{\mu_1-1}|\widetilde{T}|$, i.e. $|\mathcal{F}|\leq 2^{\mu_1k-1}$.

Without loss of generality assume $\widetilde{T}$ is regular of volume $1$ centered at the origin. Extend a finite covering of $[0,1]^{k-1}$ with $q_k$ translates of $\widetilde{T}$ to a periodic covering $\mathcal{C}$ of $\mathbb{R}^{k-1}$ with average density $q_k$, and let $\mu_1(k):= \lceil\log_2(q_k)\rceil+2k-1$.

We have that $2^{-\mu_1-1} \mathcal{C}$ is a periodic covering of $\mathbb{R}^{k-1}$ by translates of $2^{-\mu_1-1}\widetilde{T}$ with average density $q_k$, so for any polytope $\widetilde{P}$ there exists a $\vec{u}$ with $\sum_{\widetilde{S}\in \vec{u}+2^{-\mu_1+1}\mathcal{C}}|\widetilde{S}\cap \widetilde{P}|\le q_k|\widetilde{P}|$. Take $\widetilde{P}=2\widetilde{T}$, and let $\mathcal{C}'\subset \vec{u}+2^{-\mu_1-1}\mathcal{C}$ be the set of simplices which intersect $\widetilde{T}$, so that $\widetilde{T}\subset \bigcup_{\widetilde{S}\in\mathcal{C}'} \widetilde{S}$. Each $\widetilde{S}\subset \mathcal{C}'$ is contained in $\widetilde{T}+2^{-\mu_1-1}\widetilde{T}-2^{-\mu_1-1}\widetilde{T}\subset \widetilde{T}+2^{-\mu_1-1}\widetilde{T}+2^{-\mu_1-1}(k-1)\widetilde{T}\subset 2\widetilde{T}$, so $$\sum_{\widetilde{S}\in\mathcal{C}'}|\widetilde{S}|=\sum_{\widetilde{S}\in \mathcal{C}'}|\widetilde{S}\cap 2\widetilde{T}|\leq q_k|2\widetilde{T}|=2^{k-1}q_k.$$

For each $\widetilde{S} \in \mathcal{C}'$, there exists a translate $f(\widetilde{S})$ of $2^{-\mu_1-1}\widetilde{T}$ such that $\widetilde{S} \cap \widetilde{T} \subset f(\widetilde{S}) \subset \widetilde{T}$, and we construct $\mathcal{C}'':=\{f(S) : \widetilde{S} \in \mathcal{C}'\}$. Then $\sum_{\widetilde{S}'\in\mathcal{C}''}|\widetilde{S}'|\leq 2^{k-1}q_k$, all simplices in $\mathcal{C}''$ are contained in $\widetilde{T}$, and $\widetilde{T}\subset \bigcup _{\widetilde{S}'\in\mathcal{C}''}\widetilde{S}'$.

The collection $\cup_{j\ge 0}\mathcal{S}_{\mu_1,j}(\widetilde{T})$ is a dense collection of translates of $2^{-\mu_1}\widetilde{T}$ contained inside $\widetilde{T}$, and in fact for every (possibly lower dimensional) face $\widetilde{F}$ of $\widetilde{T}$, the sub-collection of simplices in $\cup_{j\ge 0}\mathcal{S}_{\mu_1,j}(\widetilde{T})$ intersecting $\widetilde{F}$ is dense among all translates of $2^{-\mu_1-1}\widetilde{T}$ contained in $\widetilde{T}$ which intersect $\widetilde{F}$. Therefore for each element $\widetilde{S} \in \mathcal{C''}$, there exist a translate $h(\widetilde{S})\in\cup_{j\ge 0}\mathcal{S}_{\mu_1,j}(\widetilde{T}')$ which contains $\widetilde{S}$. Finally, we can construct the family $\mathcal{F} := \{h(\widetilde{S}) : \widetilde{S} \in \mathcal{C}'' \}$. As $\mathcal{C''}$ is a fixed finite set, there exist $\mu_2=\mu_2(k)$ such that $\mathcal{F} \subset \mathcal{S}_{\mu_1,\mu_2}(\widetilde{T}')$. Hence, $\sum_{\widetilde{S}\in\mathcal{F}} |\widetilde{S}|\leq 2^{2k-2}q_k\leq 2^{\mu_1-1}$ as desired.

Recall by we find a family $\mathcal{F}\subset \mathcal{S}_{\mu_1,\mu_2}$ such that $\widetilde{T}\subset \bigcup_{\widetilde{S}\in \mathcal{F}}\widetilde{S}$ and $\sum_{\widetilde{S}\in \mathcal{F}} |\widetilde{S}|\leq 2^{\mu_1-1}|\widetilde{T}|$, i.e. $|\mathcal{F}|\leq 2^{\mu_1k-1}$. By , we conclude that $$\begin{aligned}
g(T)&\leq \sum_{\widetilde{S}\in\mathcal{F}} g(S)\\
&\leq\sum_{\widetilde{S}\in\mathcal{F}}  \left[2^{-\mu_1 k} g(T)+\left(\frac{1}{2^k-1}+ \mu_22^{-k}\right)d_k'(T)+(2^{2k+6}+\mu_22^{5k})\min\{n_i\}^{-1}|B|\right]\\
&\leq 2^{\mu_1k-1}\left[2^{-\mu_1 k} g(T)+\left(\frac{1}{2^k-1}+ \mu_22^{-k}\right)d_k'(T)+(2^{2k+6}+\mu_22^{5k})\min\{n_i\}^{-1}|B|\right]\end{aligned}$$ Hence as $d_k'(T)=-g^{\square}(T+T)+2^kg(T)$, we have $$g^\square(T+T)\leq \left(2^{k}-\frac{2^{-\mu_1k}}{\frac{1}{2^k-1} +\mu_22^{-k}}\right)g(T)+ \frac{2^{2k+6}+\mu_22^{5k}}{\frac{1}{2^k-1}+ \mu_22^{-k}}\min\{n_i\}^{-1}|B|.$$

### $A_\star$ is close to ${\operatorname{co}}(A_\star)$: Construction {#AstarclosetocoAstarsubsection}

In this section we prove that $|{\operatorname{co}}(A_\star)\setminus A_\star||B|^{-1}\to 0$ as $\delta \to 0$.

\[AstarclosetocoAstarprop\] We have for some function $h_{\star}(\delta) \rightarrow 0$ as $\delta \rightarrow 0$ that $|{\operatorname{co}}(A_\star) \setminus A_\star| \le h_{\star}(\delta) |B|$.

By ,,, and by , , and , we have that $$\begin{aligned}
 2^k|{\operatorname{co}}(A_\star) \setminus A_\star|\le& d_k(A_\star) -d_k({\operatorname{co}}(A_\star))+ |{\operatorname{co}}(A_\star+A_\star) \setminus (A_\star+A_\star)| \\
\le&  h_9(\delta)|B| +2^{2k}n_k(\epsilon_0,\delta)^{-1}|B|+h_{11}(\delta)|B|\\
&+\sum_{T^+}\sum_{x\in (T^++T^+)}g_{T^+}^{+\square}(x)
+\sum_{T^-}\sum_{x\in (T^-+T^-)}g_{T^-}^{-\square}(x)\\
\le& h_9(\delta)|B| + 2^{2k}n_k(\epsilon_0,\delta)^{-1}|B|+h_{11}(\delta)|B|\\
&+\binom{H_7(\delta^{\frac{1}{20}-17c})}{k}c_k''n_k(\delta,\epsilon_0)^{-1}|B|\\&+(2^k-c_k')\left(\sum_{T^+}\sum_{x\in T^+}g^+_{T^+}(x)+\sum_{T^-}\sum_{x \in T^-}g^-_{T^-}(x)\right)\\
\le& h_9(\delta)|B| + 2^{2k}n_k(\epsilon_0,\delta)^{-1}|B|+h_{11}(\delta)|B|\\
&+\binom{H_7(\delta^{\frac{1}{20}-17c})}{k}c_k''n_k(\delta,\epsilon_0)^{-1}|B|+ (2^k-c_k') |{\operatorname{co}}(A_\star) \setminus A_\star|
\\&+ (2^k-c_k') h_{10}(\delta)|B|  \end{aligned}$$

We conclude that $|{\operatorname{co}}(A_\star) \setminus A_\star| \le h_{\star}(\delta) |B|$, for a function $h_{\star} \rightarrow 0$ as $\delta \rightarrow 0$.

$A$ is close to ${\operatorname{co}}(A)$ {#AclosetocoA}
----------------------------------------

Recall that we have $d_k(A)\le \delta|B|, |A|\ge \epsilon_0|B|$, and for some functions $h_8,h_9,h_\star\to 0$ as $\delta\to 0$ that $$|{\operatorname{co}}(A_\star)\setminus A_\star|\le h_\star(\delta)|B|\text{, }\quad |A\Delta A_\star|\le h_8(\delta)|B|\text{, and}\quad d_k(A_\star)\le h_9(\delta)|B|.$$

We will now show that $|{\operatorname{co}}(A)\setminus A|\le h(\delta)|B|$ for some function $h\to 0$ as $\delta \to 0$.

\[closestarlem\] Given a polytope $\widetilde{Q}$ and $\lambda>0$, let $o$ be the barycenter of the largest volume simplex $\widetilde{T}\subset\widetilde{Q}$. If $p\not \in (1+\lambda)\widetilde{Q}$, then there is a subpolytope $\widetilde{P}\subset \widetilde{Q}$ with $|\widetilde{P}|= \left(\frac{\lambda}{2k^2}\right)^k|\widetilde{Q}|$ such that $$\frac{\widetilde{P}+p}{2}\cap\widetilde{Q}=\emptyset.$$

We may assume $p\in \partial (1+\lambda)\widetilde{Q}$, and that $\widetilde{T}$ is regular with inradius $1$, with $o$ at the origin. Then $$\widetilde{T}\subset \widetilde{Q}\subset -k\widetilde{T},$$ and we estimate the diameter of $\widetilde{Q}$ is strictly less than $2k^2$, as this is an upper bound for the side length of $-k\widetilde{T}$ (as the distance from a vertex to $o$ is $k^2$). Also, note that the distance $s$ from $o$ to $\partial \widetilde{Q}$ is at least $1$, the inradius of $\widetilde{T}$. Let $q=op\cap \partial \widetilde{Q}$, let $H$ be the homothety with center $q$ and ratio $\frac{\lambda}{2k^2}$, and let $\widetilde{P}=H(\widetilde{Q})$. Clearly $\widetilde{P}$ has the desired volume, and has diameter strictly less than $\lambda$. Let $H'$ be the homothety with center $q$ and ratio $-\frac{\lambda}{2}$. Then $H'(\widetilde{Q})$ and $\widetilde{Q}$ are separated by the supporting hyperplane at the point $q$. It is enough to show that $\frac{\widetilde{P}+p}{2}$ is contained in the interior of $H'(\widetilde{Q})$.

Note that the distance from $H'(o)$ to $\partial H'(\widetilde{Q})$ is at least $\frac{\lambda}{2}$. As $\frac{\widetilde{P}+p}{2}$ is a set of diameter strictly less than $\frac{\lambda}{2}$ containing $H'(o)=\frac{p+q}{2}$, it is contained in the interior of $H'(\widetilde{Q})$ as desired.

Note that $|{\widetilde{\operatorname{co}}}(A_\star)|\ge \frac{\epsilon_0}{2}|B|$ by . Let $\widetilde{T}\subset {\widetilde{\operatorname{co}}}(A_\star)$ be the largest volume simplex, and let $o$ be its barycenter. Consider the homothety $H$ with center $o$ and ratio $1+\lambda(\delta)$ where $\lambda(\delta)$ is a function which goes to $0$ as $\delta \to 0$ which will be chosen later. Let $\widetilde{R}=H({\widetilde{\operatorname{co}}}(A_{\star}))$. We will show now that $A\subset \widetilde{R}$. Indeed, suppose not, let $x \in A\setminus \widetilde{R}$. Then by , there is a subset $\widetilde{P}\subset {\widetilde{\operatorname{co}}}(A_\star)$ with volume $(\frac{\lambda}{2k^2})^k|{\widetilde{\operatorname{co}}}(A_\star)|$ such that $\widetilde{P}+x$ is disjoint from $2{\widetilde{\operatorname{co}}}(A_\star)$. Then, by and , $$\begin{aligned}
|A+A| &\ge |x+(\widetilde{P}\cap A_\star)|+|A_\star+A_\star|\\&\ge|x+(\widetilde{P}\cap {\operatorname{co}}(A_\star))|-h_{\star}(\delta)|B|+2^k|A_\star|-d_k(A_\star)\\
&\ge|\widetilde{P}\cap \mathbb{Z}^k|-h_{\star}(\delta)|B|+ 2^k(|A|-h_8(\delta)|B|)-h_{9}(\delta)|B|\\
&\geq|\widetilde{P}|+2^k|A|-h_{12}(\delta)|B|\\
&\ge \left(\frac{\lambda}{2k^2}\right)^k|{\widetilde{\operatorname{co}}}(A_\star)|+2^k|A|-h_{12}(\delta)|B|\\
&\ge 2^k|A|+\left(\frac{\epsilon_0}{2}\left(\frac{\lambda}{2k^2}\right)^k-h_{12}(\delta)\right)|B|.\end{aligned}$$ where $h_{12}(\delta)$ is a function with $h_{12}(\delta)\ge 2^kh_8(\delta)+h_\star(\delta)+ 2k(k+1)n_k(\epsilon_0,\delta)^{-1}$. Hence, $$\delta |B|\ge d_k(A)\ge \left(\frac{\epsilon_0}{2}\left(\frac{\lambda}{2k^2}\right)^k-h_{12}(\delta)\right)|B|.$$ Choosing $\lambda(\delta)$ such that $\frac{\epsilon_0}{2}(\frac{\lambda}{2k^2})^k-h_{12}(\delta)>\delta$ for all sufficiently small $\delta$ yields the desired contradiction. Therefore $A\subset (1+\lambda){\widetilde{\operatorname{co}}}(A_\star)$, so ${\widetilde{\operatorname{co}}}(A)\subset (1+\lambda){\widetilde{\operatorname{co}}}(A_\star)$. Hence by , $$\begin{aligned}
|{\operatorname{co}}(A)|&\le (1+\lambda)^k|{\operatorname{co}}(A_\star)|+(1+(1+\lambda)^k)2k(k+1)n_k(\epsilon_0,\delta)^{-1}|B|\\
&\le (1+2\lambda)^k|{\operatorname{co}}(A_\star)|\\
&\le |{\operatorname{co}}(A_\star)|+((1+2\lambda)^k-1)|B|\\
&\le |A_\star|+((1+2\lambda)^k-1+h_\star(\delta))|B|\\
&\le |A|+(h_8(\delta)+(1+2\lambda)^k-1+h_\star(\delta))|B|.\end{aligned}$$ Defining $\omega(\epsilon_0,\delta)=h_8(\delta)+(1+2\lambda)^k-1+h_\star(\delta)$, we have $$|{\operatorname{co}}(A)\setminus A|\le \omega(\epsilon_0,\delta)|B|$$ with $\omega(\epsilon_0,\delta)\to 0$ as $\delta \to 0$ for any fixed $\epsilon_0>0$.

Proof of b) for $k$ given for $k$ {#quantfromqualsection}
=================================

To prove b), we first prove the following closely related proposition.

\[quantprop\] There are constants $c_k$ (we can take $c_k=(4k)^{5k}$), $f_k$ and $\rho_k(\epsilon_0),n_k(\epsilon_0)$ for all $\epsilon_0>0$ such that the following is true. For every box $B=B(n_1,\ldots,n_k)$ with $n_1,\ldots,n_k \ge n_k(\epsilon_0)$, and for $A'\subset B$ a reduced set with $|A'|\ge \epsilon_0|B|$, $|{\operatorname{co}}(A')\setminus A'|\le \rho_k(\epsilon_0)|A'|$, and a triangulation $\mathcal{T}$ of $\partial{\widetilde{\operatorname{co}}}(A')$, we have that $$|{\operatorname{co}}(A')\setminus A'|\le c_{k}d_k(A')+f_k|\mathcal{T}|\min\{n_i\}^{-1}|B|.$$

We will see that this result follows from the following result.

\[magicprop\] There are constants $c^1_k,c^2_k,\eta_k>0$ (we can take $c^1_k\leq 2^{2k}(2k)^{5k}$) such that the following is true. For every box $B=B(n_1,\ldots,n_k)$ and for $\widetilde{T}\subset \widetilde{B}$ a simplex with vertices $o=x_0,x_1,\ldots,x_k$, and $A\subset T=\widetilde{T}\cap \mathbb{Z}^k$ with $\{o,x_1,\ldots,x_k\}\subset A$ we have $$|(T\setminus (1-\eta_k)\widetilde{T})\setminus A|\le \frac{1}{2}|T\setminus A|+c_k^1d_k(A)+c^2_k\min\{n_i\}^{-1}|B|.$$

We shall write $A_S:=A\cap S$.

Recall in , which recursively constructs a family of simplices $\mathcal{S}_{i,j}(\widetilde{T})$ such that $\mathcal{S}_{0,0}=\{\widetilde{T}\}$, $\mathcal{S}_{i,0}$ are the averages of a vertex in $V(T)$ with a simplex in $\mathcal{S}_{i-1,0}$, and $\mathcal{S}_{i,j}$ are the averages of two simplices in $\mathcal{S}_{i,j-1}$.

For $x$ a vertex of $\widetilde{T}$ and $\widetilde{S}=(1-2^{-i})x+2^{-i}\widetilde{T} \in \mathcal{S}_{i,0}$ and $\widetilde{S}'=\frac{1}{2}(x+\widetilde{S}) \in \mathcal{S}_{i+1,0}$, we have $$|A_{S'}| \ge 2^{-k}|A_{ S}|-2^{-k}d_k(A)-2^k\min\{n_i\}^{-1}|B|.$$

By , with $\widetilde{S}'^c$ the complement of $\widetilde{S}'$ in $\widetilde{T}$, $$\begin{aligned}
d_k(A)=|A+A|-2^k|A|&= |(A+A)\cap 2\widetilde{S'}|-2^k|A_{S'}|+|(A+A)\cap 2\widetilde{S'}^c|-2^k|A_{S'^c}|\\
&\ge |(A+A)\cap 2\widetilde{S'}|-2^k|A_{S'}|+|A_{S'^c}+A_{S'^c}|-2^k|A_{S'^c}|\\
&\ge |x+A_{S}|-2^k|A_{S'}|-2^{2k}\min\{n_i\}^{-1}|B|\\
&=|A_{S}|-2^k|A_{S'}|-2^{2k}\min\{n_i\}^{-1}|B|.\end{aligned}$$

For $\widetilde{S}\in \mathcal{S}_{i,0}$ we have $$|A_{S}| \ge 2^{-ik}|A|-\frac{1-2^{-ik}}{2^k-1}d_k(A)-2^{k+1}\min\{n_i\}^{-1}|B|.$$

For $\widetilde{S}_1, \widetilde{S}_2\in \mathcal{S}_{i,j}$, and $\widetilde{S}'=\frac{1}{2}(\widetilde{S}_1+\widetilde{S}_2)\in \mathcal{S}_{i,j+1}$, we have $$|A_{S'}| \ge \min(|A_{S_1}|,|A_{S_2}|)-2^{-k}d_k(A)-(k+2)2^{k}\min\{n_i\}^{-1}|B|.$$

Let $\widetilde{P}_1,\ldots,\widetilde{P}_{k+1}$ be a partition of $\widetilde{S}'^c$ into convex sets as in the proof of . Then by , we have $$\begin{aligned}
d_k(A)&=|A+A|-2^k|A|\\
&= |(A+A)\cap 2\widetilde{S'}|-2^k|A_{S'}|+|(A+A)\cap 2\widetilde{S'}^c|-2^k|A_{S'^c}|\\
&\ge|A_{S_1}+A_{S_2}|-2^k|A_{S'}|+\sum_{i=1}^{k+1}|A_{\widetilde{P}_i}+A_{\widetilde{P}_i}|-2^k|A_{\widetilde{P}_i}|\\
&\ge 2^k(\min(|A_{S_1}|,|A_{S_2}|)-2^k|A_{S'}|-(k+2)2^{2k}\min\{n_i\}^{-1}|B|.\end{aligned}$$

\[FinalAScor\] For $\widetilde{S}\in \mathcal{S}_{i,j}$ we have $$\begin{aligned}
|A_{S}|&\ge 2^{-ik}|A|-\left(\frac{1-2^{-ik}}{2^k-1}+j2^{-k}\right)d_k(A)-\left(2^{k+1}+j(k+2)2^{k}\right)\min\{n_i\}^{-1}|B|.\end{aligned}$$ In particular, by applied to $S$ and $T$, we have $$|S\setminus A_{S}|\leq 2^{-ik}|T\setminus A|+c^{1}_{i,j}d_k(A)+c^{2}_{i,j}\min\{n_i\}^{-1}|B|,$$ with $c^{1}_{i,j}=\frac{1-2^{-ik}}{2^k-1}+j2^{-k}$ and $c^{2}_{i,j}=(1+2^{-ik})2k(k+1)+2^{k+1}+j(k+2)2^{k}$.

Let $i=\left\lceil\log_{\frac12}\left(\frac{k^{1/k}}{(2k)^5}\right)\right\rceil$ and $j=16k\log(2k)$. Let $c_k^1=(2k)^{5k}c^1_{i,j}\leq 2^{2k}(2k)^{5k}$ and $c_k^2=(2k)^{5k}c_{i,j}^2$ where $c^1_{i,j}$ and $c^2_{i,j}$ are as in . By [@HomoBM Claim 4.2], there exists a constant $\eta_k$ and a family of simplices $\mathcal{F}\subset \mathcal{S}_{i,j}$ with $|\mathcal{F}|\leq (2k)^{5k}$ with $$\sum_{\widetilde{S}\in \mathcal{F}}|\widetilde{S}|\le \frac{1}{2}|\widetilde{T}|,$$ and $$\widetilde{T}\setminus (1-\eta_k)\widetilde{T}\subset \bigcup \mathcal{F}.$$ We prove with parameters $c_k^1,c_k^2, \eta_k$ as above. Noting that $2^{-ik}=\frac{|\widetilde{S}|}{|\widetilde{T}|}$, we have $$\begin{aligned}
    |(T\setminus A)\setminus (1-\eta_k)\widetilde{T}|&\le \sum_{\widetilde{S}\in \mathcal{F}}|S\setminus A_{S}|\\
    &\le \sum_{\widetilde{S}\in \mathcal{F}}\left(2^{-ik}|T\setminus A|+c^1_{i,j}d_k(A)+c^2_{i,j}\min\{n_i\}^{-1}|B|\right)\\
    &\le \frac{1}{2}|T\setminus A|+c_{k}^1d_k(A)+c_{k}^2\min\{n_i\}^{-1}|B|.\end{aligned}$$

We fix $\eta_k$ as in . We need one final lemma to prove .

\[containedheart\] For every $\epsilon_0>0$, there exists a constant $\rho_k(\epsilon_0)>0$ such that if $A'\subset B$ with $|A'|\ge \epsilon_0|B|$, $|{\operatorname{co}}(A')\setminus A'|\le \rho_k(\epsilon_0)|B|$, then there exists $o\in\mathbb{Z}^k$, such that (scaling with respect to $o$ and recalling we take $\eta_k$ as in ) we have $$(1-\eta_k){\widetilde{\operatorname{co}}}(A'+A')\cap \mathbb{Z}^k\subset A'+A'.$$

By , $|{\widetilde{\operatorname{co}}}(A')|\geq \left(\epsilon_0-2k(k+1) \min\{n_i\}^{-1}\right)|B|\ge \frac{\epsilon_0}{2}|B|$, so by John’s Lemma [@John], there exists an ellipsoid $\widetilde{F'}\subset {\widetilde{\operatorname{co}}}(A')$ with $|\widetilde{F'}|\geq k^{-k}\frac{\epsilon_0}{2}|B|$. Let $o'$ be the centre of this ellipsoid $\widetilde{F'}$. Let $o\in\mathbb{Z}^k$ be a point closest to $o'$ and let $p\in\partial \widetilde{F'}$ be the intersection of the ray $o'o$ with $\partial\widetilde{F'}$. Let $H'$ be the homothety centred at $p$ with ratio $\frac{|op|}{|o'p|}\geq 1-\frac{\sqrt{k}}{|o'p|}$, so that $H'(o')=o$. If $|o'p|\le 2\sqrt{k}$, then as the cross-sectional area of $\widetilde{F}'$ perpendicular to $o'p$ is at most $|\partial {\widetilde{\operatorname{co}}}(B)|$, we see that $|\widetilde{F}'|\le 2\sqrt{k}|\partial{\widetilde{\operatorname{co}}}(B)|<k^{-k}\frac{\epsilon_0}{2}|B|$, a contradiction. Hence $\widetilde{F}=H'(\widetilde{F'})\subset {\widetilde{\operatorname{co}}}(A')$ is an ellipse with center $o$ and $|\widetilde{F}|\ge(2k)^{-k}\frac{\epsilon_0}{2}|B|$. Taking a point $x'\in(1-\eta_k){\widetilde{\operatorname{co}}}(A'+A')\cap \mathbb{Z}^k$, our goal is to show that $x'\in A'+A'$.

Let $x=\frac{1}{2}(x'+o)\in \mathbb{R}^k$, and let $y$ be the intersection of the ray $ox$ with $\partial {\widetilde{\operatorname{co}}}(A')$. Note that the ratio $r=|xy|/|oy| \ge \eta_k$. Let $H$ be the homothety with center $y$ and ratio $r$. This homothety sends $o$ to $x$ and ${\widetilde{\operatorname{co}}}(A')$ to $H({\widetilde{\operatorname{co}}}(A'))$. Note that $H({\widetilde{\operatorname{co}}}(A')) \subset {\widetilde{\operatorname{co}}}(A')$ because ${\widetilde{\operatorname{co}}}(A')$ is convex. Note that $H(\widetilde{F})$ is symmetric around $o$ and satisfies $|H(\widetilde{F})|= r^k |\widetilde{F}|$. By , $$|H(\widetilde{F})\cap \mathbb{Z}^k|\geq r^k |\widetilde{F}|-2k(k+1) \min\{n_i\}^{-1}|B|\ge \eta_k^k(2k)^{-k}\frac{\epsilon_0}{4}|B|> 2\rho_k(\epsilon_0).$$ for $\rho_k(\epsilon_0)$ sufficiently small. In particular, as $H(\widetilde{F})\subset{\widetilde{\operatorname{co}}}(A')$, $$\begin{aligned}
    |H(\widetilde{F})\cap A'|&\geq |H(\widetilde{F})\cap \mathbb{Z}^k|-|{\operatorname{co}}(A')\setminus A'|> \frac{1}{2}|H(\widetilde{F})\cap \mathbb{Z}^k|.\end{aligned}$$ By the symmetry of $H(\widetilde{F})$ around $x$, we have that $z\in H(\widetilde{F})\cap \mathbb{Z}^k$ implies that also $x'-z \in H(\widetilde{F})\cap \mathbb{Z}^k$. Hence, as $H(\widetilde{F})\cap A'$ contains more than half the elements in $H(\widetilde{F})\cap \mathbb{Z}^k$, we can find $z,z'\in H(\widetilde{F})\cap A'$, such that $x'=z+z'$ and thus $x'\in A'+A'$.

Let $c_k=2c_k^1+2^{1-k}\leq (4k)^{5k}$ and $f_k=(2(k+1)(\frac{1}{2}+2^kc_k^1)+8k(k+1)+2^{k+1}+2c_k^2+(2+2^{1-k})2k(k+1)$. Let $o$ be the point supplied by . Note that as $o+A'\subset A'+A'$, we find $d_k(A'\cup\{o\})\leq d_k(A')$ and $|{\operatorname{co}}(A'\cup\{o\})\setminus (A'\cup\{o\})|\geq |{\operatorname{co}}(A')\setminus A'|-1 $, so we may assume $o\in A'$. Let $\mathcal{T}'$ be a triangulation of ${\widetilde{\operatorname{co}}}(A)$ obtained by coning off the simplices in $\mathcal{T}$ at $o$, so in particular $|\mathcal{T}|=|\mathcal{T}'|$. For each $\widetilde{T}\in \mathcal{T}'$ all vertices are in $A$. By , we have $$\begin{aligned}
|{\operatorname{co}}(A+A)\setminus (A+A)| &\le \sum_{\widetilde{T}\in \mathcal{T}'}|{\operatorname{co}}(T+T)\setminus(A+A)|\\
&= \sum_{\widetilde{T}\in\mathcal{T}'}|({\operatorname{co}}(T+T)\setminus (A+A))\setminus (1-\eta_k)2\widetilde{T}|\\
&\le \sum_{\widetilde{T}\in\mathcal{T}'}|(2\widetilde{T}\setminus (1-\eta_k)2\widetilde{T})\cap \mathbb{Z}^k)\setminus (A_{\widetilde{T}\setminus (1-\eta_k)\widetilde{T}}+A_{\widetilde{T}\setminus (1-\eta_k)\widetilde{T}})|\\
&\le\sum_{\widetilde{T}\in \mathcal{T}'}|(2\widetilde{T}\setminus (1-\eta_k)2\widetilde{T})\cap \mathbb{Z}^k|-|A_{\widetilde{T}\setminus (1-\eta_k)\widetilde{T}}+A_{\widetilde{T}\setminus (1-\eta_k)\widetilde{T}}|.\end{aligned}$$ By , , and , this is $$\begin{aligned}
\le& \sum_{\widetilde{T}\in\mathcal{T}'}\left(|2\widetilde{T}\setminus(1-\eta_k)2\widetilde{T}|-2^k|A_{\widetilde{T}\setminus (1-\eta_k)\widetilde{T}}|+(2^{k}2k(k+1)+2^{2k})\min\{n_i\}^{-1}|B|\right)\\
=&2^k\sum_{\widetilde{T}\in \mathcal{T}'}\left(|\widetilde{T}\setminus(1-\eta_k)\widetilde{T}|-|A_{\widetilde{T}\setminus (1-\eta_k)\widetilde{T}}|\right)+|\mathcal{T}|(2^{k+1}k(k+1)+2^{2k})\min\{n_i\}^{-1}|B|\\
\le& 2^k\sum_{\widetilde{T}\in \mathcal{T}'}\left(|(T\setminus A)\setminus (1-\eta_k)\widetilde{T}|\right)+|\mathcal{T}|(2^{k+2}k(k+1)+2^{2k})\min\{n_i\}^{-1}|B|.\\
\le& 2^{k}\sum_{\widetilde{T}\in \mathcal{T}'}\left(\frac{1}{2}|T\setminus A| + c_k^1d_k(A\cap T)\right)+|\mathcal{T}|(2^{k+2}k(k+1)+2^{2k}+2^kc_k^2)\min\{n_i\}^{-1}|B|\\
\le& 2^{k-1}|{\operatorname{co}}(A)\setminus A|+2^kc_k^1d_k(A)\\&+|\mathcal{T}|\left(2^k(k+1)\left(\frac{1}{2}+2^kc_k^1\right)+2^{k+2}k(k+1)+2^{2k}+2^kc_k^2\right)\min\{n_i\}^{-1}|B|.\end{aligned}$$ Hence as $d_k(A)=|A+A|-2^k|A|$ and $2^k| {\operatorname{co}}(A)|-|{\operatorname{co}}(A+A)|\le (2^k+1)2k(k+1)\min\{n_i\}^{-1}|B|$ by , we conclude $$\begin{aligned}
|{\operatorname{co}}(A)\setminus A|\le& (2c_k^1+2^{1-k})d_k(A)\\
&+|\mathcal{T}|\left(2(k+1)\left(\frac{1}{2}+2^kc_k^1\right)+8k(k+1)+2^{k+1}+2c_k^2+(2+2^{1-k})2k(k+1)\right)\\&\quad\min\{n_i\}^{-1}|B|\\
=&c_kd_k(A)+f_k|\mathcal{T}|\min\{n_i\}^{-1}|B|\end{aligned}$$

Let $\alpha=\min\{n_i\}^{-\gamma}$ with $\gamma=\frac{1}{1+\frac{1}{2}(k-1)\lfloor k/2 \rfloor}$ and $\ell=\tau_{k}\alpha^{-\frac{k-1}{2}}$ with $\tau_{k}$ as in . Note that this $\gamma$ satisfies $-\gamma=\frac{k-1}{2}\lfloor k/2 \rfloor \gamma-1$.

Take $\Delta_k(\epsilon_0)$ sufficiently small so that by , we have $|{\operatorname{co}}(A)\setminus A|\le \rho_k(\frac{\epsilon_0}{2})|B|$ where $\rho_k$ is the constant from . By , we find a subset $A'\subset A$ such that $|{\operatorname{co}}(A)\setminus {\operatorname{co}}(A')|\le \alpha |B|$ and $A'=A\cap {\operatorname{co}}(A')$ such that ${\operatorname{co}}(A')$ has at most $\ell$ vertices. In particular, we have $|A\setminus A'|\le \alpha  |B|$. By , we have $d_k(A')\le 2^k\alpha |B|+d_k(A)$.

Now, by Stanley’s resolution of the upper bound conjecture [@Stanley], as $\partial{\widetilde{\operatorname{co}}}(A')$ is a combinatorial sphere with $\ell$ vertices, if we take a triangulation $\mathcal{T}$ of $\partial {\widetilde{\operatorname{co}}}(A')$ we have $|\mathcal{T}|\le f_k'\ell^{\lfloor k/2 \rfloor}=f_k'\tau_{k-1}\alpha^{-\frac{k-1}{2}\lfloor k/2\rfloor}$ for some constant $f_k'$. By applied to $A'={\operatorname{co}}(A')\cap A\subset A$, we thus have $$|{\operatorname{co}}(A')\setminus A'|\le c_k(2^k\alpha  |B|+d_k(A))+\alpha^{-\frac{k-1}{2}\lfloor k/2\rfloor}f_k'\tau_{k}f_k\min\{n_i\}^{-1}|B|.$$ Thus, dropping , provided that $\min\{n_i\}$ is bounded from below by a function of $k,\epsilon_0$ given by and , we get as $-\gamma=\frac{k-1}{2}\lfloor k/2 \rfloor \gamma-1$ that $$\begin{aligned}
|{\operatorname{co}}(A)\setminus A|&\le c_k(2^k+1)\alpha |B|+c_kd_k(A)+\alpha^{-\frac{k-1}{2}\lfloor k/2 \rfloor}f_k'\min\{n_i\}^{-1}|B|\\
&\leq c_kd_k(A)+g_k\min\{n_i\}^{-\frac{1}{1+\frac{1}{2}(k-1)\lfloor k/2 \rfloor}}|A|.\end{aligned}$$ By taking $g_k=g_k(\epsilon_0)$ sufficiently large in terms of $\epsilon_0$ we can guarantee that the above inequality actually holds for any choice of $\{n_i\}$, which concludes the proof.

Proving a) {#1.1asection}
==========

We will now prove a). To do this, we will need the following special case of the main result of Green and Tao [@GreenTao].

\[GTspecialcase\] There exist constants $w_k$ such that for any $A\subset \mathbb{Z}^k$ with $d_k(A)\le |A|$, there exists a generalized arithmetic progression $P$ of dimension at most $k$ and size at most $|A|$, along with vectors $x_1,\ldots,x_{w_k}$ such that $$A\subset \bigcup_{i=1}^{w_k}P+x_i.$$

We apply , obtaining a generalized arithmetic progression $P$ and $x_1,\ldots,x_{w_k}\in \mathbb{Z}^k$ such that $A\subset \bigcup_{i=1}^{w_k}P+x_i$. Take $n_k^0$ to be a large threshold, chosen later. If $P$ is contained inside a hyperplane, then $A$ is covered by $w_k$ parallel hyperplanes and we are done. Similarly, if one of the side lengths of $P$ is at most $n_k^0$, then we can cover $P$ by $n_k^0$ parallel hyperplanes, so $A$ can be covered by $w_kn_k^0$ parallel hyperplanes. Therefore, we may assume that $$P=B(n_1,\ldots,n_k;v_1,\ldots,v_k;0)$$ is non-degenerate and $n_i\ge n_k^0$ for all $i$. By applying a linear transformation from $GL_k(\mathbb{Q})$ taking $v_i$ to the standard basis vectors $e_i$ and then scaling up to clear denominators, we may assume that $v_i=be_i$, where $b\in \mathbb{N}$.

\[clm5.2\] There exist a factor $b'$ of $b$ such that $b'\ge w_k!^{-w_k} b$ and the following holds. If we consider the decomposition $$A=A_1\sqcup \ldots \sqcup A_r$$ associated to the cosets $y_1,\ldots,y_r\in (
\mathbb{Z}/b'\mathbb{Z})^k$, then after possibly relabeling we have $|A_1|\ge |A_j|$ for all $j$, and for every $p\ne 1$ there exists $j_p \ne 1$ such that $$y_p+y_{j_p}\ne y_1+y_k$$ for $k\in \{1,\ldots,r\}$.

Set $b_{0}'=b$, and $y_{1,0},\ldots,y_{r_0,0}\in (\mathbb{Z}/b_{0}'\mathbb{Z})^k=( \mathbb{Z}/b\mathbb{Z})^k$ the distinct representatives of $A$, or equivalently the distinct representatives of $x_1,\ldots,x_{w_k}$. We note that in particular, this implies that $r_0\le w_k$.

We recursively construct factors $b_{j+1}'$ of $b_{j}'$ with $b_{j+1}'\ge w_k!^{-1} b_{j}'$ such that if $y_{1,j},\ldots,y_{r_j,j}\in ( \mathbb{Z}/(b'_{j}\mathbb{Z})^k$ are the distinct representatives of $A$, then the following is true. If we consider the associated coset decomposition $$A=A_{1,j}\sqcup \ldots \sqcup A_{r_j,j},$$ possibly relabeling so that $|A_{1,j}|\ge |A_{p,j}|$ for $1 \le p \le r_j$, then either for every $p\ne 1$ there exists a $\lambda(p,j)\ne 1$ such that $$y_{p,j}+y_{\lambda(p,j),j}\ne y_{1,j}+y_{\ell,j}$$ for $1 \le \ell \le r_j$, or else we have $r_{j+1}<r_j$.

Suppose that $y_{p,j}$ does not have the property that there exists $\lambda(p,j)$ such that $y_{p,j}+y_{\lambda(p,j),j}\ne y_{1,j}+y_{\ell,j}$ for all $\ell$. This is equivalent to saying that $y_{p,j}$ has the property that for all $\lambda$, there is an $\ell$ such that $(y_{p,j} - y_{1,j})+ (y_{\lambda,j} -y_{1,j})= y_{\ell,j}-y_{1,j}$. Then the cyclic group generated by $y_{p,j}-y_{1,j}$ lies entirely inside $\{0,y_{2,j}-y_{1,j},\ldots,y_{r_j,j}-y_{1,j}\}$, so has order at most $r_j \le w_k$. Setting $b_{j+1}=b_{j}/\gcd(b_{j},w_k!)$, we obtain that $y_{p,j}-y_{1,j}=0$ in $( \mathbb{Z}/b_{j+1}\mathbb{Z})^k$, so $r_{j+1}<r_j$.

As $r_j$ can decrease at most $w_k$ times from $r_0\le w_k$, there exists a $j\le w_k$ for which $r_j=r_{j+1}$. Taking $j_p=\lambda(p,j)$, $b'=b_{j}$ and $y_p=y_{p,j}$ the distinct representatives of $A$ in $(\mathbb{Z}/b_{j}\mathbb{Z})^k=(\mathbb{Z}/b'\mathbb{Z})^k$, we obtain the desired result.

Returning to the proof of a), let $P'=B(n_1,\ldots,n_k;b'e_1,\ldots,b'e_k;0)$ where $b'$ is furnished by . Let $w_k'=w_k \cdot w_k!^{k\cdot w_k}$, and $x_1',\ldots,x_{w_k'}'$ be translation vectors such that $$A\subset \bigcup_{i=1}^{w_k'}P'+x_i'.$$ Also note that $|P'|\le |A|$.

\[clm5.3\] There exists an $x$ such that $A\subset x+(b'\mathbb{Z})^k$.

Before we begin the proof of the claim we need the following lemma.

\[error\] For $X,Y\subset A$, then $$|X+Y|\ge 2^k\min(|X|,|Y|)-2^{2k}(w_k'n_k^0)^{-1}w_k'^k|A|.$$

Let $C(X),C(Y)$ be obtained by compressing $X,Y$ in each of the coordinate directions. Then $C(X),C(Y)$ are contained in the down-set $C(A)\subset C(\bigcup P'+x_i')$, which in turn is contained inside a box of side lengths $w_k'n_1,\ldots,w_k'n_k\ge w_k'n_k^0$, which has volume at most $w_k'^k\prod n_i \le w_k'^k|A|$. Therefore by [@GreenTao], we obtain $$|X+Y|\ge |C(X)+C(Y)|\ge 2^k\min(|X|,|Y|)-2^{2k}(w_k'n_k^0)^{-1}w_k'^k|A|.$$

Let $$A=A_1\sqcup \ldots \sqcup A_r$$ be the coset decomposition as in the claim with $|A_1|$ maximal, and $r \le w_k'$. We want to show that $r=1$.

We have for any $p\ne 1$ that $$\begin{aligned}
|A+A|&\ge |A_p+A_{j_p}|+\sum_i|A_1+A_i|\\
&\ge |A_p|+\sum_{i=1}^r (2^k|A_i|-2^{2k}(w_k'n_k^0)^{-1}w_k'^k|A|)\\
&\ge |A_p|+2^k|A|-2^{2k}(n_k^0)^{-1}w_k'^k|A|\end{aligned}$$ so averaging over all $p\ne 1$ we obtain $$\begin{aligned}
\label{5.3first}d_k(A)\ge \frac{1}{w_k'-1}|A\setminus A_1|-2^{2k}(n_k^0)^{-1}w_k'^k|A|.\end{aligned}$$ On the other hand, assuming $r \ge 2$ we have $$|A+A|\ge |A_1+A_2|+|A_1+A_1| \ge |A_1|+2^k|A_1|-2^{2k}(w_k'n_k^0)^{-1}w_k'^{k}|A|$$ so $$\begin{aligned}
\label{5.3second}d_k(A)\ge |A|-(2^k+1)|A\setminus A_1|-2^{2k}(w_k'n_k^0)^{-1}w_k'^k|A|.\end{aligned}$$ Adding $(w_k'-1)(2^k+1)$ of to , and using $\Delta_k|A| \ge d_k(A)$, we obtain $$((w_k'-1)(2^k+1)+1)\Delta_k|A| \ge |A| - ((w_k'-1)(2^k+1)+w_k'^{-1})2^{2k}(n_k^0)^{-1}w_k'^k|A|,$$ which gives the desired contradiction provided $\Delta_k$ is sufficiently small and $n_k^0$ is sufficiently large.

Returning to the proof of a), after translating $A$ we can assume that $A\subset (b'\mathbb{Z})^k$, so we may scale down and assume that $b'=1$.

We now show that the boxes are in some sense “near” each other.

There exists a universal constant $f_k$ so that for $P''=B(f_kn_1,\dots,f_kn_k;e_1,\dots,e_k;0)$ we have that $A\subset P''+x$ for some $x$.

Recall that $x_1',\ldots,x_{w_k'}'$ are the translation vectors for $P'=B(n_1,\dots,n_k;e_1,\dots,e_k;0)$ which cover $A$. Suppose that $|A\cap (P'+x_1)|$ is maximal, so $|A\cap (P'+x_1)|\ge \frac{1}{w_k'}|A|$. Let $A_1=A\cap (P'+x_1)$.

We first show that the width in the $j$-direction is bounded by a fixed multiple of $n_j$ for each $j$. So fix a $j$ and let $\pi_j$ be the projection in the $j$th coordinate. For a subset $\mathcal{B}\subset \{1,\ldots,w_k'\}$, let $h_j(\mathcal{B})$ be the difference between the largest and smallest values in $\{\pi_j(x_i')\}_{i\in \mathcal{B}}$. Suppose we have a set $\mathcal{B}\subset \{1,\ldots,w_k'\}$ containing $1$. If $\mathcal{B}$ is not the whole set and there is no $i \not \in \mathcal{B}$ such that $h_j(\mathcal{B}\cup \{i\})\le 100h_j(\mathcal{B})+100n_j$, then taking $\mathcal{B}'$ to be either $\{x_\ell': \pi_j(x_\ell')\ge \min \{\pi_j(x_i')\}_{i \in \mathcal{B}}\}$ or $\{x_\ell': \pi_j(x_\ell')\le \max \{\pi_j(x_i')\}_{i \in \mathcal{B}}\}$ (whichever has $\mathcal{B}'^c$ non-empty), then the sets $$Z_1=\bigcup_{i \in \mathcal{B}'} P'+x_i',\quad Z_2=\bigcup_{i\in (\mathcal{B}')^c}P+x_i'$$ have the following property. Let $z$ be the closest point of $Z_2\cap A$ in the $e_j$-direction to $Z_1$. Then by considering the projections under $\pi_j$, the sets $$(Z_1\cap A)+(Z_1\cap A),(Z_2\cap A)+(Z_2\cap A),z+A_1$$ are disjoint. By applied to these sets we obtain $$\begin{aligned}
|A+A|&\ge |(Z_1\cap A)+(Z_1\cap A)|+|(Z_2\cap A)+(Z_2\cap A)|+|z+A_1|\\
&\ge 2^k|Z_1\cap A|+2^k|Z_2\cap A|+|A_1|-2^{2k+1}(w_k'n_k^0)^{-1} w_k'^k|A|\\
&\ge 2^k|A|+\frac{1}{w_k'}|A|-2^{2k+1}(w_k'n_k^0)^{-1} w_k'^k|A|,\end{aligned}$$ a contradiction provided $\Delta_k$ is sufficiently small and $n^0_k$ sufficiently large. Hence, if $\mathcal{B}$ is not the whole set $\{1,\dots,w_k'\}$, then there is an $i\not\in \mathcal{B}$ such that $h_j(\mathcal{B}\cup\{i\})\leq 100h_j(\mathcal{B})+100n_j$.

Start with $\mathcal{B}=\{1\}$ and $h_j(\{1\})=0$. Repeatedly applying this, we see that $h_j(\{1,\ldots,w_k'\})\le f_k n_j-1$ for some universal integer constant $f_k\leq 101^{w_k'}$, independent of $j$.

We deduce there is a translate $x$ such that $P'+x_i'\subset f_kP'+x$ for all $i$.

Returning to the proof of a), taking $\epsilon_k\leq f_k^{-k}$, then as $|P'|\le |A|$ we find $A$ is a set of density at least $\epsilon_k$ inside the generalised arithmetic progression $f_kP'+x$.

Proof of and  {#appendixproofs}
=============

Decorate constants from with a dash to distinguish them from constants with the same name in .

Let $\Delta_k=\min\{\Delta_k',\Delta'_k(\epsilon_k')\}$ as given by . Let $c_k=c_k'+\frac12 ((4k)^{5k}-c_k')$, and $m_k(\delta)=\max\left\{m_k',\left(\frac{2g'_k(\epsilon'_k)\delta^{-1}}{(4k)^5k-c'_k}\right)^{1+\frac12(k-1)\lfloor k/2\rfloor}=\left(\frac{g'_k(\epsilon'_k)\delta^{-1}}{c_k-c_k'}\right)^{1+\frac12(k-1)\lfloor k/2\rfloor}\right\}$.

As $d_k(A)\leq \delta |A|\leq \Delta_k' |A|$, by a), either $A$ is covered by $m_k'\leq m_k(\delta)$ parallel hyperplanes, or there is some generalized arithmetic progression $B=B(n_1,\dots,n_k;v_1,\dots,v_k;b)$ with the $v_i$ linearly independent, $A\subset B$ and $|A|\geq \epsilon_k'|B|$.

If $n_i\leq m_k(\delta)$ for some $i$, then $B$ (and thus also $A$) is covered by $n_i\leq m_k(\delta)$ parallel hyperplanes. Hence, we may assume $\min\{n_i\}\geq m_k(\delta)$.

As $d_k(A)\leq \Delta'_k(\epsilon'_k)$, $A$ and $B$ satisfy the conditions of b), so that $$\begin{aligned}
|{\widehat{\operatorname{co}}}(A)\setminus A|&\leq c_k'd_k(A)+g'_k(\epsilon'_k)\min\{n_i\}^{-\frac{1}{1+\frac{1}{2}(k-1)\lfloor k/2 \rfloor}}|A|\\
&\leq c'_k \delta |A|+g'_k(\epsilon'_k)m_k(\delta)^{-\frac{1}{1+\frac{1}{2}(k-1)\lfloor k/2 \rfloor}}|A|\\
&= c_k \delta |A|.\end{aligned}$$ That concludes the proof.

Let $m_k(\delta),\Delta_k',c_k'$ be the constants from . Let $(4k)^{5k}>c_k>c_k'$ be any constant and $\Delta_k\le \frac{c_k'}{c_k}\Delta_k'$. By standard approximations (see e.g. [@Semisum p.3 footnote 2]) we may assume that $\widetilde{A}$ is a finite union of positive measure convex polytopes, and $\widetilde{A}$ satisfies the condition $|\widetilde{A}+\widetilde{A}| \le (2^k+\Delta_k)|\widetilde{A}|$ from . Define $\delta=\frac{|\widetilde{A}+\widetilde{A}|-2^k|\widetilde{A}|}{|\widetilde{A}|}$.

Let $N\in \mathbb{N}$, let $A_N=(\frac{1}{N}\mathbb{Z})^k\cap \widetilde{A}$, and let $(A+A)_N=(\frac{1}{N}\mathbb{Z})^k\cap (\widetilde{A}+\widetilde{A})$. Note that for each $r\in \mathbb{N}$, $A_N$ contains a translate of the combinatorial box $B(r,\ldots,r)$ for $N$ sufficiently large. In particular, this implies $A_N$ is reduced.

As $N \to \infty$ we have $\frac{1}{N^k}|A_N| \to |\widetilde{A}|$, $\frac{1}{N^k}|{\operatorname{co}}(A_N)|\to |{\widetilde{\operatorname{co}}}(\widetilde{A})|$, and $\frac{1}{N^k}|(A+A)_N|\to |\widetilde{A}+\widetilde{A}|$. Thus for $N$ sufficiently large $\frac{1}{N^k}d_k(A_N) \le \frac{1}{N^k}(|(A+A)_N|-2^k|A_N|)\le\frac{1}{N^k}\frac{c_k}{c_k'}\delta |A_N|$, so $$d_k(A_N)\le \frac{c_k}{c_k'}\delta |A_N|\le \frac{c_k}{c_k'}\Delta_k|A_N|\le\Delta_k'|A_N|.$$ By , the number of hyperplanes needed to cover $A_N$ is larger than $m_k(\frac{c_k}{c_k'}\delta)$ for $N$ sufficiently large. Therefore by , we have $|{\operatorname{co}}(A_N)\setminus A_N| \le c_k' (\frac{c_k}{c_k'}\delta)|A_N|=c_k\delta|A_N|$ for $N$ sufficiently large. Dividing by $N^k$ and taking the limit as $N\to \infty$ of both sides yields $$|{\operatorname{co}}(\widetilde{A})\setminus \widetilde{A}| \le c_k |\widetilde{A}|.$$
