Additive combinatorics

by

A Basic Question About Multiplicative Energy

As part of some research project, I got to a basic question about multiplicative energy. Embarrassingly , I wasn’t able to get any non-trivial bound for it. Here is the problem. Any information about it would be highly appreciated.

Problem. Let A=\{1,2,3,\ldots,n^{1/2}\} . Let B be a set of n real numbers. How large can the multiplicative energy E^\times(A,B) be?

  • Can we prove that E^\times(A,B) must be asymptotically smaller than n^{2} ?
  • Is there a B for which E^\times(A,B) is asymptotically larger than n^{3/2} ?

Both questions are about improving the exponent of n . Sub-polynomial improvements would be less interesting. Multiplicative energy means

E^\times(A,B) = |\{(a,a',b,b')\in A^2\times B^2\ :\ ab=a'b'\}|

Any ideas?

Isn’t this supposed to be an easy problem?!

A variant. Still here and want to read more? We can also consider the case when A is larger. Let A=\{1,2,3,\ldots,n^{\alpha}\} , where 1/2 < \alpha <1 .

In this case, a simple argument leads to an upper bound that is better than the trivial one. Let r_A(x) = |\{(a,a')\in A^2:\ a/a'=x \}| . The Cauchy-Schwarz inequality implies that

E^\times(A,B) = |\{(a,a',b,b')\in A^2\times B^2\ :\ a/a'=b'/b\}|

= \sum_{x\in A/A} r_A(x) \cdot r_B(x) \le \sqrt{\sum_{x}r_A(x)^2} \cdot \sqrt{\sum_x r_B(x)^2}

=\sqrt{E^\times(A) \cdot E^\times(B)}

It is not difficult to show that E^\times(A)=\Theta(n^{2\alpha}) , up to sub-polynomial factors. This implies that E^\times(A,B)=O(n^{3/2+\alpha}) , up to sub-polynomial factors. In this case, the trivial upper bound is E^\times(A,B)=O(n^{1+2\alpha}) .

The above still leaves a large gap between the lower bound O(n^{1+\alpha}) and the upper bound E^\times(A,B)=O(n^{3/2+\alpha}) , up to sub-polynomial factors.

Any ideas?

by

Mathematical Energy: Etymology

This might be the silliest post I’ve written so far (yes – worse than “Was Disney trying to kill mathematicians?”). I urge you to stop reading now unless (i) you are quite familiar with the mathematical notion of energy (e.g., additive energy), and (ii) you have a horrible sense of humor.

The term energy was coined by Tao and Vu. I like “energy” as a name for this object, but I never had a good answer when asked why this is how it’s called. That is, until a referee report provided me with an answer. And this wonderful referee probably didn’t even know it.

In a recent paper, Cosmin Pohoata and I used “color energy”. We have a graph G=(V,E) with colored edges. Denote the color of an edge (v_1,v_2) as \chi(v_1,v_2) . The color energy of G is

E(G) = \left|\left\{(v_1,v_2,v_3,v_4)\in V^4 :\ \chi(v_1,v_2) = \chi(v_3,v_4) \right\}\right|.

The referee complained about our notation for the multiplicity of a color c (the number of edge of color c ), and asked to change it to m_c . After this change of notation, the energy is defined by the standard formula

E = \sum m_c^2.

by

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…)

zeevCosmin
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

by

Additive Energy of Real Point Sets

Over the years, more and more interactions between Discrete Geometry and Additive Combinatorics are being exposed. These include results such as the Green–Tao ordinary lines theorem and Solymosi’s sum-product bound. One reason for this connection is that both fields study the structure and symmetries of various objects (such as sets of points or subsets of additive groups). In this post I will discuss one of the simplest connections between the two fields — studying the additive energy of a set of points in a real space {\mathbb R}^d . The main goal of the post is to present two open problems that involve the additive energy of such sets. I heard one of these problems from Nets Katz and the other from Ciprian Demeter. In future posts we might discuss more involved interactions between the two fields.

demeterckatz
Ciprian Demeter and Nets Katz.

Continue reading →

by

Additive Combinatorics Lecture Notes (part 2)

I finished my additive combinatorics class, and placed all of the lecture notes in the pdf files page. This quarter was rather short and I did not get to do several topics I had in mind. Perhaps I’ll add notes for some of these at some point. For now, let me just list the chapters that did not appear in the previous post.

  • Chapter 4 is about arithmetic progressions in dense sets. It includes Behrend’s construction, Meshulam’s theorem, and Roth’s theorem. Due to the recent developments, Meshulam’s theorem already seems somewhat outdated…
  • Chapter 5 consists of Sander’s proof of the quasi-polynomial Freiman-Ruzsa theorem in {\mathbb F}_2^n (following Lovett’s presentation). This includes proving a special case of the probabilistic technique of Croot and Sisask.
  • Chapter 6 presents the technique of relying on the third moment energy. It then uses this technique to study convex sets. I hope to also add a variant of the Balog-SzemerĂ©di-Gowers theorem.