Review Suggested Edit

You can't approve or reject suggested edits because you haven't yet earned the Edit Posts ability.

Let $\alpha$ be the smallest exponent such that we know how to calculate $\pi(n)$ in time $\tilde O(n^\alpha)$. Courtesy of Deléglise and Rivat, who removed the $+ \epsilon$ from Lagarias, Miller and Odlyzko's bound, we know that $\alpha \le \tfrac23$, but I'm going to work in terms of $\alpha$ because (a) I'm not aware that it has been lower-bounded; (b) it saves having to update this post if anyone finds a better upper bound; (c) it makes the algebra simpler.
Obviously if the signature has only one element then $\pi_{\\{a\\}}(n) = \pi(\lfloor n^{1/a}\rfloor)$ and can be calculated in $\tilde O(n^{\alpha/a})$ time.
Otherwise let $s = \\{a_1, a_2, \ldots, a_k\\}$; we sum over all primes $p$ the value of $\pi_{\\{a_2, \ldots, a_k\\}}(\lfloor n / p^{a_1}\rfloor)$, exclude numbers which don't have distinct primes by subtracting $\pi_{s'}(n)$ for each distinct $s'$ formed by merging $a_1$ with some other $a_i$, and correct for double-counting of permutations of the primes by dividing by the frequency of $a_1$ in the signature.
The core sum here is $S = \sum_{p \in \mathbb{P}} \pi_{\\{a_2, \ldots, a_k\\}}(\lfloor n / p^{a_1}\rfloor)$. (If that isn't obvious, you can take the following as a template for a fixed value of $k$ and then induct over $k$). Using standard tricks, and leaving $t$ for the time being as a variable,
\begin{eqnarray}
S &=& \sum_{p \in \mathbb{P}} \left[\left\lfloor \tfrac{n}{p^{a_1}} ight floor > \left\lfloor \tfrac{n}{t} ight floor ight] \pi_{\ldots}\left(\left\lfloor \tfrac{n}{p^{a_1}} ight floor ight) + \sum_{j=1}^{\lfloor n/t floor} \pi_{\ldots}(j) \sum_{p \in \mathbb{P}} \left[j = \left\lfloor \tfrac{n}{p^{a_1}} ight floor ight] \\
&=& \sum_{p \in \mathbb{P}} \left[\left\lfloor \tfrac{n}{p^{a_1}} ight floor > \left\lfloor \tfrac{n}{t} ight floor ight] \pi_{\ldots}\left(\left\lfloor \tfrac{n}{p^{a_1}} ight floor ight) + \sum_{j=1}^{\lfloor n/t floor} \pi_{\ldots}(j) \left(\pi(\lfloor \tfrac{n}{j} floor^{1/a_1}) - \pi(\lfloor \tfrac{n}{j+1} floor^{1/a_1}) ight) \\
\end{eqnarray}
If we let $t = n^b$ and assume that evaluating $\pi_{\\{a_2, \ldots, a_k\\}}(m)$ is in $\tilde O(m^c)$ then our main sum takes $\tilde O(t^{1/a_1})$ to sieve primes, $\tilde O(\sum_{p \in \mathbb{P}, p^{a_1} < t} (n / p^{a_1})^c)$ for recursive calls in the first sum, $\tilde O(\sum_{j=1}^{n/t} j^c)$ for recursive calls in the second sum, and $\tilde O(\sum_{j=1}^{n/t} (n/j)^{\alpha/a_1})$ for calls to $\pi$ in the second sum. Since the density of primes is within a logarithmic factor of constant, the bound for recursive calls in the first sum doesn't lose anything by being simplified to $\tilde O(\sum_{p=1}^{t^{1/a_1}} (n / p^{a_1})^c)$.
Thus our asymptotic cost is $\tilde O(n^{\beta})$ where
\begin{eqnarray}
~~\beta &=& \max(\tfrac{b}{a_1}, c + \tfrac{b}{a_1}(1 - a_1 c), (1-b)(1+c), \tfrac{\alpha}{a_1} + (1-b)(1 - \tfrac{\alpha}{a_1})) \\~~
~~&=& \max(\tfrac{b}{a_1}, c(1 - b) + \tfrac{b}{a_1}, (1-b)(1+c), 1 - b + \tfrac{\alpha b}{a_1}) \\~~
~~% &=& \max(c(1 - b) + \tfrac{b}{a_1}, (1-b)(1+c), 1 - b + \tfrac{\alpha b}{a_1}) \\~~
&=& \max(c + b(\tfrac{1}{a_1} - c), (1+c) - (1+c)b, 1 + b(\tfrac{\alpha}{a_1} - 1))
\end{eqnarray}
and we want to choose $b$ to minimise it. If $a_1 c \ge 1$ (i.e. if $\tfrac{1}{a_1} - c \le 0$) then all of the lines have non-positive gradients, so we minimise them by setting $b = 1$ and we get an overall cost of $\beta = \max(\tfrac{1}{a_1}, 0, \tfrac{\alpha}{a_1}) = \tfrac{1}{a_1}$.
Otherwise the minimum value of $\beta$ will be found at an intersection of one of the falling lines with the rising one; case analysis reveals that if $c < \alpha$ we want $b = \tfrac{(1 - c)a_1}{(1 - c)a_1 + 1 - \alpha}$ for $\beta = \tfrac{1 - \alpha c}{(1 - c)a_1 + 1 - \alpha}$; otherwise we want $b = \tfrac{a_1}{a_1 + 1}$ for $\beta = \tfrac{c+1}{a_1 + 1}$.
Observe that the very best value of $\beta$ is obtained when $c=0$ and is $\beta_0 = \tfrac{1}{a_1 + 1 - \alpha}$. Thus $\tfrac{1}{a_1 + 1} < \beta \le \tfrac{1}{a_1}$, and so if we order the prime signature descending then we can evaluate $\pi_s(n)$ in time $\tilde O(n^{1/\max(s)})$.

Let $\alpha$ be the smallest exponent such that we know how to calculate $\pi(n)$ in time $\tilde O(n^\alpha)$. Courtesy of Deléglise and Rivat, who removed the $+ \epsilon$ from Lagarias, Miller and Odlyzko's bound, we know that $\alpha \le \tfrac23$, but I'm going to work in terms of $\alpha$ because (a) I'm not aware that it has been lower-bounded; (b) it saves having to update this post if anyone finds a better upper bound; (c) it makes the algebra simpler.
Obviously if the signature has only one element then $\pi_{\\{a\\}}(n) = \pi(\lfloor n^{1/a}\rfloor)$ and can be calculated in $\tilde O(n^{\alpha/a})$ time.
Otherwise let $s = \\{a_1, a_2, \ldots, a_k\\}$; we sum over all primes $p$ the value of $\pi_{\\{a_2, \ldots, a_k\\}}(\lfloor n / p^{a_1}\rfloor)$, exclude numbers which don't have distinct primes by subtracting $\pi_{s'}(n)$ for each distinct $s'$ formed by merging $a_1$ with some other $a_i$, and correct for double-counting of permutations of the primes by dividing by the frequency of $a_1$ in the signature.
The core sum here is $S = \sum_{p \in \mathbb{P}} \pi_{\\{a_2, \ldots, a_k\\}}(\lfloor n / p^{a_1}\rfloor)$. (If that isn't obvious, you can take the following as a template for a fixed value of $k$ and then induct over $k$). Using standard tricks, and leaving $t$ for the time being as a variable,
\begin{eqnarray}
S &=& \sum_{p \in \mathbb{P}} \left[\left\lfloor \tfrac{n}{p^{a_1}} ight floor > \left\lfloor \tfrac{n}{t} ight floor ight] \pi_{\ldots}\left(\left\lfloor \tfrac{n}{p^{a_1}} ight floor ight) + \sum_{j=1}^{\lfloor n/t floor} \pi_{\ldots}(j) \sum_{p \in \mathbb{P}} \left[j = \left\lfloor \tfrac{n}{p^{a_1}} ight floor ight] \\\\
&=& \sum_{p \in \mathbb{P}} \left[\left\lfloor \tfrac{n}{p^{a_1}} ight floor > \left\lfloor \tfrac{n}{t} ight floor ight] \pi_{\ldots}\left(\left\lfloor \tfrac{n}{p^{a_1}} ight floor ight) + \sum_{j=1}^{\lfloor n/t floor} \pi_{\ldots}(j) \left(\pi(\lfloor \tfrac{n}{j} floor^{1/a_1}) - \pi(\lfloor \tfrac{n}{j+1} floor^{1/a_1}) ight) \\\\
\end{eqnarray}
If we let $t = n^b$ and assume that evaluating $\pi_{\\{a_2, \ldots, a_k\\}}(m)$ is in $\tilde O(m^c)$ then our main sum takes $\tilde O(t^{1/a_1})$ to sieve primes, $\tilde O(\sum_{p \in \mathbb{P}, p^{a_1} < t} (n / p^{a_1})^c)$ for recursive calls in the first sum, $\tilde O(\sum_{j=1}^{n/t} j^c)$ for recursive calls in the second sum, and $\tilde O(\sum_{j=1}^{n/t} (n/j)^{\alpha/a_1})$ for calls to $\pi$ in the second sum. Since the density of primes is within a logarithmic factor of constant, the bound for recursive calls in the first sum doesn't lose anything by being simplified to $\tilde O(\sum_{p=1}^{t^{1/a_1}} (n / p^{a_1})^c)$.
Thus our asymptotic cost is $\tilde O(n^{\beta})$ where
\begin{eqnarray}
\beta &=& \max(\tfrac{b}{a_1}, c + \tfrac{b}{a_1}(1 - a_1 c), (1-b)(1+c), \tfrac{\alpha}{a_1} + (1-b)(1 - \tfrac{\alpha}{a_1})) \\\\
&=& \max(\tfrac{b}{a_1}, c(1 - b) + \tfrac{b}{a_1}, (1-b)(1+c), 1 - b + \tfrac{\alpha b}{a_1}) \\\\
% &=& \max(c(1 - b) + \tfrac{b}{a_1}, (1-b)(1+c), 1 - b + \tfrac{\alpha b}{a_1}) \\\\
&=& \max(c + b(\tfrac{1}{a_1} - c), (1+c) - (1+c)b, 1 + b(\tfrac{\alpha}{a_1} - 1))
\end{eqnarray}
and we want to choose $b$ to minimise it. If $a_1 c \ge 1$ (i.e. if $\tfrac{1}{a_1} - c \le 0$) then all of the lines have non-positive gradients, so we minimise them by setting $b = 1$ and we get an overall cost of $\beta = \max(\tfrac{1}{a_1}, 0, \tfrac{\alpha}{a_1}) = \tfrac{1}{a_1}$.
Otherwise the minimum value of $\beta$ will be found at an intersection of one of the falling lines with the rising one; case analysis reveals that if $c < \alpha$ we want $b = \tfrac{(1 - c)a_1}{(1 - c)a_1 + 1 - \alpha}$ for $\beta = \tfrac{1 - \alpha c}{(1 - c)a_1 + 1 - \alpha}$; otherwise we want $b = \tfrac{a_1}{a_1 + 1}$ for $\beta = \tfrac{c+1}{a_1 + 1}$.
Observe that the very best value of $\beta$ is obtained when $c=0$ and is $\beta_0 = \tfrac{1}{a_1 + 1 - \alpha}$. Thus $\tfrac{1}{a_1 + 1} < \beta \le \tfrac{1}{a_1}$, and so if we order the prime signature descending then we can evaluate $\pi_s(n)$ in time $\tilde O(n^{1/\max(s)})$.

Communities

Review Suggested Edit