3
$\begingroup$

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

$\endgroup$

1 Answer 1

6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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