Simon Marais Problem Competition 2017

A couple of weeks ago, there was the inaugural Simon Marais Mathematics Competition, a new maths competition for undergraduate students living in the time zones between New Zealand and India inclusive.

The students’ scripts have not yet been marked. As a member of the problem committee, I will be especially interested to see how they did. The questions and solutions can be found on the Simon Marais website. There will be a greater variety of solutions posted some time in November after the scripts have been marked. I will currently permit myself a few brief comments on the problems.

I actually came up with B1, which surprised me! The idea here was to specifically come up with an easy problem. One day I was leafing through some old Olympiad material, and on a sheet of preparatory problems for a maths camp from when I was a student, I saw a problem about classifying configurations of 4 points in the plane such that the sum of the distances from each point to the other points was the same. I wondered to myself what happened in three dimensions and the problem was born.

Problem A4 is expected to be very hard and has an interesting solution which I found and wrote up here. This is similar to an approach to the fundamental theorem of algebra which I believe goes back to Gauss and which I may discuss here if I have time.

As a member of the problem committee, I am always looking out for problem submissions for future competitions and welcome anybody who has what they think might be a suitable problem to submit it (which can be directly to me, or the chair of the committee, via email).

The medians of a triangle are concurrent

In case anyone reading this does not know, a median is a line connecting a vertex of a triangle to the midpoint of the opposite edge. The theorem is that the three medians of a triangle are concurrent (i.e. they meet in a single point). Here are four proofs.

Proof 1: (Transformation geometry)

Let E and F be the midpoints as shown and let BE and CF intersect at G. Consider the dilation about A with factor 2. It sends E to C, F to B and G to Q (this is the definition of Q). Then EG and CQ are parallel, as are FG and BQ. Thus BGCQ is a parallellogram and the diagonals of a parallelogram bisect each other QED.

Proof 2: (Vectors. Efficient and boring). Write {\bf a}, {\bf b} and {\bf c} for A, B and C respectively. Let G be ({\bf a}+{\bf b}+{\bf c})/3. It is easy then to check that the midpoint D of AB is ({\bf a}+{\bf b})/2 and that A, D and G are concurrent.

Proof 3: (Why not just prove Ceva’s Theorem)

Ceva’s Theorem states that in the situation shown, AD, BE and CF are concurrent if and only if

\displaystyle \frac{BD}{DC}\frac{CE}{EA}\frac{AF}{FB}=1.

To prove this, note that in the case of concurrence

\displaystyle \frac{BD}{DC}=\frac{|ABG|}{|ACG|}.

The rest of the proof is routine.

Proof 4: (my favourite) WLOG the triangle is equilateral. Now the statement is obvious (e.g. by symmetry).

Perhaps some elaboration should be made to the WLOG. An affine transformation of \mathbb{R}^2 is a map of the form {\bf{v}}\mapsto A{\bf{v}}+{\bf{b}} where A is an invertible matrix and {\bf{b}} is a vector. The affine transformations act transitively on the set of (nondegenerate) triangles and the property of having concurrent medians is clearly invariant under these transformations.

Acknowledgements: Thanks to Inna Lukyanenko for the first proof and tikz files, and to pdftoppm for converting the .pdf output to .png.

A different proof of the fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every integer can be uniquely written as a product of primes (i.e. \mathbb{Z} is a unique factorisation domain).

The usual proof proceeds through the Euclidean algorithm. Yesterday at lunch I was surprised to learn (thanks to Ole Warnaar) of a different proof bypassing the Euclidean algorithm which I reproduce below. Its primary attraction is its cuteness, as it provides a weaker result than the usual proof (i.e. doesn’t prove that \mathbb{Z} is a Euclidean domain, or even a principal ideal domain).

Suppose that n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} where p_1,p_2,\ldots,p_k are distinct primes. Consider the finite cyclic group C_n. It has a composition series where the group C_{p_i} appears a_i times as a simple subquotient (and no other simple factors appear). Therefore by the Jordan-Holder theorem, the primes p_i together with their multiplicities a_i are unique. QED.

