We were very sorry to hear of the death, at the age of 78, of architect Rafael Viñoly. Among Rafael's vast portfolio of work is our own Andrew Wiles Building which opened almost ten years ago in October 2013 and which has been an integral part of our work in making mathematics accessible and enjoyable for our faculty, researchers, students, support staff and the wider general public.
19:30
The Villiers Quartet at the Mathematical Institute - Late Beethoven Series III
We are delighted to welcome the Villiers Quartet back to Oxford Mathematics on May 27th 2023 when they continue their 'Late Beethoven' series with three works:
Benjamin Britten - Three Divertimenti
Alexander Goehr - Quartet No. 5 "Vision of the Soldier, Er"
Interval
Ludwig van Beethoven - Quartet Op. 130
May 27th, 7.30pm. Tickets £20 and £5 student concession
There will be a pre-concert talk 6:45pm from Dr. Peter Copley who will outline the musical impetus behind the Op.130, one of Beethoven's most personal works.
17:00
A strong version of Cobham's theorem
Abstract
Let $k,l>1$ be two multiplicatively independent integers. A subset $X$ of $\mathbb{N}^n$ is $k$-recognizable if the set of $k$-ary representations of $X$ is recognized by some finite automaton. Cobham's famous theorem states that a subset of the natural numbers is both $k$-recognizable and $l$-recognizable if and only if it is Presburger-definable (or equivalently: semilinear). We show the following strengthening. Let $X$ be $k$-recognizable, let $Y$ be $l$-recognizable such that both $X$ and $Y$ are not Presburger-definable. Then the first-order logical theory of $(\mathbb{N},+,X,Y)$ is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of $(\mathbb{N},+,X)$ is decidable. Our work strengthens and depends on earlier work of Villemaire and Bès. The essence of Cobham's theorem is that recognizability depends strongly on the choice of the base $k$. Our results strengthens this: two non-Presburger definable sets that are recognizable in multiplicatively independent bases, are not only distinct, but together computationally intractable over Presburger arithmetic. This is joint work with Christian Schulz.