Erdős–Szemerédi theorem

In arithmetic combinatorics, the Erdős–Szemerédi theorem states that for every finite set $A$ of integers, at least one of the sets $A + A$ and $A \cdot A$ (the sets of pairwise sums and pairwise products, respectively) form a significantly larger set. More precisely, the Erdős–Szemerédi theorem states that there exist positive constants $c$ and $ε$ such that, for any non-empty set $A \subset ℕ$ ,

\max(|A+A|,|A\cdot A|)\geq c|A|^{1+\varepsilon }

.

It was proved by Paul Erdős and Endre Szemerédi in 1983.^[1] The notation $| A |$ denotes the cardinality of the set $A$ .

The set of pairwise sums is $A + A = {a + b : a, b \in A}$ and is called the sumset of $A$ .

The set of pairwise products is $A \cdot A = {a \cdot b : a, b \in A}$ and is called the product set of $A$ ; it is also written $AA$ .

The theorem is a version of the maxim that additive structure and multiplicative structure cannot coexist. It can also be viewed as an assertion that the real line does not contain any set resembling a finite subring or finite subfield; it is the first example of what is now known as the sum-product phenomenon, which is now known to hold in a wide variety of rings and fields, including finite fields.^[2]

Sum-Product Conjecture

The sum-product conjecture informally says that one of the sum set or the product set of any set must be nearly as large as possible. It was originally conjectured by Erdős in 1974 to hold whether $A$ is a set of integers, reals, or complex numbers.^[3] More precisely, it proposes that, for any set $A \subset ℂ$ , one has

$\max(|A+A|,|AA|)\geq |A|^{2-o(1)}.$

The asymptotic parameter in the $o (1)$ notation is $| A |$ .

Examples

If $A = {1, 2, 3, \dots, n}$ , then $| A + A | = 2| A | - 1 = O (| A |)$ using asymptotic notation, with $| A |$ the asymptotic parameter. Informally, this says that the sum set of $A$ does not grow. On the other hand, the product set of $A$ satisfies a bound of the form $| A \cdot A | \geq | A | 2 - ε$ for all $ε > 0$ . This is related to the Erdős multiplication table problem.^[4] The best lower bound on $| A \cdot A |$ for this set is due to Kevin Ford.^[5]

This example is an instance of the Few Sums, Many Products^[6] version of the sum-product problem of György Elekes and Imre Z. Ruzsa. A consequence of their result is that any set with small additive doubling (such as an arithmetic progression) has the lower bound on the product set $| AA | = Ω(| A | 2 log -1 (| A |))$ . Xu and Zhou proved^[7] that $| AA | = Ω(| A | 2 log 1-2log(2)- o (1) (| A |))$ for any dense subset $A$ of an arithmetic progression in integers, which is sharp up to the $o (1)$ in the exponent.

Conversely, the set $B = {2, 4, 8, \dots, 2 n}$ satisfies $| BB | = 2| B | - 1$ , but has many sums: $|B+B|={\binom {|B|+1}{2}}$ . This bound comes from considering the binary representation of a number. The set $B$ is an example of a geometric progression.

For a random set of $n$ numbers, both the product set and the sumset have cardinality ${\binom {n+1}{2}}$ ; that is, with high probability, neither the sumset nor the product set generates repeated elements.

Sharpness of the conjecture

Erdős and Szemerédi give an example of a sufficiently smooth set of integers $A$ with the bound

$\max\{|A+A|,|A\cdot A|\}\leq |A|^{2}e^{-{\frac {c\log |A|}{\log \log |A|}}}$ .^[1]

This shows that the $o (1)$ term in the conjecture is necessary.

Extremal cases

Often studied are the extreme cases of the hypothesis:

few sums, many product (FSMP): if $| A + A | ≪ | A |$ , then $| AA | \geq | A | 2- o (1)$ ,^[6] and
few products, many sums (FPMS): if $| AA | ≪ | A |$ , then $| A + A | \geq | A | 2- o (1)$ .^[8]

History and current results

