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$?

Zero divisor graph of a commutative ring

Posted by Jason Polak on 18. January 2018 · Write a comment · Categories: commutative-algebra · Tags: ,

Let $R$ be a commutative ring. The zero divisors of $R$, which we denote $Z(R)$ is the set-theoretic union of prime ideals. This is just because in any commutative ring, the set of subsets of $R$ that can be written as unions of prime ideals is in bijection with the saturated multiplicatively closed sets (the multiplicatively closed sets that contain the divisors of each of their elements).

Istvan Beck in 1986* introduced an undirected graph (in the sense of vertices and edges) associated to the zero divisors in a commutative ring. Recall that an undirected graph is just a set of vertices (points) and edges connecting the point. What is his graph? His idea was to let the vertices correspond to points of $R$, and the edges correspond to the relation than the product of the corresponding elements is zero.

There is a slightly different definition due to Anderson and Livingston, which is the main one used today. Let $Z(R)^*$ denote the nonzero zero divisors. Their graph is $\Gamma(R)$, which is defined as the graph whose vertices are the elements of $Z(R)^*$, and whose edges are defined by connecting two distinct points if and only if their product is zero. Naturally, if $Z(R)^*$ is not empty then the resulting graph $\Gamma(R)$ will have some edges. The actual information contained in $\Gamma(R)$ is pretty much the same as the information contained in Beck’s version and so we’ll just stick with $\Gamma(R)$.

For this idea to be more than just a curiosity, the graph theoretic properties of $\Gamma(R)$ should tell us something about hte ring theoretic properties of $R$. Does it? Anderson and Livingston showed in 1998 that there exists a vertex of $\Gamma(R)$ adjacent to every other vertex if and only if either $R = \Z/2\times A$ where $A$ is an integral domain or $Z(R)$ is an annihilator. They also showed that for $R$ a finite commutative ring, if $\Gamma(R)$ is complete, then $R\cong \Z/2\times \Z/2$ or $R$ is local with characteristic $p$ or $p^2$.
More »

Working with group rings in Sage

Posted by Jason Polak on 16. January 2018 · Write a comment · Categories: commutative-algebra, ring-theory · Tags:

Let $\Z[\Z/n]$ denote the integral group ring of the cyclic group $\Z/n$. How would you create $\Z[\Z/n]$ in Sage so that you could easily multiply elements?

First, if you’ve already assigned a group to the variable ‘A’, then

will give you the corresponding group ring and store it in the variable ‘R’. The first argument of ‘GroupAlgebra(-,-)’ is the group and the second is the coefficient ring. Sage uses ‘ZZ’ to denote the integers, ‘QQ’ to denote the rationals, etc.

So how do you specify the cyclic group $A$? The first posibility is to use the construction:

where you’d replace ‘n’ by the actual number that you want there. This is useful if you want to work with other permutation groups, because the elements of ‘A’ are stored as permutations:

The output to this snippet is:

More »

Countable dense total orders without endpoints

Posted by Jason Polak on 11. January 2018 · Write a comment · Categories: analysis · Tags: ,

A total ordering $\lt$ on a set $S$ is called dense if for every two $x,y\in S$ with $x \lt y$, there exists a $z\in S$ such that $x\lt z\lt y$. A total ordering is said to be without endpoints if for every $x\in S$ there exists $y,z\in S$ such that $y \lt x\lt z$. In other words, a total order is without endpoints if there is no largest element and no smallest element.

Obviously, if a total order is dense or without endpoints, it must be a relation on an infinite set. One such example is the rational numbers with the usual order.

Theorem. [Cantor] Up to order isomorphism, there is exactly one countable dense totally ordered set without endpoints.

So the rational numbers is the only example of such a totally ordered set up to isomorphism. In particular, this means that $\Q$ and $\Q – \{0\}$ must be order isomorphic. Can you find the isomorphism?

If we take Cantor’s theorem and remove the word ‘countable’, then the new statement is no longer true! For example, Suppose we take the real numbers $\R$. Then we claim that $\R$ is not order isomorphic to $\R – \{0\}$.

Indeed, suppose $\varphi:\R\to\R-\{0\}$ is an order isomorphism. Consider the sequence $a_0,a_1,\dots$ defined by $\varphi(a_i) = 2^{-i}$. Since $\varphi(a_i) \gt \varphi(0)$, we see that $a_0,a_1,\dots$ is a bounded strictly decreasing sequence with limit $\lim a_i = a$.

Because $\varphi$ is an order isomorphism, we conclude $0 \gt\varphi(a)$. Now let $z\in \R$ be such that $0 \gt \varphi(z)\gt \varphi(a)$. Then $z\gt a$ and so $z \gt a_n$ for some $n$. But this means that $\varphi(z) \gt 0$, which is a contradiction! Hence no order isomorphism $\R\to \R-\{0\}$ exists.

Why I left the Langlands program

Posted by Jason Polak on 07. January 2018 · 1 comment · Categories: advice, math · Tags: ,

From browsing my publications, you might notice that my research area changed after my PhD. My thesis was on orbital integrals (Langlands-related), but now I’m working on more classical topics in associative ring theory like separable algebras and Grothendieck groups. In this short article I will explain why I switched areas, in the hope that it will help other young researchers make good decisions.

Let’s go way back to my PhD, in which I solved a problem in the Langlands program. For readers that may not know about Langlands, let’s just vaguely say that it studies generalisations of modular forms through representations of matrix groups and it is motivated by number theory and reciprocity laws. As a graduate student this sounded great because I like number theory and algebra. Writing a thesis was not overly difficult either and I think I did a good job with it.

So, I was excited to get a postdoc in Australia. Besides Australia being an awesome country with cool parrots, it would be a great place to further my research. I even came up with new problems connected to my thesis on which to work. But despite being well set up, I didn’t make much progress. Although I had one paper from my thesis published, when I tried to publish the second part of my thesis, it was rejected multiple times on the grounds that it was not significant enough. From a career perspective, I wasn’t worried because I already had a few other papers (in different areas) either sent out or in progress. But as a young researcher trying to interact with a forbiddingly technical area, it was undeniably discouraging.

Nevertheless, I continued working on more problems in Langlands. In the end however, my interest in the subject began to wane quickly. It mostly wasn’t because of the paper rejection; I’ve actually had one other paper rejected in associative rings and I still happily work on associative rings. It was the fact that although Langlands field is rooted in number theory going back to Gauss, to me it felt completely disconnected from its origins when I was actually ‘doing’ the math. It probably also didn’t help that tremendous amounts of ‘advanced’ algebraic geometry would be necessary for some of the problems I was thinking about, and after giving it a good try, perverse sheaves, stacks, ind-schemes and gerbes were really not to my liking. Hey, I’m happy that some people can enjoy it for what it is, but it turns out it’s not my style.

So I moved onto something else. Actually, one of my many current projects is dimly related to my thesis, but it is far more computational (in fact, it involves writing an actual algorithm in Python) and it is not at all in the style of the traditional Langlands literature. After this project is done however, I don’t plan on continuing in this field. With my new research areas, I am much more satisfied with my work. The only downside is that I now have to find a new community and in particular, new people who are willing to write me letters of recommendation, which has turned out to be much harder than I thought. Still, the switch was absolutely worth it, just because I believe in the math I do again.

There is a lesson in this story, and that is as a young researcher, you should not use a few chosen problems as representative of the general flavour of a research area. Such problems may be interesting on their own, but they are inevitably woven into a highly specialised research microcosm. And the whole research microcosm is something you should consider as well, which includes the general direction of the field and the community and attitude surrounding it. This applies especially to the highly abstract fields that seem to be in vogue these days such as geometric representation theory, Langlands, and higher category theory. In these fields, while a senior researcher can select and distill certain easier problems that would be suitable for many students, only a small fraction of those students will actually have the interest and personality to be successful in progressing to the serious problems of that field on their own. In this regard I’d like to emphasise that it absolutely does take more than just pure brains to succeed. Personality and style is at least as important, and these are things that you may not be fully aware of as a grad student.

So my advice to the young researcher is: know the field you are getting into. Look at some papers in the field and ask yourself if you want to write similar ones. Don’t just be captivated by the ultimate, overarching motivation and instead look at the actual nitty-gritty details of the math and culture. For it is the details you will be spending time with, not the motivation.