# How big can a set of integers be if all pairs have small gcd?

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)$.

• Even more efficiently, you may beat the primes by adding all pairwise products of primes not exceeding $M$ (including their squares). – Ilya Bogdanov Oct 21 '15 at 16:31
• 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$. – Robert Israel Oct 21 '15 at 18:21
• Thus for $M=5$, in addition to the primes $\le N$ you have $\{1,4,6,8,9,10,15,25\}$. – 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}.$$

• 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... – fedja Oct 21 '15 at 18:08
• 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 :-) – fedja Oct 21 '15 at 18:13
• @Fedja: Great, that works nicely! – Eric Naslund Oct 21 '15 at 18:22
• 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 ... – Lucia Oct 22 '15 at 3:19
• @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}$ – Eric Naslund Oct 22 '15 at 11:09