MATHEMATICS

G. A. FREIMAN

ON THE ADDITION OF FINITE SETS

(Presented by Academician P. S. Novikov on May 6, 1964)

Notation. \(K=\{a_0,a_1,\ldots,a_{k-1}\};\ a_i\) are integers; \(a_i<a_{i+1}\), \(i=0,1,\ldots,k-2\); \(K+K=2K\) is the set of numbers of the form \(a_i+a_j\), in which identical sums are taken only once; \(T(M)\) is the number of elements of the finite set \(M\); \(T=T(2K)\); \(Z_n\) is the additive group of integer vectors of the Euclidean space \(E_n\); \(A\) is an increasing sequence of nonnegative integers \(a_0=1,a_1,\ldots,a_i,\ldots\); \(A(x), A_2(x)\) are the numbers of terms of the sequence \(A\) (respectively \(2A\)) not exceeding \(x\);

\[ \delta(A)=\lim_{x\to\infty}\frac{A(x)}{x} \]

is the asymptotic density of the sequence \(A\); \(D\) is a set of points in \(E_n\); \(\mu^*(D)\) is the outer measure of the set \(D\).

The following results describe the structure of the finite set \(K\), the sequence \(A\), and the set \(D\) in the case when, respectively, \(T(2K)<Ck\), \(\delta(2A)<C\delta(A)\), and \(\mu^*(2D)<C\mu^*(D)\), where \(C\) is an arbitrary positive constant.

Definition 1. Subsets \(B'\) and \(C'\) of sets \(B\) and \(C\) with an algebraic operation are called isomorphic up to the \(s\)-th degree if the mappings \(B^i\to C^i\), \(2\le i\le s+1\), naturally induced by a one-to-one mapping \(B'\to C'\), are one-to-one.

Theorem 1. Let \(T<Ck,\ C\ge 2,\ k\ge k_0\), where \(k_0\) is a sufficiently large positive number. There exist a homomorphism \(\varphi: Z_n\to Z_1\) and a convex set \(D\subset E_n\) such that:

1) \(K\subset (D\cap Z_n)\varphi\);

2) \(D\cap Z_n\) and \((D\cap Z_n)\varphi\) are isomorphic up to the first degree;

3) \(T(D\cap Z_n)<c_1k,\ c_1=c_1(C)>0\);

4) \(n\le [C-1]\).

Definition 2. The parallelepiped \(\sigma_1\mathbf{x}_1+\sigma_2\mathbf{x}_2+\cdots+\sigma_n\mathbf{x}_n,\ 0\le\sigma_i<1,\ 1\le i\le n\), is called canonical if

\[ (\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_n) = (\mathbf{e}_1,\mathbf{e}_2,\ldots,\mathbf{e}_n) \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1n}\\ x_{22} & \cdots & x_{2n}\\ 0 & \cdots & x_{nn} \end{pmatrix}, \tag{1} \]

where \(x_{ij}\) are natural numbers and \(|x_{ii}|<x_{jj},\ i<j,\ 1\le j\le n\).

For the proof of Theorem 1 we shall need the following two lemmas.

Lemma 1. Let \(T(D\cap Z_n)=V\), where \(D\) is a convex set in \(E_n\). There exist a homomorphism \(\varphi_1: Z_m\to Z_n\), a canonical parallelepiped \(H\subset Z_m\), and a vector \(\mathbf{w}\in Z_n\) such that: 1) \(D\cap Z_n\subset (H\cap Z_m)\varphi_1+\mathbf{w}\), 2) \(V(H)<c_2V,\ c_2=c_2(n)>0\).

Proof. Let \(L\) be a plane of minimal dimension \(r\) containing \(D\cap Z_n\) (\(L\) may coincide with \(E_n\)). Then \(L\cap D=D_1\) is a convex set. There is an integral frame of dimension \(r\) lying in \(D_1\), i.e. there exist vectors \(\mathbf{u},\mathbf{w}_1,\mathbf{w}_2,\ldots,\mathbf{w}_r\) such that \(\mathbf{u},\mathbf{u}+\mathbf{w}_1,\mathbf{u}+\mathbf{w}_2,\ldots,\mathbf{u}+\mathbf{w}_r\subset L\), and the vectors \(\mathbf{w}_1,\mathbf{w}_2,\ldots,\mathbf{w}_r\) are linearly independent. Let \(\mathbf{y}_1=\mathbf{x}_1,\ \mathbf{y}_i\) be an integer point on \(\mathbf{u}+L(\mathbf{w}_1,\mathbf{w}_2,\ldots,\mathbf{w}_i)\), whose distance from \(\mathbf{u}+L(\mathbf{w}_1,\mathbf{w}_2,\ldots,\mathbf{w}_{i-1})\) is positive and minimal \((2\le i\le r)\).

