Postdoctoral Research Positions in Mathematics and AI at the Sydney Mathematics Research Institute

[The following information was provided to me by Geordie Williamson, who is Director of the Sydney Mathematics Research Institute – T.]

We are currently advertising two positions in math and AI:

• A Level A position (for first time postdocs, upcoming PhDs); and
• a Level B position (for candidates with a postdoc / some research experience):

Both positions are for three years and are based at the Sydney Mathematical Research Institute. The positions are research only, but teaching at the University of Sydney is possible if desired. The successful candidate will have considerable time and flexibility to pursue their own research program.

We are after either:

1. excellent mathematicians with some interest in programming and modern AI;
2. excellent computer scientists with some interest and background in mathematics, as well as an interest in using AI to attack tough problems in mathematics.

A counterexample to the periodic tiling conjecture

Rachel Greenfeld and I have just uploaded to the arXiv our paper “A counterexample to the periodic tiling conjecture“. This is the full version of the result I announced on this blog a few months ago, in which we disprove the periodic tiling conjecture of Grünbaum-Shephard and Lagarias-Wang. The paper took a little longer than expected to finish, due to a technical issue that we did not realize at the time of the announcement that required a workaround.

In more detail: the original strategy, as described in the announcement, was to build a “tiling language” that was capable of encoding a certain “-adic Sudoku puzzle”, and then show that the latter type of puzzle had only non-periodic solutions if was a sufficiently large prime. As it turns out, the second half of this strategy worked out, but there was an issue in the first part: our tiling language was able (using -group-valued functions) to encode arbitrary boolean relationships between boolean functions, and was also able (using -valued functions) to encode “clock” functions such as that were part of our -adic Sudoku puzzle, but we were not able to make these two types of functions “talk” to each other in the way that was needed to encode the -adic Sudoku puzzle (the basic problem being that if is a finite abelian -group then there are no non-trivial subgroups of that are not contained in or trivial in the direction). As a consequence, we had to replace our “-adic Sudoku puzzle” by a “-adic Sudoku puzzle” which basically amounts to replacing the prime by a sufficiently large power of (we believe will suffice). This solved the encoding issue, but the analysis of the -adic Sudoku puzzles was a little bit more complicated than the -adic case, for the following reason. The following is a nice exercise in analysis:

Theorem 1 (Linearity in three directions implies full linearity) Let be a smooth function which is affine-linear on every horizontal line, diagonal (line of slope ), and anti-diagonal (line of slope ). In other words, for any , the functions , , and are each affine functions on . Then is an affine function on .

Indeed, the property of being affine in three directions shows that the quadratic form associated to the Hessian at any given point vanishes at , , and , and thus must vanish everywhere. In fact the smoothness hypothesis is not necessary; we leave this as an exercise to the interested reader. The same statement turns out to be true if one replaces with the cyclic group as long as is odd; this is the key for us to showing that our -adic Sudoku puzzles have an (approximate) two-dimensional affine structure, which on further analysis can then be used to show that it is in fact non-periodic. However, it turns out that the corresponding claim for cyclic groups can fail when is a sufficiently large power of ! In fact the general form of functions that are affine on every horizontal line, diagonal, and anti-diagonal takes the form

for some integer coefficients . This additional “pseudo-affine” term causes some additional technical complications but ultimately turns out to be manageable.

During the writing process we also discovered that the encoding part of the proof becomes more modular and conceptual once one introduces two new definitions, that of an “expressible property” and a “weakly expressible property”. These concepts are somewhat analogous to that of sentences and sentences in the arithmetic hierarchy, or to algebraic sets and semi-algebraic sets in real algebraic geometry. Roughly speaking, an expressible property is a property of a tuple of functions , from an abelian group to finite abelian groups , such that the property can be expressed in terms of one or more tiling equations on the graph

For instance, the property that two functions differ by a constant can be expressed in terms of the tiling equation

(the vertical line test), as well as

where is the diagonal subgroup of . A weakly expressible property is an existential quantification of some expressible property , so that a tuple of functions obeys the property if and only if there exists an extension of this tuple by some additional functions that obey the property . It turns out that weakly expressible properties are closed under a number of useful operations, and allow us to easily construct quite complicated weakly expressible properties out of a “library” of simple weakly expressible properties, much as a complex computer program can be constructed out of simple library routines. In particular we will be able to “program” our Sudoku puzzle as a weakly expressible property.

Trying out Mathstodon

It’s been a while since I’ve actively participated in social media outside of this blog – I was active in Google Buzz/Google+ for a while, until that service closed – but I’ve decided to try out Mathstodon, one of the servers of the open source social media software platform Mastodon. As I understand it, Mastodon functions in many ways similar to the significantly more well-known platform Twitter, but is decentralized into a federation of servers that share content with each other but can have their own moderation rules and add-ons. For instance, the Mathstodon server has the additional feature of supporting LaTeX in its posts. Another consequence of this decentralization is that if one for some reason ends up disagreeing with the administration of the server one is in, one has the option of transferring one’s account to a different server while staying on the same platform.

I just created an account at Mathstodon and it currently has very little content, but I hope to add some soon (though I will probably not be as prolific as some other mathematicians already on that site, such as John Baez or Nalini Joshi).

UCLA Math Undergraduate Merit Scholarship for 2023

In 2010, the UCLA mathematics department launched a scholarship opportunity for entering freshman students with exceptional background and promise in mathematics. This program was unfortunately suspended for a while due to technical reasons, but we are once again able to offer one scholarship each year.  The UCLA Math Undergraduate Merit Scholarship provides for full tuition, and a room and board allowance for 4 years, contingent on continued high academic performance. In addition, scholarship recipients follow an individualized accelerated program of study, as determined after consultation with UCLA faculty.   The program of study leads to a Masters degree in Mathematics in four years.

More information and an application form for the scholarship can be found on the web at:

https://ww3.math.ucla.edu/ucla-math-undergraduate-merit-scholarship/

To be considered for Fall 2023, candidates must apply for the scholarship and also for admission to UCLA on or before November 30, 2022.

