# A partition identity

Posted by Jason Polak on 07. April 2018 · Write a comment · Categories: number-theory · Tags: ,

There is a cool way to express 1 as a sum of unit fractions using partitions of a fixed positive integer. What do we mean by partition? If $n$ is such an integer then a partition is just a sum $e_1d_1 + \cdots + e_kd_k = n$ where $d_i$ are positive integers. For example,

7 = 4 + 1 + 1 = 4 + 2(1)

The order of the partition is not very interesting and so we identify partitions up to order. Thus, here are all the 15 partitions of 7:

7
6+1
5+2
5+1+1
4+3
4+2+1
4+1+1+1
3+3+1
3+2+2
3+2+1+1
3+1+1+1+1
2+2+2+1
2+2+1+1+1
2+1+1+1+1+1
1+1+1+1+1+1+1

Group the same numbers together so that each partition is written as $n = \sum e_id_i$ where there are $e_i$ appearances of $d_i$ (or vice-versa, it’s symmetric). Then it’s a theorem that:
$$1 = \sum (e_1!\cdots e_k!\cdot d_1^{e_1}\cdots d_k^{e_k})^{-1}.$$
This partition identity has a bunch of proofs. A neat one appears in the paper “Using Factorizations to Prove a Partition Identity” by David Dobbs and Timothy Kilbourn. In their proof, they used an asympotitc expression for the number of irreducible polynomials over a finite field of a given degree $n$ (the same $n$ that appears in the partition).

Here are some examples of this identity. For n=5, we have:

1 = 1/5 + 1/4 + 1/6 + 1/6 + 1/8 + 1/12 + 1/120

For n=7:

1 = 1/7 + 1/6 + 1/10 + 1/10 + 1/12 + 1/8 + 1/24 + 1/18
+ 1/24 + 1/12 + 1/72 + 1/48 + 1/48 + 1/240 + 1/5040

And for n=11

1 = 1/11 + 1/10 + 1/18 + 1/18 + 1/24 + 1/16 + 1/48 + 1/28 + 1/21
+ 1/56 + 1/28 + 1/168 + 1/30 + 1/24 + 1/36
+ 1/36 + 1/48 + 1/72 + 1/720 + 1/50 + 1/40 + 1/40
+ 1/90 + 1/30 + 1/90 + 1/240 + 1/80 + 1/240
+ 1/3600 + 1/96 + 1/64 + 1/192 + 1/72 + 1/96 + 1/48
+ 1/288 + 1/192 + 1/192 + 1/960 + 1/20160 + 1/324
+ 1/324 + 1/144 + 1/216 + 1/2160 + 1/1152 + 1/288 + 1/576
+ 1/4320 + 1/120960 + 1/3840 + 1/2304
+ 1/5760 + 1/40320 + 1/725760 + 1/39916800

# Stably free and the Eilenberg swindle

Posted by Jason Polak on 29. March 2018 · 2 comments · Categories: modules · Tags:

I already mentioned the idea of stably isomorphic for a ring $R$: two $R$-modules $A$ and $B$ are stably isomorphic if there exists a natural number $n$ such that $A\oplus R^n\cong B\oplus R^n$.

Let’s examine a specific case: if $A$ is stably isomorphic to a free module, then let’s call it stably free.

So, to reiterate: a module $A$ is called stably free if there exists a natural number $n$ such that $A\oplus R^n$ is free. We already saw an example of a stably free module, where $R = \mathbb{H}[x,y]$, the two variable polynomial ring over the quaternions.

One might wonder: why don’t we allow infinite $n$ in this definition? It’s because of the Eilenberg swindle, named after mathematician Samuel Eilenberg.

The Eilenberg swindle goes like this: suppose $P$ is a projective $R$-module. Then, there exists a module $Q$ such that $P\oplus Q \cong F$ where $F$ is a free module. Now, let $E = \oplus_{i=1}^\infty F$.

Then:
$$P\oplus E \cong P\oplus (P\oplus Q)\oplus (P\oplus Q)\cdots\\ P\oplus (Q\oplus P)\oplus (Q\oplus P)\oplus\\ F\oplus F\oplus F\oplus\cdots$$
Therefore, $P\oplus F$ is free. Hence, if we allowed infinite $n$ in the definition of stably free, every projective module would be stably free and there wouldn’t be much point in the definition ‘stably free’.

Here is an exercise for you:

Show that if $A$ is a stably free $R$ module that is not finitely generated, then $A$ is free.

# Stable Isomorphisms, Grothendieck Groups: Example

Posted by Jason Polak on 22. March 2018 · Write a comment · Categories: modules · Tags: ,

If $a$ and $b$ are two real numbers and $ax = bx$, then we can’t conclude that $a = b$ because $x$ may be zero. The same is true for tensor products of modules: if $A$ and $B$ are two left $R$-modules and $X$ is a right $R$-module, then an isomorphism $X\otimes_R A\cong A\otimes_R B$ does not necessarily mean that $A\cong B$. Of course, $X$ not even need be zero for this to happen.