Pi is trancendental

First the rabbit. The introduction of this function is the part which I don’t know how to motivate. Let f be a polynomial and define

\displaystyle I(z,f)=\int_0^z e^{z-t}f(t)\,dt.

Integration by parts gives the recursion

\displaystyle I(z,f)=e^z f(0)-f(z)+I(z,f')

and therefore we have the formula

\displaystyle I(z,f)=e^z\sum_{j\geq 0} f^{(j)}(0) - \sum_{j\geq 0}f^{(j)}(z).

Now suppose (for want of a contradition) that \pi i \in \overline{\mathbb{Q}}. Let the set of Galois conjugates of \pi i be \{a_1,\ldots,a_k\}. Then we have \prod_{i=1}^k (1+e^{a_i})=0, expand this as \sum_{J\subset[k]}e^{\sum_{j\in J}a_j}=0 and rewrite as

\displaystyle (2^k-d)+\sum_{i=1}^d e^{\theta_i}=0

where the \theta_i are the nonzero exponents.

Now consider

\displaystyle \sum_{i=1}^d I(\theta_i,f)=(d-2^k)\sum_{j\geq 0}f^{(j)}(0)-\sum_{j\geq 0}\sum_{i=1}^df^{(j)}(\theta_i)

Let N be an integer such that N\pi i is an algebraic integer. Let p be a (large) prime and we choose to take

\displaystyle f(x)=N^{dp}x^{p-1}\prod_{i=1}^d(x-\theta_i)^p\in\mathbb{Z}[x].

There are absolute constants A and B (independent of p) such that

\displaystyle |\sum_{i=1}^d I(\theta_i,f)|\leq A B^p

(look at the integral definition of I(z,f) and apply the naive estimate).

Now consider \sum_{i=1}^d I(\theta_i,f). It is a Galois-invariant algebraic integer, hence an integer. We have

\displaystyle \sum_{i=1}^d I(\theta_i,f)=(d-2^k)f^{(p-1)}(0)+\text{higher order terms}.

Here higher order means at least p derivatives appearing. Each of these higher order terms is divisible by p!, hence by p. Since p is prime, for large enough p, \sum_{i=1}^d I(\theta_i,f) is not divisible by p, hence nonzero.

Now every term is divisible by (p-1)!, so we get the lower bound

\displaystyle |\sum_{i=1}^d I(\theta_i,f)|\geq (p-1)!

As there are infinitely many primes, we can send choose p large enough to get a contradiction, QED.

Single variable polynomial division in sage

As far as I can tell, this isn’t done purely within sage, and requires a call to maxima.

If you want to divide the polynomial a by b to produce a quotient and remainder, the code is.

a.maxima_methods().divide(b)

The first element of the output is the quotient and the second is the remainder.

So for example

sage: R=QQ['x']
sage: a=x^210-1
sage: b=R.cyclotomic_polynomial(210)*(x-1)
sage: q,r=a.maxima_methods().divide(b)
sage: q
x^161 + 2*x^160 + 2*x^159 + x^158 - x^156 - x^155 - x^154 - x^153 - x^152 + x^150 + 2*x^149 + 2*x^148 + 2*x^147 + 2*x^146 + 2*x^145 + x^144 - x^142 - x^141 + x^139 + x^138 + x^137 + x^136 + x^135 + x^134 + x^133 + x^132 + x^131 + x^130 + x^129 + x^128 + x^127 + 2*x^126 + 3*x^125 + 3*x^124 + 2*x^123 + x^122 + x^116 + 2*x^115 + 3*x^114 + 3*x^113 + 3*x^112 + 3*x^111 + 3*x^110 + 2*x^109 + x^108 + x^105 + 2*x^104 + 2*x^103 + 2*x^102 + 2*x^101 + 2*x^100 + 2*x^99 + 2*x^98 + 2*x^97 + 2*x^96 + 2*x^95 + 2*x^94 + 2*x^93 + 2*x^92 + 2*x^91 + 2*x^90 + 2*x^89 + 2*x^88 + 2*x^87 + 2*x^86 + 2*x^85 + 2*x^84 + 2*x^83 + 2*x^82 + 2*x^81 + 2*x^80 + 2*x^79 + 2*x^78 + 2*x^77 + 2*x^76 + 2*x^75 + 2*x^74 + 2*x^73 + 2*x^72 + 2*x^71 + 2*x^70 + 2*x^69 + 2*x^68 + 2*x^67 + 2*x^66 + 2*x^65 + 2*x^64 + 2*x^63 + 2*x^62 + 2*x^61 + 2*x^60 + 2*x^59 + 2*x^58 + 2*x^57 + x^56 + x^53 + 2*x^52 + 3*x^51 + 3*x^50 + 3*x^49 + 3*x^48 + 3*x^47 + 2*x^46 + x^45 + x^39 + 2*x^38 + 3*x^37 + 3*x^36 + 2*x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^23 + x^22 - x^20 - x^19 + x^17 + 2*x^16 + 2*x^15 + 2*x^14 + 2*x^13 + 2*x^12 + x^11 - x^9 - x^8 - x^7 - x^6 - x^5 + x^3 + 2*x^2 + 2*x + 1
sage: r
0

hat tip: this question

A free semigroup

In the appendix here, we make the claim that the semigroup

\Gamma_A=\langle \begin{pmatrix}a & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix}b & 1 \\ 1 & 0 \end{pmatrix}\mid 1\leq a,b\leq A\rangle

