Limit measuring failure of sum-set cancellability

Question

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

Answer 1

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