Addition for real numbers is a little different. If $a$ and $b$ are two real numbers then $x + a = x + b$ is equivalent to $a = b$. What about for direct sums? If $A$ and $B$ are two $R$-modules, and $X$ is a third $R$ module, what if $X\oplus A\cong A\oplus B$? Is it true that $A\cong B$?

The answer is no. Perhaps this is surprising from the way direct sums work. After all, in a direct sum $X\oplus A$, it “feels like” what happens in $X$ is independent from what happens in $A$. And for vector spaces, this is true: for $k$-modules where $k$ is a field, if $X\oplus A\cong X\oplus B$, then certainly $A\cong B$, because $A$ and $B$ have the same dimension.
More »

# The Prisoner’s Dilemma

Posted by Jason Polak on 08. March 2018 · 2 comments · Categories: math · Tags:

Suppose the police suspect you and your friend of robbing one billion dollars in bitcoin. The police can only charge you and your friend with the small crime of possession of a sawed-off shotgun, however, and want both of you to confess to the robbery. So, you and your friend are put in separate rooms and given two decisions:

1. Stay silent, in which case you’ll only be charged with weapons possession
2. Confess

If both of you stay silent, then both of you will get a minor prison term. If you confess and your partner stays silent, then the police will let you go in exchange for prosecuting your partner, and vice-verson. Since your partner stayed silent, they will get the maximum sentence. If both of you confess, both of you get serious prison time but a little less than the maximum because both of you cooperated.

Since each of you is in separate rooms, you have to make the decision without knowing what your partner decides. What is the best strategy?

Game theorists like to put all the possibilities in a ‘payoff matrix’, which describes the possible outcome for each combination of decisions. Here is the payoff matrix in this case:

 Confess Stay Silent Confess (-3,-3) (0,-4) Stay Silent (4,0) (-1,-1)

# Degrees of some permutation polynomials

Let $\F_q$ be a finite field. For any function $f:\F_q\to \F_q$, there exists a polynomial $p\in \F_q[x]$ such that $f(a) = p(a)$ for all $a\in \F_q$. In other words, every function from a finite field to itself can be represented by a polynomial.

In particular, every permutation of $\F_q$ can be represented by a polynomial. This isn’t true for other finite rings, a fact which is the topic of one of my papers. At any rate, polynomials that represent permutations are called permutation polynomials.

It’s not easy to determine which polynomials are permutation polynomials. The exception is for the finite field $\F_2$, and more generally $\Z/2^w$. Then this case Ronald Rivest gave a straightforward criterion for whether a polynomial is a permutation polynomial.

However, there is a classical result that says any permutation may be represented uniquely by a polynomial whose degree is at most $q-2$. Here is an example noted by Charles Wells. Let $a,b\in\F_q$ be two distinct elements. The polynomial
$$f(x) = x + (a-b)(x-a)^{q-1} + (b-a)(x-b)^{q-1}$$
represents the transposition of $a$ and $b$. I suggest that you verify this by direct substitution, using the identity $c^{q-1} =1$ whenever $c\not=0$, which in turn follows from Fermat’s little theorem.
More »

# When is a direct product of projective modules projective?

Posted by Jason Polak on 14. February 2018 · Write a comment · Categories: homological-algebra, modules · Tags: , ,

Over a field $k$, an arbitrary product of copies of $k$ is a free module. In other words, every vector space has a basis. In particular, this means that arbitrary products of projective $k$-modules are projective.

Over the ring of integers, an arbitrary product of projective modules is not necessarily projective. In fact, a product of countably infinitely many copies of $\Z$ is not projective!

So while arbitrary direct sums of projective modules are projective, the same is not true of arbitrary products for some rings.

Besides fields, which other rings have the property that arbitrary direct products of their projective modules are projective?
More »

# Conditioning and a sum of Poisson random variables

Posted by Jason Polak on 13. February 2018 · Write a comment · Categories: statistics · Tags:

Previously we talked about the Poisson distribution. The Poisson distribution with mean $\mu \gt 0$ is a distribution on the natural numbers whose density function is
$$f(n) = \frac{e^{-\mu}\mu^n}{n!}$$
We have already seen that the Poisson distribution essentially arises from the binomial distribution as a sort of “limiting case”. In fact, the Poisson distribution is sometimes used as an approximation to the binomial distribution, even though it also arises in its own right in processes like observing the arrival of random particles from radioactive decay.

The Poisson distribution and the binomial distribution are related in another way, through conditioning on the sum of Poisson random variables.

Suppose we have two independent Poisson random variables $X_1$ and $X_2$ with means $E(X_i) = \mu_i$. Then the sum $X_1 + X_2$ also has a Poisson distribution with mean $\mu_1 + \mu_2$.

