×

New upper bound for sums of dilates. (English) Zbl 1407.11118

Summary: 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| \leq K |A|\) and \(\lambda_1, \ldots, \lambda_h \leq 2^r\), then \[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \leq K^{7rh/\ln(r+h)} |A|. \] This improves upon a result of Bukh who shows that \[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \leq 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.

MSC:

11P70 Inverse problems of additive number theory, including sumsets
11B13 Additive bases, including sumsets
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] B. Bukh. Sums of dilates. Combinatorics, Probability and Computing, 17(05):627– 639, 2008. · Zbl 1191.11007
[2] F. Chung, P. Erd˝os, and J. Spencer. On the decomposition of graphs into complete bipartite subgraphs. In Studies in Pure Mathematics, pages 95-101. Springer, 1983. · Zbl 0531.05042
[3] G. A. Fre˘ıman. Foundations of a structural theory of set addition. American Mathematical Society, Providence, R. I., 1973. Translated from the Russian, Translations of Mathematical Monographs, Vol 37. · Zbl 0271.10044
[4] G. Petridis. New proofs of Pl¨unnecke-type estimates for product sets in groups. Combinatorica, 32(6):721-733, 2012. · Zbl 1291.11127
[5] H. Pl¨unnecke. Eine zahlentheoretische anwendung der graphtheorie. J. Reine Angew. Math., 243:171-183, 1970. · Zbl 0199.36701
[6] I. Z. Ruzsa. Sumsets and structure. In Combinatorial Number Theory and Additive Group Theory, pages 87-210, 2009. · Zbl 1221.11026
[7] T. Schoen and I. D. Shkredov. Additive dimension and a theorem of Sanders. J. Aust. Math. Soc., 100(1):124-144, 2016. · Zbl 1364.11022
[8] Z. Tuza. Covering of graphs by complete bipartite subgraphs: complexity of 0-1 matrices. Combinatorica, 4(1):111-116, 1984. · Zbl 0559.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.