Variations on the Sum-Product Problem

Brendan Murphy; Oliver Roche-Newton; Ilya D. Shkredov

Variations on the Sum-Product Problem

Brendan Murphy, Oliver Roche-Newton, Ilya D. Shkredov

Research output: Contribution to journal › Article (Academic Journal) › peer-review

Abstract

This paper considers various formulations of the sum-product problem. It is shown that, for a finite set $A\subset{\mathbb{R}}$, $$|A(A+A)|\gg{|A|^{\frac{3}{2}+\frac{1}{178}}},$$ giving a partial answer to a conjecture of Balog. In a similar spirit, it is established that $$|A(A+A+A+A)|\gg{\frac{|A|^2}{\log{|A|}}},$$ a bound which is optimal up to constant and logarithmic factors. We also prove several new results concerning sum-product estimates and expanders, for example, showing that $$|A(A+a)|\gg{|A|^{3/2}}$$ holds for a typical element of $A$.

Original language	English
Journal	SIAM Journal on Discrete Mathematics
Publication status	Published - 22 Dec 2013

Bibliographical note

30 pages, new version contains improved exponent in main theorem due to suggestion of M. Z. Garaev

Keywords

math.CO

Handle.net

Persistent link

Cite this

@article{5a89ec3e7bf549699283e0052ef5dd3f,

title = "Variations on the Sum-Product Problem",

abstract = " This paper considers various formulations of the sum-product problem. It is shown that, for a finite set $A\subset{\mathbb{R}}$, $$|A(A+A)|\gg{|A|^{\frac{3}{2}+\frac{1}{178}}},$$ giving a partial answer to a conjecture of Balog. In a similar spirit, it is established that $$|A(A+A+A+A)|\gg{\frac{|A|^2}{\log{|A|}}},$$ a bound which is optimal up to constant and logarithmic factors. We also prove several new results concerning sum-product estimates and expanders, for example, showing that $$|A(A+a)|\gg{|A|^{3/2}}$$ holds for a typical element of $A$. ",

keywords = "math.CO",

author = "Brendan Murphy and Oliver Roche-Newton and Shkredov, {Ilya D.}",

note = "30 pages, new version contains improved exponent in main theorem due to suggestion of M. Z. Garaev",

year = "2013",

month = dec,

day = "22",

language = "English",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics",

}

TY - JOUR

T1 - Variations on the Sum-Product Problem

AU - Murphy, Brendan

AU - Roche-Newton, Oliver

AU - Shkredov, Ilya D.

N1 - 30 pages, new version contains improved exponent in main theorem due to suggestion of M. Z. Garaev

PY - 2013/12/22

Y1 - 2013/12/22

N2 - This paper considers various formulations of the sum-product problem. It is shown that, for a finite set $A\subset{\mathbb{R}}$, $$|A(A+A)|\gg{|A|^{\frac{3}{2}+\frac{1}{178}}},$$ giving a partial answer to a conjecture of Balog. In a similar spirit, it is established that $$|A(A+A+A+A)|\gg{\frac{|A|^2}{\log{|A|}}},$$ a bound which is optimal up to constant and logarithmic factors. We also prove several new results concerning sum-product estimates and expanders, for example, showing that $$|A(A+a)|\gg{|A|^{3/2}}$$ holds for a typical element of $A$.

AB - This paper considers various formulations of the sum-product problem. It is shown that, for a finite set $A\subset{\mathbb{R}}$, $$|A(A+A)|\gg{|A|^{\frac{3}{2}+\frac{1}{178}}},$$ giving a partial answer to a conjecture of Balog. In a similar spirit, it is established that $$|A(A+A+A+A)|\gg{\frac{|A|^2}{\log{|A|}}},$$ a bound which is optimal up to constant and logarithmic factors. We also prove several new results concerning sum-product estimates and expanders, for example, showing that $$|A(A+a)|\gg{|A|^{3/2}}$$ holds for a typical element of $A$.

KW - math.CO

M3 - Article (Academic Journal)

SN - 0895-4801

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

ER -

Variations on the Sum-Product Problem

Abstract

Bibliographical note

Keywords

Handle.net

Fingerprint

Cite this