# additive combinatorics – An intriguing inverse sumset problem

Start with a natural number $$k$$, and choose natural numbers $$K={n_1,ldots,n_k}$$ which are pairwise distinct. For each $$1leq jleq k$$, choose another integer $$i_j$$ such that $$0leq i_jleq n_j$$.

Question : What is the minimum size of the set $$A={i_1,n_1-i_1, i_2,n_2-i_2,ldots, i_k,n_k-i_k}$$ ?

I did some googling and found the term “sumset” kept floating around in my search results. As I am entirely new to the additive combinatorics and additive number theory, I was totally lost and couldn’t make out how to solve my problem.

I did find a neat geometric (graph theoretic) interpretation to my problem.

Graph Theoretic Interpretation

Suppose that we have $$2k$$ points arranged in a $$k times 2$$ array. It is easier to think of this as a $$ktimes 2$$ matrix $$A=(a_{(j,epsilon)})$$ where $$epsilonin{1,2}$$ and $$1leq jleq k$$. The points are arranged in such a way that $$a_{(j,1)} = i_j$$ and $$a_{(j,2)} = n_j-i_j$$. Now we draw lines between two points if and only if they are equal. Now, without loss of generality, after re-indexing the $$n_j$$‘s and substituting $$i_jmapsto n_j-i_j$$ if necessary, we can assume that the lines are either horizontal or vertical. Furthermore, since the $$n_j$$‘s are pariwise distinct, we cannot have the following different types of structures,

1. Any type of rectangle which has at least three sides (that is in any orientation)
2. Two vertical lines, that is amounting to $$a_{(j,1)} = a_{(j+1,1)}$$ and $$a_{(j,2)} = a_{(j+1,2)}$$

What you get after joining is a disjoint union of lines and points. The size of the set in question is now the number of disjoint components in the resulting diagram. I did some examples by hand and I am getting the minimum size of the set to be of the order of $$k/4$$. But,

Here is an interesting example

Fix a large $$Xgg 0$$, and choose $$n_j$$‘s to be precisely all those integers less than $$X$$ which can be written as sum of two squares, and choose $$i_j$$ such that both $$i_j$$ and $$n_j-i_j$$ are perfect squares. Clearly in this case, $$|K| sim X/sqrt{log(X)}$$ from a classical result of Landau (which I am currently unable to find the reference for) and $$|A| sim sqrt{X}$$

Any help is appreciated.

Thank you…

Posted on Categories Articles