Sets $A$ stable under $(x,f(x))\mapsto x+f(x)$ Let $A$ be a finite set of real numbers or integers. We know how to characterize, broadly speaking, sets $A$ such that $A+A$ is not much larger than $A$ (Freiman's theorem). I have a question that feels somewhat related but may or may not be.
What are the sets $A$ such that there is a bijection $f:A\mapsto A$ for which $$\left|\{x+f(x): x\in A\}\cap A\right|\geq (1-\epsilon) |A|,$$
where $\epsilon$ is small? In particular, if $A$ is an interval in the integers (say, $A =\{1,\dotsc,n\}$, or $A=\{-n,-n+1,\dotsc,n\}$), is there such a bijection $f$?
The related question of whether there are such $f$ altogether (with $A$ being initially unspecified) is easily settled. See below. The answer does imply that there are very many sets $A$ for which there are such $f$, but it is unclear to me whether there is a good characterization of such sets $A$ (and whether, say, $A$ can be an interval in the integers).

Require that $f$ be not just a bijection but (seen as a permutation) a long cycle. (This is not a very restrictive assumption; in fact, it is very easy to see that, if $f$ does not have many short cycles, it can be easily modified at $\epsilon |A|$ places so that it satisfies the assumption.) So, let us order the elements of $A$ (which is still an unspecified set with $n$ elements) in the following way: 
$$x_1,\; x_2 = f(x_1),\; x_3 = f(x_2),\;\dotsc,\; x_n = f(x_{n-1}).$$
Then there is a permutation $\pi$ of $\{1,2,\dotsc,n\}$ such that $$x_i+f(x_i) = x_{\pi(i)}$$ for almost all $1\leq i\leq n$ (meaning: $(1-\epsilon) n$ values of $1\leq i\leq n$). In other words $$x_i + x_{i+1} = x_{\pi(i)}$$ for almost all $1\leq i\leq n$. 
Now we see that, for any permutation $\pi$, we have a system of $(1-\epsilon) n$ linear equations in $n$ variables, and thus we must have a solution - an $(\epsilon n)$-dimensional space of solutions, in fact. Checking that there are few repetitions among the variables $x_i$ should take some work, but that should be generically the case.
 A: I'll address the special cases $A = [-n, n]$ and $A = [n]$.  
For $A = [-n, n]$ we can always find a bijection where all the sums are distinct and in the correct range: map $[-n,0]$ to $[0,n]$ and $[1,n]$ to $[-n, -1]$, preserving order in each case.
For $A = [n]$ the maximum size of the intersection is probably $\lfloor \frac{2n-1} 3 \rfloor$ (which holds for $n \leq 14$ by exhaustive search).  When $n = 3k-1$ this is $2k-1$, which can be achieved by mapping $[k]$ to $[k, 2k-1]$ and $[k+1,2k-1]$ to $[k-1]$, preserving order in each case.  I'll show that $2k-1$ is also an upper bound for the size of the intersection when $n=3k-1$.
I'll restate the problem as follows.  Let $T = \{(x, y, z) \in [n]^3 : x + y = z) \}$.  We seek to bound the size of a subset $S$ of $T$ such that the projections of $S$ onto the $x$, $y$ and $z$ coordinates are injective.  
For each $j \in [3k-1]$, write


*

*$X_j = \{(x,y,z) \in S : x \leq j)\}$.

*$Y_j = \{(x,y,z) \in S : y \leq j\}$.

*$Z_j = \{(x,y,z) \in S : z \geq 3k-j\}$.


Observe that $|X_j|, |Y_j|, |Z_j| \leq j$.
Let $W$ be the multiset union of $X_1, \ldots, X_{2k-1}, Y_1, \ldots, Y_{2k-1}, Z_1, \ldots, Z_{2k-1}$.  I claim that this contains at least $3k$ copies of every element of $T$.  Indeed, if $x, y \leq 2k$ and $z \geq k$, then $(x,y,z)$ is in $X_x, X_{x+1}, \ldots, X_{2k-1}, Y_y, Y_{y+1}, \ldots, Y_{2k-1}, Z_{3k-z}, Z_{3k-z-1}, \ldots, Z_{2k-1}$, which is a total of $(2k-x) + (2k-y) + (z-k) = 3k$ sets.
The other three cases ($x > 2k$, $y > 2k$, $z < k$) are mutually exclusive.  If $x > 2k$, then $(x,y,z)$ is in $Y_y, Y_{y+1}, \ldots, Y_{2k-1}, Z_{3k-z}, Z_{3k-z-1}, \ldots, Z_{2k-1}$, which is a total of $(2k-y) + (z-k) = k+x > 3k$ sets.  Similarly, if $y > 2k$, then $(x,y,z)$ is in $k + y > 3k$ sets.  Finally, if $z < k$, then $(x,y,z)$ is in $X_x, X_{x+1}, \ldots, X_{2k-1}, Y_y, Y_{y+1}, \ldots, Y_{2k-1}$, which is a total of $(2k-x) + (2k-y) = 4k-z > 3k$ sets.
It follows that
$$ 
3k|S| \leq \sum_{j=1}^{2k-1} (|X_j| + |Y_j| + |Z_j|) \leq 3 \sum_{j=1}^{2k-1} j = \frac {3(2k)(2k-1)} 2,
$$
and therefore $|S| \leq 2k-1$, as claimed.

We can also read structural information about the sets $S$ achieving this upper bound out of the proof.  If $|S| = 2k-1$ then the inequalities in the preceding display must be equality; for example, none of the $(x,y,z) \in T$ that appear in more than $3k$ of the $X_j, Y_j, Z_j$ can be in $S$.