The following table summarizes progress on the sum-product problem over the reals. The exponents 1/4 of György Elekes and 1/3 of József Solymosi are considered milestone results within the citing literature. All improvements after 2009 are of the form $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠1/3⁠ + c$ , and represent refinements of the arguments of Konyagin and Shkredov.^[9]

Exponent $δ$ where $max(| A + A |, | AA |) \geq | A | 1+ δ - o (1)$ for $A \subset ℝ$
Year	Exponent	Author(s)	Comments
1983	non-explicit $δ > 0$	Erdős and Szemerédi ^[10]	Only for $A \subseteq ℤ$ and of the form $1 + δ$ instead of $1 + δ - o (1)$ .
1997	$⁠ 1 / 31 ⁠$	Nathanson^[11]	Only for $A \subseteq ℤ$ and of the form $1 + δ$ instead of $1 + δ - o (1)$ .
1998	$⁠ 1 / 15 ⁠$	Ford ^[12]	Only for $A \subseteq ℤ$ and of the form $1 + δ$ instead of $1 + δ - o (1)$ .
1997	$⁠ 1 / 4 ⁠$	Elekes ^[13]	Of the form $1 + δ - o (1)$ . Valid also over $ℂ$
2005	$⁠ 3 / 11 ⁠$	Solymosi^[14]	Valid also over $ℂ$
2009	$⁠ 1 / 3 ⁠$	Solymosi ^[15]
2015	$⁠ 1 / 3 ⁠ + ⁠ 1 / 20598 ⁠ = 0.333381\dots$	Konyagin and Shkredov ^[9]
2016	$⁠ 1 / 3 ⁠ + ⁠ 5 / 9813 ⁠ = 0.333842\dots$	Konyagin and Shkredov ^[16]
2016	$⁠ 1 / 3 ⁠ + ⁠ 1 / 1509 ⁠ = 0.333996\dots$	Rudnev, Shkredov and Stevens ^[17]
2019	$⁠ 1 / 3 ⁠ + ⁠ 5 / 5277 ⁠ = 0.334280\dots$	Shakan ^[18]
2020	$⁠ 1 / 3 ⁠ + ⁠ 2 / 1167 ⁠ = 0.335047\dots$	Rudnev and Stevens ^[19]	Current record

Complex numbers

Proof techniques involving only the Szemerédi–Trotter theorem extend automatically to the complex numbers, since the Szemerédi-Trotter theorem holds over $ℂ 2$ by a theorem of Tóth.^[20] Konyagin and Rudnev^[21] matched the exponent of 4/3 over the complex numbers. The results with exponents of the form $⁠ 4 / 3 ⁠ + c$ have not been matched over the complex numbers.

Over finite fields

The sum-product problem is particularly well-studied over finite fields. Motivated by the finite field Kakeya conjecture, Wolff conjectured that for every subset $A \subseteq 𝔽 p$ , where $p$ is a (large) prime, that $max(| A + A |, | AA |) \geq min(p, | A | 1+ ε)$ for an absolute constant $ε > 0$ . This conjecture had also been formulated in the 1990s by Wigderson^[22] motivated by randomness extractors.

Note that the sum-product problem cannot hold in finite fields unconditionally due to the following example:

Example: Let $𝔽$ be a finite field and take $A = 𝔽$ . Then since $𝔽$ is closed under addition and multiplication, $A + A = AA = 𝔽$ , and so $| A + A | = | AA | = | 𝔽 |$ . This pathological example extends to taking $A$ to be any sub-field of the field in question.

Qualitatively, the sum-product problem has been solved over finite fields:

Theorem (Bourgain, Katz, Tao (2004)):^[23] Let $p$ be prime and let $A \subset 𝔽 p$ with $p δ < | A | < p 1- δ$ for some $0 < δ < 1$ . Then $max(| A + A |, | AA |) \geq c δ | A | 1+ ε$ for some $ε = ε (δ) > 0$ .

Bourgain, Katz, and Tao extended this theorem to arbitrary fields. Informally, the following theorem says that if a sufficiently large set does not grow under either addition or multiplication, then it is mostly contained in a dilate of a sub-field.

