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

In statistical hypothesis testing, the computed p-value is the probability of getting a result “as extreme” as the given data under the null hypothesis. Here, “as extreme” means relative to a test-statistic, which has some distribution under the null hypothesis.

In the natural sciences, an experiment is performed. A statistical test is used whose null hypothesis is supposed to be related to the scientific hypothesis. If the p-value is less than 0.05, the null hypothesis is rejected. This in turn can guide our beliefs about the corresponding scientific hypothesis.

For a concrete example, I took an actual coin and flipped it 32 times. I got 19 heads and 13 tails.

A $\chi^2$-test with the null hypothesis being “equal probabilities of heads and tails” gives a p-value of 0.2888. Based on this data and a rejection level of 0.05, we do not reject the null hypothesis. So, it seems like we don’t have much evidence to say that the coin isn’t fair.

Often there is more than one well-known test that can be used, simply because you can compute any sort of test statistic that you want. In such cases, results under the null may be strongly dependent on the particular test statistic used. I’d like to illustrate this with goodness-of-fit testing for normality. There are quite a few ways to test for normality. One method is the Kolmogorov-Smirnov test, and another is the Shapiro-Wilk test. Here is a little R script that looks at these two different methods of testing for normality:
More »

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

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

Blockchain is the combination of distributed computing and cryptography that underlies Bitcoin, and it is a fascinating technology that essentially allows users in a network to have usable digital currency. But cryptocurrency is not the only use of blockchain technology: it is also verifiable reputation, contracts, and information in a decentralised manner that hints at some pretty neat applications, all of which have the same underlying theme: making trade much more efficient. This is the topic of Blockchain: Blueprint for a New Economy by Melanie Swan.

The meat of this book are discussions on the uses of blockchain technology from existing ones like decentralised domain name services to possible future ones like decentralised government and secure health data verification. It turns out that there are many situations that would benefit from decentralisation and that also require verifiability. Digital currency, which has (a) decentralisation to avoid middle men like banks, and (b) verifiability so that one cannot just make up how much money is in a digital wallet, is by far not the only one.
More »

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

Showstopper! by G. Pascal Zachary chronicles the development of the Windows NT operating system released in 1993.

Showstopper! shows what a monumental project the NT kernel was. Lead by Dave Cutler, the Windows NT project was the first Microsoft operating system to use the NTFS filesystem and fully take advantage of 32-bit memory.

The main focus of the book is the personal effort of so many of the team members involved. Zachary himself went through a huge effort interviewing over a hundred people directly involved with the project and it shines through this book, giving a detailed view of the inner workings of the NT team.

The title of this book is apt and refers to the type of bug introduced in software that is so devastating that it pretty much causes it to be unusable in a typical use case. The project had so many of these bugs and lesser bugs as well numbering into the tens of thousands that it is fascinating to read the superhuman effort that went into fixing them, as well as introducing a bunch of new features as well.

I found this book particularly fascinating because I grew up using DOS, Windows 3.1, and later versions up until XP, after which I switched to Linux. My only wish is that it was a bit more technical in places. For example, there is a rather funny description of how an operating system works via an analogy to a wealthy family living in a house with a bunch of servants. Also, the author uses the word “personality” for the userspace of an OS that to me seemed rather confusing, and I think the book would have been clearer had it just used the appropriate precise terminology. At certain times when bugs or features were described, I would have liked to have a bit more of a technical description of those problems and their solutions, and perhaps less biographical details of some of the characters. Aside from these minor details, I thoroughly enjoyed reading the book.

I heartily recommend this book for anyone interested in software development or computers.

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 »

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 »

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.

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.

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

Let $R$ be a commutative ring and $(p)$ be a principal prime ideal. What can be said about the intersection $\cap_{k=1}^\infty (p)^k$? Let’s abbreviate this $\cap (p)^k$ (I like to use the convention that when limits are not specified, then the operation like intersection is taken over all possible indices).

Let’s try an example. For the integers, every principal prime is of the form $(p)$ where $p$ is a prime number or zero. And $(p)^k = (p^k)$ so $\cap (p)^k = (0)$. In fact if $R$ is any Noetherian integral domain then $\cap (p)^k = 0$.

If $R$ is not an integral domain then $\cap (p)^k$ is not necessarily zero. For example, let $S$ be an integral domain and let $R = S\times S$. In $S\times S$, the prime ideal generated by the single element $p = (1,0)$ is its own $k$-th power for all $k$. So $\cap (p)^k = p$.

Of course, it is impossible that in an integral domain to have $(p) = (p)^2$ for some principal prime $p$ unless $p = 0$. Of course, it is possible in an integral domain to have $P = P^2$ for a nonzero prime ideal $P$ that is necessarily not principal. Just take a “polynomial” ring over a field where the powers are allowed to be all nonnegative rationals; that is, a ring of the form $k[\Q^+]$ where $\Q^+$ is the monoid of all nonnegative rational numbers under multiplication. In the case of $k[\Q^+]$, a prime such that $P^2 = P$ would be the prime $P$ generated by all elements of the form $x^q$ where $q \gt 0$ is a rational number.

I will leave the reader with the following question:

Does there exist an integral domain, necessarily non-Noetherian, that contains a principal prime $(p)$ with $\cap (p)^k\not= 0$?
Posted by Jason Polak on 04. January 2018 · Write a comment · Categories: commutative-algebra

For a commutative ring, what does the partially ordered set (=poset) of primes look like? I already talked a little about totally ordered sets of primes, but what about in general?

For a general partially ordered set $S$ there are two immediate questions that come to mind:

  1. Does there exist a commutative ring whose poset of primes is $S$?
  2. Does there exist a commutative ring whose poset of primes contains an embedded copy of $S$?

For example, consider this partially ordered set:

I draw the partially ordered sets so that “higher” is larger. This partially ordered set can be embedded into the poset of prime ideals of the integers

What about the totally ordered set $\Z$ itself? It cannot exist in any poset of primes, because it has no minimal or maximal element, whereas the both the intersection and union of a chain of primes are also primes.

Can the closed interval $[0,1]$ be embedded in a poset of primes? Alas, no. Even though $[0,1]$ now has a lower and upper bound, it is a dense ordered set, and a poset of primes cannot contain a “dense part”. More precisely, suppose that $P\subset Q$ are two distinct prime ideals and let $\{P_i\}$ be a maximal chain of prime ideals between $P$ and $Q$. Let $x\in Q – P$ and let
$$P’ = \cup \{ P_i : x\not\in P_i\}\\
Q’ = \cap \{ P_i : x\in P_i\}$$
Then $P’$ and $Q’$ are two distinct prime ideals such that $P’\subset Q’$ and such that there is no prime between $P’$ and $Q’$. So, $[0,1]$ indeed cannot appear in any poset of prime ideals of a commutative ring.