# Can one show combinatorially how $\operatorname{lcm}(1, \dotsc, n)$ grows?

Let us write $$M(n)$$ for $$\operatorname{lcm}(1,\dotsc,n)$$ for $$n$$ a positive integer. Asymptotically $$M(n)$$ tends toward $$e^n$$. This result uses analytic number theory. (Lcm is least common multiple, here of the first $$n$$ positive integers, and its logarithm is a Chebyshev function.)

It also seems that $$2^n \lt M(n) \lt 3^n$$ for $$n \gt 6$$ and even $$2^n \leq M(n+1) \leq 3^n$$ for $$n \geq 0$$. Are these relations true, and are there combinatorial proofs of either?

Additionally, do these inequalities appear in the combinatorial literature?

Gerhard "Interest In LCM Is Growing" Paseman, 2020.05.19.

• If we take a logarithm, then you are asking for upper and lower estimates on the familiar $\psi(x)$ from prime number theory. So you are asking for a combinatorial proof of Chebyshev's prime number estimates. May 19 '20 at 14:46
• In what sense are the standard proofs of Chebyshev's estimates not combinatorial? And we know from Diamond and Erdos mathscinet.ams.org/mathscinet-getitem?mr=610529 that, for any $\delta>0$, similar methods can prove $(1-\delta)^n < M(n) < (1+\delta)^n$ for $n$ sufficiently large. May 19 '20 at 14:49
• There is a slick combinatorial proof of $M(n) < 4^n$, though. Let $Q$ be the set of all prime powers between $n/2$ and $n$. Then $\mathrm{LCM}(1,2,\ldots,n) \leq \mathrm{LCM}(1,2,\ldots, \lfloor n/2 \rfloor)\cdot \prod_{q \in Q} q$. But $\prod_{q \in Q} q$ divides $\binom{n}{\lfloor n/2 \rfloor} < 2^n$. So $M(n) < M(\lfloor n/2 \rfloor) \cdot 2^n$ and induction gives $M(n) < 4^n$. May 19 '20 at 14:55
• @DavidESpeyer: $3^2$ is a prime power between $6$ and $12$, but it doesn't divide $\binom{12}{6}$. May 19 '20 at 15:39
• @Sam, right. However the base of the prime power does, and that is enough for the argument. Gerhard "Willing To Tweak The Slick" Paseman, 2020.05.19. May 19 '20 at 15:47

David Speyer has given a very short proof of an upper bound for $$M(n)$$ in the comments. There is a similarly short argument that provides a lower bound on $$M(n)$$ which I believe is due to Gelfond and Schnirelmann, which goes as follows:

Let $$P_n(x)$$ denote a degree $$n-1$$ polynomial with integer coefficients. Then clearly the product $$M(n) \int_{0}^{1} P_n(x) dx$$ is an integer. Now consider $$P(x) = x^{\frac{n-1}{2}}(1-x)^{\frac{n-1}{2}}$$. For $$x \in [0,1]$$ we have that $$P_n(x) \leq 2^{-(n-1)}$$ since the maximum of $$x(1-x)$$ occurs at $$x=1/2$$. Thus $$1 \leq M(n) \int_{0}^{1} P_n(x) dx < M(n) 2^{-(n-1)}$$. Rearranging things we have that $$M(n) > 2^{n-1}.$$

• This is much like the argument I attribute to Nair. In section 9 of his article Diamond says Nair rediscovered it, and gives Gelfond and Schnirelmann as a reference. Also, the 4 should be more like 2. Gerhard "Deflation These Days, You Know?" Paseman, 2020.05.20. May 21 '20 at 4:29
• Gerhard: Yes, that seems right. I've added Schnirelmann in the citation and corrected the 4 to a 2. May 21 '20 at 4:40
• This argument assumes that $n$ is odd, and it gives $M(n-1)>2^{n-1}$. It would be cleaner to write the proof for $n$ even, with $P(x)=x^{n/2}(1-x)^{n/2}$, and obtain $M(n)>2^n$. For $n$ odd, it follows that $M(n)>M(n-1)>2^{n-1}$. So we have $M(n)>2^{n-1}$ in all cases. May 21 '20 at 10:11

As noted, these estimates are known, but possibly not "combinatorial".

In

Hardy, G. H.; Wright, E. M., An introduction to the theory of numbers., XVI + 403 p. Oxford, Clarendon Press (1938). ZBL64.0093.03.

this is denoted $$U(x) := \operatorname{lcm}(1,2,\dots,x)$$. Its asymptotics are found in Chapter XXII, which leads up to the proof of the prime number theorem.

Write $$\psi(x) = \log U(x)$$. Relevant facts (going from easier to harder):

Theorem 414: $$A_1 x < \psi(x) < A_2 x$$

Page 343: $$\psi(x) > \frac{\log 2}{4}\;x$$

Theorem 420: $$\psi(x) \sim x$$

A consequence of 420 would be: $$\text{Let }0 < A < e < B. \text{Then }A^x < U(x) < B^x \text{ for large }x$$ More recent result:

Rosser, J. Barkley; Schoenfeld, Lowell, Approximate formulas for some functions of prime numbers, Ill. J. Math. 6, 64-94 (1962). ZBL0122.05001.

They prove:
\begin{align} \psi(x) & > 0.84\;x\quad\text{for } x \ge 101 \\ \psi(x) & < 1.038\;x\quad\text{for } x > 0 \end{align}

Another title that sounds promising:

Rosser, J. Barkley; Schoenfeld, Lowell, Sharper bounds for the Chebyshev functions $$\vartheta(x)$$ and $$\psi(x)$$ (http://dx.doi.org/10.2307/2005479), Math. Comput. 29, 243-269 (1975). ZBL0295.10036.

Thanks (?) to David Speyer for providing a link to a review in German of an article in English I have yet to find. (Help with getting the article is appreciated; check my user pages as needed for contact info.) Thanks (!) to David Speyer for providing the search terms Erdos and Diamond, which lead to a survey article in 1982 by Harold Diamond on elementary methods in prime number theory. Section 9 outlines a method of Mohan Nair using integration of polynomials to provide a lower bound for $$M(n)$$ which is exponential. Although Nair's method is not as combinatorial as I would like, it inspires me to push ahead on this question.

I leave this answer to inspire others find the above article and to find and post about other articles which come remotely close to answering the question.

Gerhard "Heading Onward To The Frontier" Paseman, 2020.05.19.

• The Diamond-Erdos paper is currently available at users.renyi.hu/~p_erdos/1981-11.pdf May 19 '20 at 16:46
• David, thanks !?! Gerhard "It's No Reflection On You" Paseman, 2020.05.19. May 19 '20 at 17:05

The proof of Sylvester’s theorem from the weak pigeonhole principle in §4 of Alan Woods’s PhD thesis amounts to a combinatorial proof of bounds on Chebyshev’s $$\theta(x)$$ function (with relative error $$O(1/\log x)$$ or so). The argument is based on constructing suitable mappings on finite integer intervals by manipulating prime factorizations.