Theorem (Bourgain, Katz, Tao (2004)):^[23] Let $A$ be a subset of a finite field $𝔽$ so that $| A | > | 𝔽 | δ$ for some $0 < δ < 1$ , and suppose that $| A + A |, | AA | \leq K | A |$ . Then there exists a sub-field $G \subset 𝔽$ with $| G | \leq K C δ | A |$ , an element $x ∈ 𝔽 \ {0}$ , and a set $X \subset 𝔽$ with $| X | \leq K C δ$ so that $A \subseteq xG \cup X$ .

They suggest that the constant $C δ$ may be independent of $δ$ .

Quantitative results towards the finite field sum-product problem in $𝔽$ typically fall into two categories: when $A \subset 𝔽$ is small or large with respect to the characteristic of $𝔽$ . This is because different types of techniques are used in each setting.

Small sets

In this regime, let $𝔽$ be a field of characteristic $p$ . Note that the field is not always finite. When this is the case, and the characteristic of $𝔽$ is zero, then the $p$ -constraint is omitted.

Exponent $δ$ where $max(| A + A |, | AA |) \geq | A | 1+ δ - o (1)$ for $A \subset 𝔽$
Year	Exponent	$p$ -constraint: $\| A \| < p c$	Author(s)	Comments
2004	unquantified	$c < 1$	Bourgain, Katz, Tao ^[23]	For finite $𝔽$ only.
2007	$⁠ 1 / 14 ⁠$	$c = ⁠ 7 / 13 ⁠$	Garaev^[24]	For finite $𝔽$ only. The $p$ -constraint involves a factor of $log(\| A \|)$
2008	$⁠ 1 / 13 ⁠$	$c = ⁠ 1 / 2 ⁠$	Katz, Shen	For finite $𝔽$ only.
2009	$⁠ 1 / 12 ⁠$	$c = ⁠ 12 / 23 ⁠$	Bourgain, Garaev^[25]	For finite $𝔽$ only. $o (1)$ removed by Li.^[26]
2012	$⁠ 1 / 11 ⁠$	$c = ⁠ 1 / 2 ⁠$	Rudnev^[27]	For finite $𝔽$ only.
2016	$⁠ 1 / 5 ⁠$	$c = ⁠ 5 / 8 ⁠$	Roche-Newton, Rudnev, Shkredov^[28]
2016	$⁠ 1 / 9 ⁠$	$c = ⁠ 18 / 35 ⁠$	Rudnev, Shkredov, Shakan	This result is the best of three contemporaneous results.
2021	$⁠ 1 / 4 ⁠$	$c = ⁠ 1 / 2 ⁠$	Mohammadi, Stevens ^[29]	Current record. Extends to difference sets and ratio sets.

In fields with non-prime order, the $p$ -constraint on $A \subset 𝔽$ can be replaced with the assumption that $A$ does not have too large an intersection with any subfield. The best work in this direction is due to Li and Roche-Newton^[30] attaining an exponent of $δ = ⁠ 1 / 19 ⁠$ in the notation of the above table.

Large sets

When $𝔽 = 𝔽 p$ for $p$ prime, the sum-product problem is considered resolved due to the following result of Garaev:^[31]

Theorem (Garaev (2007)): Let $A \subset 𝔽 p$ . Then $max(| A + A |, | AA |) ≫ min(p 1/2 | A | 1/2, | A | 2 p -1/2)$ .

This is optimal in the range $| A | \geq p 2/3$ .

This result was extended to finite fields of non-prime order by Vinh^[32] in 2011.

Variants and generalizations

Other combinations of operators

Bourgain and Chang proved unconditional growth for sets $A \subseteq ℤ$ , as long as one considers enough sums or products:

Theorem (Bourgain, Chang (2003)):^[33] Let $b \in ℕ$ . Then there exists $k \in ℕ$ so that for all $A \subseteq ℤ$ , one has $max(| kA |, | A (k) |) = max(| A + A + \dots + A |, | A \cdot A \cdot \dots \cdot A |) \geq | A | b$ .

In many works, addition and multiplication are combined in one expression. With the motto addition and multiplication cannot coexist, one expects that any non-trivial combination of addition and multiplication of a set should guarantee growth. Note that in finite settings, or in fields with non-trivial subfields, such a statement requires further constraints.

Sets of interest include (results for $A \subset ℝ$ ):

$AA + A$ : Stevens and Warren^[34] show that $| AA + A | ≫ | A | ⁠ 3 / 2 ⁠ + ⁠ 3 / 170 ⁠ - o (1)$
$A (A + A)$ : Murphy, Roche-Newton and Shkredov^[35] show that $| A (A + A) | ≫ | A | ⁠ 3 / 2 ⁠ + ⁠ 5 / 242 ⁠ - o (1)$
$A (A + 1)$ : Stevens and Warren^[34] show that $| A (A + 1) | ≫ | A | ⁠ 49 / 38 ⁠ - o (1)$
$AA + AA$ : Stevens and Rudnev^[19] show that $| AA + AA | ≫ | A | ⁠ 127 / 80 ⁠ - o (1)$

References

^ ^a ^b Erdős, Paul; Szemerédi, Endre (1983), "On sums and products of integers", Studies in Pure Mathematics. To the memory of Paul Turán, Basel: Birkhäuser Verlag, pp. 213–218, CiteSeerX 10.1.1.210.6957, doi:10.1007/978-3-0348-5438-2_19, ISBN 978-3-7643-1288-6, MR 0820223.
^ Tao, Terence (2009), "The sum-product phenomenon in arbitrary rings", Contributions to Discrete Mathematics, 4 (2): 59–82, arXiv:0806.2497, Bibcode:2008arXiv0806.2497T, doi:10.11575/cdm.v4i2.61994, hdl:10515/sy5r78637, MR 2592424.
^ P. Erdős: Some recent problems and results in graph theory, combinatorics and number theory, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congress. Numer. XVII , pp. 3--14, Utilitas Math., Winnipeg, Man., 1976 MR54 #10023; Zentralblatt 352.05024.
^ Erdős, Paul (1960). "An asymptotic inequality in the theory of numbers". Vestnik Leningrad. Univ. 15: 41–49. MR 0126424.
^ Ford, Kevin (1998), "Sums and Products from a Finite Set of Real Numbers", Analytic and Elementary Number Theory, Developments in Mathematics, vol. 1, Boston, MA: Springer US, pp. 59–66, doi:10.1007/978-1-4757-4507-8_7, ISBN 978-1-4419-5058-1, S2CID 117873720, retrieved 2021-07-09
^ ^a ^b Elekes Gy., György; Ruzsa, Imre Z. (2003-08-01). "Few sums, many products". Studia Scientiarum Mathematicarum Hungarica. 40 (3): 301–308. doi:10.1556/sscmath.40.2003.3.4. ISSN 0081-6906.
^ Xu, Max Wenqiang; Zhou, Yunkun (2022). "On product sets of arithmetic progressions". arXiv:2201.00104 [math.NT].
^ Murphy, Brendan; Rudnev, Misha; Shkredov, Ilya; Shteinikov, Yuri (2019). "On the few products, many sums problem". Journal de Théorie des Nombres de Bordeaux. 31 (3): 573–602. arXiv:1712.00410. doi:10.5802/jtnb.1095. S2CID 119665080.
^ ^a ^b Konyagin, S. V.; Shkredov, I. D. (August 2015). "On sum sets of sets having small product set". Proceedings of the Steklov Institute of Mathematics. 290 (1): 288–299. arXiv:1503.05771. doi:10.1134/s0081543815060255. ISSN 0081-5438. S2CID 117359454.
^ Erdős, P.; Szemerédi, E. (1983), "On sums and products of integers", Studies in Pure Mathematics, Basel: Birkhäuser Basel, pp. 213–218, doi:10.1007/978-3-0348-5438-2_19, ISBN 978-3-7643-1288-6, retrieved 2021-07-09
^ Nathanson, Melvyn B. (1997). "On sums and products of integers". Proceedings of the American Mathematical Society. 125 (1): 9–16. doi:10.1090/s0002-9939-97-03510-7. ISSN 0002-9939.
^ Ford, Kevin (1998). "Sums and products from a finite set of real numbers". The Ramanujan Journal. 2 (1/2): 59–66. doi:10.1023/a:1009709908223. ISSN 1382-4090. S2CID 195302784.
^ Elekes, György (1997). "On the number of sums and products". Acta Arithmetica. 81 (4): 365–367. doi:10.4064/aa-81-4-365-367. ISSN 0065-1036.
^ Solymosi, József (August 2005). "On the number of sums and products". Bulletin of the London Mathematical Society. 37 (4): 491–494. doi:10.1112/s0024609305004261. ISSN 0024-6093. S2CID 56432429.
^ Solymosi, József (October 2009). "Bounding multiplicative energy by the sumset". Advances in Mathematics. 222 (2): 402–408. arXiv:0806.1040. doi:10.1016/j.aim.2009.04.006. ISSN 0001-8708.
^ Konyagin, S. V.; Shkredov, I. D. (August 2016). "New results on sums and products in ℝ". Proceedings of the Steklov Institute of Mathematics. 294 (1): 78–88. doi:10.1134/s0081543816060055. ISSN 0081-5438. S2CID 126099880.
^ Rudnev, Misha; Shkredov, Ilya; Stevens, Sophie (2019-09-10). "On the energy variant of the sum-product conjecture". Revista Matemática Iberoamericana. 36 (1): 207–232. arXiv:1607.05053. doi:10.4171/rmi/1126. ISSN 0213-2230. S2CID 119122310.
^ Shakan, George (2018-07-03). "On higher energy decompositions and the sum–product phenomenon". Mathematical Proceedings of the Cambridge Philosophical Society. 167 (3): 599–617. arXiv:1803.04637. doi:10.1017/s0305004118000506. ISSN 0305-0041. S2CID 119693920.
^ ^a ^b Rudnev, Misha; Stevens, Sophie (2020). "An update on the sum-product problem". arXiv:2005.11145 [math.CO].
^ Tóth, Csaba D. (February 2015). "The Szemerédi-Trotter theorem in the complex plane". Combinatorica. 35 (1): 95–126. arXiv:math/0305283. doi:10.1007/s00493-014-2686-2. ISSN 0209-9683. S2CID 13237229.
^ Konyagin, Sergei V.; Rudnev, Misha (January 2013). "On New Sum-Product--Type Estimates". SIAM Journal on Discrete Mathematics. 27 (2): 973–990. arXiv:1111.4977. doi:10.1137/120886418. ISSN 0895-4801. S2CID 207065775.
^ Trevisan, Luca (2009-06-20). "Guest column". ACM SIGACT News. 40 (2): 50–66. doi:10.1145/1556154.1556170. ISSN 0163-5700. S2CID 12566158.
^ ^a ^b ^c Bourgain, Jean; Katz, Nets; Tao, Terence (2004-02-01). "A sum-product estimate in finite fields, and applications". Geometric and Functional Analysis. 14 (1): 27–57. arXiv:math/0301343. doi:10.1007/s00039-004-0451-1. ISSN 1016-443X. S2CID 14097626.
^ Garaev, M. Z. (2010-07-08). "An Explicit Sum-Product Estimate in Fp". International Mathematics Research Notices. arXiv:math/0702780. doi:10.1093/imrn/rnm035. ISSN 1073-7928.
^ Bourgain, Garaev (2008). "On a variant of sum-product estimates and explicit exponential sum bounds in prime fields". Math. Proc. Cambridge Philosophical Society. 146 (1): 1. Bibcode:2008MPCPS.146....1B. doi:10.1017/S0305004108001230. S2CID 120185078.
^ Li, Liangpan (2011). "Slightly improved sum-product estimates in fields of prime order". Acta Arithmetica. 147 (2): 153–160. arXiv:0907.2051. doi:10.4064/aa147-2-4. ISSN 0065-1036. S2CID 15954935.
^ Rudnev, Misha (2011-08-25). "An Improved Sum–Product Inequality in Fields of Prime Order". International Mathematics Research Notices. 2012 (16): 3693–3705. arXiv:1011.2738. doi:10.1093/imrn/rnr158. ISSN 1687-0247.
^ Roche-Newton, Oliver; Rudnev, Misha; Shkredov, Ilya D. (2016). "New sum-product type estimates over finite fields". Advances in Mathematics. 293: 589–605. arXiv:1408.0542. doi:10.1016/j.aim.2016.02.019.
^ Mohammadi, Stevens (2021). "Attaining the exponent 5/4 for the sum-product problem in finite fields". arXiv:2103.08252 [math.CO].
^ Li, Liangpan; Roche-Newton, Oliver (January 2011). "An improved sum-product estimate for general finite fields". SIAM Journal on Discrete Mathematics. 25 (3): 1285–1296. arXiv:1101.5348. doi:10.1137/110823122. ISSN 0895-4801. S2CID 7024012.
^ Garaev, M. Z. (2008-04-14). "The sum-product estimate for large subsets of prime fields". Proceedings of the American Mathematical Society. 136 (8): 2735–2739. arXiv:0706.0702. doi:10.1090/s0002-9939-08-09386-6. ISSN 0002-9939. S2CID 16064726.
^ Vinh, Le Anh (November 2011). "The Szemerédi–Trotter type theorem and the sum-product estimate in finite fields". European Journal of Combinatorics. 32 (8): 1177–1181. arXiv:0711.4427. doi:10.1016/j.ejc.2011.06.008. ISSN 0195-6698.
^ Bourgain, Jean; Chang, Mei-Chu (2003-11-25). "On the size of $k$-fold sum and product sets of integers". Journal of the American Mathematical Society. 17 (2): 473–497. arXiv:math/0309055. Bibcode:2003math......9055B. doi:10.1090/s0894-0347-03-00446-6. ISSN 0894-0347. S2CID 15154515.
^ ^a ^b Stevens, Warren (2021). "On sum sets of convex functions". arXiv:2102.05446 [math.CO].
^ Murphy, Brendan; Roche-Newton, Oliver; Shkredov, Ilya D. (January 2017). "Variations on the Sum-Product Problem II". SIAM Journal on Discrete Mathematics. 31 (3): 1878–1894. arXiv:1703.09549. doi:10.1137/17M112316X. ISSN 0895-4801. S2CID 207074281.

