Density of square-free numbers, cube-free numbers, etc.

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

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/^2 since (2) = ^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

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

More posts involving Riemann zeta

• • Near zeros of zeta
  • Distribution of zeta zeros
  • Multivariate zeta
  • Probability of coprime sets
  • Estimating power law exponents

[1] It would be clearer if we said kth power-free, but people shorten this to k-free.

In my opinion the term k-free" is misleading. The term ought to mean a number not divisible by k, or maybe a number that has no digit k when written in some base. But the terminology is what it is.

[2] Michael Mossinghoff, Tomas Oliviera e Sliva, and Timothy Trudgian. The distribution of k-free numbers. Mathematics of Computation. Posted November 24, 2020. https://doi.org/10.1090/mcom/3581

The post Density of square-free numbers, cube-free numbers, etc. first appeared on John D. Cook.