If $\vert A + A \vert = 2\vert A \vert - 1,$ then is $A$ an arithmetic progression?

Question

For $n\in\mathbb{N},$ define $[n]:= \{ 0, 1, 2,\ldots, n-1\}.$

Suppose $A$ is a finite subset of $\mathbb{Z}$ such that $\vert A + A \vert = 2\vert A \vert - 1,$ where $\ A+B$ means the Minkowski sum of sets $A$ and $B.$

Proposition: there exists $T\in\mathbb{N},\ m\in\mathbb{Z},$ such that $A = \lbrace{Tn + m: n \in [A] \rbrace}.$ In other words, $A$ is an A.P. (arithmetic progression) of length $\vert A \vert.$

The reason we can do this in $\mathbb{Z}$ and not just $\mathbb{N}$ is because if $A$ is a A.P. (arithmetic progression) of length $k,$ and $n\neq 0,$ then $\{na+m: a\in A\}$ is also an A.P. of length $k.$ (This is easy to check).

Attempt: First, note that if $B$ is an A.P. of length $k,$ then $\vert B+B \vert = 2k-1 = 2\vert B \vert - 1.$

Next, if $\vert A + A \vert = 2\vert A \vert - 1,$ then the longest A.P. of $A$ cannot have length $k > \frac{2\vert A\vert}{3},$ since the existence of a member of $A$ not in the longest A.P. of $A$ will mean that $\vert A + A \vert \geq (2k-1) + k = 3k-1 > 3 \frac{2\vert A\vert}{3} -1 = 2\vert A\vert - 1.$ But this is all I have deduced about this problem and now I am stumped.

I came up with the question myself and don't know if the proposition is true or has a counterexample. I didn't come up with a counter-example for when $\vert A\vert$ is small, and I don't see how to use induction, but it's possible I'm missing something "obvious". I was unable to find a duplicate question.

Answer 1

As has been pointed out in other answers, the minimum possible value of $\vert A + A \vert $ is $2\vert A\vert - 1.$

Thus the contrapositive of the proposition is equivalent to: if $A$ is not an A.P., then $\vert A + A\vert\geq 2\vert A\vert, $ which I prove presently.

Let $P(n)$ be the statement:

If $x_1 < x_2 < \ldots < x_n$ do not form an A.P., then $\vert A + A \vert \geq 2\vert A \vert.$

First we verify the basis case, $n=3.$ If $\vert A \vert = 3,$ then $A = \{x_1, x_2, x_3\}$ for some $x_1<x_2<x_3.$ If $A$ is not an arithmetic progression, then $x_3 \neq x_1 + 2(x_2-x_1) = 2x_2-x_1.$ Thus we have: $x_1 + x_1 < x_1 + x_2 < x_2 + x_2 < x_2 + x_3 < x_3 + x_3\ $ are five distinct members of $A+A.$ Also, since $x_3 \neq 2x_2-x_1, $ it follows that $ x_3 + x_1 \neq 2x_2.$ In particular, either $x_1 + x_2 < x_1 + x_3 < x_2 + x_2$ or $ x_2 + x_2 < x_1 + x_3 < x_2 + x_3.$ In either case, $x_1 + x_3$ is in an interval where there are no other members of $A+A,$ and so $x_1 + x_3$ is a distinct member of $A+A$ also. Therefore, $\vert A + A \vert\geq 6 = 2\vert A \vert,$ thus verifying the basis case.

Now we prove the induction step.

Suppose $P(n)$ is true for an integer $n\geq 3.$

Suppose further that $ A = \{ x_1, x_2, \ldots, x_n, x_{n+1}\}$ where $ x_1 < x_2 < \ldots < x_n < x_{n+1}$ are real numbers that do not form an A.P.. We aim to show that $\vert A + A \vert \geq 2\vert A \vert.$

Either the first $n$ terms, $x_1, x_2, \ldots, x_n$ form an A.P., or they don't. We consider the two cases separately.

If $x_1, x_2, \ldots, x_n$ forms an A.P., then let $d:=x_2-x_1.$ Since $x_1, x_2, \ldots, x_n, x_{n+1}$ do not form an A.P., then $x_{n+1}$ can be anything $> x_n$ other than $x_n+d.$ Either $x_n < x_{n+1} < x_n + d,\ $ or $\ x_{n+1} > x_n + d.$ If $ x_n < x_{n+1} < x_n + d,\ $ then $\ \vert \{ x_{n+1} + x_j: j\in\{1,2,\ldots,n+1\}\ \}\vert = n+1\geq 3,\ $ since $\ n\geq 3.$ Else if $\ x_{n+1} > x_n + d,\ $ then all three of $\ x_{n+1} + x_{n-1},\ x_{n+1} + x_n,\ $ and $\ x_{n+1} + x_{n+1}\ $ are not in $A\setminus \{x_{n+1}\} + A\setminus \{x_{n+1}\},\ $ because they are all $\ \geq x_{n+1} + x_{n-1},\ $ which is $\ \geq 2 x_n.\ $ Either way, $\ \vert A + A \vert \geq (2n-1) + 3 = 2n+2 = 2(n+1) = 2\vert A \vert.$

