The number of totatives to the nth primorial, in an interval shorter than the nth primorial

Question

(The notation of this question will be improved over the next few days, sorry for the lack of clarity at the moment.)

Can, and if so when can, we determine the amount of natural numbers which are coprime to the $n$th-primorial number, which exist in an interval with a length smaller than the $n$th-primorial number?

Introduction

For this introduction, we will define some notation to state some formal results in an attempt to answer the above question.

For $n,a, \in \mathbb{N}$, let $S(n,a)$ be defined as the collection of intervals of the natural number line for which the interval $s$ belongs to $S(n,a)$ if it satisfies the following two conditions;

i) $|s|=(1/a) \times p_n \#$

ii) $s$ has the form $\lbrace k \times (1/a) \times p_n\#, ..., ((k+1) \times (1/a) \times p_n\#) -1\rbrace$ where $k$ is a non-negative integer. I.e $s$ is an interval of consecutive integers starting at $k \times (1/a) \times p_n\#$ and ending with $((k+1) \times (1/a) \times p_n\#) -1 $

Furthermore, let $\Lambda(n,a)$ symbolise the number of totatives of the $n$th primorial number, which exist in an interval that belongs to $S(n,a)$.

For example;

a) $\Lambda(n,1)$ is the number of totatives of $p_n \# $ that exist in an interval $s \in S(n,1)$; that interval being $\lbrace 0, ..,p_n\#-1 \rbrace$.

b) $\Lambda(n,2)$ is the number of totatives of $p_n \#$ that exist in an interval $s \in S(n,2)$; that interval could be $ \lbrace 0, .., (1/2 \times p_n \#)-1 \rbrace$ or $ \lbrace(1/2 \times p_n \#), ..., p_n \# -1 \rbrace$.

Note that by definition $\Lambda(n,1)=\phi(p_n \#) = \prod_{i=1}^n p_i -1$, where $\phi$ is Euler's totient function.

$\Lambda(n,1)$

As we know that $\Lambda(n,1)=\prod_{i=1}^n p_i -1$ from the Euler totient function, we will now prove this result using the conceptual tools that will be used to evaluate other values of $\Lambda(n,a)$. The proof uses tools of elementary probability theory, number theory and set theory.

Proof that $\Lambda(n,1)=\prod_{i=1}^n p_i -1$

Consider the interval of consecutive non-negative integers $\alpha_{p,k} = \lbrace a_{0+kp}, a_{1+kp}, ..., a_{p-1+kp} \rbrace$ where $p$ is a prime number and $k \in \mathbb{N}$.

The interval $\alpha_{p,k}$ is a complete set of incongruent residues modulo $p$ (proof excluded). Consequently $|\alpha_{p,k}|=p$.

If we were to select one member of $\alpha_{p,k}$ at random, the probability that this member is congruent to some $r$ modulo $p$ would be $1/p$. In probabilistic terms we consequently say that there is a uniform distribution of incongruent residues modulo $p$ in $\alpha_{p,k}$. A more useful probabilistic identity for our purposes is;

If we were to select one member of $\alpha_{p,k}$ at random, the probability that this member is coprime to $p$ would be $(p-1)/p$.

Now consider the interval $\bigcup_{i=k}^{k+m} \alpha_{p,i} $ where $m \in \mathbb{N}$.

If we were to select one member of $\bigcup_{i=k}^{k+m} \alpha_{p,i} $ at random, the probability that this member is congruent to some $r$ modulo $p$ is still $1/p$ (proof excluded). The probability that this member is coprime to $p$ is also still $(p-1)/p$. I.e.

i) In a interval that is the union of a discrete amount of intervals of the form $\alpha_{p,k}$, the probability that a randomly selected member is congruent to some $r$ modulo $p$ is the same as the probability that a randomly selected member of a single interval of the form $\alpha_{p,k}$, is congruent to some $r$ modulo $p$. This probability is $1/p$.

