1
$\begingroup$

Background

This question follows up on the previous question I had asked here That question had a nice answer, for the specific parameter choice $M=N+1,$ now I'm interested in $M=N\log N.$

Consider the set $\{1,2,\ldots,N\}$. Let $LCM(a,a')$ denote the lowest common multiple of the integers $a,a'.$

We say that $A\subset \{1,2,\ldots,N\}$ is $M-$good if $LCM(a,a')\geq M,$ for all $a\neq a' \in A.$

How large can the size $|A|$ be for an $M-$good set, as a function of $M,N$ as $N\rightarrow \infty$ and $M=M(N)$ also tends to infinity.

Specifically, let $M=N \log N$. What is the maximum order of $|A|$?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Idea for a lower bound: we can take all integers larger than $n/2$ that have no prime factors smaller than $2 \log n$. $\endgroup$
    – Woett
    Commented Mar 20, 2017 at 6:05
  • 2
    $\begingroup$ Tweaking Woett's excellent idea: if $f(N)$ is a function going to infinity slower than any power of $\log N$, then taking all integers between $N/f(N)$ and $N$ that have no prime factors smaller than $f(N)\log N$ achieves a slightly better lower bound: about $N/e^\gamma\log\log N$, where $\gamma$ is Euler's constant, which is twice as large as when $f(N)=2$. $\endgroup$
    – Greg Martin
    Commented Mar 20, 2017 at 7:30
  • $\begingroup$ Thanks to both of you for these comments. I can see by Mertens third theorem that the suggestion of Woett will give approximately $e^{-\gamma}(N/2)/\log\log N$ integers. Greg Martin, I am sure I don't understand your suggestion fully. So $f(N)=\log^a N$, for any $a>0$ is too fast growing. Would the next lower level be something like $f(N)=(\log \log N)^a$ for any constant $a<\infty$ or something else. Would you be kind enough to fill in some details in an answer? $\endgroup$
    – kodlu
    Commented Mar 20, 2017 at 9:55

1 Answer 1

Reset to default
1
$\begingroup$

You cannot do much better then in the construction of Woett. To see this note that the size of $A$ is bounded above by the maximal size of a set $A$, such that $gcd(a, a')<\frac{N}{\log N}$ for all $a\neq a'$ in $A$. Suppose that $A$ is a set with the latter property. For each $a\in A$, let $d(a)$ be the largest divisor of $a$ which is $<\log N$. Then the map $a\mapsto\frac{a}{d(a)}$ is injective. An integer $n$ in the image of this map has the property that it is not divisible by a prime $<\frac{n}{N/\log N}$, so we obtain $$ |A|\leq \frac{N}{(\log\log N)^2} + \#\left\{n\leq N: P^-(n)>\frac{\log N}{(\log\log N)^2}\right\}\ll\frac{N}{\log\log N}. $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ I presume $P^{-}(n)$ denotes the smallest prime divisor of $n$? $\endgroup$
    – kodlu
    Commented Mar 21, 2017 at 2:46
  • 1
    $\begingroup$ @kodlu: Yes, $P^-(n)$ is the smallest prime divisor. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Mar 21, 2017 at 19:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .