{\huge Mathematical Mischief and Skolem's Golem}
\vspace{.2in} Real implications from a fake-paper prank?
\includegraphics[width=2in]{TuringHeadArrow.png}
Marcie Rathke was not among the speakers whose talks I heard at the Algorithms Workshop at St. John's College, Oxford University, two weeks ago. She is ``famous'' for her recent paper, ``Independent, Negative, Canonically Turing Arrows of Equations and Problems in Applied Formal PDE,'' which was just accepted by the journal Advances in Pure Mathematics. Her paper could have been presented at the Oxford workshop since solving PDE's is an important algorithmic task, Oxford is known for formal approaches, and the workshop was part of Oxford's commemoration of the Turing Centennial. But it was not.
Today, October 30th, the eve of Halloween, is often called ``Mischief Night.'' It is a night when many children play tricks before they receive their treats on the next night---Halloween. Thus today is a good time to think about tricks and possible treats in the world of mathematics and theory.
Mischief Night And Math Mischief
Ken has strong ties to Oxford, and was excited to discover that Mischief Night connects to St. John's College where I just was. The earliest reference given by Wikipedia traces it to the college---in 1790. This is a story related by the college fellows about a headmaster supporting a school play that included ``an Ode to Fun which praises children's tricks on Mischief Night in most approving terms.'' Whether the college today would have approved staging a talk by ``Marcie Rathke'' is debatable, because her paper is entirely fake. It is a ``trick'' not a ``treat''. The paper is a fake, a fraud, and complete nonsense---is there incomplete nonsense?
The paper was generated by Mathgen, a web applet that creates papers in a ``structuredly random'' fashion.
Ken and I are disappointed, as the topic of ``Turing Arrows'' sounds cool and important. Surely there is room for a creative genius---a human genius---to conceptualize and develop it. Arrows suggest relational order theories of the kind proposed by the cosmologist Lee Smolin, which are a system of ``knots and networks [such that] the geometry of space arises out of [a] fundamental quantum level which is made up of an interwoven network [of] processes.'' Per theories by fellow cosmologist Max Tegmark, those processes would be Turing-computable. This would align the Turing Arrows programme with Alan Sokal's pioneering work on transformative approaches to quantum gravity.
SCIgen and Real Gen?
Mathgen is an offshoot of SCIgen, which calls itself ``An Automatic CS Paper Generator.'' The program was written and is maintained by MIT graduate students Jeremy Stribling, Max Krohn, and Dan Aguayo. Their program aims to maximize amusement, rather than coherence. The applet is easy to use: just enter some author names---yours or others'---and click go. Ken did this with our names, and to quote Queen Victoria, We are not amused. Or rather, we are bemused, because what we got looks suspiciously good. Here are the title and abstract of the auto-generated paper:
\includegraphics[width=3.5in]{LiptonReganMathGenAbstract.png}
Both of us have done real research related to constructive number theory, and we have talked about Ryan and Virginia Williams' approach to matrix product using triangles. Notably, Ken and I just recently wrote a post on polytope approaches to factoring which of course relates to the Sieve of Eratosthenes.
So we wonder, does Mathgen read Gödel's Lost Letter? More to the point, could we soon build a program that devours mathematical texts the way Google Translate does with massive data? We have blogged before about how far the methodology of IBM's ``Watson'' might be adapted to do mathematics. We see some easy improvements the SCIgen people can make, such as assuring that quantities are defined or at least introduced before they are used. With the same level of research input as Watson, how scary-plausible could Mathgen become?
Skolem and Golem
The logician Thoralf Skolem lent his name to ``Skolemization'', which remains an essential process in automated theorem proving today. He also developed primitive recursive arithmetic, and his Wikipedia bio goes so far as to say that if his work is interpreted with a certain hindsight,
``Skolem can be seen as an unwitting pioneer of theoretical computer science.''
All of this raises the spectre of the ``golemization'' of mathematics. The Golem is an ``an animated anthropomorphic being, created entirely from inanimate matter.'' Kurt Gödel supposedly killed off David Hilbert's programme to automate mathematics, but in later life he was not so sure. A project at Oxford titled ALEPH for ``A Learning Engine for Proposing Hypotheses'' draws from the Golem story.
I have been thinking more about Skolem's Problem from the wonderful talk by Joël Ouaknine, and have shared some further thoughts with him about solutions in special cases. Now I wonder, can we automate the creation of an exhaustive list of special cases that can be researched by computer, at least in the manner of PolyMath?
Skolem Cases
We are working on the general Skolem problem and have made some progress. For example, we believe we can handle some special cases---more in the near future.
Define the class of numbers $latex {N_c}&fg=000000$ to be those positive numbers $latex {n}&fg=000000$ of the form $latex {n=p^k \ell }&fg=000000$ where $latex {p}&fg=000000$ is a prime and both $latex {k}&fg=000000$ and $latex {\ell}&fg=000000$ are less than $latex {c}&fg=000000$. Possibly we can allow $latex {c}&fg=000000$ to grow slowly with $latex {n}&fg=000000$, not just be fixed.
Theorem 1 Let $latex {\lambda_1,\dots,\lambda_m}&fg=000000$ be algebraic numbers, let $latex {c>0}&fg=000000$, and let $latex {q_1(n),\dots,q_m(n)}&fg=000000$ be polynomials in $latex {n}&fg=000000$ with integer coefficients. Then we can decide whether or not there is an $latex {n}&fg=000000$ so that$latex \displaystyle \sum_{k=1}^{m} q_k(n) \lambda_{m}^{n} = 0 &fg=000000$
for $latex {n}&fg=000000$ in $latex {N_c}&fg=000000$.
We will discuss this and more soon. The proofs use properties in algebraic number theory that are computational. We hope it will be a real treat and not a trick.
Open Problems
Can we solve more cases of Skolem's Problem? Can we automate them? Are we any closer to a mathematical ``Golem,'' at least for Skolem?
Incidentally, talks at the workshop are now online, and ditto talks from the Princeton Turing Centennial Celebration, which we covered last May.
Finally, happy Halloween and enjoy your treats.