AMSI Summer Vacation Scholarship

Below is a guest blog post of Melissa Lee, who took part in a six-week summer vacation research project supported by the Australian Mathematical Sciences Institute.

 

Hi everyone! My name is Melissa Lee and I’ve recently started honours with John and Dr. Eric Swartz here at UWA. This past summer I have been working with John on an AMSI Vacation Research Scholarship. My AMSI VRS project was based on looking at structures embedded in an affine space by viewing them in terms of a game called SET. Continue reading “AMSI Summer Vacation Scholarship”

Advertisements

Green, gold or diamond access

There is been much buzz about on the question of the open access model of publishing in academic literature, and in particular, there has been recent excitement in mathematics with the recent announcement of the Forum of Mathematics led by Terry Tao and Tim Gowers. This is touted as “potentially cheap” gold access (in that there is a period of no charge to get it started, with perhaps a lengthening of this period depending on external funding) and thought to many to be the least of all evils. However, with some imagination, perhaps we shouldn’t abandon the “diamond”-hued model?

Continue reading “Green, gold or diamond access”

Science without stats

Would any of us argue that it is important for many of the experimental scientists to have a basic training in statistics? I admit, I haven’t done much statistics myself, but if I was working in horticulture or biomedicine, I think it would be a no brainer that management of data would require a rudimentary understanding of statistics. I have been fortunate to have learnt from my colleagues the utility and applicability of statistics, and I have recently had the pleasure of watching Hans Rosling documentaries promoting the significance of statistics in our everyday lives. From this reflection, I am convinced that I am unqualified to carry out an experiment of any kind!

So why is it that at my university, that many of the future scientists will know little statistics beyond what I know?

Continue reading “Science without stats”

Long Division

It was with great regret that last year I learnt that long division was no longer an oft-taught technique in Western Australian schools. Why didn’t someone tell me! I found myself teaching polynomial rings in a second year undergraduate course, but had to back-peddle a tad to show the students how it was possible to find the remainder when you divide 7 out of 10334 (the answer is 2, by the way).

Technology might well have made this calculation redundant, but it doesn’t take long to think up some good reasons why long division should go back into the curriculum. First of all, it’s an algorithm. The notion of an algorithm is a very important one in mathematics, and indeed, science. It is difficult to come up with examples of genuine sophisticated algorithms for secondary school students, beyond the wholly sequential.

Secondly, what makes long division work is the “Division Theorem”, and it is an interesting question as to what things a Division Theorem applies. The Division Theorem doesn’t work for the real numbers, but it does for integers (including the negative ones!). (We refer the interested reader to the theory of Euclidean domains).

Thirdly, we need some idea of the division algorithm to get a grip on what a real number is. Think about it, what is a real number? The idea that an infinite decimal expansion can define something uniquely, hinges on the uniqueness of the remainder in the Division theorem. Moreover, any decimal expression which repeats represents a rational number. After this is understood a student can proceed to understand what an irrational number is.

Fourthly, division of polynomials is important in tertiary level mathematics. For example, I saw just today an exercise given in class where it was asked to find the eigenvalues of the triangle (3-cycle) graph. The characteristic polynomial of the adjacency matrix of this graph is X^3-3X-2 and we can see that 2 is a root of this polynomial. So we  use long division to find the quadratic factor, which turns out to be (X+1)^2.

We conclude with a link to an article on the role of long division in school.

Can anyone think of another reason why long division is a necessary skill?

Goodstein’s Theorem

Today we have a guest post from Phill Schultz, who is a adjunct associate professor in our school.

Take any positive integer {n} and express it in complete 2–adic form, i.e. as a sum of powers of 2 in which the powers themselves are also in complete 2–adic form. For example, {34=2^{2^2+1}+2}. Now replace each 2 by 3, subtract 1 and write the result in 3–adic form, in this case {3^{3^3+1}+2}, an integer with 39 digits. Repeat the procedure, replacing 3 by 4 and so on. Although the numbers you get seem to increase rapidly, Goodstein’s Theorem states that after finitely many steps, you reach zero.

