Thursday, November 24, 2016

SquareFree numbers with exactly $k$ factors

A positive integer is squarefree if and only if it is not divisible by any perfect square other than 1. That makes them interesting. This post will be about finding the DGF squarefree numbersthat has exactly $k$ factors. We'll use symmetric polynomials to our advantage.

First, the Dirichlet Generating function of square numbers is quite straight forward. By the definition of square free numbers, every prime can be present atmost once in its prime factorization. Let $\xi_2(s)$ be the DGF of square free numbers. Then it is easy to see that,

$\xi_2(s)=\displaystyle\prod_p(1+p^{-s})$

Now, let's review about symmetric polynomials. We need two of the most fundamental symmetric polynomials. The Elementary symmetric polynomials (denoted by $e_k(x_1,x_2,\cdots)$) and the Power sum symmetric polynomials (denoted by $p_k(x_1,x_2,\cdots)$.

Consider these polynomials with finitely many variables. Then,

$e_1=x_1+x_2+x_3+\cdots$
$e_2=x_1x_2+x_1x_3+\cdots+x_2x_3+x_2x_4+\cdots$ and so on.

Similarly,

$p_k=x_1^k+x_2^k+\cdots$

Now notice something interesting. Let $x_k$ be the inverse of the $k$th prime raised to the power $s$. That is,

$x_1=2^{-s}$, $x_2=3^{-s}$, $x_3=5^{-s}$, and so on.

It is now very easy to see that $e_k =e_k(s)$ becomes the Dirichlet generating function of the square free numbers with exactly $k$ factors. It is also clear that the

$p_k =p_k(s)=\zeta_P(ks)$

where $\zeta_P(s)$ is the Prime Zeta function.

Therefore by the fundamental realtion connecting the Elementary symmetric polymials and the Power sum symmetric polynomials, we know

$e_k=\displaystyle\frac{1}{k}\sum_{j=1}^k(-1)^{j-1}e_{k-j}p_j$

This equation can now be directly translated as,

$e_k(s)=\displaystyle\frac{1}{k}\sum_{j=1}^k(-1)^{j-1}e_{k-j}(s)\zeta_P(js)$

which gives the sought after DGF in a recursive fashion. We'll use this DGF in combination with the Dirichlet Hyperbola method in the next post to find the number of squarefree numbers with exactly $k$ factors.


Until then
Yours Aye
Me