External links

Hartnett, Kevin (6 February 2019). "How a Strange Grid Reveals Hidden Connections Between Simple Numbers". Quanta Magazine.

[:0-1] Erdős, Paul; Szemerédi, Endre (1983), "On sums and products of integers", Studies in Pure Mathematics. To the memory of Paul Turán, Basel: Birkhäuser Verlag, pp. 213–218, CiteSeerX 10.1.1.210.6957, doi:10.1007/978-3-0348-5438-2_19, ISBN 978-3-7643-1288-6, MR 0820223.

[2] Tao, Terence (2009), "The sum-product phenomenon in arbitrary rings", Contributions to Discrete Mathematics, 4 (2): 59–82, arXiv:0806.2497, Bibcode:2008arXiv0806.2497T, doi:10.11575/cdm.v4i2.61994, hdl:10515/sy5r78637, MR 2592424.

[3] P. Erdős: Some recent problems and results in graph theory, combinatorics and number theory, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congress. Numer. XVII , pp. 3--14, Utilitas Math., Winnipeg, Man., 1976 MR54 #10023; Zentralblatt 352.05024.

[4] Erdős, Paul (1960). "An asymptotic inequality in the theory of numbers". Vestnik Leningrad. Univ. 15: 41–49. MR 0126424.

[5] Ford, Kevin (1998), "Sums and Products from a Finite Set of Real Numbers", Analytic and Elementary Number Theory, Developments in Mathematics, vol. 1, Boston, MA: Springer US, pp. 59–66, doi:10.1007/978-1-4757-4507-8_7, ISBN 978-1-4419-5058-1, S2CID 117873720, retrieved 2021-07-09