This remarkable result, proved by Reuben Goodstein in 1944, has an even more remarkable proof. Suppose {n_j} is the {j}–adic number constructed from {n} at the {j}th step. Replace each {j} in {n_j} by {\omega}, to get {n_j(\omega)}, a countable ordinal in Cantor Normal Form. The sequence {(n_j(\omega):\, j=2,3,\dots)} of ordinals satisfies {n_j\leq n_j(\omega)} and {n_{j+1}(\omega)<n_j(\omega)}, because of the subtraction of 1 in moving from {n_j} to {n_{j+1}}. But there is no infinite properly descending chain of ordinals, so after finitely many steps, you get {0\leq n_j\leq n_j(\omega)=0}.

My interest in Goodstein’s Theorem was sparked by John Stillwell’s new book Roads to Infinity, published in 2010 by A. K. Peters, Ltd. In it, Stillwell points out the connection between the purely arithmetical Goodstein’s Theorem and questions of truth and provability in Logic.

The proof above of Goodstein’s Theorem has some remarkable features. First, note that for each positive integer {n}, the function {j\mapsto n_j} grows rapidly before diminishing to zero exceedingly slowly. For example, Stillwell points out that the least {j} for which {4_j=0} is {3\cdot2^{402653211}-1}.

Second, note that although the hypotheses and conclusion can be expressed in the first order language of Peano Arithmetic (PA), this proof cannot. This is because PA only allows finite induction, i.e.,  “induction up to {\omega}”, whereas the proof uses transfinite induction, but only up to a countable ordinal {\varepsilon_0>\omega}. More precisely, {\varepsilon_0} (Cantor’s notation of 1883) is the ordinal that can be described either from above, as the least ordinal {\alpha} such that {\beta<\alpha\Rightarrow \beta^\omega<\alpha}, or from below as {\sup\{\omega_n:\,n<\omega\}} where {\omega_0=\omega} and {\omega_{n+1}=(\omega_n)^\omega}. The significance of {\varepsilon_0} relates to Gödel’s Incompleteness Theorem (1936), which states that in any consistent formal theory in which PA can be formulated, there are unprovable true statements. A corollary, which I call Gödel’s Corollary, is that no such theory contains a proof of its own consistency. Also in 1936, Gerhard Gentzen proved that PA is consistent by using induction up to {\varepsilon_0}. Therefore, by Gödel’s Corollary, {\varepsilon_0}–induction cannot be a valid proof method in PA.

We have seen that Goodstein’s Theorem can be expressed as a statement in PA which is true because it has a proof in a subset of ZF Set Theory which is consistent and sound, i.e., every provable statement is true. Hence in order to show that Goodstein’s Theorem is a minimal example of Gödel’s Incompleteness Theorem, it remains to show that it is unprovable in PA.

This is the crux of Stillwell’s presentation. His method is to show that the Goodstein process can be extended to a more general procedure in which {n_j} is replaced by {n_{\lambda(j)}} where {\lambda} is an arbitrary strictly increasing transformation of the natural numbers, the original being {\lambda(n)=n+1}. He shows that iterating this procedure also terminates in finitely many steps at zero, and consequently the generalised Goodstein Theorem is logically equivalent to {\varepsilon_0}–induction. Hence its provability within PA would contradict Gödel’s Corollary.

There are several known exemplars of Gödel’s Theorem within Combinatorics, such as the Paris–Harrington Theorem and the Graph Minor Theorem, but none as transparent as Goodstein’s Theorem.

Is there a 16-clue Sudoku puzzle?

A few years ago, when the Sudoku craze briefly swept the world, I became interested in one particular mathematical aspect of Sudoku – namely, what is the minimum number of clues needed for a puzzle that can be uniquely completed.

This is actually just one instance of a whole family of combinatorial problems, usually studied under names such as defining sets or critical sets, that considers when a combinatorial structure (such as a Latin square) can be reconstructed uniquely from a (small) portion of the structure.

Around that time, I found an obscure Japanese website (whose identity I have long forgotten) that had a couple of uniquely-completable Sudoku puzzles with only 17 clues. (As I am only interested in uniquely completable puzzles, I’ll drop the adjectives from now on and just assume that “puzzle” always means “uniquely completable puzzle”.)  I took these puzzles and started to “perturb” them in various ways, perhaps by swapping a number for another number, or shifting an entry to another cell, all the time keeping track of any new ones that I found. I was hoping that by finding enough 17-clue puzzles, I would eventually stumble across a 16-clue puzzle contained in one of the 17-clue ones. Continue reading “Is there a 16-clue Sudoku puzzle?”

Graph symmetry II

