Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following is a question from Tao and Vu's Additive combinatorics, which I'm stuck at and I could really use some help.

First, a definition: for two sets $X$ and $Y$ define the additive energy $W(X,Y)=|\left\{(a,a',b,b') \in X \times X \times Y \times Y: x+y = x' + y' \right\}|$. Now, the exercise just asks for examples of sets $A$, $B$, $C$ (subsets of an additive group $G$) with $|A|=|B|=|C|=N$ and for which:

1) $W(A,B)$ and $W(A,C)$ are comparable to $N^{2}$ and $W(B,C)$ is comparable to $N^{3}$;

2) $W(A,B)$ and $W(A,C)$ are comparable to $N^{3}$ and $W(B,C)$ is comparable to $N^{2}$.

I've been trying with direct-product-like sets, but with no succes :(.


share|cite|improve this question
Yes, typo. Sorry about that – Anna Apr 9 '12 at 4:27
Have you tried taking G to equal Z mod n for some n? – user28642 Apr 9 '12 at 4:35
Yes, but with no luck. Can you give more details if you found it? – Anna Apr 9 '12 at 4:40
up vote 1 down vote accepted

Let’s try to work in $\Bbb Z$, at least at first: it’s the most familiar additive group.

Clearly $W(A,B)\supseteq\{\langle a,a,b,b\rangle:\langle a,b\rangle\in A\times B\}$, so $|W(A,B)|\ge N^2$. Thus, to get $|W(A,B)|$ comparable to $N^2$, we need to try to arrange matters so that $a+b=a'+b'$ iff $\langle a,b\rangle=\langle a',b'\rangle$. Clearly that’s as small as we can get.

Suppose, on the other hand, that for each $\langle a,b\rangle\in A\times B$ and each $a'\in A$, $a+b-a'\in B$; then each $\langle a,b\rangle\in A\times B$ would generate $N$ members of $W(A,B)$, and $|W(A,B)|$ would be comparable to $N^3$. It’s not too hard to see that this is as large as we can get.

For the first problem, then, we’d like to choose $A,B$, and $C$ so that

  1. for each $\langle a,b\rangle\in A\times B$ and $a'\in A$, $a+b-a'\in B$ iff $a'=a$;

  2. for each $\langle a,c\rangle\in A\times C$ and $a'\in A$, $a+c-a'\in C$ iff $a'=a$; and

  3. for each $\langle b,c\rangle\in B\times C$ and $b'\in B$, $b+c-b'\in C$.

Suppose that $A=\{1,\dots,N\}$. Then for any $a,a'\in A$ we have $-N<a-a'<N$. Suppose now that we can choose $B$ so that if $b$ and $b'$ are distinct members of $B$, then $|b-b'|\ge N$. Now suppose that $\langle a,b\rangle\in A\times B$ and $a'\in A$. If $a+b-a'=b'\in B$, then $a-a'=b'-b$; but $|a-a'|<N$, and $|b'-b|\ge N$ unless $b=b'$, in which case $a=a'$. Thus, such a $B$ would satisfy (1). Is there such a $B$? Sure: just let $B=\{kN:k=1,\dots,N\}$.

If we let $C=B$, (2) is automatically satisfied. (3) isn’t satisfied, but it is true that if $\langle b,c\rangle\in B\times C$, $b'\in B$, and $b+c>b'$, then $b+c-b'\in C$. How many triples $\langle b,c,b'\rangle\in B\times C\times B$ are there such that $b+c>b'$?

It’s actually easier to count the triples with $b+c\le b'$. I leave it to you to verify that there are

$$\begin{align*} \sum_{i=1}^{N-1}i(N-i)&=N\sum_{i=1}^{N-1}i-\sum_{i=1}^{N-1}i^2\\ &=\frac12N^2(N-1)-\frac16N(N-1)(2N-1)\\ &=\frac{N(N-1)}6\big(3N-(2N-1)\big)\\ &=\frac16(N^3-N) \end{align*}$$

of these, and therefore $\frac56N^3+\frac16N$ triples with $b+c>b'$. This should qualify as comparable to $N^3$.

Edit: For the second problem, suppose that $N=2n$ and try

$$\begin{align*} A&=\{1,\dots,n\}\cup\{kn^2:k=1,\dots,n\},\\ B&=\{1,\dots,n\}\cup\{kn^4:k=1,\dots,n\},\text{ and}\\ C&=\{kn^2:k=1,\dots,n\}\cup\{kn^8:k=1,\dots,n\}\;. \end{align*}$$

Try to show that the overlapping parts of $A$ and $B$ and of $A$ and $C$ ensure that $|W(A,B)|$ and $|W(A,C)|$ are at least some fixed multiple of $N^3$, while $B$ and $C$ are related more like my $A$ and $B$ in the first problem.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.