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.


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



How many DISTINCT vectors we get from pairs v_i + v_j for some set of given  vectors v_i ? 
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. 


