10
$\begingroup$

I've been thinking about how factorials compare to primorials. I have not seen this argument before. If I made a mistake, please call it out. :-)

Let $x+1, x+2, \dots, x+n$ be a sequence of consecutive integers.

Let $r_{x,1},r_{x,2},\dots,r_{x,n}$ have the following properties:

  • $r_{x,i} | (x+i)$
  • $r_{x,1}, r_{x,2}, \dots, r_{x,n}$ are all relatively prime to each other.
  • $\prod\limits_{i \le n}r_{x,i}$ is the least common multiple for $x+1, x+2, \dots, x+n$

Example:

  • Let $x=35, n=5$ so that we have $36, 37, 38, 39, 40$
  • $r_{35,1}=9, r_{35,2} = 37, r_{35,3} = 19, r_{35,4}=13, r_{35,5}=40$
  • Each $r_i$ is relatively prime to each other and the product of all equals the least commmon multiple.

Let $r(x,n) = \prod\limits_{i \le n}r_{x,i}$

Claim 1: For $x \ge 36$, $\pi(x) \le \left\lfloor\frac{x}{3}\right\rfloor$

Except for $2,3$ all primes are $6x+1$ or $6x+5$.

If $x \ge 36$:

$\pi(x) \le \pi(36) + \left\lfloor\frac{x+1-36}{6}\right\rfloor + \left\lfloor\frac{x+5-36}{6}\right\rfloor \le \left\lfloor\frac{66}{6}+\frac{x-35}{6} + \frac{x-31}{6}\right\rfloor = \left\lfloor\frac{x}{3}\right\rfloor$

Claim 2: For $n \ge 36$, assuming no primes between $n$ and $2n$, there are at least $\left\lfloor\frac{2n}{3}\right\rfloor$ instances of distinct $i$ where $r_{n,i}=1$.

Note: These instances could occur anywhere between $n$ and $2n$.

Since $r_{n,1}, r_{n,2}, \dots, r_{n,n}$ are relatively prime to each other and there are less than or equal to $\left\lfloor\frac{n}{3}\right\rfloor$ primes, the rest must be $1$ and since each prime is uniquely found in one and only one $r_{n,i}$

Claim 3: For $n \ge 36$, $\dfrac{(2n)!}{n![r(n,n)]} \ge \dfrac{\left(n+\left\lfloor\frac{2n}{3}\right\rfloor\right)!}{n!}$ and $r(n,n) \le \dfrac{(2n)!}{\left(2n-\left\lfloor\frac{n}{3}\right\rfloor\right)!}$

Both of these follow directly from Claim 2:

  • $r(n,n) < \dfrac{(2n)!}{\left(2n-\left\lfloor\frac{n}{3}\right\rfloor\right)!}$ since there at most $\left\lfloor\frac{n}{3}\right\rfloor$ instances where $r_{n,i}\ne1$ and the product of any such instances is less than or equal to $\dfrac{(2n)!}{\left(2n-\left\lfloor\frac{n}{3}\right\rfloor\right)!}$

  • $\dfrac{(2n)!}{n![r(n,n)]} > \dfrac{\left(n+\left\lfloor\frac{2n}{3}\right\rfloor\right)!}{n!}$ since $\dfrac{(2n)!}{n![r(n,n)]} = \prod\limits_{i \le n \text{ and } r_{n,i}=1} (n+i)$ and there are at least $\left\lfloor\frac{2n}{3}\right\rfloor$ instances where $r_{n,i}=1$ and the product of any $\left\lfloor\frac{2n}{3}\right\rfloor$ instances will be greater or equal to $\dfrac{\left(n+\left\lfloor\frac{2n}{3}\right\rfloor\right)!}{n!}$.

Claim 4: $\dfrac{\left(n+\left\lfloor\frac{2n}{3}\right\rfloor\right)!}{n!} > \dfrac{(2n)!}{\left(2n-\left\lfloor\frac{n}{3}\right\rfloor\right)!}$

  • $\left\lfloor\frac{2n}{3}\right\rfloor \ge 2\left\lfloor\frac{n}{3}\right\rfloor$
  • The product of any two instances of $(n+i)(n+j)$ will be greater than $(n+1)(n+2) = n^2+3n + 2 > 2n$ for $n \ge 1$.
  • It follows that the $\left\lfloor\frac{2n}{3}\right\rfloor$ can be ordered into $\left\lfloor\frac{n}{3}\right\rfloor$ pairs of $2$ instances.

Claim 5: For $n \ge 36$, it is impossible that there are no primes between $n$ and $2n$.

Since $\dfrac{\left(n+\left\lfloor\frac{2n}{3}\right\rfloor\right)!}{n!} > \dfrac{(2n)!}{\left(2n-\left\lfloor\frac{n}{3}\right\rfloor\right)!}$, applying Claim 2 and Claim 3, it follows that:

$ \dfrac{1}{2}\dfrac{(2n)!}{n!} < \dfrac{(2n)!}{n![r(n,n)]}$

But this is impossible since $r(n,n) \ge n\# > 2$


Edit 1: I found some minor problems with Claim 2 and Claim 3.

While Claim 1 establishes that $\pi(x) \le \left\lfloor\frac{x}{3}\right\rfloor$, these primes could be at any point between $n+1$ and $2n$. It is not correct to assume that $r_{n,i}=1$ for $i > \left\lfloor\frac{n}{3}\right\rfloor$

I have modified argument to remove this assumption.


Edit 2: It looks like my definition of $r_i$ does not work as I expected.

For example for the sequence $36, 37, 38, 39, 40$, by my previous definition: $r_1=36, r_2=37, r_3 = 19, r_4=13, r_5=10$. But then, $\gcd(r_1,r_5)=2$.

I have updated the definition which I believe fixes the issue.


Edit 3: Removed a reference to primorial which I had missed and updated the last sentence.

It is not essential to the argument but it is incorrect. Thanks to @mathlove for noticing it.


Edit 4: Updated claim 3 based on comment by @JonMark Perry.


Edit 5: Claim 5 is not valid. See answer or comments for detail.

$\endgroup$
  • $\begingroup$ Why are the $r_{x,i}$ integers? $\endgroup$ – amakelov May 2 '17 at 22:37
  • $\begingroup$ Yeah, choose $x=i=p$ for some prime $p>2$ $\endgroup$ – amakelov May 2 '17 at 22:42
  • 1
    $\begingroup$ You might want to edit the last sentence before "Edit 1". $\endgroup$ – mathlove May 5 '17 at 5:56
  • 1
    $\begingroup$ I think your arguments in Claim 1, 2, 3, 4 are fine, but I can't understand how you get $\dfrac{1}{2}\dfrac{(2n)!}{n!} < \dfrac{(2n)!}{n![r(n,n)]}$ from Claim 2, 3 and 4. Can you please elaborate? $\endgroup$ – didgogns May 5 '17 at 12:55
  • 1
    $\begingroup$ your proof of claim 3 proves $\le$, but the statement claims $\lt$ $\endgroup$ – JMP May 6 '17 at 2:04
4
+50
$\begingroup$

Claim $5$ claims too much. We only have:

$$\frac{(2n)!}{n![r(n,n)]} \ge \frac{\left(n+\left\lfloor\frac{2n}{3}\right\rfloor\right)!}{n!} \ge \dfrac{(2n)!}{\left(2n-\left\lfloor\frac{n}{3}\right\rfloor\right)!} \ge r(n,n)$$

$\endgroup$
  • $\begingroup$ I agree the question is great, and there was a bounty, but only one upvote? Usually the balance is the other way. +1 $\endgroup$ – daniel May 12 '17 at 18:05

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.