Let $\Phi(x,p)$ = the number of integers $i$ where $0 < i \le x$ and $\gcd(x,p)=1$.

Let $p\#$ be the primorial for $p$.

Using the inclusion-exclusion principle:

$$\Phi(x,p\#) = \sum_{d|p\#}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor$$

If I apply the Heilbronn-Rohrbach Inequality, does it follow that:

$$\left\lfloor\left(\prod_{q \le p \text{ and q prime}}\frac{q-1}{q}\right)x\right\rfloor \le \sum_{d|p\#}\mu(d)\left\lfloor\frac{x}{d}\right\rfloor \le \left\lceil\left(\prod_{q \le p \text{ and q prime}}\frac{q-1}{q}\right)x\right\rceil$$

I am asking this question because the product is much easier to work with than the sum.

At the same time, my suspicion is that this inequality may be too good to be true. In which case, I am very interested in understanding the circumstances where it is not correct.

  • $\begingroup$ It is too good to be true. For x=10 and p=7, I get 2 less than 1 less than 3. Perhaps you could write down exactly how you apply the inequality to see what it gives you. Gerhard "Gets An E For Effort" Paseman, 2017.06.07. $\endgroup$ – Gerhard Paseman Jun 7 '17 at 18:25
  • $\begingroup$ Also, the key component of the H-R inequality is that the denominators are like lcm(x,y) and not just xy. How are you going to gain any traction with coprime arguments? Gerhard "Is Not Seeing The Utility" Paseman, 2017.06.07. $\endgroup$ – Gerhard Paseman Jun 7 '17 at 19:54
  • $\begingroup$ Thanks very much for calling this out. I suspected that I had not tried enough cases. If you stop at $p=5$, then the equation works. I was not clear how H-R got to this result. Here is the answer that I had been given to one of my questions. Since it works for $p=5$ but doesn't work for $p=7$, I am wondering if there are limited conditions when it is valid. $\endgroup$ – Larry Freeman Jun 7 '17 at 22:26
  • $\begingroup$ @Gerhard, i did some analysis and your example is only true at $n$ below a threshold. I will update my question adding my analysis for $p=10$. It suggests that the inequaliity is true for $n > N$ where $N$ depends on $p$ $\endgroup$ – Larry Freeman Jun 8 '17 at 3:16
  • $\begingroup$ I look forward to your analysis, but I have my reasons for thinking that the last display fails for many values of x. Indeed, knowing how many failures and where would be useful. There is a 1955 paper of D. Lehmer that indicates some x for which it holds, and a 2008 paper of Codeca and Nair that might indicate how often it fails, but work needs to be done to apply it to this case and get some numerics. Gerhard "Computer Run Would Be Faster" Paseman, 2017.06.07. $\endgroup$ – Gerhard Paseman Jun 8 '17 at 4:49

Your Answer

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

Browse other questions tagged or ask your own question.