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.)
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.
We can see that $x$ must not divide the product of the other elements of $S$ because if it does,$$\mathrm{gcd}\bigg(x,\prod_{y\in S\setminus\{x\}}y\bigg)=x\geq \frac{x}{k}$$ for every $k\geq 1$ .Erdos has proved that every set $S$ with the above property must have $\pi(n)$ elements at most.
"Let $a_n$ be a sequence of positive integers with $1<a_1<\cdots<a_n\leq N$ which has the property:
(A) $a_i\nmid \frac{a_1\cdot a_2\cdots a_n}{a_i}$ for every $i=1,...,n$ .Then $n\leq \pi(N)$ holds"
(As it was asked) here is the
proof: We will see that if a proper choise of maximum number of elements not exceeding $n$ with the mentioned property exists,then we can construct another (equivalent) set of elements containing only prime powers.
Suppose that the maximum number of elements we can choose from $\{2,...,n\}$ with the mentioned property is $r\geq \pi(n)+1$.
It is impossible to have all elements prime powers because by the pigeonhole principle there will be 2 elements $p^a,p^b$ with $a<b$ and $p^a|p^b$ which means that the desired property does not hold for $p^a$.
So,there must be at least one element that can be written as $x=k\cdot m$ with $\gcd (k,m)=1$.
If $k$ does not divide the product of the rest elements and so does $m$, then we can pull out $x$ from the set and place $k$ and $m$ into the set ,having a new set with $r+1$ elements with property (A) holding true.
(of course no other of the elements is equal to $k$ or $m$ because this would again lead to a contradiction)
But this is a contradiction since $r$ is the maximum number of elements as we assumed.
So,without loss of generality we may assume that $k$ does not divide the product of the rest,but $m$ does.
This means that we can replace $x$ with $k$ in the set with property A) holding true.
We repeat the argument again until $k$ "drops" to a prime power.
( which lets us arrive at a contradiction for prime powers as we already mentioned at the beggining)
(By the way this is not Erdos's proof but one i found some years ago.But i am almost sure Erdos proved this theorem)
So, your set must have at most $\pi(n)$ elements.
On the other hand, if your set contains at least $\pi(n)+1$ elements it could contain 2 powers of the same prime,$p,p^m$ and so the gcd you want would be at least $x=p$ (or $x=p^m$).
I think it would be more difficult to determine the asymptotic size of $S$ depending on $k$ but certainly $|S|\leq\pi(n)$ holds for a random set $S$ as you require.
