On Constant-Multiple-Free Sets Contained in Random Sets of Integers

Abstract

For a rational number \(r > 1\), a set \(A\) of positive integers is called an \(r\)-multiple-free set if \(A\) does not contain any solution of the equation \(rx = y\). The extremal problem of estimating the maximum possible size of \(r\)-multiple-free sets contained in \([n] := \{1, 2, \ldots, n\}\) has been studied in combinatorial number theory for theoretical interest and its application to coding theory. Let \(a\) and \(b\) be relatively prime positive integers such that \(a < b\). Wakeham and Wood showed that the maximum size of \((b/a)\)-multiple-free sets contained in \([n]\) is \( \frac{b}{b+1} + O(\log n)\). In this note, we generalize this result as follows. For a real number \(p \in (0, 1)\), let \([n]_p\) be a set of integers obtained by choosing each element \(i \in [n]\) randomly and independently with probability \(p\). We show that the maximum possible size of \((b/a)\)-multiple-free sets contained in \([n]_p\) is \({\frac{b}{b+p}pn} + O(\sqrt{pn} \log n \log \log n)\) with probability that goes to \(1\) as \(n \to \infty\).