Upcoming workshop on “Machine assisted proofs” at IPAM

Just a short post to advertise the workshop “Machine assisted proofs” that will be held on Feb 13-17 next year, here at the Institute for Pure and Applied Mathematics (IPAM); I am one of the organizers of this event together with Erika Abraham, Jeremy Avigad, Kevin Buzzard, Jordan Ellenberg, Tim Gowers, and Marijn Heule. The purpose of this event is to bring together experts in the various types of formal computer-assisted methods used to verify, discover, or otherwise assist with mathematical proofs, as well as pure mathematicians who are interested in learning about the current and future state of the art with such tools; this seems to be an opportune time to bring these communities together, given some recent high-profile applications of formal methods in pure mathematics (e.g, the liquid tensor experiment). The workshop will consist of a number of lectures from both communities, as well as a panel to discuss future directions. The workshop is open to general participants (both in person and remotely), although there is a registration process and a moderate registration fee to cover costs and to restrict the capacity to genuine applicants.

A Bayesian probability worksheet

This is a spinoff from the previous post. In that post, we remarked that whenever one receives a new piece of information , the prior odds between an alternative hypothesis and a null hypothesis is updated to a posterior odds , which can be computed via Bayes’ theorem by the formula

where is the likelihood of this information under the alternative hypothesis , and is the likelihood of this information under the null hypothesis . If there are no other hypotheses under consideration, then the two posterior probabilities , must add up to one, and so can be recovered from the posterior odds by the formulae

This gives a straightforward way to update one’s prior probabilities, and I thought I would present it in the form of a worksheet for ease of calculation:

A PDF version of the worksheet and instructions can be found here. One can fill in this worksheet in the following order:

1. In Box 1, one enters in the precise statement of the null hypothesis .
2. In Box 2, one enters in the precise statement of the alternative hypothesis . (This step is very important! As discussed in the previous post, Bayesian calculations can become extremely inaccurate if the alternative hypothesis is vague.)
3. In Box 3, one enters in the prior probability (or the best estimate thereof) of the null hypothesis .
4. In Box 4, one enters in the prior probability (or the best estimate thereof) of the alternative hypothesis . If only two hypotheses are being considered, we of course have .
5. In Box 5, one enters in the ratio between Box 4 and Box 3.
6. In Box 6, one enters in the precise new information that one has acquired since the prior state. (As discussed in the previous post, it is important that all relevant information – both supporting and invalidating the alternative hypothesis – are reported accurately. If one cannot be certain that key information has not been withheld to you, then Bayesian calculations become highly unreliable.)
7. In Box 7, one enters in the likelihood (or the best estimate thereof) of the new information under the null hypothesis .
8. In Box 8, one enters in the likelihood (or the best estimate thereof) of the new information under the null hypothesis . (This can be difficult to compute, particularly if is not specified precisely.)
9. In Box 9, one enters in the ratio betwen Box 8 and Box 7.
10. In Box 10, one enters in the product of Box 5 and Box 9.
11. (Assuming there are no other hypotheses than and ) In Box 11, enter in divided by plus Box 10.
12. (Assuming there are no other hypotheses than and ) In Box 12, enter in Box 10 divided by plus Box 10. (Alternatively, one can enter in minus Box 11.)

To illustrate this procedure, let us consider a standard Bayesian update problem. Suppose that a given point in time, of the population is infected with COVID-19. In response to this, a company mandates COVID-19 testing of its workforce, using a cheap COVID-19 test. This test has a chance of a false negative (testing negative when one has COVID) and a chance of a false positive (testing positive when one does not have COVID). An employee takes the mandatory test, which turns out to be positive. What is the probability that actually has COVID?

We can fill out the entries in the worksheet one at a time:

• Box 1: The null hypothesis is that does not have COVID.
• Box 2: The alternative hypothesis is that does have COVID.
• Box 3: In the absence of any better information, the prior probability of the null hypothesis is , or .
• Box 4: Similarly, the prior probability of the alternative hypothesis is , or .
• Box 5: The prior odds are .
• Box 6: The new information is that has tested positive for COVID.
• Box 7: The likelihood of under the null hypothesis is , or (the false positive rate).
• Box 8: The likelihood of under the alternative is , or (one minus the false negative rate).
• Box 9: The likelihood ratio is .
• Box 10: The product of Box 5 and Box 9 is approximately .
• Box 11: The posterior probability is approximately .
• Box 12: The posterior probability is approximately .

The filled worksheet looks like this:

Perhaps surprisingly, despite the positive COVID test, the employee only has a chance of actually having COVID! This is due to the relatively large false positive rate of this cheap test, and is an illustration of the base rate fallacy in statistics.

We remark that if we switch the roles of the null hypothesis and alternative hypothesis, then some of the odds in the worksheet change, but the ultimate conclusions remain unchanged:

So the question of which hypothesis to designate as the null hypothesis and which one to designate as the alternative hypothesis is largely a matter of convention.

Now let us take a superficially similar situation in which a mother observers her daughter exhibiting COVID-like symptoms, to the point where she estimates the probability of her daughter having COVID at . She then administers the same cheap COVID-19 test as before, which returns positive. What is the posterior probability of her daughter having COVID?

One can fill out the worksheet much as before, but now with the prior probability of the alternative hypothesis raised from to (and the prior probablity of the null hypothesis dropping from to ). One now gets that the probability that the daughter has COVID has increased all the way to :

Thus we see that prior probabilities can make a significant impact on the posterior probabilities.

Now we use the worksheet to analyze an infamous probability puzzle, the Monty Hall problem. Let us use the formulation given in that Wikipedia page:

Problem 1 Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?

For this problem, the precise formulation of the null hypothesis and the alternative hypothesis become rather important. Suppose we take the following two hypotheses:

• Null hypothesis : The car is behind door number 1, and no matter what door you pick, the host will randomly reveal another door that contains a goat.
• Alternative hypothesis : The car is behind door number 2 or 3, and no matter what door you pick, the host will randomly reveal another door that contains a goat.