[:2-6] Elekes Gy., György; Ruzsa, Imre Z. (2003-08-01). "Few sums, many products". Studia Scientiarum Mathematicarum Hungarica. 40 (3): 301–308. doi:10.1556/sscmath.40.2003.3.4. ISSN 0081-6906.

[:6-7] Xu, Max Wenqiang; Zhou, Yunkun (2022). "On product sets of arithmetic progressions". arXiv:2201.00104 [math.NT].

[8] Murphy, Brendan; Rudnev, Misha; Shkredov, Ilya; Shteinikov, Yuri (2019). "On the few products, many sums problem". Journal de Théorie des Nombres de Bordeaux. 31 (3): 573–602. arXiv:1712.00410. doi:10.5802/jtnb.1095. S2CID 119665080.

[:1-9] Konyagin, S. V.; Shkredov, I. D. (August 2015). "On sum sets of sets having small product set". Proceedings of the Steklov Institute of Mathematics. 290 (1): 288–299. arXiv:1503.05771. doi:10.1134/s0081543815060255. ISSN 0081-5438. S2CID 117359454.

[10] Erdős, P.; Szemerédi, E. (1983), "On sums and products of integers", Studies in Pure Mathematics, Basel: Birkhäuser Basel, pp. 213–218, doi:10.1007/978-3-0348-5438-2_19, ISBN 978-3-7643-1288-6, retrieved 2021-07-09

