Sums in the grid Original Research Article

Let A and B be down-sets in the grid [k]n = {0, … , k − 1}n. Given the sizes of A and B, how small can A + B = {a + b ϵ [k]n: a ϵ A, b ϵ B} be? Our main aim in this paper is to give a best-possible lower bound for | A + B | in terms of | A | and | B |. For example, although if | A | = | B | = kn−1 we may have | A + B | = kn−1, we show that if | A | = | B | = kn−1 + 1 then | A + B | ⩾ 2kn−1 + 1.