# 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.

• I find it hard to parse this question in general (what does it mean to ask "whether there are such $f$ altogether"? What does it mean to ask about functions on $A$ with $A$ left unspecified?), but particularly I am not clear on what the title means, or whether it asks the same question as the body. – LSpice Mar 23 '18 at 17:23
• The question I want answered is: for which A is there an f such that...? The question I can answer is, essentially: given a pi (partially describing how f and + interact), find all f and A such that... – H A Helfgott Mar 23 '18 at 18:50
• Do you know a construction of a specific set $A$ for a given $\epsilon>0$ with this property? – Thomas Bloom Mar 23 '18 at 19:06
• Well, the above procedure gives plenty of examples. For concreteness, you can take $A$ to be the first $n$ elements of the Fibonacci sequence. Then define $f(x)$ to be the Fibonacci number that comes right after $x$ (or $1$, if $x$ is the largest element of $A$). – H A Helfgott Mar 23 '18 at 22:26

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$.