Density of square-free numbers, cube-free numbers, k-free

An integer n is said to be square-free if no perfect square (other than 1) divides n. Similarly, n is said to be cube-free if no perfect cube (other than 1) divides n.

In general, n is said to be k-free if it has no divisor d > 1 where d is a kth power [1].

As x gets larger, the proportion of numbers less than x that are k-free approaches 1/ζ(k). That is

$\lim_{x\to\infty} \frac{Q_k(x)}{x} = \frac{1}{\zeta(k)}$

where Q_k(x) is the number of k-free positive integers less than or equal to x and ζ is the Riemann zeta function.

The values of ζ at even integers are known in closed form. So, for example, the proportion of square-free numbers less than x approaches 6/π² since ζ(2) = π²/6. For odd integers the values of ζ must be calculated numerically.

Once you have a theorem that says one thing converges to another, it’s natural to ask next is how fast it converges. How well does the limit work as an approximation of the finite terms? Are there any bounds on the errors?

In [2] the authors give new estimates the remainder term

$R_k(x) = Q_k(x) - \frac{x}{\zeta(k)}$

Python code

Let’s play with this using Python. The code below is meant to be clear rather than efficient.

    from sympy import factorint

    def kfree(n, k):
        exponents = factorint(n).values()
        return max(exponents) < k

    def Q(k, x):
        q = 1 # because 1 is not k-free
        for n in range(2, x+1):
            if kfree(n, k):
                q += 1
        return q

    print(Q(4, 1000000))

This says Q₄(1,000,000) = 923,939.

So Q₄(10⁶)/10⁶ = 0.923939. Now ζ(4) = π⁴/90, so 1/ζ(4) = 0.9239384….

We have R₄(10⁶) = 0.597 and so in this case R is quite small.

(If we didn’t know ζ in closed form, we could calculate it in python with scipy.special.zeta.)

One thought on “Density of square-free numbers, cube-free numbers, etc.”

Stilyo

7 December 2020 at 12:16

What motivates the definition of a k-free number that makes the exploration of this ratio interesting? It is interesting because it converges to the Riemann zeta function but presumably before that was known, people defined a k-free number and started thinking about it – why?

Comments are closed.

Python code

More posts involving Riemann zeta

One thought on “Density of square-free numbers, cube-free numbers, etc.”