MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Let $\Lambda$ be a lattice (discrete additive subgroup) in $\mathbb R^n$ ($n\geq 2$). In my problem, $\Lambda$ lies in a $k$ dimensional ($1< k\leq n$) subspace of $\mathbb R^n$. Let $A\subset \Lambda$ be a subset with cardinality $|A|=m$. To make it concrete, suppose $A$ is the intersection of $\Lambda$ with a hyper cube centered at origin.

My question is how to find a good upper bound on the size of the sumset $A+A$, in terms of $m,k,n$. More generally, on the size of $hA:=A+A+\ldots+A$.

I know there are theories, in particular additive combinatorics, dealing with the size of sumset. However this problem is more specific (we consider the sumset of set with itself and it lies in a subspace, etc.), hence I suspect there may be a tight upper bound.

Since I am not familiar with this filed at all (I am an engineering student), can someone give some hints or pointers? Any comment is welcome!

share|cite|improve this question
Welcome to MO. What do you mean by "A is an additive subgroup". It cannot be the standard meaning of A being a group, first since it could not be finite and second since then A+A = A and your question would be trivial, so what do you mean with this. This is important. If A would be just any subset and you do not have an additional info beyond what you gave you cannot get a bound better than the immediate (m+1)m/2 for A+A and likewise for hA (except if you fix A and let h grow, then the dimension restriction will eventually be relevant). – user9072 Nov 5 '12 at 11:52
Thanks for the response! You are right, I just wanted to mean that A is a subset of the lattice. To make it concrete, I assume that A is the intersection of lattice with some cube around the origin. – EEstudent Nov 5 '12 at 15:51
Thanks for the clarification. A simple idea to get an upper bound would be to note that if A is contained in the hypercube with side-length s than A+A is contained in the hypercube with lengths 2s and so on, and to count the points in the hypercubes. And, if your lattice is not very distorted this will not be too far from the truth. Put perhaps yours is. – user9072 Nov 5 '12 at 16:02
Yes, I tried the very basic idea before. It may not always give a good upper bound. Let the hypercube has side length s then we have a density of m/(s^n) (lattice points per unit volume), then a hypercube with length 2s will contain 2^n*m points, with a factor 2^n. However, if the lattice lies in 1-dimensional subspace, for example, only taking the points ...(-1,-1,...-1), (0,0,...0), (1,1,...1),(2,2,...2).... and so on. We see A+A has size 2m-1, independent of n. Hence I think the number k should also matter here. Could we get a better bound using volume argument (taking account of k)? – EEstudent Nov 5 '12 at 16:23
Sorry for being imprecise/not more detailed. Yes definitely you should take the fact that all this lives in a subspace into account. Two related strategies: either take only the points in this subspace in these hypercubes. Then the growth should also be like 2^k. Or "forget" the surrounding space R^n altogether. Consider just the k-dim subspace were 'everything' is happening. You then have a (convex) body [the intersection of the cube with the subspace] including all your points in A and A+A will be contained in the 'doubled' body. – user9072 Nov 5 '12 at 16:54

Your Answer


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

Browse other questions tagged or ask your own question.