Notes and Computations on Forbidden Differences

Abstract

We explore from several perspectives the following question: given a set of integers, X,  and a positive integer, N, what is the maximum size, D(X,N), of a subset, A, contained in {1,2,...,N}, before A is forced to contain two distinct elements that differ by an element of X? The set of forbidden differences, X, is called intersective if D(X,N)=o(N), with the most well-studied examples being the set of perfect squares, S, and the set numbers one less than a prime, P-1. In addition to some new results, including exact formulas and estimates for D(X,N) in some non-intersective cases like X=P and X=S+k for some small positive integers, k, we also provide a comprehensive survey of known bounds and extensive computational data. In particular, we utilize an existing algorithm for finding maximum cliques in graphs to determine D(S,N) for all N up to 300, and D(P-1,N) for all N up to 500. None of these exact values appear previously in the literature.