Take the 2-minute tour ×

Does there exist $c>0$ such that among any $n$ positive integers one may find $3$ with least common multiple at least $cn^3$?


Let me post here a proof that we may always find two numbers with lcm at least $cn^2$. Note that if $a < b$, $N$=lcm$(a,b)$, then $N(b-a)$ is divisible by $ab$, hence $N\geq ab/(b-a)$. So, it suffices to find $a$, $b$ such that $ab/(b-a)\geq cn^2$, or $1/a-1/b\leq c^{-1} n^{-2}$. Since at least $n/2$ our numbers are not less then $n/2$, denote them $n/2\leq a_1 < a_2 < \dots < a_k$, $$2/n\geq \sum (1/a_i-1/a_{i+1})\geq k \min (1/a_i-1/a_{i+1}),$$ so $\min (1/a-1/b)\leq 2/nk\leq 4/n^2$.

For triples we get lower bound about $c(n/\log n)^3$ on this way. Again consider only numbers not less then $n/2$. If all lcm's are less then $c(n/\log n)^3$, then all number itselves are less then some $n^3/2$, so for $2^k < n^3 < 2^{k+1}$ all of them do not exceed $2^k$, hence at least $n/2k$ of them belong to $[2^r,2^{r+1}]$ for the same $r$, then there exist three numbers $a < b < c$ with $c-a\leq 2^r/(n/4k)\leq 4ka/n$. Then

lcm$(a,b,c)\geq abc/((b-a)(c-a)(c-b))\geq (a/(c-a))^3\geq (n/4k)^3$.

share|improve this question
Typo: You have $\ge c^{-1} n^{-2}$ instead of $\le$. –  Harry Altman Oct 13 '10 at 7:46
thank you, I fixed it –  Fedor Petrov Oct 13 '10 at 8:13
I wonder whether this extends onto two potentially different sets. Is it true that for any two sets of positive integers $\{a_1,\ldots,a_n\}$ and $\{b_1,\ldots,b_n\}$ there exist indices $i,j\in[n]$ such that $[a_i,b_j]\ge c n^2$ with a positive absolute constant $c$? –  Seva Oct 29 '10 at 8:12

9 Answers 9

up vote 9 down vote accepted

See my post on AoPS

Edit: OK, reposting here.

The first step toward the solution, as it often happens, is to generalize the problem. Instead of just one set $A$, we shall consider $3$ sets $A,B,C$ of cardinalities $|A|,|B|,|C|$ and will try to prove that there exist $a\in A,b\in B,c\in C$ such that $[a,b,c]\ge\sigma |A|\cdot|B|\cdot|C|$.

The reason for such generalization is that we are going to employ the usual "minimal counterexample" technique (a.k.a. "infinite descent", etc.) and we have much more freedom if we are allowed to modify three different sets independently rather than just one of them.

