# Difference Sets with Local Properties

I recently attended a wonderful workshop about Algebraic methods in combinatorics, which took place in Harvard’s CMSA. There were many interesting participants from a variety of combinatorial fields, and a very friendly/productive atmosphere. My talk focused on a recent work with Cosmin Pohoata, and I also mentioned some distinct distances result that we derived. During the talk Zeev Dvir asked about an additive variant of the problem. After thinking about this variant for a bit, I think that it is a natural interesting problem. Surprisingly, so far I did not manage to find any hint of previous work on it (this might say more about my search capabilities than about the problem…)

Zeev Dvir and Cosmin Pohoata.

Let $\phi(n,k,\ell)$ denote the minimum size $A-A$ can have, when $A$ is a set of $n$ real numbers with the property that for any $A' \subset A$ with $|A'|=k$ we have $|A'-A'|\ge \ell$. That is, by having a local additive property of every small subset, we wish to obtain a global additive property of the entire set. For simplicity, we will ignore zero in the difference set. Similarly, we will ignore negative differences. These assumptions do not change the problem, but make it easier to discuss.

As a first example, note that $\phi(n,3,3)$ is the minimum number of differences determined by a set of $n$ reals with no 3-term arithmetic progressions. Behrend’s construction is a set $A$ of positive integers $a_1< a_2 < \cdots < a_n$ with no 3-term arithmetic progression and $a_n < n2^{O(\sqrt{\log n})}$. Thus, $\phi(n,3,3) < n2^{O(\sqrt{\log n})}$.

For another simple example, Consider a constant $k\ge 4$. Since we consider only positive differences, any set of $k$ reals determines at most $\binom{k}{2}$ differences. If a specific difference $d$ repeats $\lfloor k/2 \rfloor$ times, then by taking the numbers that span $d$ we obtain $A'\subset A$ such that $|A'|\le k$ and $|A'-A'| \le \binom{k}{2}- \lfloor k/2 \rfloor+1$. Thus, by asking every subset of size $k$ to span at least $\binom{k}{2}- \lfloor k/2 \rfloor+2$ differences, we obtain that no difference repeats $\lfloor k/2 \rfloor$ times in $A$. In other words

$\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2 \right) = \Omega\left(n^2\right).$

Repeating a simple argument of Erdős and Gyárfás gives

$\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +1\right) = \Omega\left(n^{4/3}\right).$

That is, when moving from $\ell = \binom{k}{2}-\lfloor k/2 \rfloor +2$ to $\ell = \binom{k}{2}-\lfloor k/2 \rfloor +1$, we move from a trivial problem to a wide open one. My work with Cosmin Pohoata leads to the following result.

Theorem 1. For any $d\ge 2$ there exists $c$ such that

$\phi\left(n,k,\binom{k}{2}-k\frac{d}{d+1}+c\right) =\Omega\left(n^{1+1/d} \right).$

For example, when $d=2$ we get the bound

$\phi\left(n,k,\binom{k}{2}-\frac{2k}{3}+c\right) =\Omega\left(n^{3/2} \right).$

When $d=3$ we get a significant improvement for the range of the Erdős-Gyárfás bound:

$\phi\left(n,k,\binom{k}{2}-\frac{2k}{3}+c\right) =\Omega\left(n^{3/2} \right). \qquad \qquad \qquad (1)$

Since not much is known for this problem, it seems plausible that additional bounds could be obtained using current tools. Our technique does not rely on any additive properties, and holds for a more abstract scenario of graphs with colored edges. Hopefully in the case of difference sets one would be able to use additive properties to improve the bounds. Moreover, so far I know nothing about much smaller values of $\ell$, such as $\phi(n,k,100k)$.

Proof sketch for Theorem 1. For simplicity, let us consider the case of $d=3$, as stated in $(1)$. Other values of $d$ are handled in a similar manner. Let $A$ be a set of $n$ reals, such that any $A'\subset A$ of size $k$ satisfies $|A'-A'|\ge \binom{k}{2}-\frac{3k}{4}+13$. We define the third distance energy of $A$ as

$E_3(A) = \left|\left\{(a_1,a_2,a_3,b_1,b_2,b_3) \in A^6 :\, a_1-b_1=a_2-b_2=a_3-b_3 >0 \right\}\right|.$

The proof is based on double counting $E_3(A)$. For $\delta\in {\mathbb R}$, let $m_\delta = \left|\left\{(a,b)\in A^2 : a-b = \delta\right\}\right|$. That is, $m_\delta$ is the number of representations of $\delta$ as a difference of two elements of $A$. Note that the number of 6-tuples that satisfy $a_1-b_1=a_2-b_2=a_3-b_3$ is $m_\delta^3$. A simple application of Hölder ‘s inequality implies

$E_3(A) = \sum_{\delta>0} m_\delta^3 \ge \frac{n^6}{|A-A|^2}.$

To obtain a lower bound for $|A-A|$, it remains to derive an upper bound for $E_3(A)$.

For $j\in {\mathbb N}$ let $k_j$ denote the number of differences $\delta \in {\mathbb R}^+$ such that $m_\delta \ge j$. A dyadic decomposition gives

$E_3(A) = \sum_{\delta>0} m_\delta^3 = \sum_{j=1}^{\log n} \sum_{\substack{\delta>0 \\ 2^j \le m_\delta < 2^{j+1}}} m_\delta^3< \sum_{j=1}^{\log n} k_{2^j} 2^{3(j+1)}. \qquad \qquad \qquad (2)$

For $j\in {\mathbb N}$ let $\Delta_j$ denote the set of $\delta>0$ with $m_\delta\ge j$ (so $|\Delta_j| = k_j$). For $\delta >0$, let $A_\delta$ be the set of points that participate in at least one of the representations of $\delta$. If there exist $\delta_1,\delta_2, \delta_3$ such that $|A_{\delta_1} \cap A_{\delta_2} \cap A_{\delta_3}| \ge k/4$, then there exist a subset $A'\subset A$ with $|A'|=k$ and $|A'-A'|< \binom{k}{2}-\frac{3k}{4}+13$ (see the paper for a full explanation). Thus, for every $\delta_1,\delta_2, \delta_3$ we have that $|A_{\delta_1} \cap A_{\delta_2} \cap A_{\delta_3}| < k/4$.

We have $k_j$ sets $A_\delta$ with $|A_\delta| \ge j$. These are all subsets of the same set $A$ of size $n$, and every three intersect in fewer than $k/4$ elements. We now have a set theoretic problem: How many large subsets can $A$ have with no three having a large intersection. We can use the following counting lemma (for example, see Lemma 2.3 of Jukna’s Extremal Combinatorics) to obtain an upper bound on $k_j$.

Lemma 2. Let $A$ be a set of $n$ elements and let $d\ge 2$ be an integer. Let $A_1,\ldots,A_k$ be subsets of $A$, each of size at least $m$. If $k \ge 2d n^d/m^d$ then there exist $1\le j_1 < \ldots < j_d \le d$ such that $|A_{j_1}\cap \ldots \cap A_{j_d}| \ge \frac{m^d}{2n^{d-1}}$.

Lemma 2 implies the bound $k_j = O(n^3/j^3)$ for large values of $j$. Combining this with $(2)$ and with a couple of standard arguments leads to $E_3(A) = O(n^{10/3})$. Combining this with $E_3(A) \ge \frac{n^6}{|A-A|^2}$ implies $|A-A|=\Omega(n^{4/3})$. $\Box$