An algorithm for complements of finite sets of integers

Abstract:

Let ${A_k} = \{ 0,{a_2},{a_3}, \ldots ,{a_k}\}$ and $B = \{ 0,{b_2},{b_3}, \ldots \}$ be sets of nonnegative integers of $k$ elements and infinitely many elements, respectively. Suppose $B$ has asymptotic density $x:d(B) = x$. If, for every integer $n \geqq 0$, we can find ${a_i} \in {A_k},{b_j} \in B$ such that $n = {a_i} + {b_j}$, then we say that ${A_k}$ has a complement of density $\leqq x$. Given ${A_k}$ and $x$ there is no known algorithm for determining if such a set $B$ exists. We define regular complement and give an algorithm for determining if $B$ exists when complement is replaced by regular complement. More precisely, given ${A_4}$ and $x = 1/3$ we give an algorithm for determining if ${A_4}$ has a regular complement $B$ with density $\leqq 1/3$. We relate this result to the Conjecture. Every ${A_4}$ has a complement of density $\leqq 1/3$.