[11] Nathanson, Melvyn B. (1997). "On sums and products of integers". Proceedings of the American Mathematical Society. 125 (1): 9–16. doi:10.1090/s0002-9939-97-03510-7. ISSN 0002-9939.

[12] Ford, Kevin (1998). "Sums and products from a finite set of real numbers". The Ramanujan Journal. 2 (1/2): 59–66. doi:10.1023/a:1009709908223. ISSN 1382-4090. S2CID 195302784.

[13] Elekes, György (1997). "On the number of sums and products". Acta Arithmetica. 81 (4): 365–367. doi:10.4064/aa-81-4-365-367. ISSN 0065-1036.

[14] Solymosi, József (August 2005). "On the number of sums and products". Bulletin of the London Mathematical Society. 37 (4): 491–494. doi:10.1112/s0024609305004261. ISSN 0024-6093. S2CID 56432429.

[15] Solymosi, József (October 2009). "Bounding multiplicative energy by the sumset". Advances in Mathematics. 222 (2): 402–408. arXiv:0806.1040. doi:10.1016/j.aim.2009.04.006. ISSN 0001-8708.

[16] Konyagin, S. V.; Shkredov, I. D. (August 2016). "New results on sums and products in ℝ". Proceedings of the Steklov Institute of Mathematics. 294 (1): 78–88. doi:10.1134/s0081543816060055. ISSN 0081-5438. S2CID 126099880.

[17] Rudnev, Misha; Shkredov, Ilya; Stevens, Sophie (2019-09-10). "On the energy variant of the sum-product conjecture". Revista Matemática Iberoamericana. 36 (1): 207–232. arXiv:1607.05053. doi:10.4171/rmi/1126. ISSN 0213-2230. S2CID 119122310.

[18] Shakan, George (2018-07-03). "On higher energy decompositions and the sum–product phenomenon". Mathematical Proceedings of the Cambridge Philosophical Society. 167 (3): 599–617. arXiv:1803.04637. doi:10.1017/s0305004118000506. ISSN 0305-0041. S2CID 119693920.

[:4-19] Rudnev, Misha; Stevens, Sophie (2020). "An update on the sum-product problem". arXiv:2005.11145 [math.CO].

[20] Tóth, Csaba D. (February 2015). "The Szemerédi-Trotter theorem in the complex plane". Combinatorica. 35 (1): 95–126. arXiv:math/0305283. doi:10.1007/s00493-014-2686-2. ISSN 0209-9683. S2CID 13237229.

