Let $\text{lcm}(x)$ be the least common multiple of $\{1,2,3,\dots, x\}$.

Hanson showed that $\text{lcm}(x) < 3^x$

I'm wondering if the following argument is valid for showing that there is always a prime $p$ such that $2x < p < 3x$ for $x \ge 246$.

Here is my argument:

(1) if prime $p$ satisfies $2x < p < 3x$, then $p | {{3x}\choose{2x}}$.

This follows from the fact that ${{3x}\choose{2x}}$ is an integer and that $p$ will not divide out by $2x!$ or $x!$.

(2) ${{3x}\choose{2x}} > \dfrac{6^x}{x}$ for $x \ge 4$

For $x \ge 4$, ${{2x}\choose{x}} \ge \dfrac{4^x}{x}$ since ${8\choose4} = 70 > \dfrac{4^4}{4} = 64$ and ${{2x}\choose{x}} = 2\left(\dfrac{2x-1}{x}\right){2(x-1)\choose{x-1}} > 2\left(\dfrac{2x-1}{x}\right)\left(\dfrac{4^{x-1}}{x-1}\right) > \dfrac{4^x}{x}$ and ${{3x}\choose{2x}} > \left(\dfrac{3x}{2x}\right)^x {{2x}\choose{x}} > \left(\dfrac{3}{2}\right)^x\dfrac{4^x}{x}$

(3) For any prime $q$ such that $\frac{3x}{2} \le q \le 2x$, it follows that $2q > 3x$ and $q \nmid {{3x}\choose{2x}}$ since it will be divided out by $2x!$.

(4) Assume that there is no prime greater than $2x$ that divides ${{3x}\choose{2x}}$

(5) It follows that ${{3x}\choose{2x}} < \text{lcm}(\frac{3x}{2})\text{lcm}(\sqrt{3x})$ since:

  • From Legendre's Formula, it is well known that if $v_p(x)$ is the highest power of $p$ that divides $x$, then $v_p({{3x}\choose{2x}}) = \sum\limits_{i \le \log_p(3n)} \left\lfloor\frac{3x}{p^i}\right\rfloor - \left\lfloor\frac{2x}{p^i}\right\rfloor - \left\lfloor\frac{x}{p^i}\right\rfloor$ which equals $1$ or $0$ for each $i$ so that $v_p({{3x}\choose{2x}}) \le \log_p(3x)$

  • If a prime $p > \sqrt{3x}$, then $v_p({{3x}\choose{2x}}) = 1$ and $p | \text{lcm}(\frac{3x}{2})$

  • If a prime $p \le \sqrt{3x}$, then $v_p({{3x}\choose{2x}}) \le \log_p(3x) \le v_p(\frac{3x}{2})+1$

(6) So that: $\dfrac{6^x}{x} < 3^{3x/2}3^{\sqrt{3x}}$

(7) But this is not true for $x \ge 246$ since:

$246\ln 6 - \ln 246 > 435.26 > 435.24 > \frac{3}{2}(246)\ln 3 + \sqrt{3\times246}\ln 3$

and for $x \ge 246$, $6 > (3^{3/2})(3^{\sqrt{3x+2} - \sqrt{3x}})\left(\dfrac{x+1}{x}\right)$

(8) So we can reject step (4).

  • $\begingroup$ I'm sorry, but I made a mistake in my answer re: the last part of your statement (5). However, I've corrected it now so please reread that part and let me know if there are any other errors in it. Thanks. $\endgroup$ – John Omielan May 20 '19 at 21:26

Your proof provides an interesting use of Hanson's lcm inequality result and appears to be basically correct, but there are few small mistakes & other issues.

In your step (5), you wrote

... $v_p({{3x}\choose{2x}}) = \sum\limits_{i \le \log_p(3n)} \left\lfloor\frac{3x}{p^i}\right\rfloor - \left\lfloor\frac{2x}{p^i}\right\rfloor - \left\lfloor\frac{x}{p^i}\right\rfloor$ which equals $1$ or $0$ for each $i$ ...

First, in the summation part of $i \le \log_p(3n)$, the $n$ I believe is supposed to be $x$. Also, in something like a math journal, the statement "equals $1$ or $0$ for each $i$" may be obvious & sufficient, but I don't believe it is for here since, I at least, didn't initially know if it was always true. FYI, here is what I did to confirm this. I let $d = p^i$ and $x = md + r$ for $m,d \in \mathbb{N}^0$ and $0 \le r \lt d$. Then,

\begin{align} \left\lfloor \frac{3x}{d} \right\rfloor - \left\lfloor \frac{2x}{d} \right\rfloor - \left\lfloor \frac{x}{d} \right\rfloor & = 3m + \left\lfloor \frac{3r}{d} \right\rfloor - 2m - \left\lfloor \frac{2r}{d} \right\rfloor - m - \left\lfloor \frac{r}{d} \right\rfloor \\ & = \left\lfloor \frac{3r}{d} \right\rfloor - \left\lfloor \frac{2r}{d} \right\rfloor - \left\lfloor \frac{r}{d} \right\rfloor \\ & = \left\lfloor \frac{3r}{d} \right\rfloor - \left\lfloor \frac{2r}{d} \right\rfloor\tag{1}\label{eq1} \end{align}