Our first attempt will be to make the reduction modulo $p^k$ where $p$ is a prime and $k\ge 1$ is an integer. Let $A_{p,k}=\{a\in A: v_p(a)=k\}$ where, as usual, $v_p(a)=\max\{v:p^v\mid a\}$. Let us replace $A$ with $A'=\{a'=p^{-k}a: a\in A_{p,k}\}$. For every $b\in B$, define $b'=\frac{b}{p^{\min(k,v_p(b))}}$. The numbers $b'$ form a set $B'$ of cardinality $|B'|\ge\frac{|B|}{(k+1)}$ because each $b'$ can be obtained from at most $k+1$ different $b\in B$. Define $C'$ in a similar way. Note that if $a'\in A', b'\in B', c'\in C'$, and $a,b,c$ are the elements of $A,B,C$ from which $a',b',c'$ were obtained, we have $[a,b,c]=p^k[a',b',c']$. Thus, if we have a minimal counterexample $A,B,C$ to our statement then $A',B',C'$ is not a counterexample, so we can find $a',b',c'$ with $[a',b',c']\ge \sigma |A'|\cdot |B'|\cdot |C'|\ge \sigma (k+1)^{-2}|A_{p,k}|\cdot|B|\cdot|C|$, which will not give us a triple $a,b,c$ with large least common multiple only if $|A_{p,k}|\le (k+1)^2p^{-k}|A|$. Thus, in our minimal counterexample, we must have this inequality for all prime $p$ and all $k\ge 1$. Note that it is trivially true with $k=0$ as well. The same inequality holds for the cardinalities of sets $B_{p,\ell}$ and $C_{p,m}$.

Now we shall try the averaging technique. Since we are dealing with a multiplicative problem, it will be convenient to use geometric means. So, let us consider the identity $$ \prod_{a\in A,b\in B,c\in C}\frac{abc}{[a,b,c]}\prod_{a\in A,b\in B,c\in C}[a,b,c]=\prod_{a\in A,b\in B,c\in C}(abc) $$ The products have $|A|\cdot|B|\cdot|C|$ factors in them and the product on the right is at least $$ (|A|!)^{|B|\cdot|C|}(|B|!)^{|A|\cdot|C|}(|C|!)^{|A|\cdot|B|}\ge e^{-3|A|\cdot|B|\cdot|C|}(|A|\cdot|B|\cdot|C|)^{|A|\cdot|B|\cdot|C|} $$

Our main task will be to estimate the first product on the left by $e^{K|A|\cdot|B|\cdot|C|}$ with some absolute $K>0$. If we manage to do that, we will immediately get the desired result "on average" with $\sigma=e^{-K-3}$. In order to do it, we'll estimate the power at which each prime $p$ can appear in this product. So, fix some $p$ and assume that $a\in A_{p,k},b\in B_{p,\ell},c\in C_{p,m}$. Then $p$ appears in the factor $\frac{abc}{[a,b,c]}$ at all only if $k+\ell+m\ge 2$ and its power in this case does not exceed $k+\ell+m+1$ (I know, this is an idiotic bound, but it holds and will allow me to have all factors of the same form). Thus, the total power in which $p$ appears in the first product is at most $$ \begin{aligned} &\sum_{k,\ell,m:k+\ell+m\ge 2}(k+\ell+m+1)|A_{p,k}|\cdot|B_{p,\ell}|\cdot|C_{p,m}| \cr &\le |A|\cdot|B|\cdot|C|\cdot\sum_{k,\ell,m:k+\ell+m\ge 2}(k+\ell+m+1)^7p^{-(k+\ell+m)} \end{aligned} $$ Since there are at most $(M+1)^2$ ways to represent a positive integer $M$ as a sum of three non-negative integers, the last sum is at most $\sum_{M\ge 2}(M+1)^9p^{-M}$.

Now it is time to put all $p$ together. We get $e^{K|A|\cdot|B|\cdot|C|}$ with $$ K=\sum_{M\ge 2,p\text{ prime}}(M+1)^9p^{-M}\log p $$ and our only task is to show that this double series converges. We can forget that $p$ is prime, just remember that $p\ge 2$. Also for any $\delta>0$, we can estimate $(M+1)^9\le C_\delta p^{\delta M}$, $\log p\le C_\delta p^{\delta}$ with some finite $C_\delta>0$. Thus, our series is dominated by $$ \sum_{M,p\ge 2}p^{\delta-(1-\delta)M}=\sum_{p\ge 2} \frac{p^{3\delta-2}}{1-p^{\delta-1}}\ge \frac 1{1-2^{\delta-1}}\sum_{p\ge 2}p^{3\delta-2}<+\infty $$ if $\delta<\frac 13$.

This proof can be easily generalized to any number of sets but the constant it gives is rather terrible. It would be nice to get some better bound even for the case of 2 sets. As usual, questions and comments are welcome.

share|improve this answer
Is there a chance you could post a copy of your proof here, as well? Most people would have to create a new account in order to comment there. Moreover, it makes sense to have the question and proof in the same thread, in case someone wants to refer to both in the future. –  Gjergji Zaimi Oct 8 '11 at 22:25
Done............. –  fedja Oct 8 '11 at 22:41
1 $ $ –  Steven Gubkin Oct 9 '11 at 0:29
@ fedja You can post comments "under the character limit" by following your post with dollar signs enclosing empty spaces. –  Steven Gubkin Oct 9 '11 at 0:30
Thanks! $ $ –  fedja Oct 9 '11 at 0:45

With n = 48, any three members of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35, 36, 40, 42, 45, 56, 60, 63, 70, 72, 84, 90, 105, 120, 126, 140, 168, 180, 210, 252, 280, 315, 360, 420, 504, 630, 840, 1260, 2520} have lcm at most 2520, so $c\le35/1536=0.227\ldots$.