Assuming the prizes are distributed randomly, we have and . The new information is that, after door 1 is selected, door 3 is revealed and shown to be a goat. After some thought, we conclude that is equal to (the host has a fifty-fifty chance of revealing door 3 instead of door 2) but that is also equal to (if the car is behind door 2, the host must reveal door 3, whereas if the car is behind door 3, the host cannot reveal door 3). Filling in the worksheet, we see that the new information does not in fact alter the odds, and the probability that the car is not behind door 1 remains at 2/3, so it is advantageous to switch.

However, consider the following different set of hypotheses:

• Null hypothesis : The car is behind door number 1, and if you pick the door with the car, the host will reveal another door to entice you to switch. Otherwise, the host will not reveal a door.
• Alternative hypothesis : The car is behind door number 2 or 3, and if you pick the door with the car, the host will reveal another door to entice you to switch. Otherwise, the host will not reveal a door.

Here we still have and , but while remains equal to , has dropped to zero (since if the car is not behind door 1, the host will not reveal a door). So now has increased all the way to , and it is not advantageous to switch! This dramatically illustrates the importance of specifying the hypotheses precisely. The worksheet is now filled out as follows:

Finally, we consider another famous probability puzzle, the Sleeping Beauty problem. Again we quote the problem as formulated on the Wikipedia page:

Problem 2 Sleeping Beauty volunteers to undergo the following experiment and is told all of the following details: On Sunday she will be put to sleep. Once or twice, during the experiment, Sleeping Beauty will be awakened, interviewed, and put back to sleep with an amnesia-inducing drug that makes her forget that awakening. A fair coin will be tossed to determine which experimental procedure to undertake:

• If the coin comes up heads, Sleeping Beauty will be awakened and interviewed on Monday only.
• If the coin comes up tails, she will be awakened and interviewed on Monday and Tuesday.
• In either case, she will be awakened on Wednesday without interview and the experiment ends.

Any time Sleeping Beauty is awakened and interviewed she will not be able to tell which day it is or whether she has been awakened before. During the interview Sleeping Beauty is asked: “What is your credence now for the proposition that the coin landed heads?”‘

Here the situation can be confusing because there are key portions of this experiment in which the observer is unconscious, but nevertheless Bayesian probability continues to operate regardless of whether the observer is conscious. To make this issue more precise, let us assume that the awakenings mentioned in the problem always occur at 8am, so in particular at 7am, Sleeping beauty will always be unconscious.

Here, the null and alternative hypotheses are easy to state precisely:

• Null hypothesis : The coin landed tails.
• Alternative hypothesis : The coin landed heads.

The subtle thing here is to work out what the correct prior state is (in most other applications of Bayesian probability, this state is obvious from the problem). It turns out that the most reasonable choice of prior state is “unconscious at 7am, on either Monday or Tuesday, with an equal chance of each”. (Note that whatever the outcome of the coin flip is, Sleeping Beauty will be unconscious at 7am Monday and unconscious again at 7am Tuesday, so it makes sense to give each of these two states an equal probability.) The new information is then

• New information : One hour after the prior state, Sleeping Beauty is awakened.

With this formulation, we see that , , and , so on working through the worksheet one eventually arrives at , so that Sleeping Beauty should only assign a probability of to the event that the coin landed as heads.

There are arguments advanced in the literature to adopt the position that should instead be equal to , but I do not see a way to interpret them in this Bayesian framework without a substantial alteration to either the notion of the prior state, or by not presenting the new information properly.

If one has multiple pieces of information that one wishes to use to update one’s priors, one can do so by filling out one copy of the worksheet for each new piece of information, or by using a multi-row version of the worksheet using such identities as

We leave the details of these variants of the Bayesian update problem to the interested reader. The only thing I will note though is that if a key piece of information is withheld from the person filling out the worksheet, for instance if that person relies exclusively on a news source that only reports information that supports the alternative hypothesis and omits information that debunks it, then the outcome of the worksheet is likely to be highly inaccurate, and one should only perform a Bayesian analysis when one has a high confidence that all relevant information (both favorable and unfavorable to the alternative hypothesis) is being reported to the user.

What are the odds?

An unusual lottery result made the news recently: on October 1, 2022, the PCSO Grand Lotto in the Philippines, which draws six numbers from to at random, managed to draw the numbers (though the balls were actually drawn in the order ). In other words, they drew exactly six multiples of nine from to . In addition, a total of tickets were bought with this winning combination, whose owners then had to split the million peso jackpot (about million USD) among themselves. This raised enough suspicion that there were calls for an inquiry into the Philippine lottery system, including from the minority leader of the Senate.

Whenever an event like this happens, journalists often contact mathematicians to ask the question: “What are the odds of this happening?”, and in fact I myself received one such inquiry this time around. This is a number that is not too difficult to compute – in this case, the probability of the lottery producing the six numbers in some order turn out to be in – and such a number is often dutifully provided to such journalists, who in turn report it as some sort of quantitative demonstration of how remarkable the event was.

But on the previous draw of the same lottery, on September 28, 2022, the unremarkable sequence of numbers were drawn (again in a different order), and no tickets ended up claiming the jackpot. The probability of the lottery producing the six numbers is also in – just as likely or as unlikely as the October 1 numbers . Indeed, the whole point of drawing the numbers randomly is to make each of the possible outcomes (whether they be “unusual” or “unremarkable”) equally likely. So why is it that the October 1 lottery attracted so much attention, but the September 28 lottery did not?

Part of the explanation surely lies in the unusually large number () of lottery winners on October 1, but I will set that aspect of the story aside until the end of this post. The more general points that I want to make with these sorts of situations are:

1. The question “what are the odds of happening” is often easy to answer mathematically, but it is not the correct question to ask.
2. The question “what is the probability that an alternative hypothesis is the truth” is (one of) the correct questions to ask, but is very difficult to answer (it involves both mathematical and non-mathematical considerations).
3. The answer to the first question is one of the quantities needed to calculate the answer to the second, but it is far from the only such quantity. Most of the other quantities involved cannot be calculated exactly.
4. However, by making some educated guesses, one can still sometimes get a very rough gauge of which events are “more surprising” than others, in that they would lead to relatively higher answers to the second question.