[21] Konyagin, Sergei V.; Rudnev, Misha (January 2013). "On New Sum-Product--Type Estimates". SIAM Journal on Discrete Mathematics. 27 (2): 973–990. arXiv:1111.4977. doi:10.1137/120886418. ISSN 0895-4801. S2CID 207065775.

[22] Trevisan, Luca (2009-06-20). "Guest column". ACM SIGACT News. 40 (2): 50–66. doi:10.1145/1556154.1556170. ISSN 0163-5700. S2CID 12566158.

[:3-23] Bourgain, Jean; Katz, Nets; Tao, Terence (2004-02-01). "A sum-product estimate in finite fields, and applications". Geometric and Functional Analysis. 14 (1): 27–57. arXiv:math/0301343. doi:10.1007/s00039-004-0451-1. ISSN 1016-443X. S2CID 14097626.

[24] Garaev, M. Z. (2010-07-08). "An Explicit Sum-Product Estimate in Fp". International Mathematics Research Notices. arXiv:math/0702780. doi:10.1093/imrn/rnm035. ISSN 1073-7928.

[25] Bourgain, Garaev (2008). "On a variant of sum-product estimates and explicit exponential sum bounds in prime fields". Math. Proc. Cambridge Philosophical Society. 146 (1): 1. Bibcode:2008MPCPS.146....1B. doi:10.1017/S0305004108001230. S2CID 120185078.

[26] Li, Liangpan (2011). "Slightly improved sum-product estimates in fields of prime order". Acta Arithmetica. 147 (2): 153–160. arXiv:0907.2051. doi:10.4064/aa147-2-4. ISSN 0065-1036. S2CID 15954935.

[27] Rudnev, Misha (2011-08-25). "An Improved Sum–Product Inequality in Fields of Prime Order". International Mathematics Research Notices. 2012 (16): 3693–3705. arXiv:1011.2738. doi:10.1093/imrn/rnr158. ISSN 1687-0247.

[28] Roche-Newton, Oliver; Rudnev, Misha; Shkredov, Ilya D. (2016). "New sum-product type estimates over finite fields". Advances in Mathematics. 293: 589–605. arXiv:1408.0542. doi:10.1016/j.aim.2016.02.019.

[29] Mohammadi, Stevens (2021). "Attaining the exponent 5/4 for the sum-product problem in finite fields". arXiv:2103.08252 [math.CO].

[30] Li, Liangpan; Roche-Newton, Oliver (January 2011). "An improved sum-product estimate for general finite fields". SIAM Journal on Discrete Mathematics. 25 (3): 1285–1296. arXiv:1101.5348. doi:10.1137/110823122. ISSN 0895-4801. S2CID 7024012.

[31] Garaev, M. Z. (2008-04-14). "The sum-product estimate for large subsets of prime fields". Proceedings of the American Mathematical Society. 136 (8): 2735–2739. arXiv:0706.0702. doi:10.1090/s0002-9939-08-09386-6. ISSN 0002-9939. S2CID 16064726.

[32] Vinh, Le Anh (November 2011). "The Szemerédi–Trotter type theorem and the sum-product estimate in finite fields". European Journal of Combinatorics. 32 (8): 1177–1181. arXiv:0711.4427. doi:10.1016/j.ejc.2011.06.008. ISSN 0195-6698.

[33] Bourgain, Jean; Chang, Mei-Chu (2003-11-25). "On the size of $k$-fold sum and product sets of integers". Journal of the American Mathematical Society. 17 (2): 473–497. arXiv:math/0309055. Bibcode:2003math......9055B. doi:10.1090/s0894-0347-03-00446-6. ISSN 0894-0347. S2CID 15154515.

[:5-34] Stevens, Warren (2021). "On sum sets of convex functions". arXiv:2102.05446 [math.CO].

[35] Murphy, Brendan; Roche-Newton, Oliver; Shkredov, Ilya D. (January 2017). "Variations on the Sum-Product Problem II". SIAM Journal on Discrete Mathematics. 31 (3): 1878–1894. arXiv:1703.09549. doi:10.1137/17M112316X. ISSN 0895-4801. S2CID 207074281.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]