In my previous post I discussed various measures of symmetry of the vertex set of a graph. The main terms introduced were vertex-transitive, vertex-primitive, vertex-quasiprimitive, vertex-biprimitive and vertex-biquasiprimitive. It was also seen that the class of vertex-transitive graphs was very large and so we often place further symmetry conditions on our graphs so that we can obtain interesting results. In this post I wish to discuss conditions on the symmetry of the edge set {E\Gamma} and arc set {A\Gamma}.

A graph {\Gamma} is called edge-transitive if {\mathrm{Aut}(\Gamma)} acts transitively on the set of edges of {\Gamma} and is called arc-transitive if {\mathrm{Aut}(\Gamma)} acts transitively on the set of arcs. As long as there are no isolated vertices (that is vertices with no neighbours) then an arc-transitive graph will also be vertex-transitive and edge-transitive. Such graphs are often called symmetric.

I will first discuss how to construct all arc-transitive graphs. Let {G} be a transitive permutation group on a set {\Omega}. The orbits of {G} on {\Omega\times\Omega} are called orbitals. An orbital {\mathcal{O}} is called self-paired if for all {(\alpha,\beta)\in \mathcal{O}} the element {(\beta,\alpha)} also lies in {\mathcal{O}}. This is equivalent to there being an element {g\in G} that interchanges {\alpha} and {\beta}. For each self-paired orbital we can construct a graph {\Gamma} with vertex set {\Omega} and edges {\{\alpha,\beta\}} for all {(\alpha,\beta)\in \mathcal{O}}. The group {G} is an arc-transitive group of automorphisms of {\Gamma}. Moreover, all arc-transitive graphs arise in this way.

 

Continue reading “Graph symmetry II”

Graph symmetry

John claims that he and Gordon are confused by the various adjectives used by us graph symmetry people and how they relate to each other so I have decided to write some posts outlining the main ones and their importance. There is a nice diagram on wikipedia illustrating the relationship between the main ones and I will use that as the basis of my discussion.

Throughout I will use {\Gamma} to denote a graph and {G} to denote a group (unfortunately some authors use the reverse.) All graphs will be simple (that is, undirected, no multiple edges, and no loops) and finite. The full automorphism group of a graph, that is the group of all permutations of the set of vertices that take edges to edges, will be denoted by {\mathrm{Aut}(\Gamma)}. I will use {V\Gamma} to denote the set of vertices, {E\Gamma} to denote the set of edges and {A\Gamma} to denote the set of arcs, that is the set of ordered pairs of adjacent vertices.

The first adjective is regular. A graph is called regular if each vertex has the same number of neighbours. This number is referred to as the valency of the graph.

A graph is called vertex-transitive if {\mathrm{Aut}(\Gamma)} acts transitively on the set of vertices, that is, for all {v, u\in V\Gamma} there exists an automorphism {g} such that {u^g=v}. Sometimes we wish to restrict our attention to a subgroup {G} of {\mathrm{Aut}(\Gamma)} and say that {\Gamma} is {G}-vertex-transitive if {G} acts transitively on {V\Gamma}.

One consequence of a graph being vertex-transitive is that it is regular: if an automorphism {g} maps {u} to {v} then it also maps the neighours of {u} to the nieghbours of {v}. However, not all regular graphs are vertex-transitive. In fact, it is even possible for a regular graph to have a trivial automorphism group, for example, the Frucht graph.

Continue reading “Graph symmetry”

Generalised quadrangles VI: translation generalised quadrangles

I am finally onto my last post on generalised quadrangles. The topic of this one is translation generalised quadrangles. These are a special case of elation generalised quadrangles outlined in my last post. The main source for this post has been Michel Lavrauw’s Phd thesis which is availiable from Ghent’s PhD theses in finite geometry page.

Recall that an elation generalised quadrangle (EGQ) is a generalised quadrangle with a base point {x} and a group of automorphisms that fixes each line incident with {x} and acts regularly on the set of points not collinear with {x}. A translation generalised quadrangle (or TGQ) is an EGQ with an abelian elation group. In this case the elation group is referred to as a translation group. We saw in the EGQ post, that {\mathsf{W}(3,q)}, for {q} even, has an abelian elation group and so is an example of a TGQ. It has been proved by Stan Payne and Jef Thas that for a TGQ, the elation group must be elementary abelian and in particular {s} and {t} are powers of the same prime.

Continue reading “Generalised quadrangles VI: translation generalised quadrangles”

Up ↑