ii) In a interval that is the union of a discrete amount of intervals of the form $\alpha_{p,k}$, the probability that a randomly selected member is coprime to $p$ is the same as the probability that a randomly selected member of a single interval of the form $\alpha_{p,k}$ is coprime $p$. This probability is $(p-1)/p$.

Now consider the case when an interval $I$ can be written as the union of a discrete amount of intervals of the form $\alpha_{p,i}$, but can also be written as the union of a discrete amount of intervals of the form $\alpha_{q,j}$; such that $I = \bigcup_{i=k}^{k+m} \alpha_{p,i} =\bigcup_{j=c}^{c+d} \alpha_{q,j} $ where $m,d \in \mathbb{N}$, $k,c$ are non negative integers and $q$ is a prime number not equal to the prime number $p$.

It can be proven that if we select a member of $I$ randomly, the probability that the member is congruent to some $r_1$ modulo $p$ is independent of the probability that the member is congruent to some $r_2$ modulo $q$ (proof excluded). The consequences of the independency of those probabilities are;

i)If we select a member of $I$ randomly, the probability that the member is both congruent to some $r_1$ modulo $p$ and congruent to some $r_2$ modulo $q$ is just $1/p \times 1/q$.

ii)If we select a member of $I$ randomly, the probability that the member is both coprime to $p$ and coprime to $q$ is just $((p-1)/p) \times ((q-1)/q)$.

So consider the interval $P_n=\lbrace 0,..., p_n\# -1\rbrace$.

This interval can be written as the union of a discrete amount of intervals of the form $\alpha_{q,k}$ for each prime number $q \leq p_n$. Furthermore;

