What if $\sigma_0(n)$ could be computed efficiently? (Part 3)

The $\sigma_i(n)$ function is an important arithmetic function and as typical for such functions, it can not be computed efficiently for large input parameters $n$ due to the factorization problem. But in contrast to $\sigma_1(n)$, which does reveal the factorization of $n$ immediately (at least if $n=pq$), $\sigma_0(n)$ does not, or at least not that easy (see Part 2 and Part 1). Additionally, $\sigma_1(n)$ has also the strange property that it can be computed recursively, as i showed in that [post].

However, we know how to compute, or better, how to decide, if $\sigma_0(n)$ is $2$ or not. This is because $\sigma_0(n) = 2$ if and only if $n$ is a prime number. And primality can be checked by the AKS-Algorithm in deterministic polynomial time. If AKS is too slow for you, there much more faster probabilistic polynomial time algorithms. They utilize that a prime number has special properties, e.g., they use Fermat-Little-Theorem. But so called base-$b$ pseudo prime numbers can survive this process and still pretend to be a prime number. Repeating the whole process with different values for $b$ often helps. Only a few pseudo prime numbers still remain for nearly all choices of $b$. These numbers are called carmichael numbers, and in [1] it was proved that there are infinite many such numbers. However, the probability to announce a false-positive for such algorithm is negligible after a few rounds.


To compute $\sigma_0(n)$ for composite integers $n$, one has to use different paths. There exists Zero-Knowledge proofs, that can be used to prove against a verifier that an integer is e.g., the product of two safe primes or that it is square-free. And for the later type of number, Adleman even presented a Zero-Knowledge proof regarding their number of prime factors. He uses that the number of real quadratic residues in $\mathbb{Z}^*_N$ is ~ $N/2^m$ if $N$ has $m$ prime factors. Given a list of $k$ random integers, the prover will be only able to compute around $k/2^m$ quadratic roots in that case, which can be verified independently. Furthermore, it is also efficiently possible to decide if $N$ is a square or a perfect power.

# Another approach #

For the rest, i assume that $N$ is square-free. I will talk about another approach that perhaps may lead to another view on the problem to get information about $\sigma_0(n)$. The basic observation is that, if $N$ has $m$ prime factors, then the number of divisors is $2^m$, from which you can build $2^{m}$ distinct pairs $(d_i,N/d_i)$. As i showed in this [post], whenever the difference $pq-N$ is a prime number $> \sqrt{N}$, then the two integers $p-d_i$ and $q-N/d_i$ have to be co-prime, and that must hold for all divisors $d_i$. You can calculate that probability, assuming that $p$ and $q$ are random. The graph for the first values of $N$ looks like

Figure 1: The probability that an integer $N$ creates co-prime pairs.  (The points are connected only due to visual reasons.)

So for example, pick the integer $15$, which has divisors $1,3,5,15$. The probability that, for random $p$ and $q$, it is

• $\gcd(p-1,q-15) = 1$
• $\gcd(p-3,q-5) = 1$
• $\gcd(p-5,q-3) = 1$
• $\gcd(p-15,q-3) = 1$

simultaneously, is around $30\%$. The function that outputs that probability for each integer (see Figure 1), has the typical behaviour as other arithmetical functions, which is mostly due to the fact, that an integer's prime factorization is involved. It jumps around rapidely and shows no obvious predicable pattern. For $N=1$, you get the known value of $6/\pi^2 \approx 61\%$.

Obviously, the more prime factors $\rightarrow$ the more pairs $\rightarrow$ the less is the chance that all this pairs are co-prime, which can also be seen from the picture above. Let us call this the $\mathcal{P}$-Function. It takes as the input an integer $N$ and computes the probability that all the pairs, that are created by the divisors of $N$ are co-prime $$\mathcal{P}: \mathbb{N} \rightarrow [0,1]$$ So Figure 1 shows $\mathcal{P}$ for the input values $1$ to $50$. The function has some interesting properties, and i am going to write all this up in a paper. For example you can ask: Are there two integer $N_1$ and $N_2$ with $\mathcal{P}(N_1)=\mathcal{P}(N_2)$? If no, is $\mathcal{P}^{-1}(N)$ computable? Efficiently? If yes, what precision is necessary?

But i am still unsure what can be concluded from the rule: $$\text{If } \sqrt{N} < pq-N \in \mathbb{P} \text{ then } \gcd(p-d_i,q-N/d_i) = 1\text{ for all divisors }d_i\text{ of }N$$ My hope was, that this can be used to give a prediction, perhaps even only a very bad prediction, about $\mathcal{P}(N)$. Assume the two integers $A$ and $B$ set were created by the following algorithm:

1. Set $A = B = 0$.
2. Generate $p$ and $q$ randomly from the interall $I$.
3. Test if $\gcd(p-d_i,q-N/d_i) = 1$ for all divisors $d_i$ of $N$
4. If this is true $A = A + 1$
5. If false, i.e., at least one pair is not co-prime, $B = B + 1$.
6. Goto Step 2.

After enough rounds it holds $\mathcal{P}(N) \approx \frac{A}{A+B}$. For this algorithm, the factorization of $N$ must be known. However, $N$ is unknown, then the information $\sqrt{N} < pq-N \in \mathcal{P}$ is already enough to decide that they are co-prime, hence $A = A + 1$.

If this all is not sufficient, one actually can also take all the divisors of $pq$ into account, since the following is true:

Lemma. If $\sqrt{N} < pq-N \in \mathbb{P}$ then $\gcd(\delta_j-d_i,pq/\delta_j-N/d_i) = 1$ for all divisors $d_i$ of $N$ and for all divisors $\delta_j$ of $pq$.

[1] W. R. Alford; Andrew Granville, Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers". Annals of Mathematics 139: 703–722