Alternatively, if $x_1, x_2, \ldots, x_n$ do not form an A.P., then by the induction hypothesis, $ \vert A\setminus \{x_{n+1}\} + A\setminus \{x_{n+1}\} \vert \geq 2 \vert A\setminus \{x_{n+1}\} \vert = 2n.\ $ Now, since $\ x_{n+1} > x_n > \ldots > x_2 > x_1,$ it must be the case that $x_{n+1} + x_n$ and $x_{n+1} + x_{n+1}$ are both distinct numbers, both not in $A\setminus \{x_{n+1}\} + A\setminus \{x_{n+1}\}.\ $ Therefore, $\ \vert A+A \vert = \vert \left( ( A\setminus \{x_{n+1}\}) \cup \{x_{n+1}\} \right) + \left( ( A\setminus \{x_{n+1}\}) \cup \{x_{n+1}\} \right) \vert = \underbrace{\vert A\setminus \{x_{n+1}\} + A\setminus \{x_{n+1}\} \vert}_{\geq 2n} + \underbrace{ \vert \{ x_{n+1} \} + A \vert}_{\geq 2} \geq 2n + 2 = 2(n+1) = 2\vert A \vert.$

This proves the induction step and completes the proof.

Answer 2

I think I've found a proof.

First of all, $|S+S| \ge 2|S|-1$ for all finite $S \subseteq \mathbb{Z}$: write $S = \{s_1, \ldots, s_n\}$, where $s_1 < \ldots < s_n$. Then $S+S = \{s_1, \ldots, s_n\} + \{s_1, \ldots, s_n\}$ is a superset of $\{s_1+s_1, s_1+s_2, \ldots, s_1+s_n, s_2+s_n,\ldots, 2s_n\}$ which has $2|S|-1$ distinct elements.

Let $n$ be the cardinality of $A$. We proceed by induction on $n$. The base case is where $n=2$: then $A$ is trivially an arithmetic progression.

Otherwise, let $A = \{a_1,\ldots,a_n\}$ where $a_1 < \ldots < a_n$. Let $B=A \setminus \{a_1\}$. Then $A+A = \{2a_1, a_1+a_2, \ldots, a_1+a_n\} \cup (B+B)$. Since neither $2a_1$ nor $a_1+a_2$ can be elements of $B+B$, $|B+B| \le |A+A|-2 = 2|B|-1$, which by the lemma above means that $|B+B| = 2|B|-1$. By the induction hypothesis, $B$ is an arithmetic progression. Also, this means that $a_1+a_i$ for $3 \le i \le n$ must be elements of $B+B$. We must have $a_1+a_3=2a_2$ (since $a_1+a_3 < a_2+a_3$), which implies that $A$ must have been an arithmetic progression as well.

Answer 3

Let's consider a small case $k=4$, $A = \{a,b,c,d\}$ with $a < b < c < d$. The Minkowski sum $A + A$ has already at least $2k-1=7$ unique elements: $$a+a < a+b < b+b < b + c < c + c < c + d < d + d.$$ If we want that $|A+A| = 2|A|-1$ it must be that all other summations in the Minkowski sum are equal/match to one of the above. Thing is, for example, the sum $a + c$ can only ever be matched by $b + b$ in the above sequence: $a + b$ is already too small, and $b + c$ is already too big. We can apply the same argument to $b+d$: it can only match with $c+c$. From these 2 observations we already know that both $a < b < c$ and $b < c < d$ form an arithmetic progression, and so $a < b < c < d$ form an arithmetic progression. The generalization to any case is, I hope, straightforwardly seen from here.

Let $A=\{a_1,\dots,a_n\}$ with $a_1 < \dots < a_n$. We identify the following $2k-1$ elements in $A+A$: $$a_1+a_1 < a_1+a_2 < a_2+a_2 < \dots < a_n+a_n.$$ Consider $a_i + a_{i+2}$ for $1 \leq i \leq k-2$. It has to equal $2a_{i+1}$. We thus have that $a_i < a_{i+1} < a_{i+2}$ form an arithmethic progression for all $i$. Since all these progression overlap we have that all $a_j$'s form an arithmetic progression.