Recent content on What's all this, then?
Vowels in Australian placenames In the state of Victoria, Australia, there is a town called called Euroa . Like many Australian place names with lots of vowels, this name is taken from a local Aboriginal word; this one means “joyful”. A friend of mine staying there pointed out that the name had four vowels, which led us to wonder what Australian place names had either any four vowels…
The previous blog post showed some examples of self-avoiding paths, all on orthogonal (Cartesian) grids. But there are lots of other grids. Two other “natural” grids are hexagonal and triangular. The hexagonal grid looks like beeswax, or chicken wire (known as “gopher wire” in parts of the world where gophers are troublesome). That is, the edges of the grid are the edges of…
Suppose we start at \((0,0)\) on the cartesian grid, and wander about randomly only in North, South, East and West directions, never visiting a vertex more than once. How far will we wander before we come to a point around which there are no unvisited vertices? This is best answered experimentally, and indeed it’s already be done - note that this article is behind a paywall, but the result…
A self avoiding walk is a path through a graph where no vertex is visited more than once. One problem is to consider the cartesian lattice, and the paths from \((0,0)\) to \((m,n)\). If we only allow paths in the “positive direction”, so that from \((i,j)\) the path can only proceed to \((i+1,j)\) or \((i,j+1)\) we have what are sometimes called “staircase paths”: The…
The Asian Technology Conference in Mathematics is a friendly, genial conference which has been held almost every year since 1996. All the proceedings are freely available on that website, but there is no search method. If you want to find out if anybody has presented a paper about, say, teaching linear algebra with Python, you’re stuck. To help, I created a database of all papers and authors…
Recall from the previous post that the Weierstrass-Durand-Kerner (WDK) method finds all roots of a polynomial equation in a manner similar to Newton’s method, and so converges quadratically. The Aberth-Ehrlich method (more commonly called Aberth’s method), is similar, but converges cubically, and as we will see, is similar to Halley’s method for root finding. Derivation from…
This is a method for finding all the roots of a polynomial simultaneously, by applying a sort of Newton-Raphson method. It gets its name from everybody associated wth it: Weierstrass published a version of the algorithm in 1891, and then rediscovered (independently) by Durand in 1960 and Kerner in 1966, as you can see at its Wikipedia page . It’s easier to describe by an example: \[ x^4 -…
Recap, and background Two posts ago we showed how, given four points in the plane in general position, but with a few restrictions, it was possible to find two parabolas through those points. We used computer algebra. The steps were: Create four equations \[ (Ax_i+By_i)^2+Cx_i+Dy_i+E=0 \] for each of the four \((x_i,y_i)\) coordinates. Solve the first three equations for \(C\), \(D\) and \(E\):…
It is (well?) known that if \(x = at^2+bt+c\) and \(y=pt^2+qt+r\), then \[ (Ax+By)^2+Cx+Dy+E=0 \] where \[\begin{aligned} A&=p\\ B&=-a\\ C&=qv_2-2pv_1\\ D&=-bv_2+2av_1\\ E&=v_1^2-v_2v_3 \end{aligned}\] with \(\langle v1, v2, v3\rangle =\langle a,b,c\rangle \times \langle p,q,r\rangle\); that is, the \(v_i\) values are the elements of the cross product of the vectors of the coefficients. In other…
Introduction It is (or should be) well known that a parabola has the cartesian form \[ (Ax+By)^2+Cx+Dy+E = 0. \] This looks as though there are five values needed, but we can divide through in such a way as to make any of the coefficients we like equal to 1: \[ (Px+Qy)^2+Rx+Sy+1 = 0. \] and so we see that only four values are needed to define a parabola. A parabola thus has one more degree of…
Although the method is simple to describe, the algebra becomes messy when written in full generality. For example, suppose we use the second method, with three points \((x_1,y_1)\), \((x_2,y_2)\), \((x_3,y_3)\) none of which are at the origin. The three equations are \begin{gather} (Ax_1+By_1)^2+Cx_1+Dy_1=0\\ (Ax_2+By_2)^2+Cx_2+Dy_2=0\\ (Ax_3+By_3)^2+Cx_3+Dy_3=0 \end{gather} Solving the first two…
A bicentric heptagon is one for which all vertices lie on a circle, and for which all edges are tangential to another circle. If \(R\) and \(r\) are the radii of the outer and inner circles respectively, and \(d\) is the distance between their centres, there is an expression which relates the three values when a bicentric heptagon can be formed. To start, define \[ a = \frac{1}{R+d},\quad b =…
Introduction Poncelet’s porism or Poncelet’s closure theorem is one of the most remarkable results in plane geometry. It is most easily described in terms of circles: suppose we have two circles \(C\) and \(D\), with \(D\) lying entirely inside \(C\). Pick a point \(p_0\) on \(C\), and find the tangent from \(p_0\) to \(D\). Let \(p_1\) be the other intersection of the tangent line at…
A totally different approach to dithering is error diffusion . Here, the image is scanned pixel by pixel. Each pixel is thresholded t0 1 or 0 depending on whether the pixel value is greater than 0.5 or not, and the error - the difference between the pixel value and its threshold - is diffuse across neighbouring pixels. The first method was developed by Floyd and Steinberg, who proposed the…
Image dithering , also known as half-toning , is a method for reducing the number of colours in an image, while at the same time trying to retain as much of its “look and feel” as possible. Originally this was required for newspaper printing, where no shades of grey were possible, and only black and white could be printed. So a light grey area would be printed as a few dots of black,…
In the previous post, we saw that a small change to the method of false position provided much faster convergence, while retaining its bracketing. This was the Illinois method which is only one of a whole host of similar methods, some of which converge even faster. And as a reminder, here’s its definition, with a very slight change: Given \(x_{i-1}\) and \(x_i\) that bracket a root and their…
Such a long time since a last post! Well, that’s academic life for you … If you look at pretty much any modern textbook on numerical methods, of which there are many, you’ll find that the following methods will be given for the solution of a single non-linear equation \(f(x)=0\): direct iteration, also known as fixed-point iteration bisection method method of false position,…
Carroll originally invented his Doublets in 1877, they were published in “Vanity Fair” (the magazine, not the Thackeray novel) in 1879. Some years later, in an 1892 letter, Carroll added another rule: that permutations were allowed. This allows very neat chains such as: roses, noses, notes, steno, stent, scent Because the words stay the same length here, but more connectivity is…
Apparently there’s a version of Doublets (see previous post) which allows you to add or delete a letter each turn. Thus we can go from WHEAT to BREAD as WHEAT, HEAT, HEAD, READ, BREAD which is shorter than the ladder given in that previous post. However, we can easily adjust the material from that post to implement this new version. There are two major differences: We have to use all the…
Lewis Carroll’s game of Doublets Such a long time since my last post! Well, that’s the working life for you. Anyway, recently I was reading about Lewis Carroll - always one of my favourite people - and was reminded of his word game “Doublets” in which one word is turned into another by changing one letter at a time, each new word being English. You can read Carroll’s…
Plagiarism, text matching, and academic integrity Every modern academic teacher is in thrall to giant text-matching systems such as Ouriginal or Turnitin . These systems are sold as “plagiarism detectors”, which they are not - they are text matching systems, and they generally work by providing a report showing how much of a student’s submitted work matches text from other…
What this post is about In the previous post we showed how to set up a simple interactive map using Python and its folium package. As the example, we used a Federal electorate situated within the city of Melbourne, Australia, and the various voting places, or polling places (also known as polling “booths”) associated with it. This post takes the map a little further, and we show how to…
Message about the underlying software NOTE: much of the material and discussion here uses the Python package 'folium', which is a front end to the Javascript package 'leaflet.js'. The lead developer of leaflet.js is Volodymyr Agafonkin , a Ukrainian up until recently living and working in Kyiv. Leaflet version 1.80 was released on April 18, “in the middle of war”, with “air raid…
In this post we look at two Divisions from the recent Federal election: the inner city seat of Melbourne , and the bayside seat of Macnamara . Up until the recent election, Melbourne was the only Division to have a Greens representative. Macnamara, previously known as “Melbourne Ports” has been a Labor stronghold for all of its existence. The near miss: Macnamara The contest in…
This continues on from the previous post, trying to make some sense of the voting in my electorate of Wills and the neighbouring electorate of Cooper . Both these electorates (or more formally “Divisions”), as I mentioned in the previous post, are very similar in their geography, demography, and history. Last post I simply showed a map of voting booths, using a circle roughly…
So the Australian federal election of 2022 is over as far as the public is concerned; all votes have been cast and now it’s a matter of waiting while the Australian Electoral Commission tallies the numbers, sorts all the preferences, and arrives at a result. Because of the complications of the voting system, and of all the checks and balances within it, a final complete result may not be…
This post illustrates the working of Ramanujan’s generating functions for solving Euler’s diophantine equation \(a^3+b^3=c^3+d^3\) as described by Andrews and Berndt in “Ramanujan’s Lost Notebook, Part IV”, pp 199 - 205 (Section 8.5). The text is available from Springer . Ramanujan’s result is that if \[ f_1(x) = \frac{1+53x+9x^2}{1-82x-82x^2+x^3} =…
Wordle is a pleasant game, basically Mastermind with words. You choose an English word (although it can also be played in other languages), and then you’re told if your letters are incorrect, correct but in the wrong place, or correct and in the right place. These are shown by the colours grey, yellow, and green. The genius is that you can share your result: the grid of coloured squares…
I was going to make a little post about Wordle , but I go sidetracked exploring five letter words. At the same time, I had a bit of fun with regular expressions and some simple scripting with ZSH . The start was to obtain lists of 5-letter words. One is available at the Stanford Graphbase site; the file sgb-words.txt contains “the 5757 five-letter words of English”. Others are…
What does one do on the first day of a new year but write a blog post, and in it clearly delineate all plans for the coming year? Well, I’m doing the first part, but not the second, as I know that any plans will not be fulfilled - something always gets in the way. You will notice a complete absence of posts last year after April. This was due to pressures both at work and outside, and left…
Steffensen’s method is based on Newton’s iteration for solving a non-linear equation \(f(x)=0\): \[ x\leftarrow x-\frac{f(x)}{f’(x)} \] Newton’s method can fail to work in a number of ways, but when it does work it displays qudratic convergence ; the number of correct signifcant figures roughly doubling at each step. However, it also has the disadvntage of needing to…
As is well known, tanh-sinh quadrature takes an integral \[ \int_{-1}^1f(x)dx \] and uses the substitution \[ x = g(t) = \tanh\left(\frac{\pi}{2}\sinh t\right) \] to transform the integral into \[ \int_{-\infty}^{\infty}f(g(t))g’(t)dt. \] The reason this works so well is that the derivative \(g’(t)\) dies away at a double exponentional rate ; that is, at the rate of \[ e^{-e^t} \] In…
An article by Bailey, Jeybalan and LI, “A comparison of three high-precision quadrature schemes”, and available online here , compares Gauss-Legendre quadrature, tanh-sinh quadrature, and a rule where the nodes and weights are given by the error function and its integrand respectively. However, Nick Trefethen of Oxford has shown experimentally that Clenshaw-Curtis quadrature is…
Note: This blog post is mainly computational, with a hint of proof-oriented mathematics here and there. For a more in-depth analysis, read the excellent article “Gauss, Landen, Ramanujan, the Arithmetic-Geometric Mean, Ellipses, pi, and the Ladies Diary” by Gert Akmkvist and Bruce Berndt, in The American Mathematical Monthly , vol 95 no. 7 (August-September 1988), pages 585-608, and…
In all the previous discussions of voting power, we have assumed that all winning coalitions are equally likely. But in practice that is not necessarily the case. Two or more voters may be opposed on so many issues that they would never vote the same way on any issues: such a pair of voters may be said to be quarrelling . To see how this may make a difference, consider the voting game \[ [51;…
As we have seen previously, it’s possible to compute power indices by means of polynomial generating functions. We shall extend previous examples to include the Deegan-Packel index, in a way somewhat different to that of Alonso-Meijide et al (see previous post for reference). Again, suppose we consider the voting game \[ [30;28,16,5,4,3,3] \] What we’ll do here though, rather than…
We have explored the Banzhaf and Shapley-Shubik power indices, which both consider the ways in which any voter can be pivotal, or critical, or necessary, to a winning coalition. A more recent power index, which takes a different approach, was defined by Deegan and Packel in 1976, and considers only minimal winning coalitions . A winning coalition \(S\) is minimal if every member of \(S\) is…
Recently I friend and I wrote a semi-serious paper called “The geometry of impossible objects” to be delivered at a mathematics technology conference. The reviewer was not hugely complimentary, saying that there was nothing new in the paper. Well, maybe not, but we had fun pulling together some information about impossible shapes and how to draw them. You can see some of our programs…
Introduction and recapitulation Recall from previous posts that we have considered two power indices for computing the power of a voter in a weighted system; that is, the ability of a voter to influence the outcome of a vote. Such systems occur when the voting body is made up of a number of “blocs”: these may be political parties, countries, states, or any other groupings of people,…
As we all know, American Presidential elections are done with a two-stage process: first the public votes, and then the Electoral College votes. It is the Electoral College that actually votes for the President; but they vote (in their respective states) in accordance with the plurality determined by the public vote. This unusual system was devised by the Founding Fathers as a compromise between…
Naive implementation of Banzhaf power indices As we saw in the previous post, computation of the power indices can become unwieldy as the number of voters increases. However, we can very simply write a program to compute the Banzhaf power indices simply by looping over all subsets of the weights: def banzhaf1 (q,w): n = len(w) inds = [ 0 ] * n P = [[]] # these next three lines creates the powerset…
After the 2020 American Presidential election, with the usual post-election analyses and (in this case) vast numbers of lawsuits, I started looking at the Electoral College, and trying to work out how it worked in terms of power. Although power is often conflated simply with the number of votes, that’s not necessarily the case. We consider power as the ability of any state to affect the…
Every four years (barring death or some other catastrophe), the USA goes through the periodic madness of a presidential election. Wild behaviour, inaccuracies, mud-slinging from both sides have been central since George Washington’s second term. And the entire business of voting is muddied by the Electoral College, the 538 members of which do the actual voting: the public, in their own…
The rational numbers are well known to be countable, and one standard method of counting them is to put the positive rationals into an infinite matrix \(M=m_{ij}\), where \(m_{ij}=i/j\) so that you end up with something that looks like this: \[ \left[\begin{array}{ccccc} \frac{1}{1}&\frac{1}{2}&\frac{1}{3}&\frac{1}{4}&\dots\\\[1ex] \frac{2}{1}&\frac{2}{2}&\frac{2}{3}&\frac{2}{4}&\dots\\\[1ex]…
A few posts ago I showed how to do this in Python. Now it’s Julia’s turn. The data is the same: spread of influenza in a British boarding school with a population of 762. This was reported in the British Medical Journal on March 4, 1978, and you can read the original short article here . As before we use the SIR model , with equations \begin{aligned} \frac{dS}{dt}&=-\frac{\beta…
The purpose of this post will be to see if we can implement the algorithm in Julia, and thus leverage Julia’s very fast execution time. We are working with polynomials defined on nilpotent variables, which means that the degree of any generator in a polynomial term will be 0 or 1. Assume that our generators are indexed from zero: \(x_0,x_1,\ldots,x_{n-1}\), then any term in a polynomial will…
Introduction We know that there is no general sub-exponential algorithm for computing the permanent of a square matrix. But we may very reasonably ask – might there be a faster, possibly even polynomial-time algorithm, for some specific classes of matrices? For example, a sparse matrix will have most terms of the permanent zero – can this be somehow leveraged for a better algorithm?…
As a first blog post for 2020, I’m dusting off one from my previous blog, which I’ve edited only slightly. I’ve been looking up at the sky at night recently, and thinking about the sizes of things. Now it’s all very well to say something is for example a million kilometres away; that’s just a number, and as far as the real numbers go, a pretty small one (all finite…
As I discussed in my last blog post, the permanent of an \(n\times n\) matrix \(M=m_{ij}\) is defined as \[ \text{per}(M)=\sum_{\sigma\in S_n}\prod_{i=1}^nm_{i,\sigma(i)} \] where the sum is taken over all permutations of the \(n\) numbers \(1,2,\ldots,n\). It differs from the better known determinant in having no sign changes. For example: \[\text{per} \begin{bmatrix} a&b&c\\ d&e&f\\ g&h&i…
Introduction Python is of course one of the world’s currently most popular languages, and there are plenty of statistics to show it. Of all languages in current use, Python is one of the oldest (in the very quick time-scale of programming languages) dating from 1990 - only C and its variants are older. However, it seems to keep its eternal youth by being re-invented, and by its constantly…