% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages %\usepackage{cleveref} \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf New upper bound for sums of dilates} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{ Albert Bush \qquad Yi Zhao\thanks{Partially supported by NSF grant DMS-1400073.}\\ \small Department of Mathematics and Statistics\\[-0.8ex] \small Georgia State University\\[-0.8ex] \small Atlanta, GA 30303\\ \small\tt albertbush@gmail.com \qquad yzhao6@gsu.edu } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Nov 1, 2016}{Jul 6, 2017}\\ \small Mathematics Subject Classifications: 11P70, 11B13, 05C70} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} For $\lambda \in \mathbb{Z}$, let $\lambda \cdot A = \{ \lambda a : a \in A\}$. Suppose $r, h\in \mathbb{Z}$ are sufficiently large and comparable to each other. We prove that if $|A+A| \le K |A|$ and $\lambda_1, \ldots, \lambda_h \le 2^r$, then \[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \le K^{ 7 rh /\ln (r+h) } |A|. \] This improves upon a result of Bukh who shows that \[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \le K^{O(rh)} |A|. \] Our main technique is to combine Bukh's idea of considering the binary expansion of $\lambda_i$ with a result on biclique decompositions of bipartite graphs. % keywords are optional \bigskip\noindent \textbf{Keywords:} sumsets; dilates; Pl\"unnecke--Ruzsa inequality; graph decomposition; biclique partition \end{abstract} \section{Introduction} Let $A$ and $B$ be nonempty subsets of an abelian group, and define the \emph{sumset} of $A$ and $B$ and the \emph{$h$-fold sumset} of $A$ as \begin{align*}A+B := \{ a + b: a \in A, b \in B\} \text{\hspace{3px} and \hspace{3px}} hA := \{ a_1 + \ldots + a_h: a_i \in A\}, \end{align*} respectively. When the set $A$ is implicitly understood, we will reserve the letter $K$ to denote the doubling constant of $A$; that is, $K := |A+A|/|A|$. A classical result of Pl\"unnecke bounds the cardinality of $hA$ in terms of $K$ and $|A|$. \begin{theorem}[Pl\"unnecke's inequality \cite{plu70}]\label{plunnecke} For any set $A$ and for any nonnegative integers $\ell$ and $m$, if $|A+A| = K |A|$, then \[ |\ell A - m A| \le K^{\ell + m} |A|. \] \end{theorem} \noindent See the survey of Ruzsa \cite{ruz09} for variations, generalizations, and a graph theoretic proof of Theorem \ref{plunnecke}; see Petridis \cite{pet12} for a new inductive proof. Given $\lambda \in \mathbb{Z}$, define a \emph{dilate} of $A$ as \begin{align*}\lambda \cdot A := \{ \lambda a: a \in A\}. \end{align*} %Throughout the paper, Suppose $\lambda_1 , \ldots , \lambda_h$ are nonzero integers. Since $\lambda_i \cdot A \subseteq \lambda_i A$, one can apply Theorem \ref{plunnecke} to conclude that \begin{align*}|\lambda_1 \cdot A + \ldots + \lambda_h \cdot A| \le K^{\sum_i |\lambda_i|}|A|. \end{align*} Bukh \cite{buk08} significantly improved this by considering the binary expansion of $\lambda_i$ and using Ruzsa's covering lemma and triangle inequality. % \text{\quad and \quad} s := \sum_{i=1}^h \sum_{j=0}^r \lambda_{i,j}. %\end{align} \begin{theorem}[Bukh \cite{buk08}]\label{buk08} For any set $A$, if $\lambda_1 , \ldots , \lambda_h \in \mathbb{Z}\setminus \{0\}$ and $|A+A| = K|A|$, then \[ | \lambda_1 \cdot A + \ldots + \lambda_h \cdot A| \le K^{7 + 12 \sum_{i=1}^h \log_2 (1+ |\lambda_i|)}|A|. \] \end{theorem} %For a cleaner, but less precise bound, one can use the trivial observation that $\sum_{j=0}^r \lambda_{i,j} \le \log_2 (1 + |\lambda_i|)$ to ascertain that If $|\lambda_i| \le 2^r$ for all $i$, %Since $\log_2 (1+|\lambda_i|) \le r+1$, then Theorem \ref{buk08} yields that \begin{align}\label{logbound} | \lambda_1 \cdot A + \ldots + \lambda_h \cdot A| \le K^{O(rh)}|A|. \end{align} In this paper we prove a bound %is subquadratic in the exponent which is an improvement to Theorem \ref{buk08} that improves \eqref{logbound} when $r$ and $h$ are sufficiently large and comparable to each other. Throughout the paper $ln$ stands for the natural logarithm. \begin{theorem}\label{mainthm} Suppose $r, h \in \mathbb{Z}$ are sufficiently large and \begin{equation} \label{eq:mn} \min \{r+1, h\} \ge 10 \left(\ln \max\{r+1, h\} \right)^2. \end{equation} Given a set $A$ and nonzero integers $\lambda_1, \ldots, \lambda_h$ such that $|\lambda_i| \le 2^r$, if $|A+A| = K|A|$, then \begin{equation} \label{eq:main} | \lambda_1 \cdot A + \ldots + \lambda_h \cdot A| \le K^{7 rh/ \ln (r+h)} |A|. \end{equation} \end{theorem} The proof of Theorem \ref{mainthm} relies on Theorem \ref{buk08} as well as a result of Tuza~\cite{Tuza84} on decomposing bipartite graphs into bicliques (complete bipartite subgraphs). The key idea is to connect Bukh's technique of considering the binary expansion of $\lambda_i$ to the graph decomposition problem that allows us to efficiently group certain powers of 2. We remark here that in all of the above theorems, the condition $|A+A| = K|A|$ can be replaced with $|A-A| = K|A|$ with no change to the conclusion. %As mentioned in \cite{buk08}, the constants in Theorem \ref{buk08} (and consequently the relationship of $\eps$ to $r+h$ in Theorem \ref{mainthm}) are not optimal, and we make no effort to optimize them here. It is likely that Theorem \ref{mainthm} is not best possible -- we discuss this in the last section. %We will use $\log$ for $\log_2$ in the rest of the paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%% BASIC TOOLS %%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Basic Tools} We need the following analogue of Ruzsa's triangle inequality, see \cite[Theorem 1.8.7]{ruz09}. %we will refer to by the same name. \begin{theorem}[Ruzsa \cite{ruz09}] \label{ruzsatriangle} For any sets $X, Y,$ and $Z$, \[ | X + Y| \le \frac{|X+Z||Z+Y|}{|Z|}. \] \end{theorem} A useful corollary of Theorem~\ref{ruzsatriangle} is as follows. \begin{corollary} \label{easyobs} For any sets $A$ and $B$, if $p_1$ and $p_2$ are nonnegative integers and $|A+A| \le K|A|$, then \[ |B + p_1 A - p_2 A| \le K^{p_1 + p_2 + 1}|B + A|. \] \end{corollary} \begin{proof} Apply Theorem \ref{ruzsatriangle} with $X = B$, $Y = p_1 A - p_2 A$, and $Z = A$, then apply Pl\"unnecke's inequality (Theorem \ref{plunnecke}). \end{proof} We can use Corollary~\ref{easyobs} to prove the following proposition that we will use in the proof of Theorem \ref{mainthm}. \begin{proposition}\label{easyobsgen} %For any positive integer $q$, If $k_1, \ell_1, \ldots , k_q , \ell_q$ are nonnegative integers, $K> 0$, and $A_1, \ldots , A_q, C$ are sets such that $|A_i + A_i| \le K|A_i|$, then \begin{equation}\label{withc} |C + k_1 A_1 - \ell_1 A_1 + \ldots + k_q A_q - \ell_q A_q| \le |C + A_1 + \ldots + A_q| \cdot K^{q + \sum_{i=1}^q (k_i + \ell_i)}. \end{equation} In particular, \begin{equation}\label{withoutc} |k_1 A_1 - \ell_1 A_1 + \ldots + k_q A_q - \ell_q A_q| \le |A_1 + \ldots + A_q| \cdot K^{q + \sum_{i=1}^q (k_i + \ell_i)}. \end{equation} \end{proposition} \begin{proof} \eqref{withoutc} follows from \eqref{withc} by taking $C$ to be a set with a single element so it suffices to prove \eqref{withc}. We proceed by induction on $q$. The case $q = 1$ follows from Corollary~\ref{easyobs} immediately. When $q > 1$, suppose the statement holds for any positive integer less than $q$. Applying Corollary~\ref{easyobs} with $B = C + k_1 A_1 - \ell_1 A_1 + \ldots + k_{q-1} A_{q-1} - \ell_{q-1} A_{q-1}$ and $A = A_q$, we obtain that \begin{align}\label{stage1} & \hspace{5px} | C + k_1 A_1 - \ell_1 A_1 + \ldots + k_q A_q - \ell_q A_q| \nonumber \\ \le & \hspace{5px} K^{k_q + \ell_q + 1} |C + k_1 A_1 -\ell_1 A_1 + \ldots + k_{q-1} A_{q-1} - \ell_{q-1} A_{q-1} + A_q|. \end{align} Now, let $C' = C + A_q$ and apply the induction hypothesis to conclude that \begin{align}\label{stage2} & \hspace{5px} |C' + k_1 A_1 - \ell_1 A_1 + \ldots + k_{q-1} A_{q-1} - \ell_{q-1} A_{q-1}| \nonumber \\ \le & \hspace{5px}|C' + A_1 + \ldots + A_{q-1}| \cdot K^{q-1 + \sum_{i=1}^{q-1} (k_i + \ell_i)} \end{align} Combining \eqref{stage1} with \eqref{stage2} gives the desired inequality: \begin{equation} |C + k_1 A_1 - \ell_1 A_1 + \ldots + k_q A_q - \ell_q A_q| \le |C + A_1 + \ldots + A_q| \cdot K^{q + \sum_{i=1}^q (k_i + \ell_i)}. \qedhere \nonumber \end{equation} \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% PROOF OF MAIN THEOREM %%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem \ref{mainthm}} Given $\lambda_1, \ldots , \lambda_h \in \mathbb{Z} \setminus \{0\}$, we define \begin{align}\label{rands} r := \max_i \lfloor \log_2 |\lambda_i| \rfloor \end{align} and write the binary expansion of $\lambda_i$ as \begin{align}\label{lambda}\lambda_i = \epsilon_i \sum_{j=0}^r \lambda_{i,j} 2^j \text{, where $\lambda_{i,j} \in \{0,1\}$ and $\epsilon_i \in \{-1, 1\}$}. \end{align} Bukh's proof of Theorem \ref{buk08} actually gives the following stronger statement. %which we will use in the proof of Theorem \ref{mainthm}. \begin{theorem}[\cite{buk08}] \label{binbound} If $\lambda_1, \ldots , \lambda_h \in \mathbb{Z} \setminus \{0\}$ and $|A+A| = K|A|$, then \begin{align*}| \lambda_1 \cdot A + \ldots + \lambda_h \cdot A| \le K^{7 + 10r + 2 \sum_i \sum_j \lambda_{i,j} }|A|. \end{align*} \end{theorem} In his proof of Theorem \ref{buk08}, the first step is to observe that \[ \lambda_1 \cdot A + \ldots + \lambda_h \cdot A \subseteq \sum_{j=0}^r (\lambda_{1,j} 2^j) \cdot A + \ldots + \sum_{j=0}^r (\lambda_{h,j} 2^j) \cdot A. \] In our proof, we also consider the binary expansion of $\lambda_i$, but we do the above step more efficiently by first grouping together $\lambda_i$ that have shared binary digits. In order to do this systematically, we view the problem as a graph theoretic problem and apply the following result of Tuza~\cite{Tuza84}. \begin{theorem}[Tuza~\cite{Tuza84}]\label{ces} There exists $n_0$ such that the following holds for any integers $m\ge n \ge n_0$ such that $n\ge 10 (\ln m) ^2 $. Every bipartite graph $G$ on two parts of size $m$ and $n$ can be decomposed into edge-disjoint complete bipartite subgraphs $H_1, \ldots , H_q$ such that $E(G) = \cup_{i} E(H_i)$ and \begin{equation} \label{eq:Tuza} \sum_{i=1}^q |V(H_i)| \le \frac{3mn}{\ln m}. \end{equation} \end{theorem} Tuza stated this result \cite[Theorem 4]{Tuza84} for the \emph{covers} of $G$, where a \emph{cover} of $G$ is a collection of subgraphs of $G$ such that every edge of $G$ is contained in at least one of these subgraphs. However, the cover provided in his proof is indeed a decomposition. Furthermore, the assumption $n\ge 10 (\ln m) ^2 $ was not stated in \cite[Theorem 4]{Tuza84} but such kind of assumption is needed.\footnote{In his proof, copies of $K_{q, q}$ were repeatedly removed from $G$, where $q= \lfloor \ln m/ \ln j\rfloor$ for $2\le j\le (\ln m)\ln\ln m$. By a well-known bound on the Zarankiewicz problem, every bipartite graph $G$ with parts of size $m$ and $n$ contains a copy of $K_{q, q}$ if $|E(G| \ge (q-1)^{1/q} (n-q+1) m^{1-1/q} + (q-1)m$. A simplified bound $|E(G| \ge (1+ o(1)) n m^{1-1/q}$ was used in \cite{Tuza84} but it requires that $q m^{1/q} = o(n)$.} Indeed, \eqref{eq:Tuza} becomes false when $n= o(\ln m)$ because $\sum_{i=1}^q |V(H_i)| \ge m+ n$ for any cover $H_1, \ldots , H_q$ of $G$ if $G$ has no isolated vertices. Note that \eqref{eq:Tuza} is tight up to a constant factor. Indeed, Tuza~\cite{Tuza84} provided a bipartite graph $G$ with two parts of size $n\le m$ such that every biclique \emph{cover} $H_1, \ldots , H_q$ of $G$ satisfies $\sum_{i=1}^q |V(H_i)| \ge mn/ (e^2\ln m)$, where $e= 2.718...$. \begin{proof}[Proof of Theorem \ref{mainthm}] Let $r, h\in \mathbb{Z}$ be sufficiently large and satisfy \eqref{eq:mn}. Given nonzero integers $\lambda_1, \ldots , \lambda_h$, define $r$ and $\lambda_{i,j}$ as in \eqref{rands} and \eqref{lambda}. We define a bipartite graph $G = (X,Y,E)$ as follows: let $X = \{ \lambda_1, \ldots , \lambda_h\}$, $Y = \{ 2^0, \ldots , 2^r \}$, and $E = \{ (\lambda_i, 2^j): \lambda_{i,j} = 1 \}$. In other words, $\lambda_i$ is connected to the powers of 2 that are present in its binary expansion. We apply Theorem \ref{ces} to $G$ and obtain a biclique decomposition $H_1, \ldots , H_q$ of $G$. %That is, $\mathcal{H}$ is a set of edge-disjoint complete bipartite graphs whose union covers the edge set of $G$. Assume $H_i := (X_i, Y_i, E_i)$ where $X_i \subseteq X$, $Y_i \subseteq Y$. We have $E_i = \{ (u,v): u\in X_i, v\in Y_i\}$ and \begin{align}\label{concl} \sum_{i=1}^q \left(|X_i| + |Y_i| \right)\le \frac{ 3 (r+1)h }{\ln \max\{r+1, h\} }. \end{align} Now, we connect this biclique decomposition to the sum of dilates $\lambda_1 \cdot A + \ldots + \lambda_h \cdot A$. Since the elements of $X$ and $Y$ are integers, we can perform arithmetic operations with them. For $j=1, \ldots , q$, let \[ \gamma_j := \sum_{y \in Y_j} y, \] and since $\mathcal{H}$ is a biclique decomposition, for $i = 1, \ldots , h$, we have \[ \lambda_i = \epsilon_i \sum_{j: \lambda_i \in X_j} \gamma_j .\] Applying the above to each $\lambda_i$ along with the fact that $B + (\alpha + \beta) \cdot A \subseteq B + \alpha \cdot A + \beta \cdot A$ results in \begin{align}\label{reversesummation} \lambda_1 \cdot A + \ldots + \lambda_h \cdot A \subseteq \epsilon_1 \sum_{j: \lambda_1 \in X_j} (\gamma_j \cdot A) + \ldots + \epsilon_h \sum_{j: \lambda_h \in X_j} (\gamma_j \cdot A). \end{align} Let $k_j := | \{ \lambda_i \in X_j : \lambda_i > 0 \}|$, $\ell_j := |\{ \lambda_i \in X_j: \lambda_i < 0\}|$, and note that $k_j + \ell_j = |X_j|$. By regrouping the terms in \eqref{reversesummation}, we have \begin{align*} & \hspace{5px}\epsilon_1 \sum_{j: \lambda_1 \in X_j} \gamma_j \cdot A + \ldots + \epsilon_h \sum_{j: \lambda_h \in X_j} \gamma_j \cdot A \\ = & \hspace{5px} k_1 ( \gamma_1 \cdot A ) - \ell_1 (\gamma_1 \cdot A) + \ldots + k_q ( \gamma_q \cdot A) - \ell_q (\gamma_q \cdot A) . \end{align*} Since $|\gamma_j \cdot A + \gamma_j \cdot A| = |A+A| \le K|A| = K| \gamma_j \cdot A |$, we can apply Proposition~\ref{easyobsgen} to conclude that \begin{align}\label{stp1} \nonumber & \hspace{5px}|k_1 ( \gamma_1 \cdot A ) - \ell_1 (\gamma_1 \cdot A) + \ldots + k_q ( \gamma_q \cdot A) - \ell_q (\gamma_q \cdot A)| \\ \le & \hspace{5px}|\gamma_1 \cdot A + \ldots + \gamma_q \cdot A| \cdot K^{q + \sum_{i=1}^q k_i + \ell_i} \le |\gamma_1 \cdot A + \ldots + \gamma_q \cdot A| \cdot K^{2\sum_{i=1}^q |X_i|}. \end{align} For $1\le i\le q$ and $0\le j\le r$, let $\gamma_{i,j} = 1$ if $2^j$ is in the binary expansion of $\gamma_i$ and $0$ otherwise. Observe that \[ \max_j \lfloor \log_2 \gamma_j \rfloor \le \max_i \lfloor \log_2 |\lambda_i| \rfloor = r \text{\hspace{5px} and \hspace{5px}} \sum_{j=0}^r \gamma_{i,j} = |Y_i|. \] Hence, by Theorem \ref{binbound}, \begin{align}\label{stp2} |\gamma_1 \cdot A + \ldots + \gamma_q \cdot A| \le K^{7 + 10r + 2 \sum_{i=1}^q \sum_{j=0}^r \gamma_{i,j}} |A| = K^{7 + 10r + 2 \sum_{i=1}^q |Y_i|} |A|. \end{align} Combining \eqref{stp1} and \eqref{stp2} with \eqref{concl} results in \[ | \lambda_1 \cdot A + \ldots + \lambda_h \cdot A| \le K^{7 + 10r + 2 \sum_{i=1}^q (|X_i|+|Y_i|)} |A| \le K^{7 + 10r + \frac{6(r+1)h}{\ln \max\{ r+1, h\} } } |A|. \] We have $7+10r = o( (r+1)h/ \ln \max\{ r+1, h \} )$ because of \eqref{eq:mn} and the assumption that $r, h$ are sufficiently large. %$\log \max\{r+1, h\}\to \infty$. Together with \[ \ln \max\{r+1, h\}\ge \ln \frac{r+1+h}2 \ge (1- o(1)) \ln (r+h), \] this implies that $ | \lambda_1 \cdot A + \ldots + \lambda_h \cdot A| \le K^{ 7rh / \ln (r+h) } |A|$, as desired. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%% CONCLUSION %%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Concluding Remarks} %\begin{itemize}[leftmargin=*] %\item Instead of Theorem~\ref{ces}, in an earlier version of the paper we applied a result of Chung, Erd\H{o}s, and Spencer \cite{chuerdspe83}, which states that every graph on $n$ vertices has a biclique decomposition $H_1, \ldots , H_q$ such that $\sum_{i=1}^q |V(H_i)| \le (1+o(1)) n^2/ (2\ln n)$. Instead of \eqref{eq:main}, we obtained that \[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \le K^{O((r+h)^2/\ln (r+h) ) } |A|. \] This bound is equivalent to \eqref{eq:main} when $r=\Theta(h)$ but weaker than Bukh's bound \eqref{logbound} when $r$ and $h$ are not close to each other. %\item Although the assumption \eqref{eq:mn} may not be optimal, Theorem~\ref{mainthm} is not true without any assumption on $r$ and $h$. For example, when $r$ is large and $h=o(\ln r)$, \eqref{eq:main} becomes $|\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \le K^{ o(r ) } |A|$, which is false when $A= \{1, \dots, n\}$. %\item %Bukh commented that having a bound that depended on the number of binary digits in each $\lambda_i$ (as in \ref{binbound}) is, for various reasons, unnatural. If each of $\lambda_1, \dots, \lambda_r$ has $O(1)$ digits in its binary expansion, then Theorem~\ref{buk08} yields that $|\lambda_1 \cdot A + \ldots + \lambda_r \cdot A| \le K^{O(r)}|A|$. Bukh asked if this bound holds whenever $\lambda_i \le 2^r$: \begin{question}[Bukh \cite{buk08}]\label{bukhconj} For any set $A$ and for any $\lambda_1 , \ldots , \lambda_r \in \mathbb{Z} \setminus \{0\}$, if $|A+A| = K|A|$ and $0 < \lambda_i \le 2^r$, then \[ | \lambda_1 \cdot A + \ldots + \lambda_r \cdot A| \le K^{O(r)}|A|. \] \end{question} \noindent In light of Question~\ref{bukhconj}, one can view Theorem~\ref{mainthm} as providing modest progress by proving a subquadratic bound of quality $O(r^2/\ln r)$ whereas Theorem~\ref{buk08} shows that the exponent is $O(r^2)$. %\item Generalized arithmetic progressions give supporting evidence for Question~\ref{bukhconj}. A \emph{generalized arithmetic progression} $P$ is a set of the form \[ P := \{ d + x_1 d_1 + \ldots + x_k d_k: 0 \le x_i < L_i \}. \] Moreover, $P$ is said to be \emph{proper} if $|P| = L_1 \cdot \ldots \cdot L_k$. One can calculate that if $P$ is proper, then \[ |P+P| \le (2L_i - 1)^k \le 2^k |P| =: K |P|. \] Additionally, one can calculate that for any $\lambda_1, \ldots , \lambda_h \in \mathbb{Z}^+$, if $\lambda_i \le 2^r$ then \[ |\lambda_1 \cdot P + \ldots + \lambda_h \cdot P| \le (\lambda_1 + \ldots + \lambda_h)^k |P| = 2^{k \log_2(\lambda_1 + \ldots + \lambda_h)}|P| = K^{r + \log_2{h}}|P|. \] Freiman's theorem \cite{fre73} says that, roughly speaking, sets with small doubling are contained in generalized arithmetic progressions with bounded dimension. Using this line of reasoning, Schoen and Shkredov \cite[Theorem 6.2]{schshk16} proved that %used a result of Sanders on the Bogolyubov-Ruzsa lemma to prove \[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \le e^{O( \log_2^6 (2K) \log_2\log_2 (4K)) (h + \log_2 \sum_i |\lambda_i| ) }|A|. \] This naturally leads us to ask a more precise version of Question~\ref{bukhconj}. \begin{question} If $|A+A| = K|A|$, then is \[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A| \le K^{O(h+ \ln \sum_i |\lambda_i| ) } |A| ?\] \end{question} %\end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{Acknowledgment} We thank Boris Bukh and Giorgis Petridis for reading an earlier version of this paper and giving valuable comments. We also thank an anonymous referee for suggesting \cite{Tuza84} as well as other helpful comments. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{1} \bibitem{buk08} B.~Bukh. \newblock Sums of dilates. \newblock {\em Combinatorics, Probability and Computing}, 17(05):627--639, 2008. \bibitem{chuerdspe83} F.~Chung, P.~Erd{\H{o}}s, and J.~Spencer. \newblock On the decomposition of graphs into complete bipartite subgraphs. \newblock In {\em Studies in Pure Mathematics}, pages 95--101. Springer, 1983. \bibitem{fre73} G.~A. Fre{\u\i}man. \newblock {\em Foundations of a structural theory of set addition}. \newblock American Mathematical Society, Providence, R. I., 1973. \newblock Translated from the Russian, Translations of Mathematical Monographs, Vol 37. \bibitem{pet12} G.~Petridis. \newblock New proofs of {P}l{\"u}nnecke-type estimates for product sets in groups. \newblock {\em Combinatorica}, 32(6):721--733, 2012. \bibitem{plu70} H.~Pl{\"u}nnecke. \newblock Eine zahlentheoretische anwendung der graphtheorie. \newblock {\em J. Reine Angew. Math.}, 243:171--183, 1970. \bibitem{ruz09} I.~Z. Ruzsa. \newblock Sumsets and structure. \newblock In {\em Combinatorial Number Theory and Additive Group Theory}, pages 87--210, 2009. \bibitem{schshk16} T.~Schoen and I.~D. Shkredov. \newblock Additive dimension and a theorem of {S}anders. \newblock {\em J. Aust. Math. Soc.}, 100(1):124--144, 2016. \bibitem{Tuza84} Z.~Tuza. \newblock Covering of graphs by complete bipartite subgraphs: complexity of {$0$}-{$1$}\ matrices. \newblock {\em Combinatorica}, 4(1):111--116, 1984. \end{thebibliography} \end{document}