How many DISTINCT vectors we get from pairs v_i + v_j for some set of given vectors v_i ?

Question

Consider some set of vectors v_i i=1...N , v_i \in Z^k.

e.g. N = 10^4; k = 10

Consider all possible sums: v_i + v_j.

Is it possible to estimate how many DISTINCT vectors we get in advance without making summation ? (some algorithm ? what is complexity of this algorithm ?)

Obviously maximal number is N(N+1)/2 - when all obtained vectors are distinct. Minimal number is "1" - when all v_i are equal to each other.

======

The question can be reformulated in other terms: consider polynomial P = \sum_i z^{(v_i)} where z^v means z_1^{(v_1)}z_2{(v_2)}... z_k^{(v_k)}.

Consider P^2. How many monomials we get ? (Is it possible to estimate it looking on P it self).

===

Of course we can ask about growth of triple sums: v_i + v_j + v_k and so forth.

===

Why this is interesting (for me) ? The practical (for me) question is it reasonable to write and start some prog or not ?

If I know that answer is N^4 =10^16 - it will take ~3 years - unreasonable. If I know in advance that we have much smaller number the prog is worth to write and we get result in reasonable time.

If we have some set of vectors w_p p=1...M and we want to analyse how many distinct elements are there we need to make ~M^2 compares. So if w_p = v_i + v_j we need M^2~N^4 compares. But for N=10^4 this is 10^16 which is beyond say "pentium" abilities - 10^16/10^9 = 10^7 seconds ~ 10^4 hours ~ 10^3 days ~ 3 years...

So the task is hopeless and you do not need to start such a program. But if I know in advance that the number of distinct vectors is much smaller, then it is reasonable to wait for the answer.

============

Answer 1

Even the case $k=1$ is interesting. There is much work showing that if the sumset is small then the original set is nearly an arithmetic progression. One early paper on the topic is J H B Kemperman, On small sumsets in an abelian group, Acta Mathematica, Volume 103, Numbers 1-2, 63-88.

EDIT: Here's a much more recent result. Yonutz V. Stanchescu, The structure of $d$-dimensional sets with small sumset, J. Number Theory 130 (2010), no. 2, 289–303, MR2564897 (2010j:11147).

According to reviewer Ping Ding, The author shows the following theorems. Let $K$ be a finite subset of ${\bf Z}^d$ of affine dimension $d\ge2$. If $k=|K|\gt3\times4^d$ and $$|K+K|\lt(d+4/3)|K|−(3d^2+5d+8)/6$$ then $K$ lies on $d$ parallel lines. Conversely, if the set $K$ lies on $d$ parallel lines and $$|K+K|<(d+2)|K|−(d+1)(d+2)/2$$ then the set $K$ is contained in $d$ parallel arithmetic progressions with the same common difference, having together no more than $$v=|K+K|−d|K|+d(d+1)/2$$ terms.

But there are literally dozens of results about these sumsets, many of them due to or building on the work of Gregory Freiman.

Answer 2

Your question is a little unclear, but I take it you want some sort of sampling method that estimates the number of distinct sums.

I'll answer a more general question. This method is not as well known as it should be. Suppose $f:X\to Y~$ where $X=\{x_1,\ldots,x_n\}$ and $Y~$ is some set. You want to estimate $|f(X)|$, the number of distinct function values.

Generate $N~$ elements of $X$, uniformly at random with replacement. Let $K$ be the number of elements $x_i$ in your sample with the property that $f(x_j)\ne f(x_i)$ for every $j<i$. Then the expectation of $K/N$ equals $|f(X)|/n$, so if $N$ is large enough you can estimate $|f(X)|\approx nK/N$.

In your application, the hard part is the test "$f(x_j)\ne f(x_i)$ for every $j<i$ ". You don't need to calculate all sums to do that. You want to find the pairs of vectors with a given sum, so for each first vector do a binary search to find the second. Or something like that, in practice it should be fast with some careful data structure design.

It should also be possible to do it by summing a large random selection of vector pairs then counting the coincidences in their sums. This paper should give hints.