Fix $n$ and $k$. I want a set $S\subseteq\{1,\ldots,n\}$ with the property that for every $x\in S$,


$$\mathrm{gcd}\bigg(x,\prod\_{y\in S\setminus\{x\}}y\bigg)<\frac{x}{k}.$$


How small should a random $S$ be to have this property with high probability? More importantly, what sort of math is this, and where can I learn more? (I only guessed in my tags.)



Sets whose elements are mutually "weakly" coprime?
Let's just consider the case $k=1$ where the problem asks for sets $S$ such that each element of $S$ does not divide the product of the rest of the elements of $S$. I claim that if $S$ has fewer than $\exp(\frac{1}{10} \sqrt{\log n\log \log n})$ elements then with high probability this happens. On the other hand if $S$ has more than $\exp(10\sqrt{\log n \log \log n})$ elements then with high probability some element of $S$ will divide the product of the remaining elements. With more effort this gap can probably be closed. (Also, as will be seen from the proof the argument also works if $k$ is not too big -- that is in the range $k\le \exp(\frac{1}{10} \sqrt{\log n\log \log n})$ say.)


The reasoning relies on some facts about smooth numbers. Let $\Psi(x,y)$ denote the number of integers up to $x$ all of whose prime factors are below $y$. We are interested in the range when $y$ is about $\exp(c\sqrt{\log x\log \log x})$ for some constant $c$, and here $\Psi(x,y)$ is about size $x\exp(-\sqrt{\log x\log \log x} (\frac{1}{2c}+o(1)))$; moreover the number of squarefree smooth numbers is also of this size. 


I need one more observation. If $s$ numbers are chosen randomly from $1$ to $n$, then their product will very likely be divisible by all primes up to $s/\log n$ -- if not there is a prime $p<s/\log n$ not dividing all these $s$ numbers which happens with probability $(1-1/p)^{s} = O(1/n)$, and there are at most $n/\log n$ such primes $p$, for a total probability of at most $1/\log n$. In the other direction, if $s$ numbers (with $s$ reasonably large) are chosen randomly from $1$ to $n$ then their product is very likely not divisible by $p^2$ for every prime $p>s^3$ say. To see this, if we pick a prime $p>s^3$ then the chance that $p^2$ divides the product is $O(s^2/p^2)$ ($p$ could divide two of the $s$ elements; the probability of dividing $3$ elements is even smaller) and summing this over all $p>s^3$ still gives a total probability of $O(1/s)$. 


Now we are ready for the proof. Suppose $S$ has fewer than $L\_1=\exp(\frac 1{10} \sqrt{\log n\log \log n})$ elements. From our remark on the number of smooth integers, we may see with high probability each element of $S$ is *not* $L\_1^3$ smooth. That is each element of $S$ is likely to be divisible by a prime larger than $|S|^3$. But then as observed above, such a large prime is unlikely to divide two elements of $S$, and therefore with high probability every element of $S$ does not divide the product of the rest. 


For the other assertion, suppose now that $S$ has more than $L\_2 =\exp(10\sqrt{\log n\log \log n})$ elements. From our observation on smooth numbers, with high probability $S$ contains a squarefree number that is $\exp(\sqrt{\log n\log \log n})$ smooth. But with high probability the product of the remaining elements of $S$ is divisible by all primes up to $(|S|-1)/\log n$ which is a good deal bigger than $\exp(\sqrt{\log n\log \log n})$. In other words, the squarefree smooth number that we are likely to find in $S$ will divide the product of the remaining numbers with high probability. 


This completes the proof. Let me add that the shape of the answer $\exp(\sqrt{\log n\log \log n})$ arises in other contexts (e.g. factoring algorithms such as the quadratic sieve) for a similar reason: it is the break even value of $y$ where the probability of being $y$ smooth is roughly $1/y$, and that's roughly what's being used above.


