Convex sets have many differences

Thanks to Sophie Stevens for helpful discussions at the Georgia discrete analysis conference leading to this post. We show that if ${A}$ has small (slightly generalized) third order energy, then ${A}$ has a large difference set. We present an argument due to Shkredov and Schoen. This has the advantage of being drastically simpler (and slightly stronger) than the analog for sumsets, which was discussed in this previous blog post. We say ${b \gtrsim a}$ if ${a = O(b \log^c |A|)}$ for some ${c >0}$ .

Let ${A, B \subset \mathbb{R}}$ be finite. We define the sumset and product set via

$\displaystyle A+B := \{a + b : a \in A , b \in B\} , \ \ \ \ \ \ AB := \{ab : a \in A , b \in B\}.$

We have the following difference–product conjecture.

Conjecture 1: Let ${\delta \leq 1}$ . Then for any finite ${A \subset \mathbb{Z}}$ one has

$\displaystyle |A-A| + |A A| \gtrsim |A|^{1 + \delta}. \ \ \spadesuit$

We say a finite ${A = \{a_1 < \ldots < a_k\} \subset \mathbb{R}}$ is convex if

$\displaystyle a_{i+1} - a_i > a_i - a_{i-1}, \ \ \ 2 \leq i \leq k-1.$

The following conjecture is due to Erdős.

Conjecture (Convex): Suppose ${A \subset \mathbb{R}}$ is convex. Then

$\displaystyle |A-A| \gtrsim |A|^2. \ \ \spadesuit$

Study of the quantity ${d^+(A)}$ has played a crucial role in recent progress on both conjectures, which we define now. For ${A \subset \mathbb{R}}$ finite, we define

$\displaystyle d^{+}(A) := \sup_{B \neq \emptyset}\frac{ E_3^+(A,B) }{|A| |B|^2},$

where

$\displaystyle E_3^+(A,B) = \sum_x r_{A- B}(x)^3 , \ \ \ \ r_{A-B}(x) = \#\{(a, b ) \in A \times B : x = a - b\}.$

See my recent paper on Conjecture 1 for a lengthy introduction to ${d^+(A)}$ . We mention here that ${1 \leq d^+(A) \leq |A|}$ and intuitively the larger ${d^+(A)}$ is the more additive structure ${A}$ has. For instance, we have

$\displaystyle E_3^+(A) \leq d^+(A) |A|^3. \ \ \ \ \ (1)$

Indeed ${d^+(A)}$ is a higher order analog of the more common additive energy of a set, where we have some flexibility in choosing ${B}$ (for instance, we choose ${B = A-A}$ below).

An application of Cauchy–Schwarz, as explained in equation 2 of this paper, reveals

$\displaystyle |A|^{3/2} \leq |A-A| d^+(A)^{1/2}.\ \ \ \ \ (2)$

Thus if ${d^+(A) \lesssim 1}$ , we have that ${|A+A| \gtrsim |A|^{3/2}}$ . We conjecture that this can be improved.

Conjecture (dplus): Let ${A \subset \mathbb{R}}$ be finite. Then

$\displaystyle |A-A| \gtrsim |A|^2 d^+(A)^{-1}. \ \ \ \ \spadesuit$

This would imply Conjecture (Convex) and Conjecture 1 for ${\delta = 1/2}$ . The goal of the rest of this post is to prove the current state of the art progress due to Shkredov and Schoen. The proof of Theorem 1 is simple enough that we compute the constant.

Theorem 1: Let ${A}$ be a subset of any additive group. Then

$\displaystyle |A-A| > \frac{|A|^{8/5}}{4d^+(A)^{3/5}}. \ \ \ \spadesuit$

We will use

$\displaystyle E_3^+(A) = \sum_x E^+(A, A_x) ,\ \ \ \ \ (3)$

as is explained using a simple geometric argument in equation 9 of this paper of Murphy, Rudnev, Shkredov, and Shteinikov. For ${x \in A-A}$ , let

$\displaystyle A_x := A \cap (A + x).$

Thus

$\displaystyle |A_x| = r_{A-A}(x).$

Let

$\displaystyle P =\{x \in A-A : r_{A-A}(x) \geq \frac{|A|^2}{2|A-A|}\},$

be the set of popular differences. Thus

$\displaystyle \sum_{x \in P} r_{A-A}(x) \geq (1/2) |A|^2.\ \ \ \ \ (4)$

By two applications of Cauchy–Schwarz,

$\displaystyle \sum_{x \in P} |A_x| |A| = \sum_{x \in P } \sum_y r_{A - A_x}(y) \leq \sum_{x\in P} E^+(A,A_x)^{1/2} |A - A_x|^{1/2} \leq \left(\sum_x E^+(A,A_x) \sum_{x \in P} |A- A_x| \right)^{1/2} .$

Combining this with (3) and (4), we find

$\displaystyle \frac{|A|^6}{4E_3^+(A)} \leq \sum_{x \in P} |A - A_x|.$

Now we use Katz–Koelster inclusion of the form

$\displaystyle A- A_x \subset (A-A) \cap (A - A -x),$

to find

$\displaystyle \frac{|A|^6}{4E_3^+(A)} \leq \sum_{x \in P} |D \cap (D - x) |, \ \ \ D := A- A.$

Since ${x \in P}$ , we have ${(1/2) |A|^2 |A-A|^{-1} \leq r_{A-A}(x)}$ , and so

$\displaystyle \frac{|A|^6}{4E_3^+(A)} \leq \frac{2 |A-A|}{|A|^2} \sum_{x \in P} r_{D-D}(x)r_{A-A}(x) \leq \frac{2|A-A|}{|A|^2} E^+(A,D).\ \ \ \ \ (5)$

By Cauchy–Schwarz (interpolating ${\ell_2}$ between ${\ell_3}$ and ${\ell_1}$ ), we have

$\displaystyle E^+(A,D)^2 \leq E_3^+(A,D) |A||D|,$

and so by the definition of ${d^+(A)}$ , (2), and (5), we arrive at

$\displaystyle \frac{|A|^{15}}{64|D|^{3}} \leq E_3^+(A)^2 E_3^+(A,D) \leq d^+(A)^3 |A|^7 |D|^2.$

Simplifying gives the (slightly stronger) desired

$\displaystyle \frac{|A|^8}{64 d^+(A)^3} \leq |A-A|^5. \ \ \ \spadesuit$

Developing a fourth moment analog of the above result would be worthwhile as it would have applications to finite field sum-product problem (edit: Ilya Shkredov and I pursued this idea further in a recent preprint).

	Temperature in Natur… on How Does ChatGPT read?
	Eva Tutor on Truthfulness of AI models like…
	David Burns on Can Chat-GPT Do Math?
	Azzouzi Marouan on Can Chat-GPT Do Math?
	khiannaian on Can Chat-GPT Do Math?

George Shakan

Data Science and Math Blog

Convex sets have many differences

Related

2 thoughts on “Convex sets have many differences”

Leave a ReplyCancel reply