On constant-multiple-free sets contained in a random set 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 on estimating the maximum possible size of $r$-multiple-free sets contained in $[n]:=1,2,...,n$ has been studied for its own interest in combinatorial number theory and application to coding theory. Let $a$, $b$ be positive integers such that $a<b$ and the greatest common divisor of $a$ and $b$ is 1. Wakeham and Wood showed that the maximum size of $(b/a)$-multiple-free sets contained in $[n]$ is $\frac{b}{b+1}n+O(\log n)$. In this paper 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$.

arXiv comment9 pages, 1 figure, Abstract was modified