Skip to main content
added 108 characters in body
Source Link
user45947
  • 965
  • 4
  • 17

InProbabilistically, 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):

coprime bounds

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

coprime bounds

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

coprime bounds

added 335 characters in body
Source Link
user45947
  • 965
  • 4
  • 17

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

coprime bounds

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

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

coprime bounds

Source Link
user45947
  • 965
  • 4
  • 17

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