Suppose $A\subset[1,N]$ is a set of integers. If for any distinct $a,b\in A$ we have $(a,b)\leq M$ then how big can $|A|$ be?

If $M=1$ then $|A|$ is at most $\pi(N)$ since the map $a\mapsto P_+(a)$ (which sends $a$ to its largest prime factor) is an injection to the primes, and so the primes themselves are the most efficient. If $M=N$ then we can take $|A|=N$. What about $M$ in between? Can you beat the primes? It would be safe to assume that $A$ consists solely of $M$-smooth numbers since we can decompose $A=A_1\cup A_2$ where each $a\in A_1$ is $M$-smooth and each $a\in A_2$ has a prime factor which at least $M+1$. The large prime factors appearing as divisors in $A_2$ cannot be repeated, so $|A_2|\leq \pi(N)$.

  • 1
    $\begingroup$ Even more efficiently, you may beat the primes by adding all pairwise products of primes not exceeding $M$ (including their squares). $\endgroup$ – Ilya Bogdanov Oct 21 '15 at 16:31
  • 2
    $\begingroup$ Actually, for $M= 1$ you have $|A| = \pi(N) + 1$: you can have $1$ as well as the primes. @IlyaBogdanov: there's no reason to restrict to pairwise products, you can throw in products of arbitrarily many (not necessarily distinct) primes $x = p_1 \ldots p_n$, $p_1 \le \ldots \le p_n$, as long as $x/p_1 \le M$. $\endgroup$ – Robert Israel Oct 21 '15 at 18:21
  • $\begingroup$ Thus for $M=5$, in addition to the primes $\le N$ you have $\{1,4,6,8,9,10,15,25\}$. $\endgroup$ – Robert Israel Oct 21 '15 at 18:28

We'll prove that the maximal cardinality of such a set for $M^2\leq N$ has size equal to $$\pi(N)+\sum_{1<n\leq M} \pi(p(n))$$ where $p(n)$ is the smallest prime factor of $n$. Since $$\sum_{1<n\leq M} \pi(p(n))\sim \frac{M^2}{2\log^2 M},$$ this proves that Ilya Bogdanov's example of including all pairwise products of primes not exceeding $M$ is nearly optimal in terms of asymptotics.

As you suggest in the question, this problem is equivalent to constructing the largest subset $A\subset S_M(N)$ such that $\gcd(a,b)\leq M$ for every $a,b\in A$ where $S_M(N)$ is the set of $n\leq N$ whose largest prime factor is at most $M$.

To see why, suppose that $A$ satisfies $\gcd(a,b)\leq M$ for every $a,b\in A$. Then every prime that is greater than $M$ can divide at most one element of $A$. If $p>M$ divides $a\in A$, then making $a=p$ only helps create a larger set $A$. Since these primes do not interact with the $M$-smooth numbers, the proof is complete.

Let $T(N,M)$ denote the maximum size of such a set $A\subset S_M(N)$. Then the size of the largest subset of $[1,N]$ with pairwise $\gcd$'s bounded by $M$ is $$\pi(N)-\pi(M)+T(N,M).$$

As mentioned by Fedja in the comments s, the reasoning above for the primes extends to all integers. By considering those primes $p,q\leq M$ such that $pq>M$, we see that there can only be exactly one such number divisible by $pq$. Similarly for any $p,q,r$ with $pq,qr,rp\leq M$ and $pqr>M$ there can only be one number in our set divisible by $pqr$. Thus we find that the maximal size is the sum over those integers whose largest proper divisor is less than $M$. Since the largest proper divisor of $n$ equals $n/p(n)$ where $p(n)$ is the least prime factor, we can group things based on this, and we have that $$T(N,M)=\sum_{1<p\leq M}\sum_{n\leq M:\ p(n)\geq p}1.$$ Rearranging this equals $$\sum_{1<n\leq M}\sum_{p\leq p(n)}1=\sum_{n\leq M}\pi\left(p(n)\right),$$ and for composite $n$ $p(n)\leq\sqrt{n}$, so the primes dominate this sum. Thus asymptotically we have $$T(N,M)\sim\sum_{p\leq M}\pi(p)\sim\frac{M^{2}}{2\log^{2}M}.$$

  • 2
    $\begingroup$ You can continue in the same spirit: consider pairs of primes $p,q\le M$ with $pq>M$. Any such pair can enter just one number, so we can as well have all pairs there. Next consider all triples such that the product of any 2 is less than or equal to $M$ but the triple product is $>M$. Again, any triple can enter at most one number, so take them all, etc. After that, of course, just add $[1,M]$. So to describe a maximal cardinality set it easy. As to the size, it looks like we just need to play with the prime number theorem carefully to figure the asymptotics but I have to teach a class now... $\endgroup$ – fedja Oct 21 '15 at 18:08
  • 1
    $\begingroup$ This set can be also described as the set of all numbers whose largest proper divisor is not greater than $M$, which allows to estimate the size of the complement way faster than with my prime count idea. Now it is time to run on the stairs :-) $\endgroup$ – fedja Oct 21 '15 at 18:13
  • $\begingroup$ @Fedja: Great, that works nicely! $\endgroup$ – Eric Naslund Oct 21 '15 at 18:22
  • $\begingroup$ There's still something off if $M>\sqrt{N}$ which you should account for. Fedja's description of numbers with largest proper divisor not larger than $M$ is very nice. For example, this includes all numbers with no prime factors below $N/M$ which has interesting asymptotics when $M$ is larger than $\sqrt{N}$ (eventually getting to $N$ when $M=N$). So you could either restrict attention to small ranges of $M$, or perhaps flesh out the argument a little bit more ... $\endgroup$ – Lucia Oct 22 '15 at 3:19
  • $\begingroup$ @Lucia: You're right, I have edited the question for now, but I'll add in a nice form for the sum when $M>\sqrt{N}$ $\endgroup$ – Eric Naslund Oct 22 '15 at 11:09

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.