Numbers with exactly 1 square (prime) factor

Question

I have recently learned that numbers with no square (prime, assumed in the following) factor are called square-free numbers. I have read that it would asymptotically grows towards

$$\#\{SquareFree\} under\ n = \frac{6n}{\pi^2}$$

I am curious and am wondering if there's a similar behaviour for people with exactly 1 square prime factor or even k?

What I am referring to here: For example, 2100 = $2^2\times3\times5^2\times7$ which has 2 square prime factors, namely $2^2$ and $5^2$. Here $1^2$ and $10^2$ doesn't count for my purpose.

Thanks for reading and thinking :)

Answer 1

Here I would proudly present to you the result that I and some friends have actually got after doing more math on it. Would someone read it and check if it's correct?

First, it is known that the number of square-free is

$$\sum_{i=1}^{\sqrt{n}}\mu{(i)}\left\lfloor{\frac{n}{i^2}}\right\rfloor$$ Where $\mu$ is the mobius function.

Now I would apply this to the question, counting numbers with exactly k prime square factors. If $i$ is not square-free, its coefficient is still 0. If $i$ has less than k prime factors, its coefficient is 0 as well because we don't count it at all. If it has m prime factors where m≥k, it's coefficient will be $$(-1)^{m-k}\binom{m}{k}$$ by "Generalized Inclusion-Exclusion Principle". Hence, if we denote the number of primes factors of $i$ by $p(i)$, formula is

$$C_k(n)=(-1)^k\sum_{i=1}^{\sqrt{n}}\left\lfloor{\frac{n}{i^2}}\right\rfloor\binom{p(i)}{k}$$

Would someone like to calculate the ratio of this to n? i.e. $\lim_{n\rightarrow\inf}\frac{C_k(n)}{n}$?

Much love, Gareth

Answer 2

At the end of this answer, the "probability" an integer has exactly $k$ prime factors which divide it more than once will be denoted $r_k$ and will be expressed using elementary symmetric "polynomials" $e_k$ in infinitely many variables. The generating function for $r_k$ is also given.

---

Heuristically, divisibility by distinct primes are "independent events," which we can use to calculate the "probability" of integers having particular factorization properties. That is, if $p$ and $q$ are distinct primes, then divisibility by $p$ has no correlation with divisibility by $q$. We should think of this as an example of the identity $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$ for independent variables $X$ and $Y$. And this remains true for three primes, four primes, even all of the primes simultaneously (at least, according to the heuristic). This allows us to calculate the "probability" of any "event" which can be described in a prime-by-prime fashion (which is another incarnation of the "local-global philosophy" of modern number theory).

For example, being squarefree (global description) is equivalent to being indivisible by every squared prime (local description). The "probability" a "randomly picked" integer $n$ is not divisible by $p^2$ is $1-1/p^2$. If we view these as independent events, this yields a "probability" of $\prod_p(1-1/p^2)=1/\zeta(2)=6/\pi^2$ that a "random" integer is squarefree. This is an example of an Euler product. Roughly speaking, for our purposes an Euler product is of the form $\prod E_p(1/p)$, where all but finitely many $E_p(x)$s are $1+o(x)$.

I put "probability" in quotes because actually we are talking about density in the sense of probabilistic number theory; density is not a bona fide probability measure because it is not countably additive. (The "event" $X=n$ has density $0$ for every particular integer $n$, but the union of these "events" is the whole "sample space" which has density $1$. No countable set has a uniform distribution.)

The "probability" a number has a prime power $p^v$ in its prime factorization is $(1-\frac{1}{p})\frac{1}{p^v}$ (compare with the formula for Euler's totient $\varphi(n)$). Thus, the "probability" a random integer "equals" $n$ is the product of $(1-\frac{1}{p})\frac{1}{p^{\large v_p(n)}}$ over all primes $p$, where $v_p(n)$ is the exponent of $p$ that appears in $n$'s prime factorization (called the $p$-adic valuation). As expected, this probability vanishes; the product $\prod(1-\frac{1}{p})$ diverges to $0$ as it is the reciprocal of the harmonic series.

Now let's play fast and loose with infinities for a moment. If an "event" $E$ (set of integers) may be described locally, i.e. if for each prime $p$ there is a set $V_p$ of admissible exponents (so $n\in E \iff v_p(n)\in V_p$ for all $p$), then when we sum the probabilities $\prod_p (1-\frac{1}{p})\frac{1}{p^v}$ up over all $n\in E$, we can "factor" the infinite sum as the Euler product $\prod_p (1-\frac{1}{p})(\sum_{v\in V_p}\frac{1}{p^v})$ for the density (or "probability") of $E$. This is of course nonsense: we factored an infinite sum of zeros into a product of nonzero factors which may converge to a positive limit! And yet, this Euler product heuristic is used ubiquitously (since it seems to work, numerically).

Given a finite set of primes $S$, the density of integers $n$ which are divisible by the specific primes of $S$ twice or more and divisible by all other primes at most once is given by the Euler product $\prod_p E_p$ where

$$ E_p = \begin{cases} \displaystyle \left(1-\frac{1}{p}\right)\left(\frac{1}{p^2}+\frac{1}{p^3}+\cdots\right) & p\in S \\ \displaystyle \left(1-\frac{1}{p}\right)\left(1+\frac{1}{p}\right) & p\not\in S \end{cases} $$

Since this differs from $\prod (1-\frac{1}{p^2})$ in only finitely many factors, compare the products with a ratio:

$$ \frac{\prod_p E_p}{\prod_p (1-\frac{1}{p^2})} = \prod_{p\in S} \frac{(\frac{1}{p^2}+\frac{1}{p^3}+\cdots)}{(1+\frac{1}{p})} =\prod_{p\in S}\frac{1}{p^2-1} $$

Thus we conclude $\prod_p E_p=\frac{1}{\zeta(2)}\prod_{p\in S}\frac{1}{p^2-1}$, using the zeta function $\zeta(s)=\prod_p(1-\frac{1}{p^s})^{-1}$.

Let's dangerously assume countable additivity: summing $\prod_p E_p$ over all sets $S$ of $k$ primes gives

$$ r_k=\left[\prod_p \Big(1-\frac{1}{p^2}\Big)\right] e_k\!\left(\frac{1}{p^2-1}\right)_{p} \tag{$\bullet$}$$

as the density of integers with exactly $k$ prime factors dividing it more than once, where $e_k$ is the elementary symmetric "polynomial" in infinitely many variables evaluated at $1/(p^2-1)$ for all primes $p$.

The Newton-Girard identities tell us how to write $e_k(x_1,x_2,x_3,\cdots)$ in terms of the power sum symmetric "polynomials" $\psi_k(x_1,x_2,x_3,\cdots)=x_1^k+x_2^k+x_3^k+\cdots$ (the identities, appropriately stated, are valid for an infinite number of variables). Indeed, the ordinary generating function of these densities is

$$ \begin{array}{ccl} \displaystyle\sum_{k=0}^\infty r_kt^k & = & \displaystyle\left[\prod_p\Big(1-\frac{1}{p^2}\Big)\right]\sum_{k=0}t^k e_k\Big(\frac{1}{p^2-1}\Big) \\[4pt] & = & \displaystyle \prod_p\Big(1-\frac{1}{p^2}\Big)\Big(1+\frac{t}{p^2-1}\Big) \\[4pt] & = & \displaystyle\prod_p \Big(1+\frac{t-1}{p^2}\Big). \end{array} \tag{$\circ$}$$