Archive for algebra

Le Monde puzzle [#960]

Posted in Kids, R with tags , , , , , on April 28, 2016 by xi'an

An arithmetic Le Monde mathematical puzzle:

Given an integer k>1, consider the sequence defined by F(1)=1+1 mod k, F²(1)=F(1)+2 mod k, F³(1)=F²(1)+3 mod k, &tc. [With this notation, F is not necessarily a function.] For which value of k is the sequence the entire {0,1,…,k-1} set?

This leads to an easy brute force resolution, for instance writing the R function

crkl<-function(k) return(unique(cumsum(1:(2*k))%%k))

where 2k is a sufficient substitute for ∞. Then the cases where the successive images of 1 visit the entire set {0,1,…,k-1} are given by

> for (i in 2:550) if (length(crkl(i))==i) print(i)
[1] 2
[1] 4
[1] 8
[1] 16
[1] 32
[1] 64
[1] 128
[1] 256
[1] 512

which suspiciously looks like the result that only the powers of 2 k=2,2²,2³,… lead to a complete exploration of the set {0,1,…,k-1}. Checking a few series in the plane back from Warwick, I quickly found that when k is odd, (1) the sequence is of period k and (2) there is symmetry in the sequence, which means it only takes (k-1)/2 values. For k even, there is a more complicated symmetry, with the sequence being of period 2k, symmetric around its two middle values, and taking the values 1,2,..,1+k(2k+1)/4,..,1+k(k+1)/2. Those values cannot cover the set {0,1,…,k-1} if two are equal, which means an i(i+1)/2 congruent to zero modulo k, hence equal to k. This is clearly impossible when k is a power of 2 because i and i+1 cannot both divide a power of 2. I waited for the published solution as of yesterday’s and the complete argument was to show that when N=2p, the corresponding sequence [for N] is made (modulo p) of the sequence for p plus the same sequence translated by p. The one for N is complete only if the one for p is complete, which by recursion eliminates all cases but the powers of 2…

statistics in Le Monde

Posted in Books, Kids, Statistics, University life with tags , , , , , , , on April 28, 2013 by xi'an

In the current weekend edition of Le Monde, science leaflet (soon to disappear from the weekend edition alas!, Pierre Barthélémy wrote his tribune on a (not that recent) PLoS paper on roadkills that seems to use capture-recapture (or should) to evaluate the real number of roadkills from their disappearance rate. And Cédric Villani muses in his carte blanche on the relevance of mathematical models in social sciences, using the recent blunder by Reinhart and Rogoff as an argument: this sounds for the least extreme as there are many counter-examples in political sciences, sociology, psychology, &tc. I think he is missing the point that, while all models are wrong (in the sense physical models can be “right”), there are some models that can prove useful. A last item of interest (?) was the announcement of the new volume in the maths popularisation series, which is dedicated to the fourth dimension. I hope they also deal with higher dimensions, otherwise it could get quickly boring! It reminded me of the textbook I had to teach from the semester I taught basic vector space algebra in Cornell: the chapter on dimension 2 got followed by one on dimension 3, then one on dimension 4…

five years in Edinburgh

Posted in Kids, Mountains, Travel, University life with tags , , , , , , , on April 12, 2013 by xi'an

Duddingston Loch, Holyrood Park, Edinburgh, September 6, 2011Got an email with this tantalizing offer of a five year postdoctoral position in mathematics at the University of Edinburgh:

Chancellor's Fellowship (five positions) [tenure-track posts at Lecturer or Reader

Applications are invited for up to five Chancellor's Fellowship posts in
Mathematics. Each Fellowship provides a research-focused reduced-teaching position
for up to 5 years, followed immediately by a standard open-ended (ie "tenured")
lectureship or readership post.

Applicants should have research interests in any area of:

Applied and Computational Mathematics
Financial Mathematics
Mathematical Physics
Operational Research
Pure Mathematics

One of the positions will be specifically dedicated to algebra (Representation
Theory, very broadly conceived).

Applicants will have a research record of the highest calibre, exhibiting the
potential to become an international leader. We welcome candidates whose interests
may also reach out to other disciplines.

Appointment will normally be made on the Lecturer scale, £37,382 - £44,607.
Dependent on experience, and in exceptional circumstances, appointment may be to
Senior Lecturer/Reader level for which the salary scale is £47,314 - £53,233.

Interviews will be held during May 2013. Applications containing a detailed CV and
an outline of a proposed research programme should be made online

tak1ng sudoku ser1ously

Posted in Books, Statistics, University life with tags , , , , , on March 14, 2013 by xi'an

“There is something deeply satisfying in encountering opacity.” (p.9)

I think it was last summer at the Australasian Statistics conference in Adelaide that I saw this book by Jason Rosenhouse and Laura Taalman, Taking Sudoku seriously: The math behind the World’s most popular pencil puzzle. (Or was it in Kyoto at the ISBA meeting?!) In any case, I mentioned my long-term interest in this puzzle (as readers of the ‘Og will undoubtedly have noticed!) and proposed to write a review for Chance. A few weeks later the book arrived at home. Which was a mistake as my wife who is a much deeper Sudoku fanatic than I stole the book with a vague promise to write the review! It is only a few weeks ago that I was able to truly get the book (if not the review) back…

“This is surely the most trivial of pursuits.” (p.4)

In case you never tried to solve a Sudoku puzzle, open your favourite newspaper, news website or phone, and you should immediately find one of those 9×9 squares to fill with integers between 1 and 9, under three sets of constraints: row-wise, column-wise, and block-wise. (The book describes all kinds of variations with no particularly added value.) Depending on the number of integers already present on the grid and on their location, the resolution of the puzzle gets from obvious to close to impossible by hand. This range in the difficulty and the resulting challenges may explain for the popularity of the method, although it remains a mystery to many bystanders. There are many strategies for solving Sudokus, from the (Sherlock Holmes) elimination of obviously impossible values to branching processes carrying guesses until a binary conclusion. The book covers some of those: forced cells, twins, X-wings, and Ariadne’s thread (moving from Star Wars to The Lord of the Ring!). It however does not bring any novel technique to solve Sudokus, at least at the pencil level, so potential readers with this intent in mind should abstain!

“Sudoku is math in the small.” (p.171)

Now many may wonder about the connections between Sudokus and mathematics. Some mathematicians are clearly sceptical. For instance, I remember discussing solving Sudoku grids in the métro with a friend and Mathematics colleague from Paris-Dauphine and she was quite surprised by this fascination, as she did not see any mathematical appeal in the exercise. In my eyes, this is a logical puzzle at the very least (there is one way of setting all the entries and some obligatory paths for filling the grid that have to be exposed), which makes Sudoku vaguely mathematical. I am also attracted by the automated resolution of those puzzles, as shown by my simulated annealing attempt a (long) while ago, even though I am aware that the state-of-the-art codes are beyond my reach. (They are not detailed either in the book.) Reading this book actually made me think of potential alternatives for simulating annealing, from using additional integers during relaxation, to solving a set of algebraic equations under relaxed constraints. (I wonder if Gröbner bases are used by the fastest resolution codes.)

“We are unaware of any result about Sudoku puzzles provable using the techniques of graph-coloring that could not have been arrived at more easily by other means.” (p.133)

Taking Sudoku Seriously does exhibit some of those connections, it may however feel contrived for some readers (and unintelligible to others), as the mathematical objects have an existence of their own and do not appear to directly contribute to the resolution of the puzzle. An exception in the first case is the one of Latin and Greco-Latin squares in Chapters 2 and 4, which are Sudokus of sort, while an exception to the second is the mention of Gröbner bases in Chapter 8 for solving sets of algebraic equations providing the solution to Sudokus in the form of complex roots of unity. Some number theory gets introduced along the way, as well as algebra (permutation and symmetry groups, polynomials) and graph theory. Analysis is rather absent from this volume and so is probability (hence simulated annealing). Except for a rather artificial and unrelated entry about Newton’s cannonball and Archimede’s derivation of the area of a circle in Chapter 7.

“We have a number of different audiences in mind.” (p.xi)

A few days prior to finish reading the book, I received my copy of Significance with a review of Taking Sudoku Seriously by Nicola Tilt. Glancing quickly at it, I read she was wondering about the intended audience for the book, which also is an issue with me. Neophytes and mathematicians alike will learn little about maths from reading the book, since the difficult questions (like counting the number of Sudokus and of non-equivalent Sudokus, or creating Sudokus) are not answered. The most interesting input is, in my opinion, the discussion of computer-based mathematical proofs. From the four-colour theorem to counting the number of Sudokus, to counting the number of fundamentally different Sudoku squares [as 5,472,730,538]. Unfortunately, the book publication date (April 2011) means that it missed the “big news”, namely the resolution of what the authors call “The rock star problem”, which is the determination of “the minimum number of starting clues possible in a Sudoku puzzle with a unique solution” (p.164). On Jan. 1, 2012, Gary McGuire, Bastian Tugemann, and Gilles Civario from University College Dublin used a mix of mathematics and computer power to prove that the minimum is indeed 17, as posited by the authors. (A result to feature prominently in the revised edition, if any!)

“We are curious for a living.” (p.191)

To conclude, and to be fair with the authors, the book reads nicely (on high quality glossy paper), once you limit your expectations to see some links between maths and Sudokus, it offers a lot of Sudokus and related puzzles, with solutions at the back of the book, and, above all, it teaches to some degree mathematical reasoning by running complete arguments on 4×4 Shidokus and extrapolating the results to the 9×9 Sudokus (or not, as in the case of polynomials where the extrapolation does not work, Section 8.2). Worth perusing on your way to work, trying to complete the puzzle at hand before the next stop!

As a postultimate remark, a paper by Hiroshi Watanabe from the University of Tokyo was arXived a few days ago: it contains further links about the mathematical properties of Sudokus, incl. one with a nine-state Potts model, but mostly a simulated annealing algorithm to find a “difficult” Sudoku. Contrary to my early attempt, this algorithm explores the space of all Sudoku puzzles, thus moves from one Sudoku to another at each iteration (“with the Metropolis criterion with the Boltzmann weight”, I wonder why Boltzmann?!).The hardest sudoku found by this method is represented below: it has a depth of 10 and would require 50,000 backtracking attempts to solve! Just “impossible to solve by hand”. (It took the equivalent of 11 cpu-core-years to create it.) As pointed out to me by Anthony Leverrier, from INRIA, the author added in the second version of his arXiv preprint that the puzzle can be easily solved by hand… So you may give it a try.

The hardest Sudoku ever, by H. Watanabe

Numerical analysis for statisticians

Posted in Books, R, Statistics, University life with tags , , , , , , , , , on August 26, 2011 by xi'an

“In the end, it really is just a matter of choosing the relevant parts of mathematics and ignoring the rest. Of course, the hard part is deciding what is irrelevant.”

Somehow, I had missed the first edition of this book and thus I started reading it this afternoon with a newcomer’s eyes (obviously, I will not comment on the differences with the first edition, sketched by the author in the Preface). Past the initial surprise of discovering it was a mathematics book rather than an algorithmic book, I became engrossed into my reading and could not let it go! Numerical Analysis for Statisticians, by Kenneth Lange, is a wonderful book. It provides most of the necessary background in calculus and some algebra to conduct rigorous numerical analyses of statistical problems. This includes expansions, eigen-analysis, optimisation, integration, approximation theory, and simulation, in less than 600 pages. It may be due to the fact that I was reading the book in my garden, with the background noise of the wind in tree leaves, but I cannot find any solid fact to grumble about! Not even about  the MCMC chapters! I simply enjoyed Numerical Analysis for Statisticians from beginning till end.

“Many fine textbooks (…) are hardly substitutes for a theoretical treatment emphasizing mathematical motivations and derivations. However, students do need exposure to real computing and thoughtful numerical exercises. Mastery of theory is enhanced by the nitty gritty of coding.” 

From the above, it may sound as if Numerical Analysis for Statisticians does not fulfill its purpose and is too much of a mathematical book. Be assured this is not the case: the contents are firmly grounded in calculus (analysis) but the (numerical) algorithms are only one code away. An illustration (among many) is found in Section 8.4: Finding a Single Eigenvalue, where Kenneth Lange shows how the Raleigh quotient algorithm of the previous section can be exploited to this aim, when supplemented with a good initial guess based on Gerschgorin’s circle theorem. This is brilliantly executed in two pages and the code is just one keyboard away. The EM algorithm is immersed into a larger M[&]M perspective. Problems are numerous and mostly of high standards, meaning one (including me) has to sit and think about them. References are kept to a minimum, they are mostly (highly recommended) books, plus a few papers primarily exploited in the problem sections. (When reading the Preface, I found that “John Kimmel, [his] long suffering editor, exhibited extraordinary patience in encouraging [him] to get on with this project”. The quality of Numerical Analysis for Statisticians is also a testimony to John’s editorial acumen!)

“Every advance in computer architecture and software tempts statisticians to tackle numerically harder problems. To do so intelligently requires a good working knowledge of numerical analysis. This book equips students to craft their own software and to understand the advantages and disadvantages of different numerical methods. Issues of numerical stability, accurate approximation, computational complexity, and mathematical modeling share the limelight in a broad yet rigorous overview of those parts of numerical analysis most relevant to statisticians.”

While I am reacting so enthusiastically to the book (imagine, there is even a full chapter on continued fractions!), it may be that my French math background is biasing my evaluation and that graduate students over the World would find the book too hard. However, I do not think so: the style of Numerical Analysis for Statisticians is very fluid and the rigorous mathematics are mostly at the level of undergraduate calculus. The more advanced topics like wavelets, Fourier transforms and Hilbert spaces are very well-introduced and do not require prerequisites in complex calculus or functional analysis. (Although I take no joy in this, even measure theory does not appear to be a prerequisite!) On the other hand, there is a prerequisite for a good background in statistics. This book will clearly involve a lot of work from the reader, but the respect shown by Kenneth Lange to those readers will sufficiently motivate them to keep them going till assimilation of those essential notions. Numerical Analysis for Statisticians is also recommended for more senior researchers and not only for building one or two courses on the bases of statistical computing. It contains most of the math bases that we need, even if we do not know we need them! Truly an essential book.


Get every new post delivered to your Inbox.

Join 1,022 other followers