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.

  • $\begingroup$ 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. $\endgroup$
    – LSpice
    Mar 23 '18 at 17:23
  • $\begingroup$ 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... $\endgroup$ Mar 23 '18 at 18:50
  • $\begingroup$ Do you know a construction of a specific set $A$ for a given $\epsilon>0$ with this property? $\endgroup$ Mar 23 '18 at 19:06
  • $\begingroup$ 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$). $\endgroup$ 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.