MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let [a,b] = {k integer | a < k <= b}. Further let

  • Comp[a,b] = product_{c in [a,b]} c composite;
  • Fact[a,b] = product_{k in [a,b]} k integer;
  • Prim[a,b] = product_{p in [a,b]} p prime.

Question: For n > 2 and n not in {10,15,27,39} is it true that

$$ \text{Comp}[{\left\lfloor n /2 \right\rfloor}, n] < \text{Fact}[1, {\left\lfloor n /2 \right\rfloor}] \ \text{Prim}[{\left\lfloor n /2 \right\rfloor}, n] \ ? $$

Update: The state of affairs: Gjergji Zaimi showed that for large enough n the inequality is true. In my answer I affirm that the inequality is true in the range 40 <= n <= 10^5. It remains open whether 10^5 is 'large enough' in the sense of Gjergji's analysis.

share|cite|improve this question
This problem is as much "localized" as Bertrand's postulate is as the latter is an immediate consequence thereof. So at least this would lead to a proof of Bertrand's postulate which, concluding from your answer, is not widely known. "Motivate the rather odd looking exceptional set." I cannot. However I can point to the fact that most number theoretic inequalities have a lower bound with regard to their validity (see for example the formulas in Rosser, Schoenfeld on prime numbers). What you call 'odd looking' is an ubiquitous phenomenon in formulas which involve prime numbers. – Bruce Arnold Jan 2 '10 at 18:32
Yes Jose: this seems to me to be a perfectly reasonable question. It says "does the product of the primes in some region beat the product of the composites by some given factor, at least for n sufficiently large". Maybe you would have liked it better if he had written "for all n sufficiently large" rather than given the exceptional set? The exceptional set is just noise at the beginning (and almost certainly has nothing to do with your Sloane link). – Kevin Buzzard Jan 2 '10 at 20:03
@Bruce: I'm not asking for a defense, I agree it is interesting. What I'm asking for is an edit of the question. Instead of having me (and future readers) trying to figure out why the question is interesting, please edit the question to inform us why you find it interesting--what led you to it, applications, similar problems, etc. Thank you. – Ben Weiss Jan 2 '10 at 21:09
This seems to be a rather unattractive formulation of the question "Is the product of the primes between n and 2n bigger than sqrt(2n choose n)?" – Reid Barton Jan 2 '10 at 23:01
I'm just suggesting that the question be put into a "normal form" so that people who know about this stuff can see how strong a bound it is. – Reid Barton Jan 2 '10 at 23:28
up vote 9 down vote accepted

This answer is just to point out that the result is true for large enough $n$. Let's rewrite it as $$\prod_{n\le p\le 2n}p > \sqrt{\binom{2n}{n}}$$ Since $\binom{2n}{n}\approx \frac{4^n}{n}$ introducing Chebyshev's functions $$\theta(x)=\sum_{p\le x}\text{log}p\quad,\quad \psi(x)=\sum_{p^{\alpha}\le x}\text{log}p$$ They satisfy $$\psi(x)=\theta(x)+O(\sqrt{x}\text{log}^2x)$$ What we want to prove is $$\theta(2n)-\theta(n) > n\text{log}2$$ It is a well-known asymptotics that $$\psi(x)=x+O(x\text{exp}(-c\sqrt{\text{log}x}))$$ for some positive $c$. In fact under the Riemann Hypothesis it is even true that $$\psi(x)=x+O(\sqrt{x}\text{log}^2x)$$ but we don't need this refinement. Now $$\theta(2n)-\theta(n)=n+O(n\text{exp}(-c\sqrt{\text{log}n}))$$ and this proves your assertion for large enough $n$. A good reference where all these results are proven is for example "Problems in Analytic Number Theory" by M.Ram Murty. I hope this helps, even though I did not mention any thing about possible small counterexamples. To find the smallest $n$ for which this argument works you'd have to look up each of these equations individually and look for specific bounds.

share|cite|improve this answer
Thanks Gjergjj. IMO a virtue of the down voted question is that it links the parlance as seen on popular sites like 'The Prime Glossary' (but also on Math. of Comp.) using the terms 'compositorial', 'factorial' and 'primorial' with the Chebyshev's arithmetic functions. The part of the question which is concerned with 'possible small counterexamples' remains open. An effective lower bound of the validity of your asymptotic analysis is still appreciated. – Bruce Arnold Jan 3 '10 at 13:44

A computational approach to the Compositorial-Factorial-Primorial Inequality (CFPI).

Let $u_{0}=1,u_{1}=1,u_{2}=1/2$ and for $n>2$ define $u_{n}$ by $$ {\text{if}\ n\ \ \text{odd} \ \text{then }\text{if}\ n\ \ prime\ \ \text{then } \ u_{n}=1/n\text{ else }u_{n}=n\ \text{fi}\ \text{fi};} $$ $$ {\text{if}\ n\ \text{even}\ \text{then } \text{if}\ n/2\ prime\ \text{then}\ u_{n} =n\text{ else }u_{n}=4/n\ \text{fi}\ \text{fi}.} $$ Let the sequence of partial products of $u_{n}$ given by $U_{0}=1$ and $$ U_{n}=U_{n-1}u_{n}\quad\left( n>0\right) . $$ The CFPI as stated in the question is equivalent to the statement $$ \text{numerator }U_{n}<\text{denominator }U_{n}\quad\left(n\geq40\right) .$$

Using this algorithm I checked the CFPI in the range $40 \leq n \leq 10^5$ and found no counterexamples.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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