Since $r$ and $d$ are positive, both terms are non-negative and $\left\lfloor \frac{3r}{d} \right\rfloor \ge \left\lfloor \frac{2r}{d} \right\rfloor$, so \eqref{eq1} is non-negative. Since $\left\lfloor \frac{3r}{d} \right\rfloor \le 2$, the only way \eqref{eq1} can be anything other than $0$ or $1$ would be for $\left\lfloor \frac{3r}{d} \right\rfloor = 2$ (which requires $\frac{2d}{3} \le r \lt 1$) and $\left\lfloor \frac{2r}{d} \right\rfloor = 0$ (which requires $0 \le r \lt \frac{d}{2}$). Since there is no overlap between those $2$ regions, the result of \eqref{eq1} must always be $0$ or $1$.

Next, you state

If a prime $p > \sqrt{3x}$, then $v_p({{3x}\choose{2x}}) = 1$ and $p | \text{lcm}(\frac{3x}{2})$

For $x = 5$, note that $p = 5 \gt \sqrt{15}$, but ${{3x}\choose{2x}} = {{15}\choose{10}} = 3 \times 7 \times 11 \times 13$, so $v_p({{3x}\choose{2x}}) = 0$ in this case. A correct statement to make would be something like $v_p({{3x}\choose{2x}}) \leq 1$. Note this doesn't really affect your argument and it actually strengthens it slightly as you want to have a sufficiently small upper bound.

With the next statement of

If a prime $p \le \sqrt{3x}$, then $v_p({{3x}\choose{2x}}) \le \log_p(3x) \le v_p(\frac{3x}{2})+1$

first note I believe you mean the last part to be $v_p\left(\text{lcm}\left(\frac{3x}{2}\right)\right) + 1$ instead. However, for $p = 2$ and $x = 4$, then $\log_p(3x) = \log_2(12) \gt 3$, but $v_p\left(\text{lcm}\left(\frac{3x}{2}\right)\right) + 1 = v_2(60) + 1 = 2 + 1 = 3$. A correct statement could use the fact that $v_p$ is always an integer, so you can just use the integer component of the log to get $v_p({{3x}\choose{2x}}) \le \left\lfloor \log_p(3x) \right\rfloor \le v_p\left(\text{lcm}\left(\frac{3x}{2}\right)\right) + 1$.

Finally, for the second part of (7), you wrote

and for $x \ge 246$, $6 > (3^{3/2})(3^{\sqrt{3x+2} - \sqrt{3x}})\left(\dfrac{x+1}{x}\right)$

I don't see how you get this. Your step (6) states that $\dfrac{6^x}{x} < 3^{3x/2}3^{\sqrt{3x}}$. If you multiply by $x$ and take the $x$'th root of both sides, you get $6 \lt 3^{3/2}3^{\sqrt{3/x}}x^{1/x}$. I suggest not only showing how you got your result, but also how you proved it to be always be true for $x \ge 246$.

Here is how I would prove that (6) is not true for $x \ge 246$. First, note that since logarithms, including the natural logarithm, are a strictly increasing function for positive numbers, so $a \ge b \iff \log a \ge \log b$. Thus, take the natural logarithm of both side of (6) and move the right side to the left side to get the following function

\begin{align} f(x) & = \ln(6)x - \ln(x) - \frac{3\ln(3)}{2}x - \ln(3)\sqrt{3}\sqrt{x} \\ & = \left(\ln(6) - \frac{3\ln(3)}{2}\right)x - \ln(3)\sqrt{3}\sqrt{x} - \ln(x) \tag{2}\label{eq2} \end{align}

You've already shown that $f(246) \gt 0$. If can show that $f'(x) \ge 0$ for $x \ge 246$, then $f(x) \gt 0$ for all $x \ge 246$. Differentiating \eqref{eq2} gives

\begin{align} f'(x) & = \left(\ln(6) - \frac{3\ln(3)}{2}\right) - \left(\frac{\ln(3)\sqrt{3}}{2}\right) \frac{1}{\sqrt{x}} - \frac{1}{x} \\ & = \frac{1}{x}\left(\left(\ln(6) - \frac{3\ln(3)}{2}\right)x - \left(\frac{\ln(3)\sqrt{3}}{2}\right)\sqrt{x} - 1\right) \tag{3}\label{eq3} \end{align}

Note that

$$g(x) = \left(\ln(6) - \frac{3\ln(3)}{2}\right)x - \left(\frac{\ln(3)\sqrt{3}}{2}\right)\sqrt{x} - 1 \tag{4}\label{eq4}$$

is a quadratic equation in $\sqrt{x}$. As the coefficient of $x$, i.e., $\ln(6) - \frac{3\ln(3)}{2} = 0.143841\ldots \gt 0$, the value will always be positive for large enough $x$. Let $y = \sqrt{x}$ to transform \eqref{eq4} to

$$h(y) = \left(\ln(6) - \frac{3\ln(3)}{2}\right)y^2 - \left(\frac{\ln(3)\sqrt{3}}{2}\right)y - 1 \tag{5}\label{eq5}$$

Note that $h(\sqrt{246}) = 19.462358\ldots$. Also,

$$h'(y) = 2\left(\ln(6) - \frac{3\ln(3)}{2}\right)y - \left(\frac{\ln(3)\sqrt{3}}{2}\right) \tag{6}\label{eq6}$$

Since $h'(\sqrt{246}) = 3.560690\ldots$ and $h'(y)$ is a strictly increasing linear function, this shows that, in summary, $f(x)$ in \eqref{eq2} is always positive for $x \ge 246$, which confirms what you're trying to prove.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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