is free on the given generators.

Here, I will give a proof. It is a simpler version of the ping-pong argument commonly used to prove that a group is free on a given set of generators.

First a simple observation. it suffices to prove that the set

\left\{ \begin{pmatrix}a & 1 \\ 1 & 0 \end{pmatrix}\mid 1\leq a\leq A\right \}

generates a free semigroup.

Now, consider the action of our semigroup on the interval (1,\infty) by fractional linear transformations:

\begin{pmatrix}a & b \\ c & d \end{pmatrix}\cdot x=\frac{ax+b}{cx+d}

In particular, note that

\begin{pmatrix}a & 1 \\ 1 & 0 \end{pmatrix}\cdot x=a+\frac{1}{x}.

Now suppose that

\begin{pmatrix}y_1 & 1 \\ 1 & 0 \end{pmatrix}\cdots\begin{pmatrix}y_m & 1 \\ 1 & 0 \end{pmatrix}=\begin{pmatrix}z_1 & 1 \\ 1 & 0 \end{pmatrix}\cdots\begin{pmatrix}z_n & 1 \\ 1 & 0 \end{pmatrix}

Apply both sides to some x\in(1,\infty). The LHS lies in (y_1,y_1+1) and the RHS lies in (z_1,z_1+1). Therefore y_1=z_1 and the rest is an easy induction.

Some easy singular Schubert varieties

I write w for both an element of the Weyl group and the corresponding point in G/B. Let X_w be a Schubert variety. Then T_eX_w\subset T_e(G/B) is an inclusion of \mathfrak{b} representations. The latter is generated by the -\theta-weight space, where \theta is the highest root.

Suppose w\geq s_\theta, where s_\theta is the reflection corresponding to \theta. Then the \mathbb{P}^1 connecting e and s_\theta lies in X_w (think of the corresponding SL2), so the -\theta-weight space lies in T_eX_w. Since this generates T_e(G/B), we have T_eX_w=T_e(G/B).

Therefore if w_0\neq w\geq s_\theta, then X_w is singular. This includes some of the first examples of singular Schubert varieties, for example the B2 singular Schubert variety and one of the A3 ones.

BIRS (Banff, Canada)

I was fortunate to recently spend a week at the Banff International Research Station, for a conference on Whittaker Functions: Number Theory, Geometry and Physics. Rather than talk about the mathematics, I will concentrate on the facilities in this post. BIRS has been successfully running many maths workshops for many years now and are in high demand as they consistently do a good job overall.

