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

Irrelevance of Bias

There were quite some places in mathematical problems in which a condition imposed to make the problem supposedly difficult actually turns out to be irrelevant. The first instance where I saw something like this in the 'Compass and Straight edge constructions' in which the concept of collapsible compass actually turns out to be irrelevant. This fact is called the Compass Equivalence Theroem.

In this post, we see one such 'irrelevance' in probability theory. I've often wondered whether actual coin tosses are really fair and, if not, how to make them fair. I did some searches and quite surprised to see that this turns out be an easy problem with a simple solution (atleast in theory).

Consider you've a coin with a probability $p$ of turning up heads. Say you want to create a game out of this coin such that each player has a $50\%$ probability of winning. This can be done by the following procedure:

Toss the coin twice. If the results of both the tosses are same, ignore the two tosses and toss again. Repeat until you've different results in both the tosses. Now if the result is $HT$, the first player wins. Else, the second player does.

This works because $\mathbb{P}(HT)=p(1-p)$ whereas $\mathbb{P}(TH)=(1-p)p$.

As both has the same probability of happening and these are the only two outcomes. (Note that, we have toss the coin in 'twos' and we can't combine the intermediate parts of two tosses).

The beauty of this procedure is two-fold. First, the entire argument boils down to the commutative property of multiplication and the second is that we don't even have to know what the unfair probability is. Incredible!!

Now that we have dealt with making an unfair coin to come up with a fair result, let's look at the other way. Now we have a fair coin; how can we make game in which the winning probability of someone is $\alpha$.

This again has a simple solution. Cast the real number $\alpha$ in binary terms. Flip the fair coin until it gives the first Head. Now the player wins, if the $n$th digit in the binary expansion is $1$ and loses otherwise.

Say for example, $\alpha=\frac{3}{4}=(0.11)_2$. Now the player wins if the first Heads appears in first or the second toss and loses otherwise.

$\mathbb{P}(Win)=\mathbb{P}(\text{First Head in }1^{st}\text{ toss})+\mathbb{P}(\text{First Head in }2^{nd}\text{ toss})=\frac{1}{2}+\frac{1}{4}=\frac{3}{4}$.

All this means is that we can take any (un)fair coin with arbitrary probability $p$ and use it to create an arbitrary probability $\alpha$ of winning for some player. In other words, the bias doesn't matter.

The only difference would be that would be needing more and more tosses for the game to conclude depending the unfairness of the coin and winning probability. With that in mind, we will do something more.

Say we want to create a equal probability of winning between three players with an unfair coin. We can directly generalize the first argument and achieve this with the following procedure.

Toss the coin thrice. If all the results are the same, repeat. Else, either exactly one Heads has appeared or exactly one Tails. Assume WLOG, exactly one Heads. Then the the First player wins if the Heads happened in the first toss, the Second player wins if it did in the second toss else the third player wins.

This procedure can be applied to $4$ players, $5$ players, .. Oh wait, for $6$ players, we can do better. Instead of making six tosses every time and waiting for exactly one Heads (or one Tails), we can do it with four tosses.

Toss the coin $4$ times until exactly two Heads appear. Discard other batches of four tosses. Now the First player wins when the Heads occur in positions $(1,2)$, Second wins in positions $(1,3)$, Third wins in $(1,4)$, Fourth in $(2,3)$, Fifth in $(2,4)$ and the Sixth in $(3,4)$.

Similarly, among $10$ players, instead of tossing the coin in batches of ten, we can toss it in batches of five and wait for exactly two Heads (or two Tails) to appear.

By now one can see that we can use the unfair coin and create a game with equal probability of winning among $\binom{n}{k}$ players. Though I'vnt done much analysis further, a judicious choice depending on $n$, $k$ and $p$ will lead to shorter games than the other choices available. Quite neat, don't you think?

Yours Aye

Me

Bridge between Generating functions

I've always wondered about the question of going from OGF to the EGF or vice versa. Turns out this is not too complicated, though it needs some precise mathematical justification. That aside, I find the 'transition' between the generating functions very useful in some cases and very beautiful in others. Anyways, that will be discussion in this post. First, the simpler case of moving from EGF to OGF.

Note that these are just simple manipulations which anyone can do and I do it here just for the fun of doing it.

Let $f_e(x)$ be the EGF of a sequence. That is, 

$f_e(x)=\displaystyle a_0+a_1\frac{x}{1!}+a_2\frac{x^2}{2!}+a_3\frac{x^3}{3!}+\cdots$

Now using the definition of the Gamma integral, one can easily see that,

$f_o(x)=\displaystyle\int\limits_{0}^{\infty}e^{-t}f_e(tx)\, dt$

Technically, we should say that this equality holds provided either the sum on the LHS or the integral on the RHS converges.

For the simplest non-trivial sequence of $a_k=1, k \geq 0$, we know that $f_e(x)=e^x$ and $f_o(x)=1/(1-x)$ which readily satisfies the above equation.

Now for the opposite direction, we make use of the inverse Laplace transform of $t^n$. That is,

$\displaystyle\mathcal{L}^{-1}\left\{\frac{1}{s^{n+1}}\right\}=\frac{t^n}{n!}$

Again simple manipulations yield, $\displaystyle\mathcal{L}^{-1}\left\{\frac{1}{s}f_o\left(\frac{1}{s}\right)\right\}=f_e(t)$

Here again, the trivial case can be seen to work well here. However, we can one another nice application. Consider the OGF of the number of ways to partition a number $n$ with each part atmost $3$. That is,

$f_o(x)=\displaystyle\frac{1}{(1-x)(1-x^2)(1-x^3)}$

This generating function by itself does not help us in finding the number of partitions directly. Let's find the EGF of the same and see how useful it is.

$\displaystyle\frac{1}{s}f_o\left(\frac{1}{s}\right)=\frac{s^5}{(s-1)(s^2-1)(s^3-1)}$

Using Wolfram Alpha to compute the Inverse Laplace Transform of the above we get,

$f_e(t)=\displaystyle \frac{1}{12}t^2e^t+\frac{7}{12}te^t+\frac{47}{72}e^t+\frac{2}{9}Re[e^{\omega t}]+\frac{1}{8}e^{-t}$

where $\omega$ is the cubic root of unity. Knowing that $n![t^n]t^ke^t=n(n-1)\cdots(n-k+1)$, we have

$n![t^n]f_e(t)=\displaystyle \frac{n(n-1)}{12}+\frac{7n}{12}+\frac{47}{72}+\frac{2}{9}Re[\omega^n]+\frac{(-1)^n}{8}$

This already is a cool closed form expression for partition of $n$ with each part atmost $3$. If we also note that $Re[\omega^n]$ is periodic with period $3$, we now have an expression which can also be shown to count the number of triangles with perimeter $n$.

Hope you enjoyed this. I've a couple of ideas for my next post.

Until then

Yours Aye

Me

Lemma - Dyadic (XOR) Convolution Theorem

Note1: This lemma is used to prove the Dyadic Convolution Theorem.

Note2: To understand this proof, you should have a good understanding of Bit-wise operators. The first answer of this question has a nice explanation in case you need it.

Lemma Let $n(k)$ count the number of $1$s in the binary expansion of the non-negative integer $k$. We then claim that $n(i)+n(j)$ and $n(i \oplus j)$ have the same parity. Here again $\oplus$ denote the BitXOR operator.

(In the following proof, we use $'\&'$ to denote BitAND and $'|'$ to denote BitOR)

Proof It suffices to prove that $n(i)+n(j)-n(i\oplus j)$ is even. To do this, we find $n(i|j)$ in two ways. First, $i|j$ has a 0 if both bits of $i$ and $j$ in a position are 0, while otherwise it has a 1. Therefore,

$n(i|j)=n(i \oplus j)+n(i\&j)$

Here, $n(i \oplus j)$ counts the number of 1's in positions that has a 1 in exactly one of two numbers $i$ and $j$, while $n(i\&j)$ counts the number of 1's in positions that has a 1 in both the numbers.

On the other hand, we can simply use the inclusion-exclusion principle to compute $n(i|j)$. Here we have,

$n(i|j)=n(i)+n(j)-n(i\&j)$

Equating the two we get, $n(i)+n(j)-n(i\oplus j)=2\text{ }n(i\&j)$. $\blacksquare$

Dyadic (XOR) Convolution theorem

The Dyadic (XOR) convolution of the sequences $a$ and $b$ is the sequence $c=a*b$ defined by

$c_k=\displaystyle\sum_{i\oplus j = k}a_ib_j=\sum_{i}a_ib_{i\oplus k}$

where the symbol $\oplus$ stands for bit-wise XOR operator. All the three sequences must of the same length that is a power of 2 (we could pad them with zeroes if they are not).

The Dyadic (XOR) convolution theorem states that for two sequences $a$ and $b$,

$c=a*b \implies H_mc=H_ma\cdot H_mb$

where $\cdot$ deontes pointwise multiplication and $H_m$ is the Hadamard matrix. We omit the normalization of the matrix throughout this post.

Though all these are available in Wikipedia and other webpages, nowhere was I able to find a proof of the Dyadic (XOR) convolution theorem. So that is the point of this post. Let's attack the theorem head-on.

Before we proceed to the proof of the convolution theorem, we notice a property of the Hadamard matrices. Indexing the rows and colomns of the Hadamard matrices from 0, we can directly have the $(i,j)$ of entry of the matrix using the following formula.

$(H_m)_{(i,j)}=(-1)^{n(i\&j)}$

where $n(k)$ counts the number of 1s in the binary expansion of the non-negative ineger $k$.This definition plays a crucial role in our proof. We now have all that we need to prove the Dyadic (XOR) convolution theorem. For simplicity, we drop the suffix in the Hadamard matrix, $H_m$. 

Proof of the Convolution Theorem Notice that the $k$th element of the vector $Ha$ is given by

$(Ha)_k=(-1)^{n(0\&k)}a_0+(-1)^{n(1\&k)}a_1+(-1)^{n(2\&k)}a_2+\cdots$

We get this by directly multiplying the $k$th row of the Hadamard matrix with the $a$ vector. Similar expression holds for $Hb$. Therefore, the $k$the entry of the pointwise product is

$\begin{align}
(Ha)_k\cdot(Hb)_k&=\displaystyle\left(\sum_i (-1)^{n(i\&k)}a_i\right)\left(\sum_j (-1)^{n(j\&k)}a_j\right)\\
&=\bigl((-1)^{n(0\&k)}a_0+(-1)^{n(1\&k)}a_1+(-1)^{n(2\&k)}a_2+\cdots\bigl)\bigl((-1)^{n(0\&k)}b_0+(-1)^{n(1\&k)}b_1+(-1)^{n(2\&k)}b_2+\cdots\bigl)
\end{align}$

Therefore,

$[a_ib_j](Ha)_k\cdot(Hb)_k=(-1)^{n(i\&k)+n(j\&k)}$

where $[]$ denotes the Coefficient extracting operator.

Now the $k$th element of $Hc$ is

$(Hc)_k=(-1)^{n(0\&k)}c_0+(-1)^{n(1\&k)}c_1+\cdots$

Therefore, $[c_r](Hc)_k=(-1)^{n(r\&k)}$ from which we get

$[a_ib_{i \oplus r}](Hc)_k=(-1)^{n(r\&k)}$ (Using $c_r=a_0b_{0 \oplus r}+a_1b_{1 \oplus r}+a_2b_{2 \oplus r}+\cdots$)

Plugging in $r=i \oplus j$ gives

$[a_ib_j](Hc)_k=(-1)^{n((i \oplus j)\&k)}=(-1)^{n(i\&k\text{ } \oplus \text{ } j\&k)}$

For the Dyadic Convolution theorem to hold, we have to show that the coefficients are equal. That means, the exponents have the same parity. Take, $i'=i\&k$ and $j'=j\&k$. Using the lemma, we see that this is indeed true. $\blacksquare$

An application of Bivariate Ordinary Generating functions

It's interesting to note how each type of Generating function has its own advantages and disadvantages. For example, we saw how, given an OGF or an EGF, partial sums are readily available with certain simple manipulations. But in case of DGFs, we had to rely on Dirichlet's Hyperbola method to evaluate the partial sums.

On the other hand, if you are able to calculate the number of numbers satisfying a 'property' via DGF, then it's not too hard to also calculate the sum of numbers satisfying the same 'property' with a simple change in the DGF. However, it is not the case with OGFs.

Consider the question of finding the number of numbers with atmost $n$ digits whose digit-sum is $k$. We can easily construct its OGF as follows.

$f(x) = (1+x+x^2+\cdots+x^9)^n$

The above expression simply says that each digit can take any value from 0 to 9. Expand $f(x)$ and the coefficient of $[x^k]$ will give you the required answer.

Here we consider the question of finding the sum of numbers with atomst $n$ digits with a digit-sum of $k$. I'm not saying that this cannot be done with an one-variable OGF, but certainly using a bivariate OGF makes things simpler. In addition to noting how much each digit adds to the sum, we must also make a note of each of the digit with its place value. We define some functions as follows:

$f_n(x,y) = 1+xy^{10^{n-1}}+x^2y^{2.10^{n-1}}+\cdots+x^9y^{9.10^{n-1}}$

Each function $f_n(x,y)$ encodes the information about the $n$th digit, making a note of what it adds to the digit sum and digit with its place value. Defining a new function

$f(x,y)=f_1(x,y).f_2(x,y)\cdots.f_n(x,y)$

gives what we need. Differentiating the above generating function w.r.t $y$ and substituting $y=1$ (If you wanna know what this does, refer 'Multivariate Generating Functions' in 'Analytic Combinatorics'), tells us how much each digit contributes to the overall 'sum of numbers with atmost $n$ digits'. . We now let,

$g(x)=\dfrac{d}{dy}f(x,y)\biggl\vert_{y=1}$

This Generating function we are left with is a single variable OGF in which the coefficient of $x^k$ gives the sum of numbers whose digit-sum is $k$. Play around with numbers with certain other 'properties' and you will really see what this post is trying to convey.

I think my next post will be on Multiset Cycle Indices, though am not sure where and/or how to start. C ya then.



Until then
Yours Aye,
Me