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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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.