To explain these points it is convenient to adopt the framework of Bayesian probability. In this framework, one imagines that there are competing hypotheses to explain the world, and that one assigns a probability to each such hypothesis representing one’s belief in the truth of that hypothesis. For simplicity, let us assume that there are just two competing hypotheses to be entertained: the null hypothesis , and an alternative hypothesis . For instance, in our lottery example, the two hypotheses might be:

• Null hypothesis : The lottery is run in a completely fair and random fashion.
• Alternative hypothesis : The lottery is rigged by some corrupt officials for their personal gain.

At any given point in time, a person would have a probability assigned to the null hypothesis, and a probability assigned to the alternative hypothesis; in this simplified model where there are only two hypotheses under consideration, these probabilities must add to one, but of course if there were additional hypotheses beyond these two then this would no longer be the case.

Bayesian probability does not provide a rule for calculating the initial (or prior) probabilities , that one starts with; these may depend on the subjective experiences and biases of the person considering the hypothesis. For instance, one person might have quite a bit of prior faith in the lottery system, and assign the probabilities and . Another person might have quite a bit of prior cynicism, and perhaps assign and . One cannot use purely mathematical arguments to determine which of these two people is “correct” (or whether they are both “wrong”); it depends on subjective factors.

What Bayesian probability does do, however, is provide a rule to update these probabilities , in view of new information to provide posterior probabilities , . In our example, the new information would be the fact that the October 1 lottery numbers were (in some order). The update is given by the famous Bayes theorem

where is the probability that the event would have occurred under the null hypothesis , and is the probability that the event would have occurred under the alternative hypothesis . Let us divide the second equation by the first to cancel the denominator, and obtain

One can interpret as the prior odds of the alternative hypothesis, and as the posterior odds of the alternative hypothesis. The identity (1) then says that in order to compute the posterior odds of the alternative hypothesis in light of the new information , one needs to know three things:

1. The prior odds of the alternative hypothesis;
2. The probability that the event occurs under the null hypothesis ; and
3. The probability that the event occurs under the alternative hypothesis .

As previously discussed, the prior odds of the alternative hypothesis are subjective and vary from person to person; in the example earlier, the person with substantial faith in the lottery may only give prior odds of (99 to 1 against) of the alternative hypothesis, whereas the cynic might give odds of (even odds). The probability is the quantity that can often be calculated by straightforward mathematics; as discussed before, in this specific example we have

But this still leaves one crucial quantity that is unknown: the probability . This is incredibly difficult to compute, because it requires a precise theory for how events would play out under the alternative hypothesis , and in particular is very sensitive as to what the alternative hypothesis actually is.

For instance, suppose we replace the alternative hypothesis by the following very specific (and somewhat bizarre) hypothesis:

• Alternative hypothesis : The lottery is rigged by a cult that worships the multiples of , and views October 1 as their holiest day. On this day, they will manipulate the lottery to only select those balls that are multiples of .

Under this alternative hypothesis , we have . So, when happens, the odds of this alternative hypothesis will increase by the dramatic factor of . So, for instance, someone who already was entertaining odds of of this hypothesis would now have these odds multiply dramatically to , so that the probability of would have jumped from a mere to a staggering . This is about as strong a shift in belief as one could imagine. However, this hypothesis is so specific and bizarre that one’s prior odds of this hypothesis would be nowhere near as large as (unless substantial prior evidence of this cult and its hold on the lottery system existed, of course). A more realistic prior odds for would be something like – which is so miniscule that even multiplying it by a factor such as barely moves the needle.