Define the nondegenerate linear transformation \(\varphi_2:E_r\to E_n\) by the relations \(e_i\varphi_2=y_i,\ 1\leq i\leq r\). Let \(D_2=(D_1-u)\varphi_2^{-1}\). Applying Lemma 4 from \((^5)\), we obtain a parallelepiped \(H_1\supset D_2\), whose edges can be represented in the form (1), \(x_{ij}\geq 1\). Since a convex body containing only one integral point has volume not exceeding \(2^n\) (Minkowski’s theorem, (1), p. 184), we have \(V(H_1)<c_3V(D_2)=c_3V(D_3)\leq 2^n c_3V\).

There exist a canonical parallelepiped \(H\), a homomorphism \(\varphi_3:E_r\to E_r\), and an integral point \(v\), for which
\[ H_1\cap Z_r\subset (H\cap Z_r)\varphi_3+v,\qquad V(H)\leq 2^r V(H_1). \]
Then \(\varphi_1=\varphi_3^{-1}\varphi_2,\ w=u+v\varphi_2\).

Lemma 2. Let \(\overline K\subset Z_n,\ T(2\overline K)<Ck,\ C\geq 2,\ \overline K\subset D\subset E_n\), where \(D\) is a convex set for which \(T(D\cap Z_n)=V\). There exist a homomorphism \(\varphi_4:Z_m\to Z_n\), a convex set \(D_1\subset E_m\), and a set \(K'\subset \overline K\), for which
\[ T(K')>\varepsilon k,\qquad \varepsilon>0, \]
such that: 1) \(K'\subset (D_1\cap Z_m)\varphi_4;\) 2)
\[ T(D_1\cap Z_m)<c_4V(V/k)^{-c_5},\qquad c_4=c_4(n,C),\quad c_5=c_5(n,C). \]

The arguments needed in order to show that Theorem 1 follows from Lemma 2 are carried out essentially in \((^5)\).

Proof of Theorem 1. From Lemmas 1 and 2 it follows that there exist a homomorphism \(\varphi_5:Z_m\to Z_n\), a canonical parallelepiped \(H\subset E_m\), and a vector \(w\in Z_n\) such that: 1) \(K'\subset (H\cap Z_m)\varphi_5+w\); 2)
\[ V(H)<c_6V(V/k)^{-c_5}. \]

As shown at the end of the proof of Lemma 3 in \((^5)\), one can specify a homomorphism \(\varphi_6:Z_p\to Z_n\), a canonical parallelepiped \(H_1\subset E_p\), and \(w_1\in E_n\) such that: 1) \(\overline K\subset (H_1\cap Z_p)\varphi_6+w_1\), 2)
\[ V(H_1)<c_7V(V/k)^{-c_5}. \]
The proof is completed in the same way as the proof of Theorem 1 in \((^5)\), with the sole difference that, in constructing the sequence \(\{\varphi_i,\ H_i,\ w_i\}\) indicated there, instead of Lemma 3 one uses the just-described construction of \(\varphi_6,\ H_1\), and \(w_1\), carried out with the aid of Lemma 2.

For the proof of Lemma 2 we shall need the following.

Lemma 3. Let \(r\) random variables \(\xi_1,\xi_2,\ldots,\xi_r\) be given, in general dependent, each of which assumes the two values 0 and 1. If
\[ P(\xi_i=0)=\sum_{\substack{u_j=0,1\\ j\ne i\\ u_i=0}} P_{u_1u_2\ldots u_r}\geq \gamma>\frac12,\qquad 1\leq i\leq r, \]
where \(P_{u_1u_2\ldots u_r}=P(\xi_1=u_1,\ \xi_2=u_2,\ldots,\xi_r=u_r)\), then there exists a set of values \(u_1,u_2,\ldots,u_r\) such that
\[ P_{u_1u_2\ldots u_r}\geq c_8\,V^{-r}c_9^r,\qquad \text{where } c_8=c_8(\gamma),\quad c_3=(1-\gamma)^{1-\gamma}\gamma^\gamma>\frac12 . \]

Proof. Let
\[ m=\max_{u_i} P_{u_1u_2\ldots u_r}. \]
Then
\[ \gamma r\leq \sum_{i=1}^r P(\xi_i=0) = \sum_{s=1}^r sP_{u_1u_2\ldots u_r} < s_0m+(s_0-1)C_r^1m+\cdots+1\cdot C_r^{s_0-1}m+r-s_0, \]
\[ +s_0,\qquad \text{where } s_0=[(1-\gamma)r+2]\text{ and }m>1/F,\quad F=C_r^{s_0-1}+2C_r^{s_0-2}+\cdots+s_0. \]
From
\[ C_r^{s_0-1}<c_{10}(\gamma)/V^{-r}c_9^r \]
(see, for example, \((^2)\), p. 245, formula (12)) the validity of the lemma follows.

Proof of Lemma 2. In view of Lemma 1 one may assume that \(D\subset H-w\), where \(H\) is a canonical parallelepiped of volume \(V\), \(w\in Z_n\).

We retain the notation \(W,\ S,\ J_1,\ Q_i,\ H_a,\ J_1',\ h_i\) of the work \((^4)\). Change the quantity \(Q_i\), setting it equal to \(Q_i=h_i/M\), where \(M=(V/k)^{1/4n}\). Define the set \(J_1'\) as follows:
\[ J_1'=\bigcup_{p_i,q_i} H_a,\qquad \text{where }(p_i,q_i)=1,\quad 1\leq i\leq n,\quad 1\leq q_i\leq q_0, \]

\(q_0=M^2\). Then
\[ \operatorname{mes} J_1' \ll \sum \frac{2^n}{q_1q_2\ldots q_n Q_1Q_2\ldots Q_n}\ll \frac{2^n}{V}M^{3n}. \]
Suppose that for some \(\vec a\in \bar J_1'\), \(\vec a\in H_{\mathbf a}\), the inequality
\[ |S(\vec a)|>\frac{1}{\sqrt{C+\varepsilon/2}}\,k,\qquad \varepsilon>0 \]
holds. Since
\[ |(\mathbf z,\mathbf x)|\leq \sum_{i=1}^n |(\mathbf z,\mathbf x_i)| < c_{11}\sum_{i=1}^n \frac{h_i}{q_iQ_i}<c_{11}n\frac1M, \]
we have
\[ |S(\vec a)-S(\mathbf a)|\leq \sum_{\mathbf x\in \bar K}\left|e^{2\pi i(\mathbf z,\mathbf x)}-1\right|\leq c_{12}\frac{k}{M}, \]
whence, for \(k\) sufficiently large, the inequality follows
\[ |S(\mathbf a)|\geq \frac{1}{\sqrt{C+\varepsilon}}\,k. \tag{2} \]

We shall show that one can choose \(\mathbf a_1,\mathbf a_2,\ldots,\mathbf a_r\in \bar J_1\) in such a way that, for any choice of \(n+r\) integers \(A_j\), \(1\leq j\leq n+r\), for which
\[ |A_j|\leq R,\qquad R=(V/k)^{1/3(n+r)},\qquad \sum_{i=n+1}^{n+r} A_j^2>0, \]
for at least one \(i,\ 1\leq i\leq n\), the inequality
\[ \left|A_1x_{1i}+A_2x_{2i}+\cdots+A_nx_{ni}-(\mathbf a_1,\mathbf x_i)A_{n+1}-\cdots-(\mathbf a_r,\mathbf x_i)A_{n+r}\right|\leq g=(V/k)^{1/3n} \tag{3} \]
would fail.

Suppose the points \(\mathbf a_1,\mathbf a_2,\ldots,\mathbf a_{j-1}\) have already been chosen. Put in (3) \(A_i=0\), \(i\geq n+j+1\), \(A_{n+j}=1\). Then
\[ G_{ji}-g\leq (\mathbf a_j,\mathbf x_i)\leq G_{ji}+g, \tag{4} \]
where
\[ G_{ji}=\pm\bigl(A_1x_{1i}+A_2x_{2i}+\cdots+A_nx_{ni}-(\mathbf a_1,\mathbf x_i)A_{n+1}-\cdots-(\mathbf a_{j-1},\mathbf x_i)A_{n+j-1}\bigr). \]
Condition (4) defines a strip perpendicular to \(\mathbf x_i\), of width \(2g/|\mathbf x_i|\); the collection of conditions (4) for all \(i\) is a parallelepiped of volume not exceeding \(c_{13}g^n/V\). All possible combinations of the values \(A_i,\ 1\leq i\leq n+j-1\), determine \((2R+1)^{n+j-1}\) parallelepipeds, whose total volume does not exceed
\[ c_{14}\frac{g^n}{V}R^{n+j-1}. \]
The sum \(U_j\) of the parallelepipeds \(H_{\mathbf a}\) having common points with those constructed has volume not exceeding
\[ c_{15}\frac{g^n}{V}R^{n+j-1}. \]
Since
\[ \operatorname{mes} J_1' + r c_{15}\frac{g^n}{V}R^{n+r-1}<\frac12\,\operatorname{mes} J_1, \]
the choice of \(\mathbf a_j\notin U_j,\ 1\leq j\leq r\), is possible for any finite \(r\).

From inequality (2), with the aid of Lemma 1, it follows from (3) that for \(k_1\) vectors \(\mathbf x\) from \(\bar K\),
\[ \left(k_1>\frac{1+1/\sqrt{C+\varepsilon}}{2}\,k\right), \]
the conditions
\[ \{(\mathbf a,\mathbf x)\}=A_{\mathbf x}+\beta+\theta_{\mathbf x},\qquad 0\leq \theta_{\mathbf x}<\tfrac12, \]
are satisfied, where \(A_{\mathbf x}\) is an integer, \(\beta=P/Q\), \(Q=[q_1,q_2,\ldots,q_n]\). Hence, for \(\mathbf a_i,\ 1\leq i\leq r\), we obtain
\[ \frac{p_{i1}}{q_{i1}}Q_i x_1+\frac{p_{i2}}{q_{i2}}Q_i x_2+\cdots+\frac{p_{in}}{q_{in}}Q_i x_n+Q_i x_{n+i}=P_i+s, \]
\[ 0\leq s<\frac P2,\qquad 1\leq i\leq r. \tag{5} \]
This condition is satisfied for \(k_{1i}\) points of \(\bar K\), while for the remaining \(k_{2i}=k-k_{1i}\) points condition (5) holds with \(P/2\leq s<P\).

Consider the hyperplanes \(L_{i0}, L_{i1}, L_{i2}\subset E_{n+r}\), defined by relation (5) respectively with \(s=0, P/2, P\); \(P_{i0}\) (\(P_{i1}\)) is the strip between \(L_{i0}\) and \(L_{i1}\) (\(L_{i1}\) and \(L_{i2}\)), including \(L_{i0}\) (\(L_{i1}\)); \(N\) is the cylinder bounded by the hyperplanes passing through each of the faces \(H\subset E_n=L(e_1,e_2,\ldots,e_n)\) parallel to \(L(e_{n+1},e_{n+2},\ldots,e_{n+r})\);
\[ H_{u_1u_2\ldots u_r}=\left(\bigcap_{i=1}^r P_{iu_i}\right)\cap N;\qquad H'=\bigcup_{\substack{u_i=0,\ 1\leq i\leq r}} H_{u_1u_2\ldots u_r}. \]

Define \(\varphi_7: Z_{n+r}\to Z_n\) by the relation
\[ (x_1,x_2,\ldots,x_{n+r})\varphi_7=(x_1,x_2,\ldots,x_n). \]
In view of Lemma 3, there exists \(H_{u_1u_2,\ldots,u_r}=H''\) such that
\[ k''T\bigl((H''\cap Z_{n+r})\varphi_7\cap K\bigr)>c_{16}\sqrt{r}\,c_9^r k,\qquad \gamma=\frac{1+1/\sqrt{C}+\varepsilon}{2}. \]
Since, for sufficiently large \(r\),
\[ T\bigl(2(\overline K\varphi_7^{-1}\cap H'')\bigr)<T(2\overline K)<Ck<2^r k'', \]
it follows, in view of Lemma 2 from (5), that there exists a hyperplane \(L_1\subset E_{n+r}\) such that
\[ T\bigl(L_1\cap(K\varphi_7^{-1}\cap H'')\bigr)>\varepsilon k,\qquad \varepsilon>0,\quad \varepsilon=\varepsilon(n,C), \]
and \(L_1\parallel L(e_1,e_2,\ldots,e_n)\). We may suppose that the set of points
\[ L_1\cap H'\cap Z_{n+r} \]
is not contained in a plane having dimension smaller than \(n+r-1\). Consider the set \(G\) of hyperplanes \(L\) parallel to \(L_1\) and passing through integral points.

The area of a fundamental parallelepiped of the lattice in the plane \(L_1\) is equal to \(1/h\), where \(h\) is the distance between two neighboring hyperplanes \(Z\subset G\). Minkowski’s inequality for the product of the successive minima of a convex closed symmetric body of volume
\[ V(V\lambda_1\lambda_2\cdots\lambda_n\le 2^n,\ \text{see (1), p. 187}) \]
shows that in \(L_1\) there exists a fundamental parallelepiped whose edge lengths \(u_1,u_2,\ldots,u_{n+r-1}\) do not exceed \(2^n/h^2\).

The edges of the parallelepiped \(H'\) are equal to
\[ y_i=x_i-(a_1,x_i)e_{n+1}-\cdots-(a_r,x_i)e_{n+r},\quad 1\le i\le n, \]
and to \(e_s,\ n+1\le s\le n+r\). If \(f=\max_i V_i\), where \(V_i\) is the volume of the parallelepiped constructed on \(y_i\) and \(u_1,u_2,\ldots,u_{n+r-1}\), then there exist at least \([f]\) planes \(Z\subset G\) whose intersections with \(H'\) are nonempty. But
\[ V_i= \left\| \begin{matrix} u_{11} & u_{12} & \cdots & u_{1\,n+r}\\ u_{21} & u_{22} & \cdots & u_{2\,n+r}\\ \cdot & \cdot & \cdot & \cdot\\ u_{n+r-1\,1} & u_{n+r-1\,2} & \cdots & u_{n+r-1\,n+r}\\ y_{1i} & y_{2i} & \cdots & y_{n+r\,i} \end{matrix} \right\| = \]
\[ =\left|A_1x_{1i}+A_2x_{2i}+\cdots+A_nx_{ni}-(a_1x_i)A_{n+1}-\cdots-(a^r,x_i)A_{n+r}\right|, \]
where \(|A_i|\le c_{17}h\), and it cannot be that
\[ \sum_{j=n+1}^{n+r} A_j^2=0, \]
since \(L_1\parallel[e_1,e_2,\ldots,e_n]\).

If
\[ h^{-1}\ge c_{18}(V/k)^{c_5},\qquad c_5=1/6\,(n+r)^2, \]
then \([f]\ge g\). If, however,
\[ h^{-1}<c_{18}(V/k)^{c_5}, \]
then for the number \(p\) of nonempty intersections of \(H'\) with \(L\subset G\) the inequality
\[ p>c_{19}(V/k)^{c_5} \]
holds, whence it follows that always
\[ T(H'\cap L_1\cap Z_{n+r})<c_{20}V(V/k)^{-c_5}. \]
Lemma 2 is proved.

From Theorem 1 there immediately follows the following strengthening of the Brunn–Minkowski inequality:

Theorem 2. Let
\[ \mu^*(2D)\le C\mu^*(D),\qquad C\ge 2^n. \]
There exist \(Z_m\to E_n\), a rectangular canonical parallelepiped \(H\), and a convex set \(D_1\) such that:
1) \(D\subset(H\cap Z_m)\varphi+D_1\);
2) \((H\cap Z_m)\times D\subset E_m\times E_n\) is isomorphic to \((H\cap Z_m)\varphi+D_1\);
3) \(T(H\cap Z_n)\mu^*(D_1)<c_{21}\mu^*(D),\quad c_{21}=c_{21}(C,n)\);
4) \(m\le [C-2^n]\).

From Theorem 1 follows the validity of Theorem 4 in (5) for any \(C\ge 1\).

Yelabuga State
Pedagogical Institute

Received
6 V 1964

References

1. J. W. S. Cassels, An Introduction to the Theory of Diophantine Approximation, IL, 1961.
2. S. N. Bernstein, Probability Theory, Moscow–Leningrad, 1946.
3. G. A. Freiman, Izv. Vyssh. Uchebn. Zaved., Mathematics, No. 3 (28), 151 (1962).
4. G. A. Freiman, ibid., No. 3 (40), 156 (1964).
5. G. A. Freiman, ibid., No. 6 (43), 171 (1964).