On addition of two sets of integers

From MaRDI portal





Let \(A=\{a_1,a_2,\dots,a_k\}\) and \(B=\{b_1,b_2,\dots,b_\ell\}\) be two sets of integers with \(0=a_1<a_2<\cdots <a_k\) and \(0=b_1<b_2<\cdots <b_\ell\). Denote the set \(\{a_i+b_j: 1\leq i\leq k\), \(1\leq j\leq \ell\}\) by \(A+B\). Assume that \(a_k\geq b_\ell\). \textit{G. A. Freiman} [Izv. Vyssh. Uchebn. Zaved. Mat. 1959, No. 6, 202-213 (1959; Zbl 0096.25904)] first considered \(|A+A|\). In [ibid. 1962, No. 3, 151-157 (1962; Zbl 0156.05102)] \textit{G. A. Freiman} further considered \(|A+B|\) and showed that (i) if \(a_k\leq k+\ell-3\), then \(|A+B|\geq a_k+\ell\); (ii) if \(a_k\geq k+\ell-2\) and \((a_1,a_2,\dots,b_\ell)=1\), then \(|A+B|\geq k+\ell+\min\{k,\ell\}-3\). \textit{V. F. Lev} and \textit{P. Y. Smeliansky} [Acta Arith. 70, 85-91 (1995; Zbl 0817.11005)] sharpened this and showed that (use Kneser's theorem) (i) if \(a_k\leq k+\ell-2-\delta\) then \(|A+B|\geq a_k+\ell\); (ii) if \(a_k\geq k+\ell-1-\delta\) and \((a_1,\dots,a_k)=1\), then \(|A+B|\geq k+2\ell-2-\delta\), where \(\delta=1\) if \(b_\ell=a_k\), and \(\delta=0\) if \(b_\ell<a_k\). In the present paper the modular version of the above result is given. Let \(q\) be a positive integer. For any set \(T\) of integers let \(d_T\) denote the greatest common divisor of elements of \(T-\{t\}\), where \(t\in T\), and let \(\overline{T}\) denote the set of residue classes modulo \(q\) having nonempty intersection with \(T\). Suppose that \(A\) is the union of \(A_1,A_2,\dots,A_t\) with \(|\overline{A}_i|=1\) and \(\overline{A}_i\cap \overline{A}_j=\phi\) \((i\neq j)\), and \(B\) is the union of \(B_1,B_2,\dots,B_s\) with \(|\overline{B}_i|=1\) and \(\overline{B}_i\cap \overline{B}_j=\phi\) \((i\neq j)\). The following result is proved. Theorem. (i) if \(q\leq |\overline{A}|+|\overline{B}|-1\), then \[ |A+B|\geq q+|B|+(\max_i|A_i|-2) |\overline{B}|; \] (ii) if \(q\geq |\overline{A}|+|\overline{B}|\) and \((d_A,d_B,q)=1\), then \[ |A+B|\geq \min\{2q/(q,d_A),\;|\overline A|+|\overline B|-1\}+|\overline B|+(\max_i|A_i|-2)|\overline B|. \] For \(q=a_k\) the theorem implies the result of Lev and Smeliansky.











This page was built for publication: On addition of two sets of integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4345824)