share|improve this answer
yes, but in general, for large values of $n$, if we take all $n$ numbers being divisors of the same common multiple $N$, then $N\gg n^3$ (since the number of divisors grows slower then $N^{\epsilon}$ for any $\epsilon>0$) –  Fedor Petrov Oct 10 '10 at 19:08
Yes, that's why I stopped at 2520. I have more ideas for lowering the upper bound, but so far no ideas for a lower bound. –  Charles Oct 10 '10 at 19:20
I may prove smth like $C(n/\log n)^3$ from below. –  Fedor Petrov Oct 10 '10 at 19:31
If you take all numbers of the form $2^{t_1}3^{t_2}5^{t_3}7^{t_4}$ where $t_1\in [0,4], t_2\in [0,3], t_3\in [0,2], t_4\in [0,1]$, then the max. LCM is $M=75600$, the cardinality $n=5!$, the quotient is $M/n^3=.043...$ –  Mark Sapir Oct 10 '10 at 19:42
If you reduce the range of t1, t2, and t3 by 1 you get 0.022786458333..., but further improvements don't seem possible with this method (unless you use primes > 20 or prime powers > 1000000). –  Charles Oct 10 '10 at 20:43

If you take all numbers of the form $2^{t_1}3^{t_2}5^{t_3}$, where $t_1\in [0,3], t_2\in [0,2], t_3\in [0,1]$ then the maximal LCM is $8*9*5=360$, the cardinality $n=4!=24$, the quotient $360/24^3=.026...$. I cannot find a smaller number yet.

Update: Let $S$ be the set. Let $X$ be the set of prime divisors of $S$. Without loss of generality we can assume that $X=2,3,...,p_k$ (all primes up to $p_k$). Indeed, we can always replace a bigger prime from $X$ by a smaller prime that does not without increasing the constant $C$. Now every element in $S$ $2^{l_1}...p_k^{l_k}$ corresponds to a vector $(l_1,...,l_k)$ in ${\mathbb Z}^k$. Let $\bar S$ be the set of all these vectors corresponding to numbers from $S$. Consider the partial component-wise order on ${\mathbb Z}^k$ (this makes the grid ${\mathbb Z}^k$ into a lattice (with intersection and join). Let $u_1,...,u_s$ be all the maximal vectors in $\bar S$ with respect to this partial order. We can assume that with every $x\in S$, $S$ contains all divisors of $X$. Therefore for every $u_i$, $\bar S$ contains all $v\le u$. These $v$'s form a parallelepiped $U_i$. The number of points in the union of all the parallelepipeds $U_i$ is $n$, the number of elements in $S$. Now we need to take any LCM of three $u_i$, and compare it with $k$. All the examples so far are such that there is only one maximal $u_i$ in $\bar S$. I think the only hope to prove that $C$ vanishes is to consider the case when there are many maximal vectors in $\bar S$. This is also the way to show that $C$ has a non-trivial lower bound.

share|improve this answer
By adding in 7 you can get to 0.02278645833..., but I can't immediately improve on that. –  Charles Oct 10 '10 at 20:38

For the question as asked, 2520 may exhibit the minimum. Perhaps the question is as $n$ increases.

For any set $S$ of positive integers consider $B_S$, the LCM of the entire set, and also $C_S$, the greatest LCM among all the 3 element subsets of $S$. Let $B_n$ and $C_n$ be the smallest values of $B_S$ and $C_S$ over $n$ element sets. Finally, let $b_n=\frac{B_n}{n^3}$ and $c_n=\frac{C_n}{n^3}$. Certainly $C_n \le B_n$ and also $C_n \le n\cdot (n-1) \cdot (n-2)$. A set achieving a minimum of $B_n$ should be all divisors of a certain number (the LCM). More precisely, we can enlarge to such a set: $B_6=C_6=12$ coming from $\{1,2,3,4,6,12\}$. Also, $B_5=C_5=12$ coming from any 5 element subset. Hence $b_5=c_5=\frac{12}{5^3}=0.096...$ and $b_6=c_6=\frac{12}{6^3}=\frac{1}{18}=0.0555...$. As noted, $B_{48}=2520$ so $c_{48} \le b_{48}=0.02278645833...$. I suspect that $b_n$ and $c_n$ are never again that small for $n>48$. It also would seem that, while $c_n<1$, $b_n$ grows, probably without bound.

Numbers having more divisors than any smaller number are called highly composite numbers and supply minima of $b_n$. The sequence A002182 given in the OEIS up to 2162160, the smallest integer with 320 divisors. This shows $b_{320}=0.0659...$.

Following a link it would appear that the 100th HCN is $2^6\cdot 3^3 \cdot 5^2 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23$ showing $b_{8064}=4.288...$

So this may be a case where the small numbers are misleading (as discussed in another recent question.)

Certainly a set achieving a minimum of $c_n$ (for n>N) may as well contain all divisors of its members. Past that I am still thinking.

share|improve this answer
If the question was about the lcm of the set, then HCN would be the right approach and it would suffice to show that the minimum is achieved at 2520. But {2, 3, 5, 7}, for example, has maximal 3-lcm of 105, not 210, so more is needed to show that c > 0. –  Charles Oct 11 '10 at 1:30

It occurs to me that since we seem to be having no luck proving divisors of 2520 give the solution we should maybe look at what might be a simpler problem; looking at ${\it pairs}$ with large LCM. We'd want to compare the LCM to $n^2$. The divisors of 12 give $c=12/6^2=1/3$. Can we prove that 1/3 can't be bettered for pairs?

share|improve this answer
For pairs I may prove $cn^2$ lower bound, see update. –  Fedor Petrov Oct 13 '10 at 6:24

For two numbers, this also follows easily from Graham's conjecture. Suppose, to simplify the life, that $n=2k$, and let $a_1>\dotsb>a_k$ be the $k$ largest elements of the set under consideration. By Graham's conjecture, there exist $i,j\in[k]$ with $i\ne j$ and $a_i/(a_i,a_j)\ge k$. Now $[a_i,a_j]=a_ia_j/(a_i,a_j)\ge ka_j\ge ka_k\ge k^2=n^2/4$.

share|improve this answer
yes, ans slightly worse estimate may be gotten since Graham conjecture is proved for prime values of $k$ :) but is 1/4 the best constant? My impression is that the right asymptotics is n^2+o(n^2) –  Fedor Petrov Oct 28 '10 at 21:31
Graham's conjecture is actually proved for all $k$ in a 1996 paper by Balasubramanian and Soundararajan. So, we get a clean coefficient of $1/4$ in this way. Indeed, this argument shows that if $a_k$ is the $k$th largest element of our set, then $\max [a_i,a_j]\ge ka_k$ -- which is potentially usefull if you think of improving the coefficient. –  Seva Oct 29 '10 at 8:17