The interval $P_n$ can be written as the union of $(p_n\#)/q$ amount of intervals of the form $\alpha_{q,k}$ for each prime number $q \leq p_n$.

Therefore;

If we select a member of $P_n$ at random, the probability that the member is coprime to all $q$ where $q \leq p_n$, is $\prod_{i=1}^n (p_i -1)/p_i = (\prod_{i=1}^n p_i -1)/(|P_n|)$.

So the number of totatives of $p_n \#$ in $P_n$ is $\prod_{i=1}^n (p_i -1)$.

Furthermore $P_n$ is the only member of $S(n,1)$, therefore $\Lambda(n,1)=\prod_{i=1}^n p_i -1$, agreeing with Euler's totient function value for $p_n \#$

Q.E.D

$\Lambda(n,p_{n-1}\#)$

This example is purely to show how an argument can go wrong when evaluating some $\Lambda(n,a)$

Remember $\Lambda(n,p_{n-1}\#)$ symbolises the number of totatives of the $n$th primorial number within an interval in $S(n, p_{n-1}\#)$.

Consider the intervals in $S(n, p_{n-1}\#)$. Those intervals are in fact intervals of the form $\alpha_{p_n,k}$ (proof excluded). There certainly exists intervals of the form $\alpha_{p_n,k}$ which contain no totative of the $n$th primorial. Thus we expect that $\Lambda(n,p_{n-1}\#) \ngeq 1$

However, remember that if we select a member of the interval $P_n$ randomly, the probability that it is coprime to $p_n\#$ is $\prod_{i=1}^n (p_i -1)/p_i$.

Observe that $p_{n+1}-1 \geq p_n$ which leads to the following inequality;

Demir inequality: $\prod_{i=1}^n (p_i -1)/p_i \geq 1/p_n$

I'm not sure if this inequality is named (?) but at least for now I will name it the Demir inequality.

From the Demir inequality we get the following result;

If we select a member of $P_n$ randomly, the probability that it is coprime to $p_n\#$ is larger than $1/p_n$

But also from the Demir inequality, it appears to the untrained mathematician that there must be at least one totative of the $n$th primorial number in every interval of the form $\alpha_{p_n,k}$, i.e $\Lambda(n,p_{n-1}\#) \geq 1$, which we know is simply untrue.

To explain this; consider the expression "$\Lambda(n,p_{n-1}\#) \geq 1$" in terms of the behaviour of intervals of the form $\alpha_{q,k}$ where $q \leq p_n$ and is a prime number.

Remember that the amount of intervals of the form $\alpha_{q,k}$ whose union is $P_n$, is $(p_n\#)/q$.

Consider an interval $s \in S(n,q)$, that is an interval of the form $\lbrace k \times (1/q) \times p_n\#, ..., ((k+1) \times (1/q) \times p_n\#) -1\rbrace$ contained in $P_n$ and whose length is $q$.

Now suppose that that the interval $s$ can be expressed as the union of intervals of the form $\alpha_{q,k}$. Then $s$ must be the union of $(p_n\#)/q \times 1/q$ amount of intervals of the form $\alpha_{q,k}$. But $(p_n\#)/q \times 1/q$ can not take an integer value.

Consider what happens when an interval can be expressed as a non-integer value of intervals of the form $\alpha_{q,k}$. Remember that in a interval that is the union of a discrete amount of intervals of the form $\alpha_{q,k}$, the probability that a randomly selected member is coprime to $q$ is the same as the probability that a randomly selected member of a single interval of the form $\alpha_{q,k}$ is coprime $q$. Howeve,r if we were to select a member of an interval which is the union of a discrete amount of intervals of the form $\alpha_{q,k}$ and an interval which is not of the form $\alpha_{q,k}$, the probability that the member is coprime to $q$ is not necessarily $(q-1)/q$. Furthermore there is a variance to $(q-1)/q$ which results from the fact that if we select a member of an interval that is not of the form $\alpha_{q,k}$, the probability that this member is coprime to $q$ depends on the position that this interval would take inside an interval of the form $\alpha_{q,k}$.

Now consider an interval of the form $\alpha_{p_n,k}$ again. An interval of the form $\alpha_{p_n,k}$ cannot be expressed in the form $\bigcup_{i=j}^{j+m} \alpha_{q,i} $ for all $q<p_n$, where $j$ is a non-negative integer and $m\in \mathbb{N}$. Therefore if we select a member of $\alpha_{p_n,k}$ randomly, the probability that the member is coprime to $p_n\#$ is $\prod_{i=1}^n (p_i -1)/p_i \pm V$ where $V$ is the variance resulting from the non-integer amount of intervals of the form $\alpha_{q,i}$ whose union is $\alpha_{p_n,k}$ for some $q<p_n$. Therefore it is not necessarily the case that if we select a member of an interval of the form $\alpha_{p_n,k}$ randomly, the probability that it is coprime to $p_n\#$ is greater or equal to $1/p_n$, for example when $\prod_{i=1}^n (p_i -1)/p_i - V < 1/p_n$. Therefore it is not necessarily the case that $\Lambda(n,p_{n-1}\#) \geq 1$.

Discrete vs Continuous approach

To give some background on the rationality of these arguments, we refer to the concepts of a discrete probabilistic model and a continuous probabilistic model.

Essentially, the model I have used relies on intervals of the form $\alpha_{p,k}$ which can be thought of as cycles of residues modulo $p$. The cycles themselves are treated as discrete packages, whereby we know that $p_n \#$ is the end of the cycles associated with prime numbers upto $p_n$, so we can build this discrete probabilistic model of totatives to the $n$th primorial number. Thereby the rest of this approach relies on discrete probability theory. That is, it relies on being able to identify the amount of intervals of the form $\alpha_{p,k}$ in intervals smaller than $P_n$.

If we don't, we are in effect treating this like a continuous probabilistic model, requiring the calculation of variance to compensate for the differences between the actual discrete probabilistic situation and mathematical tradition, where I am in particularly referring to the probabilities of residue conditions in smaller intervals smaller than $P_n$. Although the variance approach is valid, for now it is simpler to ignore it.

Traditionally, the OP question has been approached with a disregard of using the cycles I mentioned as discrete packages, producing results which rely on variance and are attached to general integers as opposed to numbers relating to $p_n\#$. The reason for this change by me, is that we can directly relate prime numbers to primorial numbers; where all prime numbers less than some $p_{n+1}^2$ are those in the interval $\lbrace p_n, .., (p_{n+1}^2 -1) \rbrace$ which are totatives to the $n$th primorial, essentially the aim of my approach is to model the of distribution prime numbers directly from primorial numbers.

$\Lambda(n,2)$

Let $L|S(n,a), q|$ be the number of intervals of the form $\alpha_{q,k}$ whose union is equal to an interval $s \in S(n,a)$. Restrict $a$ to integers which are only divisible by it's prime factors once. It follows that immediately from a conjecture stated above.

$L|S(n,1), q| =p_n\# /q$ where $q$ is prime number less than or equal to $p_n$

Also we can derive the following result;

$L|S(n,a), q| = 1/a \times L|S(n,1), q|$ iff $gcd(a,q)=1$.

Remember $P_n = \lbrace 0, ..., (p_n \#) -1 \rbrace$ is the only interval in $S(n,1)$. So the conjecture above results from the fact that $L|S(n,1), q| = p_n \# / q $ and if $gcd(a,q)=1 $ then$ L|S(n,1), q|$ is still divisible by $a$ giving us a discrete amount of intervals of the form $\alpha_{q,k}$ whose union is some $s \in S(n,a)$. However if $gcd(a,q)>1$, then L|S(n,1), q| is not divisible by $a$.

For example;

There are half as many intervals of the form $\alpha_{3,k}$ whose union is an interval $s \in S(n,2)$, as there are of intervals of the form $\alpha_{3,k}$ whose union is the interval $P_n$.

There are half as many intervals of the form $\alpha_{q,k}$ whose union is an interval $s \in S(n,2)$, as there is of intervals of the form $\alpha_{q,k}$ whose union is the interval $P_n$ for all $2<q\leq p_n$.

In evaluating $\Lambda(n,2)$ remember that $L|S(n,a), q| = 1/a \times L|S(n,1), q|$ iff $gcd(a,q)=1$ therefore $(L|S(n,2),q|)/(L|S(n,1), q|) = 1/2 $ for all $q : gcd(2,q)=1$. Therefore the statement is true for all $q \leq p_n$ except $q=2$.

So consider $L|S(n,2), 2|$. Remember $L|S(n,1),2| = $p_n# /2$. Note that $p_n# /2$ is odd therefore $(p_n# /2) -1$ is even. Therefore $L|S(n,2), 2]| \geq ((p_n# /2) -1)/2 $.

Consider $L|S(n,2), 2]| = b \times L|S(n,1),2]|$. Then $b \times (p_n\# /2) \geq (((p_n\# /2) -1)/2)$. And so $b = (((p_n\# /2) -1)/2) / (p_n \# /2) = (p_n \# /2) -1) / (p_n \#)$.

Note that $1/2 \geq( (p_n\# /2) -1) / (p_n \#) = b$. Therefore $L|S(n,2), q| \geq b \times L|P_n, q|$ for all $q$ which are prime numbers less than or equal to $p_n$.

Therefore $\Lambda(n,2) \geq b \times \Lambda(n,1)$.

I.e $\Lambda(n,2) \geq ((p_n\# /2) -1) / (p_n \#) \times \prod_{i=1}^n p_i -1$. And following the demir inequality we get that;

$\Lambda(n,2) \geq ((p_n\# /2) -1)/p_n$

For $\Lambda(n,3)$ I got $\Lambda(n,3) \geq ((p_n\# /3) -2)/p_n$

Furthermore

Following the reasoning of this thread we reach the inequality;

$\Lambda(n,a) \geq ((p_n\# /a) -(a-1))/p_n$

So in order to find the smallest interval that contains totatives of $p_n\#$, using this method, we need to solve the following:

$(p_{n-1}\# / a) - (a-1)/p_n \geq 1$. Rearranging this in terms of $a$ we have $(p_{n}\# / a) - (a-1) \geq p_n$ therefore $p_{n}\# - a(a-1) \geq ap_n$ therefore $p_{n}\# \geq ap_n + a(a-1)$

Let $b=p_{n-1}\#$ such that the inequality can now be expressed as $bp_n \geq ap_n + a(a-1)$ Therefore $p_n(b-a) \geq a(a - 1)$. We can see that $a\neq b$ if $a>1$ because we reach a contradiction otherwise.

Now consider $a=p_{n-2}\#$; thus the inequality becomes $p_n(p_{n-1}\# - p_{n-2}\#) \geq (p_{n-2}\#)(p_{n-2}\# -1)$ therefore $p_n (p_{n-1} -1)(p_{n-2}\#) \geq (p_{n-2}\#)(p_{n-2}\# -1)$ therefore $p_n(p_{n-1} -1) \geq (p_{n-2}\# -1)$ which is true for $p_n \leq 11$ i.e

$\Lambda(n,p_{n-2}\#) \geq 1$ when $n \leq 5$; for example, there is at least one totative to $p_5\#$ in an interval $s \in S(5,30)$

Now consider $a=p_{n-3}\#$; thus the inequality becomes $p_n(p_{n-1}\# - p_{n-3}\#) \geq (p_{n-3}\#)(p_{n-3}\# -1)$ therefore $p_n (p_{n-1} p_{n-2} -1)(p_{n-3}\#) \geq (p_{n-3}\#)(p_{n-3}\# -1)$ therefore $p_n(p_{n-1}p_{n-2} -1) \geq (p_{n-3}\# -1)$.

Generalizing this for $a=p_{n-d}\#$ where $d<n$; the inequality becomes $p_n(p_{n-1}\# - p_{n-d}\#) \geq (p_{n-d}\#)(p_{n-d}\# -1)$ therefore $p_n (p_{n-1} p_{n-2} ...p_{n-(d-1)} -1)(p_{n-d}\#) \geq (p_{n-d}\#)(p_{n-d}\# -1)$ therefore $p_n(p_{n-1}p_{n-2} ... p_{n-(d-1)} -1) \geq (p_{n-d}\# -1)$. I.e

An interval $s \in S(n,p_{n-d}\#)$ for $d<n$, contains a totative of $p_n\#$ if $n,d$ satisfy the following inequality; $p_n(p_{n-1}p_{n-2} ... p_{n-(d-1)} -1) \geq (p_{n-d}\# -1)$.

Agree/Disagree?

Answer 1

Probabilistically, at least, we know how the coprimes to $p_k\#$ are distributed in intervals of length $h$.In general, considering the number of coprimes to $n$ in an arbitrary interval of length $h$, the expectance is given by $$h \frac{\phi(n)}{n},$$ where $\phi(n)$ is the Euler totient function. If $n$ is odd, the variance is given by \begin{align*} G(n,h) = \prod_{ \substack{ {p \mid n} } } \left( 1-\frac{2}{p} \right) \sum_{ \substack{ {d \mid n} } } \frac{\mu^2(d)}{\rho(d)} d \left\{\frac{h}{d}\right\} \left( 1 - \left\{\frac{h}{d}\right\} \right). \end{align*} If $n$ is even the variance is given by \begin{align*} G(n,h) = \prod_{ \substack{ {p \mid n'} } } \left( 1-\frac{2}{p} \right) \sum_{ \substack{ {d \mid n'} } } \frac{\mu^2(d)}{\rho(d)} d \left\{\frac{h}{2d}\right\} \left( 1 - \left\{\frac{h}{2d}\right\} \right). \end{align*} Here $n'$ is the largest odd divisor of $n$, $\mu(n)$ is the Möbius function, $\rho(n) := \prod_{p \mid n}(p-2)$ for any squarefree integer $n$, and {x} is the fractional part of x. The derivation of these expressions can be found in the article On the mean square distribution of primitive roots of unity by Hausman and Shapiro.

Note that through the inequality $\{x\} ( 1 - \{x\} ) \leq x$, $G(n,h)$ satisfies the upper bound
\begin{align*} G(n,h) \leq h \frac{\phi(n)}{n}. \end{align*} This bound holds for even and odd $n$.

For an actual example of the supremum and infimum of the number of coprimes to $p_k\#$ in an interval of length $h$, consider the following plot for $k=5$ (red and blue, mean subtracted) plotted together with the standard deviations $\pm\sqrt{G(p_k\#,h)}$ (black):

Answer 2

Since I haven't posted this construction on MathOverflow (only referred to an ArXiv posting at Erik Westzynthius's cool upper bound argument: update? ), let me show that one can have intervals of the given type for small values of $d$.

Using the notation of the problem, $n$ (not $k$, as in the ArXiv posting) is the number of distinct prime factors, and $N=p_n$# (not $n$) is the number to which we are finding totatives in arbitrary intervals. Conveniently for me, $N$ and its divisors are squarefree. Let us pick $m$ smallest so that $1 - \sum_{m \lt j \leq n} 1/p_j \gt 1/p_m$. Some sample values of $[n,m]$ for different $n$ are: [10, 3], [100, 5] [1000,10]. For large enough $n$, $m^e \lt n$ by using Mertens' theorem on estimating sums of reciprocals of primes.

Now let us look at an interval containing $L$ integers and consider totatives of $M=p_m$# in this interval. There are about $L\pi^{-1}(M)$ many such, where I measure the density of totatives in an interval by $\pi^{-1}(M) = \phi(M)/M$, and this estimate of $L\pi^{-1}(M)$ is off from reality by at most $2^m$. (If the interval had 0 as an endpoint, I could use $2^{m-1}$ for an error.) We will later upper bound $1/\pi^{-1}(M)$ by $4\log m$. Now there will be fewer numbers which are also totatives of $N$: for each prime $p_j$ with $m \lt j \leq n$, this will be those totatives of $M$ not divisible by $p_j$. So about $L\pi^{-1}(M)/p_j$ members of the $L$ integers are not totatives of $N$ because they are totatives of $M$ and multiples of the prime $p_j$.

So let's add up the number of all these nontotatives and include some error terms, which I will explain near the end. The number of nontotatives of $N$ is (possibly overcounted by) $L(1 - \pi^{-1}(M)) + E_1 + \sum_{m \lt j \leq n} (L\pi^{-1}(M)/p_j + E_j)$. If we pick $L$ large enough that this quantity is smaller than $L$, we have a totative in the interval. Rearranging terms, we want $$ \frac{E_1 + \sum_{m \lt j \leq n} E_j}{\pi^{-1}(M)(1 - \sum_{m \lt j \leq n} 1/p_j)} \lt L . $$

Now, $E_1$ represents the error for our estimate of nontotatives of $M$ in the interval, which has the same absolute value as our estimate of totatives in that interval. This value is bounded by $2^m$. For $m \lt j \leq n$, $E_j$ is the error estimating the number of totatives to $M$ in a different interval, namely one of length about $L/p_j$, since these correspond to their multiples by $p_j$ in the original interval. Although one would hope for better estimates on $E_j$, I will use the same one: $2^m$. Because of the choice of $m$, and my weak upper bound on $1/\pi^{-1}(M)$, I can weaken the inequality to say that if $2^{m+2}(n-m+1)p_m\log m \lt L$, then one of the $L$ integers is a totative of $N$. Translated to the present problem, this says that for $n$ big enough (likely $n \gt 10$), picking $d$ less than but close to $n^{1/e}$ will give a totative to $p_n$# in any interval of length $p_n$#$/p_{n-d}$#.

Although I like this result, one can actually give an asymptotically better explicit result using methods found in Opera di Cribro and work of Harlan Stevens. These give interval lengths like $n^{4 + 4\log\log n}$, which is asymptotically not as good as Iwaniec's inexplicit $C(n\log n)^2$ or the hoped-for $n(\log n)^2$, similar to a conjecture of Cramer.

Gerhard "Still Looks Pretty To Me" Paseman, 2015.09.10