On the Spectrum of Maximal \(k\)-Multiple Free Sets of Integers

A set of integers is \(k\)-multiple-free if it never contains two integers \(x\) and \(kx\), where \(k\) is a given integer greater than \(1\). Such a set \(S\) is maximal in \([1,n] = \{1,2,\dots,n\}\) if \(S \cup \{t\}\) is not \(k\)-multiple free for any \(t\) in \([1,n] \setminus S\). In this paper we investigate the size of maximal \(k\)-multiple-free subsets of \([1,n]\), prove that the smallest such set has \(\frac{(k^5-k^3+1)n}{k(k+1)(k^3-1)}+ 0(\log n)\) members, and show that given \(k\) and \(n\), if \(s\) is any integer between the minimum and maximum possible orders, there is a maximal \(k\)-multiple-free subset of \([1,n]\) with \(s\) elements.