Here is a direction to explore. I describe it for quadruples, but, perhaps, a similar game can be played with triples.

Suppose that $A$ is a set of $n$ integers, all larger than $n$, such that for any $a,b,c,d\in A$ we have $[a,b,c,d]<cn^4$, with a sufficiently small constant $c$. Consider the set $S$ of all fractions (not necessarily irreducible) of the form $u/a$ with $a\in A$ and $0\le u\le a$. Although this is not immediate, it is likely to be true and possible to prove that $|S|\gg n^2$. Can we prove, in addition, that $|S+S|\gg |S|^2$? If so, the assertion will follow from the observation that any two different elements of $S+S$ are at least $1/(cn^4)$ away from each other, whereas we have $\Omega(n^4)$ different elements, all lying in $[0,2]$.

share|improve this answer

Here is a rewriting of the proof of ${(\frac{n}{\log n})}^3$ lower bound which seems to allow some leeway to play with. Let $p$ be a prime around and less than $\frac{n}{3\log n}$. Then there must be $3\log n$ numbers in the same residue class mod $p$. For three of these, say $ap+r < bp+r < cp+r$, we have $c/a < 2$. The LCM is at least $\frac{a}{c}p^3$ (the case where a fraction of the numbers have r=0 is easy).

The main advantage seems to be the choice of many primes.

Two possibilities:

  1. We want our prime to be around $\frac{n}{10}$ (say) rather than $ \frac{n}{3\log n} $. but the problem is we cannot claim $ >> \log n$ residues for such a prime. Is it feasible to prove that for one of the many primes we have in the range, there must be a residue which appears many times? Looks hard to me though.

  2. Instead of looking for the same residues, for a pair $ap+r,bp+s$, we can look to minimize $as-br$ since the gcd of this pair must divide this. So we can look at numbers $a/r$. Also we can set up relations -for example there must be three (many?) numbers $ap+r,bp+s,cp+t$ such that $\frac{a+1}{r}=\frac{b+1}{s}=\frac{c+1}{t}$ (mod p).

share|improve this answer

EDIT: This answers the wrong question. > cn^3 is wanted, not > cp^3 . END EDIT

To even hope for such a c, you will need to avoid the following kind of set: fix t with at least n factors, then for primes p larger than t take the set S_p = {sp: s divides t} . For large enough p, LCM of S_p = tp < p^2 < cp^3 .

Gerhard "Ask Me About System Design" Paseman, 2010.10.10

share|improve this answer

Your Answer


