5
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark Lewko
    May 19, 2020 at 14:46
  • 4
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    May 19, 2020 at 14:49
  • 8
    $\begingroup$ 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$. $\endgroup$
    – David E Speyer
    May 19, 2020 at 14:55
  • 1
    $\begingroup$ @DavidESpeyer: $3^2$ is a prime power between $6$ and $12$, but it doesn't divide $\binom{12}{6}$. $\endgroup$
    – Sam Hopkins
    May 19, 2020 at 15:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – Gerhard Paseman
    May 19, 2020 at 15:47

4 Answers 4

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    May 21, 2020 at 4:29
  • $\begingroup$ Gerhard: Yes, that seems right. I've added Schnirelmann in the citation and corrected the 4 to a 2. $\endgroup$
    – Mark Lewko
    May 21, 2020 at 4:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – GH from MO
    May 21, 2020 at 10:11
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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