# Example of sets with additive property

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 :(.

Thanks.

-
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

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.

-