On the other hand, what is the conditional density $P(X_1 = n_1, X_2 = n_2~|~ X_1 + X_2 = n)$? Here, $n_1 + n_2 = n$. By definition, it is
$$\frac{P(X_1 = n_1, X_2 = n- n_1)}{P(X_1 + X_2 = n)}$$
This is
$$\binom{n}{n_1}p^{n_1}(1-p)^{n-n_1}$$
where $p = \mu_1/(\mu_1+\mu_2)$. So, the joint density of two Poisson random variables conditioning on their sum being $n$ is binomial!

# Maximum likelihood, moments, and the uniform distribution

Suppose we have observations from a known probability distribution whose parameters are unknown. How should we estimate the parameters from our observations?

Throughout we’ll focus on a concrete example. Suppose we observe a random variable drawn from the uniform distribution on $[0,\theta]$, but we don’t know what $\theta$ is. Our one observation is the number $a$. How can we estimate $\theta$?

One method is the ubiquitous maximum likelihood estimator. With this method, we put our observation into the density function, and maximize it with respect to the unknown parameter. The uniform distribution has density $f(x) = 1/\theta$ on the interval $[0,\theta]$ and zero elsewhere. This function is maximized when $\theta = a$. For if $\theta$ were any smaller, then $f(a)$ would be zero.

Also, it’s easy to see that if we draw $n$ samples $a_1,\dots,a_n$ from this distribution, the maximum likelihood estimator for $\theta$, which is the value of $\theta$ that maximizes the joint probability density function, is $\max_i \{a_i\}$.
More »

# Where does the Poisson distribution come from?

Posted by Jason Polak on 08. February 2018 · Write a comment · Categories: statistics · Tags: ,

The Poisson distribution is a discrete probability distribution on the natural numbers $0,1,2,\dots$. Its density function depends on one parameter $\mu$ and is given by
$$d(n) = \frac{e^{-\mu}\mu^n}{n!}$$
Not surprisingly, the parameter $\mu$ is the mean, which follows from the exponential series
$$e^x = \sum_{n=0}^\infty \frac{x^n}{n!}$$
Here is what the density function looks like when $\mu=5$:

How does the Poisson distribution actually arise?

It comes from the following process: suppose you have a fixed interval of time, and you observe the number of occurrences of some phenomenon. In practice, it might be ‘the number of buses to arrive at a given bus stop’. Whatever it is, you’re counting something.

Moreover, this process has to satisfy the important “Poisson axiom”: if you take two disjoint intervals of time that are small, then the number of occurrences in the first is independent of the number of occurrences in the second. Here, “small” means that as the size of the intervals approaches zero, the results should approach independence.
More »

# On normal numbers and e

Posted by Jason Polak on 30. January 2018 · Write a comment · Categories: number-theory · Tags: ,
A real number is simply normal in base $b$ if the frequency of each base $b$ digit in the first $n$ digits tends to a limit as $n$ goes to infinity, and each of these limits is the same.

In other words, a real number is simply normal in base $b$ if each digit appears with equal frequency. It may not be the case of course that the frequency is well-defined: as you keep computing more and more decimal digits of a number, the frequency of any given digit could keep oscillating.

A real number is normal in base $b$ if the frequency of each length $k$ string of numbers exists and is equal to $1/b^k$.

A rational number can be simply normal in some base. For example, 0.12345678901234567890…. is simply normal in base ten. Rational numbers can’t be normal, since their decimals repeat. Irrational numbers can be normal, and in fact almost every number is normal in the sense of the Lebesgue measure. Champernowne proved that the number

0.123456789101121314…

is normal to every base. Mathematicians believe that $e$ and $\pi$ are normal but no one has ever proved it, or found a proof that they are not normal. It’s tempting to look at some numerical evidence. For example, here are the frequencies of the digits in the first 301029 decimal digits of $e$:

 0 30057 1 30283 2 29785 3 30316 4 30206 5 30044 6 30375 7 30065 8 30055 9 29843

Counting these took about 2.4 seconds. Looks like the digit ‘6’ occurs the most often, whereas ‘2’ occurs the least often. Is this about what we’d expect? Here’s the result of a $\chi^2$-test for goodness of fit, the null hypothesis being that the probability of each digit is the same:

X-squared = 11.309, df = 9, p-value = 0.2551

Looks like there’s no reason to be alarmed. Of course, since the normality and simple normality of a number depends only on the “tail” of its expansion, just testing a finite number of digits can be misleading. The rational number defined by the first 301029 digits of $e$ is not normal or simply normal.

The frequencies for all two digit combinations starts off like this:

 00 2957 01 3035 02 3040 03 2978

You probably don’t want to look at the other 96 frequencies. But a $\chi^2$-test reveals the following:

X-squared = 108.06, df = 99, p-value = 0.2506

Although this is rather convincing that $e$ is normal, none of this proves anything. If it is, you’d expect 12345 to occur about three times in the first 301029 digits. In fact it does, the first time starting at the 166412th digit. The sequence 99999 only occurs once, starting at the 290471st digit. Even though the odds are against it, the starting six digit sequence 271828 actually does occur once, at the 252474th digit. Maybe that will help you memorise $e$?