Return to Question

The problem below is suggested by this one.

Suppose that we are given $2k$ integers $x_1,\dotsc,y_k$, and we want to find an integer $a$ so that $\gcd(a+x_i,a+y_i)>1$ for each $i\in[1,k]$. This is certainly possible if the product of any $\kappa$ of the differences $y_i-x_i$ has at least $\kappa$ distinct prime factors, for each $\kappa\in[1,k]$: for, by Hall's theorem, we can then associate with each $i\in[1,k]$ a prime $p_i\mid y_i-x_i$ so that all primes $p_1,\dotsc,p_k$ are pairwise distinct, and then use the Chinese Remainder Theorem to find $a$ subject to $a\equiv -x_i\pmod{p_i}$, $i\in[1,k]$.

Intuitively, I would expect that for the ``random'' choice of $x_1,\dotsc,y_k$ this should be possible. Can something of this sort be proved rigorously?

Fix an integer $k\ge 1$ and choose $z_1,\dotsc,z_k\in[1,N]$ at random, for $N$ large (or consider $[N,2N]$ instead). What is the probability that for every $\kappa\in[1,k]$, the product of any $\kappa$ of the numbers $z_i$ has at least $\kappa$ distinct prime factors?

If $k=1$, then the probability is $1-N^{-1}$ trivially; if $k=2$, then it still seems to be $1-O(N^{-1})$, in a slightly less obvious way. For any fixed $k$, the set of all integers with fewer than $k$ distinct prime factors is known to have zero density (references can be found here); consequently, for $k$ fixed and $N$ growing, with probability $1-o_k(1)$ all of $z_1,\dotsc,z_k$ will have at least $k$ distinct prime factors, whence, of course, the product of any $\kappa$ of them will have at least $k\ge\kappa$ distinct prime factors. Still, it seems to me that much more can be said; maybe, along the following lines:

What is the smallest number of integers to be deleted from $[1,N]$ so that for every choice of $\kappa\le k$ remaining integers, their product has at least $\kappa$ distinct prime factors?

The problem below is suggested by this one.

Suppose that we are given $2k$ integers $x_1,\dotsc,y_k$, and we want to find an integer $a$ so that $\gcd(a+x_i,a+y_i)>1$ for each $i\in[1,k]$. This is certainly possible if the product of any $\kappa$ of the differences $y_i-x_i$ has at least $\kappa$ distinct prime factors, for each $\kappa\in[1,k]$: for, by Hall's theorem, we can then associate with each $i\in[1,k]$ a prime $p_i\mid y_i-x_i$ so that all primes $p_1,\dotsc,p_k$ are pairwise distinct, and then use the Chinese Remainder Theorem to find $a$ subject to $a\equiv -x_i\pmod{p_i}$, $i\in[1,k]$.

Intuitively, I would expect that for the ``random'' choice of $x_1,\dotsc,y_k$ this should be possible. Can something of this sort be proved rigorously?

Fix an integer $k\ge 1$ and choose $z_1,\dotsc,z_k\in[1,N]$ at random, for $N$ large (or consider $[N,2N]$ instead). What is the probability that for every $\kappa\in[1,k]$, the product of any $\kappa$ of the numbers $z_i$ has at least $\kappa$ distinct prime factors?

If $k=1$, then the probability is $1-N^{-1}$ trivially; if $k=2$, then it still seems to be $1-O(N^{-1})$, in a slightly less obvious way. For any fixed $k$, the set of all integers with fewer than $k$ distinct prime factors is known to have zero density (references can be found here); consequently, for $k$ fixed and $N$ growing, with probability $1-o_k(1)$ all of $z_1,\dotsc,z_k$ will have at least $k$ distinct prime factors, whence, of course, the product of any $\kappa$ of them will have at least $k\ge\kappa$ distinct prime factors. Still, it seems to me that much more can be said; maybe, along the following lines:

What is the smallest number of integers to be deleted from $[1,N]$ so that for every choice of $\kappa\le k$ remaining integers, their product has at least $\kappa$ distinct prime factors?

The problem below is suggested by this one.

Suppose that we are given $2k$ integers $x_1,\dotsc,y_k$, and we want to find an integer $a$ so that $\gcd(a+x_i,a+y_i)>1$ for each $i\in[1,k]$. This is certainly possible if the product of any $\kappa$ of the differences $y_i-x_i$ has at least $\kappa$ distinct prime factors, for each $\kappa\in[1,k]$: for, by Hall's theorem, we can then associate with each $i\in[1,k]$ a prime $p_i\mid y_i-x_i$ so that all primes $p_1,\dotsc,p_k$ are pairwise distinct, and then use the Chinese Remainder Theorem to find $a$ subject to $a\equiv -x_i\pmod{p_i}$, $i\in[1,k]$.

Intuitively, I would expect that for the ``random'' choice of $x_1,\dotsc,y_k$ this should be possible. Can something of this sort be proved rigorously?

Fix an integer $k\ge 1$ and choose $z_1,\dotsc,z_k\in[1,N]$ at random, for $N$ large (or consider $[N,2N]$ instead). What is the probability that for every $\kappa\in[1,k]$, the product of any $\kappa$ of the numbers $z_i$ has at least $\kappa$ distinct prime factors?

If $k=1$, then the probability is $1-N^{-1}$ trivially; if $k=2$, then it still seems to be $1-O(N^{-1})$, in a slightly less obvious way. For any fixed $k$, the set of all integers with fewer than $k$ distinct prime factors is known to have zero density (references can be found here); consequently, for $k$ fixed and $N$ growing, with probability $1-o_k(1)$ all of $z_1,\dotsc,z_k$ will have at least $k$ distinct prime factors, whence, of course, the product of any $\kappa$ of them will have at least $k\ge\kappa$ distinct prime factors. Still, it seems to me that much more can be said; maybe, along the following lines:

What is the smallest number of integers to be deleted from $[N,2N]$ so that for every choice of $\kappa\le k$ remaining integers, their product has at least $\kappa$ distinct prime factors?

The problem below is suggested by this one.

Suppose that we are given $2k$ integers $x_1,\dotsc,y_k$, and we want to find an integer $a$ so that $\gcd(a+x_i,a+y_i)>1$ for each $i\in[1,k]$. This is certainly possible if the product of any $\kappa$ of the differences $y_i-x_i$ has at least $\kappa$ distinct prime factors, for each $\kappa\in[1,k]$: for, by Hall's theorem, we can then associate with each $i\in[1,k]$ a prime $p_i\mid y_i-x_i$ so that all primes $p_1,\dotsc,p_k$ are pairwise distinct, and then use the Chinese Remainder Theorem to find $a$ subject to $a\equiv -x_i\pmod{p_i}$, $i\in[1,k]$.

Intuitively, I would expect that for the ``random'' choice of $x_1,\dotsc,y_k$ this should be possible. Can something of this sort be proved rigorously?

Fix an integer $k\ge 1$ and choose $z_1,\dotsc,z_k\in[1,N]$ at random, for $N$ large (or consider $[N,2N]$ instead). What is the probability that for every $\kappa\in[1,k]$, the product of any $\kappa$ of the numbers $z_i$ has at least $\kappa$ distinct prime factors?

If $k=1$, then the probability is $1-N^{-1}$ trivially; if $k=2$, then it still seems to be $1-O(N^{-1})$, in a slightly less obvious way. For any fixed $k$, the set of all integers with fewer than $k$ distinct prime factors is known to have zero density (references can be found here); consequently, for $k$ fixed and $N$ growing, with probability $1-o_k(1)$ all of $z_1,\dotsc,z_k$ will have at least $k$ distinct prime factors, whence, of course, the product of any $\kappa$ of them will have at least $k\ge\kappa$ distinct prime factors. Still, it seems to me that much more can be said; maybe, along the following lines:

What is the smallest number of integers to be deleted from $[1,N]$ so that for every choice of $\kappa\le k$ remaining integers, their product has at least $\kappa$ distinct prime factors?

The problem below is suggested by this one.

Suppose that we are given $2k$ integers $x_1,\dotsc,y_k$, and we want to find an integer $a$ so that $\gcd(a+x_i,a+y_i)>1$ for each $i\in[1,k]$. This is certainly possible if the product of any $\kappa$ of the differences $y_i-x_i$ has at least $\kappa$ distinct prime factors, for each $\kappa\in[1,k]$: for, by Hall's theorem, we can then associate with each $i\in[1,k]$ a prime $p_i\mid y_i-x_i$ so that all primes $p_1,\dotsc,p_k$ are pairwise distinct, and then use the Chinese Remainder Theorem to find $a$ subject to $a\equiv -x_i\pmod{p_i}$, $i\in[1,k]$.

Intuitively, I would expect that for the ``random'' choice of $x_1,\dotsc,y_k$ this should be possible. Can something of this sort be proved rigorously?

Fix an integer $k\ge 1$ and choose $z_1,\dotsc,z_k\in[1,N]$ at random, for $N$ large (or consider $[N,2N]$ instead). What is the probability that for every $\kappa\in[1,k]$, the product of any $\kappa$ of the numbers $z_i$ has at least $\kappa$ distinct prime factors?

My guess is that the probability in question is close to $1$ for $N$ large. For example, if $k=1$ then the probability is $1-N^{-1}$ trivially; if $k=2$ then it still seems to be $1-O(N^{-1})$, in a slightly less obvious way.

The problem below is suggested by this one.

Suppose that we are given $2k$ integers $x_1,\dotsc,y_k$, and we want to find an integer $a$ so that $\gcd(a+x_i,a+y_i)>1$ for each $i\in[1,k]$. This is certainly possible if the product of any $\kappa$ of the differences $y_i-x_i$ has at least $\kappa$ distinct prime factors, for each $\kappa\in[1,k]$: for, by Hall's theorem, we can then associate with each $i\in[1,k]$ a prime $p_i\mid y_i-x_i$ so that all primes $p_1,\dotsc,p_k$ are pairwise distinct, and then use the Chinese Remainder Theorem to find $a$ subject to $a\equiv -x_i\pmod{p_i}$, $i\in[1,k]$.

Intuitively, I would expect that for the ``random'' choice of $x_1,\dotsc,y_k$ this should be possible. Can something of this sort be proved rigorously?

Fix an integer $k\ge 1$ and choose $z_1,\dotsc,z_k\in[1,N]$ at random, for $N$ large (or consider $[N,2N]$ instead). What is the probability that for every $\kappa\in[1,k]$, the product of any $\kappa$ of the numbers $z_i$ has at least $\kappa$ distinct prime factors?

If $k=1$, then the probability is $1-N^{-1}$ trivially; if $k=2$, then it still seems to be $1-O(N^{-1})$, in a slightly less obvious way. For any fixed $k$, the set of all integers with fewer than $k$ distinct prime factors is known to have zero density (references can be found here); consequently, for $k$ fixed and $N$ growing, with probability $1-o_k(1)$ all of $z_1,\dotsc,z_k$ will have at least $k$ distinct prime factors, whence, of course, the product of any $\kappa$ of them will have at least $k\ge\kappa$ distinct prime factors. Still, it seems to me that much more can be said; maybe, along the following lines:

What is the smallest number of integers to be deleted from $[N,2N]$ so that for every choice of $\kappa\le k$ remaining integers, their product has at least $\kappa$ distinct prime factors?