Location:
Banff is a tourist town in the picturesque Canadian Rocky mountains. The standard way to get there is via Calgary airport, catching the Banff airporter bus (one-way 2 hours, CAD54 with BIRS discount applied). BIRS itself is part of the larger Banff Centre, which is mainly an arts venue situated on a hill with elevated views over the town.

Food and Lodging:
Participants are all accommodated onsite in clean and comfortable single rooms sharing a bathroom with one other participant. There were some participants complaining about the temperature but I found no problems. The meals are also onsite in a buffet arrangement, and generally of a good quality (and hence tempting to pig out on the dessert). Internet access exists and works. I didn’t subject this to any serious stress tests.

Academic Facilities:
Here is a picture of Manish Patnaik giving his talk.

Maniish Patnaik

You can see the tiered seating (good) and the lack of blackboard space (bad). There was space from an architectural point of view to put in blackboards that can be moved up and down, so for a dedicated conference centre this is especially disappointing. All talks were recorded by an automated system (it is possible that not all were remembered to be recorded, as this process required manually pressing a button at the start of each talk).

Unfortunately some people continue to turn down lights during slide talks, despite the slides being perfectly visible under normal lighting conditions. This is annoying because it strains the eyes to make notes, and makes it harder to work on other things when (some) speakers inevitably power through their slides at too rapid a pace.

There are also other small private discussion rooms equipped with whiteboards for participants’ use.

Stephen D. Miller:
Stephen D. Miller was originally scheduled to attend and give a talk, but got screwed over by an airline and ended up deciding not to come. He then recorded a talk which we watched (and you can too (mp4)) and skyped in at the end of the viewing to answer questions. This worked surprisingly well, which I suspect is more a function of the speaker being Stephen as opposed to the format.

I overheard some other participants remark that they were still disappointed that Stephen didn’t come as they were hoping to discuss informally with him. Experienced conference-goers will naturally and immediately recognise this sentiment, knowing that the informal discussions that take place at a conference can be even more important than the formal program.

Afterwards:
It is a little known fact that it is possible to spend a couple of additional days at BIRS afterwards. A few of us availed ourselves of this welcome opportunity.

My talk:
I did not give a talk at this conference. I did however give a talk on my recent work on geometric extension algebras at the University of Alberta the following week.

The scenic route from Banff to Edmonton

The scenic route from Banff to Edmonton

My 2016 Senate Election Vote

It is possible to check if your vote for the Senate was counted correctly in the 2016 Australian Federal election. To begin, go to this AEC website, download the Formal Preferences file for your relevant state or territory and unzip.

In my case, I download the Queensland file. The preferences I gave the first five candidates were 2, 1, 46, 47 and 20 so I type

grep 2,1,46,47,20 aec-senate-formalpreferences-20499-QLD.csv

and out comes

Griffith,South Brisbane,874,32,29,",,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2,1,46,
47,20,3,45,44,43,42,41,40,68,69,70,71,113,82,81,80,79,78,77,76,72,73,74,75,37,
38,66,67,23,27,35,36,99,100,101,102,103,104,105,64,65,21,22,62,63,106,107,108,
109,48,49,32,33,34,60,61,114,115,116,117,118,119,18,4,120,121,58,59,24,25,26, 30,31,19,5,110,111,28,29,57,56,55,54,53,52,17,16,15,14,13,12,11,10,9,8,7,6,50,
51,98,97,112,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,122"

The output begins with my electorate and polling place. I don’t know what the next three numbers mean. The numbers following the string of commas are my preferences, in order that the candidates appeared on the ballot paper.

Here is where it gets embarrassing. Eagle eyed readers will immediately have noticed that there is no 39 in this list, and there are two 82s. Nevertheless, I believe it is still formal.

Using the distribution of preferences from this other AEC site, it is possible to track my vote through the count. It passes through the hands of a few no-hopers before reaching Larissa Waters (Green) who is elected in 9th place.

Larissa Waters is elected at the 738th count with a surplus of only 181 votes. In theory my vote should then transfer at a paltry value of 181/209475 (about .0009) to Suzanne Grant (Xenophon team) but the vagaries of the inclusive Gregory system and the existence of loss by fraction makes it hard to say this with any certainty.