2
$\begingroup$

In this recent MO question, it was shown that the maximal cardinality of a subset $A(M,N)$ of $[1,N]$ where the pairwise GCD's of all set elements are upper bounded by $M,$ with $M^2\leq N$ has size equal to $$\pi(N)+\sum_{1\leq n\leq N} \pi(p(n))\sim \pi(N)+\frac{M^2}{2 \log^2 M}, $$ where $p(n)$ is the smallest prime factor of $n$. Let's denote that case by the case of small GCD, as in the original question.

I am interested in the bounded (in terms of a function of $N$) case where the bound is larger. Specifically, let $M>\sqrt{N}$ say $M=N^a \log^b N$ ($b^{th}$ power of log not iterated log) with $b\geq 1$ and $a<1$. What can then be said about the size of the subset $A(M,N)$ of $[1,N]$? The case of $M=\sqrt{N} \log^2 N$ or $M=\sqrt{N} \log^2 N / \log\log N$ looks intriguing.

If a similar estimate holds, then it would seem that it is possible to have $$A(M,N)\gg N$$ where the implied constant may possibly depend on $M,N$.

It also looks like $a\leq 1/2$ must hold since otherwise the lower bound becomes larger than $N,$ which is absurd.

$\endgroup$
3
  • $\begingroup$ @Eric Naslund, this question is about the $M^2>N$ case of the maximal size of a bounded gcd set question you answered. $\endgroup$
    – kodlu
    Nov 1, 2015 at 21:29
  • $\begingroup$ The at-sign doesn't notify someone who hasn't participated in the question, kodlu. $\endgroup$ Nov 2, 2015 at 22:28
  • $\begingroup$ @GerryMyerson, thanks for letting me know. $\endgroup$
    – kodlu
    Nov 2, 2015 at 22:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.