Remark 1 The contrast between alternative hypothesis and alternative hypothesis illustrates a common demagogical rhetorical technique when an advocate is trying to convince an audience of an alternative hypothesis, namely to use suggestive language (“`I’m just asking questions here”) rather than precise statements in order to leave the alternative hypothesis deliberately vague. In particular, the advocate may take advantage of the freedom to use a broad formulation of the hypothesis (such as ) in order to maximize the audience’s prior odds of the hypothesis, simultaneously with a very specific formulation of the hypothesis (such as ) in order to maximize the probability of the actual event occuring under this hypothesis. (A related technique is to be deliberately vague about the hypothesized competency of some suspicious actor, so that this actor could be portrayed as being extraordinarily competent when convenient to do so, while simultaneously being portrayed as extraordinarily incompetent when that instead is the more useful hypothesis.) This can lead to wildly inaccurate Bayesian updates of this vague alternative hypothesis, and so precise formulation of such hypothesis is important if one is to approach a topic from anything remotely resembling a scientific approach. [EDIT: as pointed out to me by a reader, this technique is a Bayesian analogue of the motte and bailey fallacy.]

At the opposite extreme, consider instead the following hypothesis:

• Alternative hypothesis : The lottery is rigged by some corrupt officials, who on October 1 decide to randomly determine the winning numbers in advance, share these numbers with their collaborators, and then manipulate the lottery to choose those numbers that they selected.

If these corrupt officials are indeed choosing their predetermined winning numbers randomly, then the probability would in fact be just the same probability as , and in this case the seemingly unusual event would in fact have no effect on the odds of the alternative hypothesis, because it was just as unlikely for the alternative hypothesis to generate this multiples-of-nine pattern as for the null hypothesis to. In fact, one would imagine that these corrupt officials would avoid “suspicious” numbers, such as the multiples of , and only choose numbers that look random, in which case would in fact be less than and so the event would actually lower the odds of the alternative hypothesis in this case. (In fact, one can sometimes use this tendency of fraudsters to not generate truly random data as a statistical tool to detect such fraud; violations of Benford’s law for instance can be used in this fashion, though only in situations where the null hypothesis is expected to obey Benford’s law, as discussed in this previous blog post.)

Now let us consider a third alternative hypothesis:

• Alternative hypothesis : On October 1, the lottery machine developed a fault and now only selects numbers that exhibit unusual patterns.

Setting aside the question of precisely what faulty mechanism could induce this sort of effect, it is not clear at all how to compute in this case. Using the principle of indifference as a crude rule of thumb, one might expect

where the denominator is the number of patterns among the possible lottery outcomes that are “unusual”. Among such patterns would presumably be the multiples-of-9 pattern , but one could easily come up with other patterns that are equally “unusual”, such as consecutive strings such as , or the first few primes , or the first few squares , and so forth. How many such unusual patterns are there? This is too vague a question to answer with any degree of precision, but as one illustrative statistic, the Online Encyclopedia of Integer Sequences (OEIS) currently hosts about sequences. Not all of these would begin with six distinct numbers from to , and several of these sequences might generate the same set of six numbers, but this does suggests that patterns that one would deem to be “unusual” could number in the thousands, tens of thousands, or more. Using this guess, we would then expect the event to boost the odds of this hypothesis by perhaps a thousandfold or so, which is moderately impressive. But subsequent information can counteract this effect. For instance, on October 3, the same lottery produced the numbers , which exhibit no unusual properties (no search results in the OEIS, for instance); if we denote this event by , then we have and so this new information should drive the odds for this alternative hypothesis way down again.

Remark 2 This example demonstrates another demagogical rhetorical technique that one sometimes sees (particularly in political or other emotionally charged contexts), which is to cherry-pick the information presented to their audience by informing them of events which have a relatively high probability of occurring under their alternative hypothesis, but withholding information about other relevant events that have a relatively low probability of occurring under their alternative hypothesis. When confronted with such new information , a common defense of a demogogue is to modify the alternative hypothesis to a more specific hypothesis that can “explain” this information (“Oh, clearly we heard about because the conspiracy in fact extends to the additional organizations that reported “), taking advantage of the vagueness discussed in Remark 1.

Let us consider a superficially similar hypothesis:

• Alternative hypothesis : On October 1, a divine being decided to send a sign to humanity by placing an unusual pattern in a lottery.

Here we (literally) stay agnostic on the prior odds of this hypothesis, and do not address the theological question of why a divine being should choose to use the medium of a lottery to send their signs. At first glance, the probability here should be similar to the probability , and so perhaps one could use this event to improve the odds of the existence of a divine being by a factor of a thousand or so. But note carefully that the hypothesis did not specify which lottery the divine being chose to use. The PSCO Grand Lotto is just one of a dozen lotteries run by the Philippine Charity Sweepstakes Office (PCSO), and of course there are over a hundred other countries and thousands of states within these countries, each of which often run their own lotteries. Taking into account these thousands or tens of thousands of additional lotteries to choose from, the probability now drops by several orders of magnitude, and is now basically comparable to the probability coming from the null hypothesis. As such one does not expect the event to have a significant impact on the odds of the hypothesis , despite the small-looking nature of the probability .

In summary, we have failed to locate any alternative hypothesis which

1. Has some non-negligible prior odds of being true (and in particular is not excessively specific, as with hypothesis );
2. Has a significantly higher probability of producing the specific event than the null hypothesis; AND
3. Does not struggle to also produce other events that have since been observed.

One needs all three of these factors to be present in order to significantly weaken the plausibility of the null hypothesis ; in the absence of these three factors, a moderately small numerical value of , such as does not actually do much to affect this plausibility. In this case one needs to lay out a reasonably precise alternative hypothesis and make some actual educated guesses towards the competing probability before one can lead to further conclusions. However, if is insanely small, e.g., less than , then the possibility of a previously overlooked alternative hypothesis becomes far more plausible; as per the famous quote of Arthur Conan Doyle’s Sherlock Holmes, “When you have eliminated all which is impossible, then whatever remains, however improbable, must be the truth.”

We now return to the fact that for this specific October 1 lottery, there were tickets that managed to select the winning numbers. Let us call this event . In view of this additional information, we should now consider the ratio of the probabilities and , rather than the ratio of the probabilities and . If we augment the null hypothesis to

• Null hypothesis : The lottery is run in a completely fair and random fashion, and the purchasers of lottery tickets also select their numbers in a completely random fashion.

Then is indeed of the “insanely improbable” category mentioned previously. I was not able to get official numbers on how many tickets are purchased per lottery, but let us say for sake of argument that it is 1 million (the conclusion will not be extremely sensitive to this choice). Then the expected number of tickets that would have the winning numbers would be

(which is broadly consistent, by the way, with the jackpot being reached every draws or so), and standard probability theory suggests that the number of winners should now follow a Poisson distribution with this mean . The probability of obtaining winners would now be

and of course would be even smaller than this. So this clearly demands some sort of explanation. But in actuality, many purchasers of lottery tickets do not select their numbers completely randomly; they often have some “lucky” numbers (e.g., based on birthdays or other personally significant dates) that they prefer to use, or choose numbers according to a simple pattern rather than go to the trouble of trying to make them truly random. So if we modify the null hypothesis to

• Null hypothesis : The lottery is run in a completely fair and random fashion, but a significant fraction of the purchasers of lottery tickets only select “unusual” numbers.

then it can now become quite plausible that a highly unusual set of numbers such as could be selected by as many as purchasers of tickets; for instance, if of the 1 million ticket holders chose to select their numbers according to some sort of pattern, then only of those holders would have to pick in order for the event to hold (given ), and this is not extremely implausible. Given that this reasonable version of the null hypothesis already gives a plausible explanation for , there does not seem to be a pressing need to locate an alternate hypothesis that gives some other explanation (cf. Occam’s razor). [UPDATE: Indeed, given the actual layout of the tickets of ths lottery, the numbers form a diagonal, and so all that is needed in order for the modified null hypothesis to explain the event is to postulate that a significant fraction of ticket purchasers decided to lay out their numbers in a simple geometric pattern, such as a row or diagonal.]

Remark 3 In view of the above discussion, one can propose a systematic way to evaluate (in as objective a fashion as possible) rhetorical claims in which an advocate is presenting evidence to support some alternative hypothesis:

1. State the null hypothesis and the alternative hypothesis as precisely as possible. In particular, avoid conflating an extremely broad hypothesis (such as the hypothesis in our running example) with an extremely specific one (such as in our example).
2. With the hypotheses precisely stated, give an honest estimate to the prior odds of this formulation of the alternative hypothesis.
3. Consider if all the relevant information (or at least a representative sample thereof) has been presented to you before proceeding further. If not, consider gathering more information from further sources.
4. Estimate how likely the information was to have occurred under the null hypothesis.
5. Estimate how likely the information was to have occurred under the alternative hypothesis (using exactly the same wording of this hypothesis as you did in previous steps).
6. If the second estimate is significantly larger than the first, then you have cause to update your prior odds of this hypothesis (though if those prior odds were already vanishingly unlikely, this may not move the needle significantly). If not, the argument is unconvincing and no significant adjustment to the odds (except perhaps in a downwards direction) needs to be made.

A counterexample to the periodic tiling conjecture

Rachel Greenfeld and I have just uploaded to the arXiv our announcement “A counterexample to the periodic tiling conjecture“. This is an announcement of a longer paper that we are currently in the process of writing up (and hope to release in a few weeks), in which we disprove the periodic tiling conjecture of Grünbaum-Shephard and Lagarias-Wang. This conjecture can be formulated in both discrete and continuous settings:

Conjecture 1 (Discrete periodic tiling conjecture) Suppose that is a finite set that tiles by translations (i.e., can be partitioned into translates of ). Then also tiles by translations periodically (i.e., the set of translations can be taken to be a periodic subset of ).

Conjecture 2 (Continuous periodic tiling conjecture) Suppose that is a bounded measurable set of positive measure that tiles by translations up to null sets. Then also tiles by translations periodically up to null sets.

The discrete periodic tiling conjecture can be easily established for by the pigeonhole principle (as first observed by Newman), and was proven for by Bhattacharya (with a new proof given by Greenfeld and myself). The continuous periodic tiling conjecture was established for by Lagarias and Wang. By an old observation of Hao Wang, one of the consequences of the (discrete) periodic tiling conjecture is that the problem of determining whether a given finite set tiles by translations is (algorithmically and logically) decidable.

On the other hand, once one allows tilings by more than one tile, it is well known that aperiodic tile sets exist, even in dimension two – finite collections of discrete or continuous tiles that can tile the given domain by translations, but not periodically. Perhaps the most famous examples of such aperiodic tilings are the Penrose tilings, but there are many other constructions; for instance, there is a construction of Ammann, Grümbaum, and Shephard of eight tiles in which tile aperiodically. Recently, Rachel and I constructed a pair of tiles in that tiled a periodic subset of aperiodically (in fact we could even make the tiling question logically undecidable in ZFC).

Our main result is then

Theorem 3 Both the discrete and continuous periodic tiling conjectures fail for sufficiently large . Also, there is a finite abelian group such that the analogue of the discrete periodic tiling conjecture for is false.

This suggests that the techniques used to prove the discrete periodic conjecture in are already close to the limit of their applicability, as they cannot handle even virtually two-dimensional discrete abelian groups such as . The main difficulty is in constructing the counterexample in the setting.

The approach starts by adapting some of the methods of a previous paper of Rachel and myself. The first step is make the problem easier to solve by disproving a “multiple periodic tiling conjecture” instead of the traditional periodic tiling conjecture. At present, Theorem 3 asserts the existence of a “tiling equation” (where one should think of and as given, and the tiling set is known), which admits solutions, all of which are non-periodic. It turns out that it is enough to instead assert the existence of a system

of tiling equations, which admits solutions, all of which are non-periodic. This is basically because one can “stack” together a system of tiling equations into an essentially equivalent single tiling equation in a slightly larger group. The advantage of this reformulation is that it creates a “tiling language”, in which each sentence in the language expresses a different type of constraint on the unknown set . The strategy then is to locate a non-periodic set which one can try to “describe” by sentences in the tiling language that are obeyed by this non-periodic set, and which are “structured” enough that one can capture their non-periodic nature through enough of these sentences.

It is convenient to replace sets by functions, so that this tiling language can be translated to a more familiar language, namely the language of (certain types of) functional equations. The key point here is that the tiling equation

for some abelian groups is precisely asserting that is a graph

of some function (this sometimes referred to as the “vertical line test” in U.S. undergraduate math classes). Using this translation, it is possible to encode a variety of functional equations relating one or more functions taking values in some finite group (such as a cyclic group).

The non-periodic behaviour that we ended up trying to capture was that of a certain “-adically structured function” associated to some fixed and sufficiently large prime (in fact for our arguments any prime larger than , e.g., , would suffice), defined by the formula

for and , where is the number of times divides . In other words, is the last non-zero digit in the base expansion of (with the convention that the last non-zero digit of is ). This function is not periodic, and yet obeys a lot of functional equations; for instance, one has for all , and also for (and in fact these two equations, together with the condition , completely determine ). Here is what the function looks like (for ):

It turns out that we cannot describe this one-dimensional non-periodic function directly via tiling equations. However, we can describe two-dimensional non-periodic functions such as for some coefficients via a suitable system of tiling equations. A typical such function looks like this:

A feature of this function is that when one restricts to a row or diagonal of such a function, the resulting one-dimensional function exhibits “-adic structure” in the sense that it behaves like a rescaled version of ; see the announcement for a precise version of this statement. It turns out that the converse is essentially true: after excluding some degenerate solutions in which the function is constant along one or more of the columns, all two-dimensional functions which exhibit -adic structure along (non-vertical) lines must behave like one of the functions mentioned earlier, and in particular is non-periodic. The proof of this result is strongly reminiscent of the type of reasoning needed to solve a Sudoku puzzle, and so we have adopted some Sudoku-like terminology in our arguments to provide intuition and visuals. One key step is to perform a shear transformation to the puzzle so that many of the rows become constant, as displayed in this example,

and then perform a “Tetris” move of eliminating the constant rows to arrive at a secondary Sudoku puzzle which one then analyzes in turn:

It is the iteration of this procedure that ultimately generates the non-periodic -adic structure.

Using the Smith normal form to manipulate lattice subgroups and closed torus subgroups

Let denote the space of matrices with integer entries, and let be the group of invertible matrices with integer entries. The Smith normal form takes an arbitrary matrix and factorises it as , where , , and is a rectangular diagonal matrix, by which we mean that the principal minor is diagonal, with all other entries zero. Furthermore the diagonal entries of are for some (which is also the rank of ) with the numbers (known as the invariant factors) principal divisors with . The invariant factors are uniquely determined; but there can be some freedom to modify the invertible matrices . The Smith normal form can be computed easily; for instance, in SAGE, it can be computed calling the function from the matrix class. The Smith normal form is also available for other principal ideal domains than the integers, but we will only be focused on the integer case here. For the purposes of this post, we will view the Smith normal form as a primitive operation on matrices that can be invoked as a “black box”.

In this post I would like to record how to use the Smith normal form to computationally manipulate two closely related classes of objects:

• Subgroups of a standard lattice (or lattice subgroups for short);
• Closed subgroups of a standard torus (or closed torus subgroups for short).

(This arose for me due to the need to actually perform (with a collaborator) some numerical calculations with a number of lattice subgroups and closed torus subgroups.) It’s possible that all of these operations are already encoded in some existing object classes in a computational algebra package; I would be interested to know of such packages and classes for lattice subgroups or closed torus subgroups in the comments.

The above two classes of objects are isomorphic to each other by Pontryagin duality: if is a lattice subgroup, then the orthogonal complement

is a closed torus subgroup (with the usual Fourier pairing); conversely, if is a closed torus subgroup, then

is a lattice subgroup. These two operations invert each other: and .

Example 1 The orthogonal complement of the lattice subgroup

is the closed torus subgroup

and conversely.

Let us focus first on lattice subgroups . As all such subgroups are finitely generated abelian groups, one way to describe a lattice subgroup is to specify a set of generators of . Equivalently, we have

where is the matrix whose columns are . Applying the Smith normal form , we conclude that

so in particular is isomorphic (with respect to the automorphism group of ) to . In particular, we see that is a free abelian group of rank , where is the rank of (or ). This representation also allows one to trim the representation down to , where is the matrix formed from the left columns of ; the columns of then give a basis for . Let us call this a trimmed representation of .

Example 2 Let be the lattice subgroup generated by , , , thus with . A Smith normal form for is given by

so is a rank two lattice with a basis of and (and the invariant factors are and ). The trimmed representation is

There are other Smith normal forms for , giving slightly different representations here, but the rank and invariant factors will always be the same.

By the above discussion we can represent a lattice subgroup by a matrix for some ; this representation is not unique, but we will address this issue shortly. For now, we focus on the question of how to use such data representations of subgroups to perform basic operations on lattice subgroups. There are some operations that are very easy to perform using this data representation:

• (Applying a linear transformation) if , so that is also a linear transformation from to , then maps lattice subgroups to lattice subgroups, and clearly maps the lattice subgroup to for any .
• (Sum) Given two lattice subgroups for some , , the sum is equal to the lattice subgroup , where is the matrix formed by concatenating the columns of with the columns of .
• (Direct sum) Given two lattice subgroups , , the direct sum is equal to the lattice subgroup , where is the block matrix formed by taking the direct sum of and .

One can also use Smith normal form to detect when one lattice subgroup is a subgroup of another lattice subgroup . Using Smith normal form factorization , with invariant factors , the relation is equivalent after some manipulation to

The group is generated by the columns of , so this gives a test to determine whether : the row of must be divisible by for , and all other rows must vanish.

Example 3 To test whether the lattice subgroup generated by and is contained in the lattice subgroup from Example 2, we write as with , and observe that

The first row is of course divisible by , and the last row vanishes as required, but the second row is not divisible by , so is not contained in (but is); also a similar computation verifies that is conversely contained in .

One can now test whether by testing whether and simultaneously hold (there may be more efficient ways to do this, but this is already computationally manageable in many applications). This in principle addresses the issue of non-uniqueness of representation of a subgroup in the form .

Next, we consider the question of representing the intersection of two subgroups in the form for some and . We can write

where is the matrix formed by concatenating and , and similarly for (here we use the change of variable ). We apply the Smith normal form to to write

where , , with of rank . We can then write

(making the change of variables ). Thus we can write where consists of the right columns of .

Example 4 With the lattice from Example 2, we shall compute the intersection of with the subgroup , which one can also write as with . We obtain a Smith normal form

so . We have

and so we can write where

One can trim this representation if desired, for instance by deleting the first column of (and replacing with ). Thus the intersection of with is the rank one subgroup generated by .

A similar calculation allows one to represent the pullback of a subgroup via a linear transformation , since

where is the concatenation of the identity matrix and the zero matrix. Applying the Smith normal form to write with of rank , the same argument as before allows us to write where consists of the right columns of .

Among other things, this allows one to describe lattices given by systems of linear equations and congruences in the format. Indeed, the set of lattice vectors that solve the system of congruences

for , some natural numbers , and some lattice vectors , together with an additional system of equations

for and some lattice vectors , can be written as where is the matrix with rows , and is the diagonal matrix with diagonal entries . Conversely, any subgroup can be described in this form by first using the trimmed representation , at which point membership of a lattice vector in is seen to be equivalent to the congruences

for (where is the rank, are the invariant factors, and is the standard basis of ) together with the equations

for . Thus one can obtain a representation in the form (1), (2) with , and to be the rows of in order.

Example 5 With the lattice subgroup from Example 2, we have , and so consists of those triples which obey the (redundant) congruence

the congruence

and the identity

Conversely, one can use the above procedure to convert the above system of congruences and identities back into a form (though depending on which Smith normal form one chooses, the end result may be a different representation of the same lattice group ).

Now we apply Pontryagin duality. We claim the identity

for any (where induces a homomorphism from to in the obvious fashion). This can be verified by direct computation when is a (rectangular) diagonal matrix, and the general case then easily follows from a Smith normal form computation (one can presumably also derive it from the category-theoretic properties of Pontryagin duality, although I will not do so here). So closed torus subgroups that are defined by a system of linear equations (over , with integer coefficients) are represented in the form of an orthogonal complement of a lattice subgroup. Using the trimmed form , we see that

giving an explicit representation “in coordinates” of such a closed torus subgroup. In particular we can read off the isomorphism class of a closed torus subgroup as the product of a finite number of cyclic groups and a torus:

Example 6 The orthogonal complement of the lattice subgroup from Example 2 is the closed torus subgroup

using the trimmed representation of , one can simplify this a little to

and one can also write this as the image of the group under the torus isomorphism

In other words, one can write

so that is isomorphic to .

We can now dualize all of the previous computable operations on subgroups of to produce computable operations on closed subgroups of . For instance:

• To form the intersection or sum of two closed torus subgroups , use the identities

  

  and

  

  and then calculate the sum or intersection of the lattice subgroups by the previous methods. Similarly, the operation of direct sum of two closed torus subgroups dualises to the operation of direct sum of two lattice subgroups.
• To determine whether one closed torus subgroup is contained in (or equal to) another closed torus subgroup , simply use the preceding methods to check whether the lattice subgroup is contained in (or equal to) the lattice subgroup .
• To compute the pull back of a closed torus subgroup via a linear transformation , use the identity

  

  Similarly, to compute the image of a closed torus subgroup , use the identity

  

Example 7 Suppose one wants to compute the sum of the closed torus subgroup from Example 6 with the closed torus subgroup . This latter group is the orthogonal complement of the lattice subgroup considered in Example 4. Thus we have where is the matrix from Example 6; discarding the zero column, we thus have

Request for comments from the ICM Structure Committee

[This post is collectively authored by the ICM structure committee, whom I am currently chairing – T.]

The ICM structure committee is responsible for the preparation of the Scientific Program of the International Congress of Mathematicians (ICM). It decides the structure of the Scientific Program, in particular,

• the number of plenary lectures,
• the sections and their precise definition,
• the target number of talks in each section,
• other kind of lectures, and
• the arrangement of sections.

(The actual selection of speakers and the local organization of the ICM are handled separately by the Program Committee and Organizing Comittee respectively.)

Our committee can also propose more radical changes to the format of the congress, although certain components of the congress, such as the prize lectures and satellite events, are outside the jurisdiction of this committee. For instance, in 2019 we proposed the addition of two new categories of lectures, “special sectional lectures” and “special plenary lectures”, which are broad and experimental categories of lectures that do not fall under the traditional format of a mathematician presenting their recent advances in a given section, but can instead highlight (for instance) emerging connections between two areas of mathematics, or present a “big picture” talk on a “hot topic” from an expert with the appropriate perspective. These new categories made their debut at the recently concluded virtual ICM, held on July 6-14, 2022.

Over the next year or so, our committee will conduct our deliberations on proposed changes to the structure of the congress for the next ICM (to be held in-person in Philadelphia in 2026) and beyond. As part of the preparation for these deliberations, we are soliciting feedback from the general mathematics community (on this blog and elsewhere) on the current state of the ICM, and any proposals to improve that state for the subsequent congresses; we had issued a similar call on this blog back in 2019. This time around, of course, the situation is complicated by the extraordinary and exceptional circumstances that led to the 2022 ICM being moved to a virtual platform on short notice, and so it is difficult for many reasons to hold the 2022 virtual ICM as a model for subsequent congresses. On the other hand, the scientific program had already been selected by the 2022 ICM Program Committee prior to the invasion of Ukraine, and feedback on the content of that program will be of great value to our committee.

Among the specific questions (in no particular order) for which we seek comments are the following:

1. Are there suggestions to change the format of the ICM that would increase its value to the mathematical community?
2. Are there suggestions to change the format of the ICM that would encourage greater participation and interest in attending, particularly with regards to junior researchers and mathematicians from developing countries?
3. The special sectional and special plenary lectures were introduced in part to increase the emphasis on the quality of exposition at ICM lectures. Has this in fact resulted in a notable improvement in exposition, and should any alternations be made to the special lecture component of the ICM?
4. Is the balance between plenary talks, sectional talks, special plenary and sectional talks, and public talks at an optimal level?  There is only a finite amount of space in the calendar, so any increase in the number or length of one of these types of talks will come at the expense of another.
5. The ICM is generally perceived to be more important to pure mathematics than to applied mathematics.  In what ways can the ICM be made more relevant and attractive to applied mathematicians, or should one not try to do so?
6. Are there structural barriers that cause certain areas or styles of mathematics (such as applied or interdisciplinary mathematics) or certain groups of mathematicians to be under-represented at the ICM?  What, if anything, can be done to mitigate these barriers?
7. The recently concluded virtual ICM had a sui generis format, in which the core virtual program was supplemented by a number of physical “overlay” satellite events. Are there any positive features of that format which could potentially be usefully adapted to such congresses? For instance, should there be any virtual or hybrid components at the next ICM?

Of course, we do not expect these complex and difficult questions to be resolved within this blog post, and debating these and other issues would likely be a major component of our internal committee discussions.  Nevertheless, we would value constructive comments towards the above questions (or on other topics within the scope of our committee) to help inform these subsequent discussions.  We therefore welcome and invite such commentary, either as responses to this blog post, or sent privately to one of the members of our committee.  We would also be interested in having readers share their personal experiences at past congresses, and how it compares with other major conferences of this type.   (But in order to keep the discussion focused and constructive, we request that comments here refrain from discussing topics that are out of the scope of this committee, such as suggesting specific potential speakers for the next congress, which is a task instead for the 2022 ICM Program Committee. Comments that are specific to the recently concluded virtual ICM can be made instead at this blog post.)