3
$\begingroup$

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).

$\endgroup$
1
  • $\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$ May 20, 2019 at 21:26

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .