1
$\begingroup$

Let $\mathcal{M}$ be a set of $M$ distinct positive integers, all of size roughly $N$. Assume that the pairwise gcd of elements of $\mathcal{M}$ is large for all pairs. For illustration, let's take $M \approx \sqrt{N}$, and assume that $\gcd(m_1,m_2) \approx N/M \approx \sqrt{N}$ or larger for all pairs $m_1,m_2 \in \mathcal{M}$. (It's not too difficult to see that this is what "large" gcd means here, since it's not possible that all pairwise gcd's are significantly larger than $N/M$.)

It's clear how to construct such a set $\mathcal{M}$: fix one big common factor of order ca. $\sqrt{N}$, and then choose the elements of $\mathcal{M}$ as (maybe pairwise coprime) multiples of this common factor.

But is this the only possibility? In other words: If I have a set of $\sqrt{N}$ numbers, all of order roughly $N$, and if the pairwise gcd is always $\sqrt{N}$ or larger, then does it mean that these numbers all have a large common factor which is the same for all numbers? (Or maybe there is a small set of possible large factors, and every element of $\mathcal{M}$ is a multiple of one of these factors.)

I am aware that the question is somewhat imprecise. Also, the numbers and the gcd's and the cardinality of the set don't have to be exactly what is written above, but could be a bit smaller or larger. But the question is: is it generally true that having so many large gcd's requires all numbers to be multiples of a large common factor, or multiples of a small set of possible large common factors, and if yes, then what sort of argument could prove such a structural result? Also, what happens when I don't request all pairwise gcd's to be so large, but just a "high" proportion of gcd's?

Improve this question
$\endgroup$
8
  • $\begingroup$ You can't have any small differences, second differences, third differences, etc. So yes, that is what they look like: multiples of the same gcd. For high proportion, do 3-smooth numbers satisfy? Gerhard "You're Not Just Talking Smooth" Paseman, 2019.05.24. $\endgroup$
    – Gerhard Paseman
    Commented May 24, 2019 at 14:53
  • $\begingroup$ Do you have any specific bounds? For example, how small is $m_1$ allowed to be in terms of $N$, or how large is $m_M$ allowed to be? $\endgroup$
    – user44191
    Commented May 24, 2019 at 22:33
  • $\begingroup$ I’m gonna be lazy and note the following. Let’s write S instead of \mathcal{M} since I’m on my phone. Let m\in S. There are << N^\eps divisors of m. In particular there are << N^\eps divisors of m that are of size \sqrt{N}. For each such divisor d | m of size \sqrt{N}, let S_d := {n\in S : d | n}. Observe that the union of the S_d is all of S by hypothesis. Observe also that every S_d is of the “trivial” form. Thus there is a decomposition of S into a union of few “trivial” subsets. I hope I get to learn a weighted Erdos-Ko-Rado theorem in the inevitable “correct” answer to this question! $\endgroup$
    – alpoge
    Commented May 24, 2019 at 23:39
  • $\begingroup$ Thank you all for the answers. @Gerhard: It's a correct observation. However, as I understand this really only applied when ALL $M^2$ pairwise gcd's are that large. If I can only assume that, say, $M^2/10$ pairwise gcd's are that large, then such an argument doesn't really apply anymore, right? $\endgroup$
    – Kurisuto Asutora
    Commented May 25, 2019 at 10:44
  • $\begingroup$ @user44191: I am thinking of $m_1, ..., m_M$ of being roughly of the same size, so let's say they are all in $[N,2N]$. I didn't mean that they all have to be extremely close to $N$. $\endgroup$
    – Kurisuto Asutora
    Commented May 25, 2019 at 10:45

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .