Suppose $A$, $B$ are finite sets of positive integers. 


Let $$\mathcal{S}\_n = \{C \subset [1,n] \, : \, A+C = B+C \}, $$ and denote $a\_n = |\mathcal{S}\_n|$.


Note that for any $X \in \mathcal{S}\_n$ and $Y \in \mathcal{S}\_m$, the set $X \cup (Y+n) \subset [1,m+n]$ is in $\mathcal{S}\_{m+n}$, hence $a\_m \cdot a\_n \le a\_{m+n}$ for all $m$, $n$. 


By Fekete's Lemma, it follows that $$m(A, B) := \lim\_{n\to\infty} \sqrt[n]{a\_n}$$ exists and is finite, in particular $0\le m(A, B) \le 2$.


If $A$ and $B$ do not have the same least and greatest elements, then $m(A,B) = 0$; if they do, then $m(A,B) \ge 1$. If $A = B$, then $m(A,B) = 2$. 



> 
> What can we say about $m(A,B)$ in general? Can we compute it given $A$ and $B$?
> 
> 
> 



Limit measuring failure of sum-set cancellability
$m(A,B)$ may be computed as follows. By translation we may assume that $A,B \subset [1,k]$ for some natural number $k$.


Let $V = 2^{[1,k]}$ denote the power set of $[1,k]$. Observe that a subset $C$ of $[1,n]$ can be identified with a sequence $v\_1, v\_2, \dots, v\_{n+k+1}$ in $V$ by setting $v\_i := \{ j \in [1,k]: i-j \in C \}$. This sequence has the properties that $v\_1 = v\_{n+k+1} = \emptyset$ and each $v\_{i+1}$ is a shift of $v\_i$ in the sense that
$$ (v\_{i+1} \cap [2,k]) = (v\_i \cap [1,k-1]) + 1.$$
Conversely, any sequence $v\_1, v\_2,\dots,v\_{n+k+1} \in V$ with these properties uniquely determines a subset $C$ of $[1,n]$.


To put it another way, if we let $E \subset V \times V$ denote the set of pairs $(v,v')$ of elements $v,v'$ of $V$, such that $v'$ is a shift of $v$ (in the above sense), then the subsets $C$ of $[1,n]$ can be placed in one-to-one correspondence with the paths of length $n+k$ from the vertex $\emptyset$ to itself in the directed graph $G = (V,E)$.


Let $V'$ denote the collection of sets $v \in V$ with the property that
$$ k+1 \in A + v \iff k+1 \in B + v;$$
equivalently, $v$ is either contained in both $k+1-A$ and $k+1-B$, or is disjoint from both $k+1-A$ and $k+1-B$. By chasing all the definitions, we see that a set $C \in [1,n]$ lies in ${\mathcal S}\_n$ if and only if the associated path $v\_1,\dots,v\_{n+k+1} \in V$ lies entirely in $V'$. Thus, $a\_n$ is just the number of paths of length $n+k$ from $\emptyset$ to itself in the induced directed graph $G' = (V', E \cap (V' \times V'))$.


We can restrict from $V'$ to the subset $V''$, defined as the set of vertices in $V'$ that are both reachable in $G'$ from $\emptyset$ and from which one can reach $\emptyset$ in $G'$; we can then restrict to the induced subgraph $G'' = (V'', E \cap (V'' \times V''))$. We then have the formula
$$ a\_n = e^T A^{n+k} e$$
where $A$ is the $|V''| \times |V''|$ adjacency matrix of $G''$ (labeling the vertices of $V''$ arbitrarily) and $e$ is the basis vector associated to the vertex $\emptyset$. By Perron-Frobenius (noting from construction of $V''$ that $A$ is irreducible), $a\_n^{1/n}$ then converges to the largest eigenvalue of $A$, which is a quantity that can be computed. Thus for instance, $m(A,B)$ will always be an algebraic integer of degree at most $2^k$.


