Powers With Repetitions

What's so cool about 57459558593³ expressed in base 12400?

And why is something like that really rare?

For the answer, you'll have to read my latest paper, co-written with Andrew Bridy, Robert J. Lemke Oliver, and Arlo Shallit.

Using a Decision Method to Prove a New Theorem in Number Theory

The mathematician David Hilbert had a dream, a dream to mechanize mathematics. He hoped that every true mathematical result had a formal proof, and furthermore, that this formal proof would be discoverable by algorithmic methods. All you would have to do is state your theorem in some formal mathematical language, perform the algorithm, and voila! You would have a proof or disproof.

But Hilbert's dream was killed by Kurt Gödel and Alan Turing in the early 20th century. Gödel showed that, given any sufficiently powerful axiom system (roughly speaking, it's enough to be able to define addition and multiplication of integers), there would be true results lacking any formal proof. And Turing showed that, even if we restrict ourselves to provable results, there is no algorithm that, given a mathematical statement, will always halt and correctly report "provable" or "unprovable".

Nevertheless, there are some logical theories in which (a) every well-formed statement is provable or disprovable and (b) there is, in fact, an algorithm to find a proof or disproof. Such a theory is sometimes called decidable and the corresponding algorithm is called a prover. The first-order theory of the natural numbers with addition, often called Presburger arithmetic, is one such theory; it has a prover. Unfortunately, Presburger arithmetic is not very powerful, and although it has some practical applications, I am not aware of a single significant mathematical theorem proved using a Presburger prover.

However, when Presburger arithmetic is augmented with a certain additional function on natural numbers called V_k, for a fixed integer k ≥ 2, it remains decidable. And now it is powerful enough to prove things people really want to prove! My former master's student, Hamoon Mousavi, wrote a prover called Walnut for this bigger theory, and with it we have proven many new theorems of genuine mathematical interest. And we also reproved many results in the literature for which the only proofs previously known were long, tedious, and case-based.

Recently, my co-authors Aayush Rajasekaran and Tim Smith used a different method to algorithmically prove a new result in number theory. It concerns palindromes, which are numbers that, when considered as a string of digits in some integer base b ≥ 2, read the same forward and backwards. For example, the number 717 is a palindrome in base 10, but it is also a palindrome in base 2, since in binary it is 1011001101.

Last year, the number theorist William D. Banks started studying the additive number theory of palindromes. He proved that every natural number is the sum of at most 49 decimal palindromes. More recently, this result was improved by Florian Luca, Lewis Baxter, and the late Javier Cilleruelo, who proved that every natural number is the sum of at most 3 palindromes in base b, for all b ≥ 5. However, it seems that so far, nobody proved any bound at all for bases b = 2, 3, 4.

Here is our result: every natural number is the sum of at most 9 binary palindromes. The bound "9" is probably not the best possible result, as empirical results suggest the best possible bound is probably 4. Probably somebody will improve our bound soon! What makes our result interesting, though, is how we did it. Instead of the heavily case-based approach of Banks and Cilleruelo-Luca-Baxter, we used a decision method: we recoded the problem as a formal language theory problem, and then used the fact that this formalism has a decidable logical theory associated with it. Then we used publicly-available software to prove our result.

Here are the details: we created a certain kind of automaton, called a nondeterministic nested-word automaton, that takes integers n, represented in base 2, as input. Given an input representing an integer n, our automaton "guesses" a possible representation as a sum of palindromes, and then "verifies" that its guess is correct. Here the "verifies" means checking that the summands are indeed palindromes (read the same forwards and backwards) and that they sum to n. If the guess succeeds, the automaton accepts the input. Then the "sum of palindromes" theorem we want to prove amounts to claiming that the automaton accepts every possible natural number as input.

Luckily for us, the so-called "universality problem" (does a given automaton accept every input?) is actually decidable for nested word automata, a result proved by Alur and Madhusudan. We used the ULTIMATE automata library to then check the universality of the automaton we created. For more details, see our preprint.

Could other theorems in number theory be proved using this method? Yes, we proved a few more in our preprint. The holy grail would be a decidable logical theory strong enough to express traditional theorems about primes. If such a theory existed, we could, at least in theory, prove statements like Goldbach's conjecture (every even number > 2 is the sum of two primes) purely mechanically, by expressing them in the proper formalism and then running a prover. But currently we do not even know whether Presburger arithmetic, together with a predicate for primality, is decidable.

What's next? Well, a lot! But that will be the subject of Aayush's master's thesis, so you'll have to wait to find out.

Bloom's Bizarro World

It's always entertaining to visit Bizarro World, a place where a mediocrity like C. S. Lewis is revered as a deep thinker, where "natural law" is viewed as a serious philosophical and legal theory, and where a 3rd rate college like Hillsdale is spoken of with reverence.

In today's visit, let us read this piece by one Nathan Schlueter, an academic so forgettable that I have already forgotten how to spell his last name. Prof. Schlueter is under the delusion that Allan Bloom's The Closing of the American Mind is not only an important book, it's so important that 30 years after its publication, it merits an entire symposium.

I read The Closing of the American Mind back in 2000, after someone recommended it to me. It was, to put it simply, a disaster. Bloom was a professor at the University of Chicago; we overlapped teaching there for a few years. At the time, focused on my own research, my only knowledge of him was the unflattering stories about him that I had heard from students.

It was apparent from nearly the first page of Closing that Bloom was a deeply troubled individual. His book, ostensibly a critique of higher education, was so clearly a rant based on Bloom's own intellectual and sexual insecurities that I found it almost painful to read. I wrote the following review for amazon back then, and here it is again, cleaned up a little:

This is not just a bad book. It is a sick one.

Bloom's obsessions are clear on almost every page: sex and rock music. Although clothed in a pretentious philosophical language, his objections betray what's really on his mind: he feels left out. The sexual revolution of the Sixties passed him by, and like the child whose playmates decide he's not good enough to get into the game, he retaliates by labelling everything about his opponents evil.

The poet Philip Larkin had Bloom's number when he wrote in his poem, Annus Mirabilis:

Sexual intercourse began
In nineteen sixty-three
(which was rather late for me)-
Between the end of the "Chatterley" ban
And the Beatles' first LP.

Like many neo-conservatives, Bloom doesn't really understand the principle of free speech. He says it "has given way to freedom of expression, in which the obscene gesture enjoys the same protected status as demonstrative discourse." In other words, freedom of speech should only apply to the stuff that Bloom approves of. (He also doesn't apparently know that the Canadian constitution guarantees "freedom of expression", precisely to avoid arbitrary Bloom-style distinctions.)

Like many professors in the humanities, he is deeply distrustful of science. And so he continues to push thinkers like Plato as essential to understanding the world, displaying no comprehension of the intellectual revolution brought by, for example, Charles Darwin. Is it still fruitful to read the Greeks? Certainly. But to pretend that we have learned nothing in 2000 years, that the insights of science play no part in an informed understanding of the world, is to play the part of the small child who insists, contrary to all evidence, that there is really is a Santa Claus.

Ultimately, this books tells us not about the mind of Americans, but rather the small, sanctimonious, and quite closed mind of one university professor named Allan Bloom.

It is no surprise at all that this Bloom Symposium is being published by Robert George's Witherspoon Institute, the very same place that funded and guided the Regnerus study on gay parents, a laughable piece of scholarship that just so happened to confirm Robert George's own negative view of homosexuality.

These folks have very closed minds, and their natural habitat is a setting where their prejudices can be confirmed and clothed in academic respectability.

I Am The Yeggman

Recently I was reminded about an unfamiliar word that plays a part in my family history: "yegg".

According to the OED, a "yegg" is a burglar or safe-breaker, and its etymology is given as "Said to be the surname of a certain American burglar and safe-breaker."

The earliest citations given in the OED are

1903 N.Y. Evening Post 23 June (Cent. D. Supp.), The prompt breaking up of the organized gangs of professional beggars and yeggs.

1905 N.Y. Times 2 Jan. (Cent. Dict. Suppl.), Detective Sergeants..captured on the Bowery three men who, they say, are among the most successful ‘yeggmen’, or safe~crackers, in the business.

A related word is "yeggman":

1906 A. Stringer Wire Tappers 100 ‘Now, nitro-glycerine I object to, it's so abominably crude.’.. ‘And so odiously criminal!’ she interpolated. ‘Precisely. We're not exactly yeggmen yet.’

However, using a newspaper database, I found several earlier citations:

Minneapolis Star-Tribune, November 25 1899, p. 12: ...for Mr. Alness did not know until the detectives told him that "John Yegg & Co." is a bit of thieves' slang, "yegg" standing for one who is ready to beg or steal, stealing preferred as more honorable...

Bloomington, IL Pantagraph, December 28 1899, p. 3: The gang ... numbers at least twenty-five members, who call themselves Yeggmen.

New York Sun, January 22 1900, p. 2: Four crooks, whom the Pinkerton agents describe as hobo safe burglars belonging to a new fraternity known as "Yeggs," were arrested in Newark last Thursday night...

The uncommon words "yegg", "yeggs", "yeggman", "yeggmen" reached the zenith of their popularity around 1920-1935 and are only rarely used today. Here is a google ngram search:

Uncommon Descent Lies Again

The blog Uncommon Descent is, of course, one of the two main propaganda arms of the intelligent design movement --- the other one being "Evolution News". Since the ID movement is essentially based on religious dogma and deception, it's no surprise that these blogs have a large amount of fake content. But I am always surprised at how shamelessly they mislead.

One of the recent entries at Uncommon Descent is a good example. They refer to a 1980 article of Hamming entitled "The Unreasonable Effectiveness of Mathematics". It's not hard for anyone to verify that what I just wrote is the correct title of Hamming's article; indeed, the full text of the article is easily available online.

I am not going to criticize Hamming's article in much detail here. There is much that is good in it, but I feel his final conclusion is unmerited. On what rigorous basis can we measure how effective mathematics is, and on what basis are we allowed to conclude that the effectiveness we observe is "unreasonable"? It seems purely a matter of personal taste.

My own personal taste is that mathematics is remarkably ineffective, because the vast majority of events that we see in the physical world are quite difficult to model accurately. If we release a single tritium atom in a lecture hall at 10:00 AM, where will it be at 11:00 AM? No physicist in the world can tell you with very much precision.

Similarly, Hamming asks, "How can it be that simple mathematics, being after all a product of the human mind, can be so remarkably useful in so many widely different situations?" Well, lots of mathematics is not remarkably useful. Much of what I personally do has little real-life application. So how can we measure, in a precise way, when that usefulness is "remarkable" and when it is not? Hamming does not tell us. My own personal view is that humans tend to use what is effective and discard what is not. If, for example, dancing were more effective in describing the physical world, scientists would be ballerinas.

In any event, Hamming's observations are not my main point. My main point is that, at Uncommon Descent the title of Hamming's article has been altered from "The Unreasonable Effectiveness of Mathematics" to "The Unreasonable Effectiveness of Mathematics vs. Evolution". Whether this change is a matter of deliberate deception or pure incompetence, I am not certain. But it is part of a larger pattern that we see repeated.

Bad Mathematics on Π Day

Every March 14 you can expect a flood of stories about the famous number π = 3.14159... . And you can also expect that most of them are bad, written by people who know very little mathematics and don't bother to get their facts checked by a mathematician.

Here's an example: the writer, Tia Ghose, says that π is "an infinitely long, nonrepeating number". Later she says "Because pi is an infinite number...".

This is not correct. More than that, it illustrates a very, very common misunderstanding: confusing a real number with its representation in some base.

Real numbers do not have "lengths" and are not "infinitely long". π is not an "infinite number". (All real numbers are finite.) Instead, one could speak about the base-10 representation of a number (or, more generally, about the base-k representation of the number for some integer k ≥ 2). This representation is "infinitely long", but so is the representation of every real number! For example the base-10 representation of 1/3 is 0.3333.... and the base-10 representation of 1/2 is 0.5000.... . The thing that makes π different from these examples is not that π's representation is "infinitely long", but rather that it is not ultimately periodic. "Ultimate periodicity" means that, after some point, the representation consists of a single block of digits that repeats forever, so the representation looks like x.uvvvvvv.... for some blocks x, u, v.

That's what the author apparently means by "nonrepeating", but "nonrepeating" is such a vague term that it should be avoided. Some kinds of repetitions are inevitable in the base-10 representation of any number. For example, in the base-10 representation of π we quickly find the repetitions "33" and "88" and "99". The first group of three consecutive identical digits to appear is 111; the first group of four consecutive identical digits to appear is 9999. At the same position we even get 999999 ! Now, not every real number will have a base-10 representation with blocks of consecutive identical digits, but there are beautiful theorems, like Dejean's theorem whose proof was recently completed, that say specifically what kinds of repetitions cannot be avoided.

More bad math follows in the same article. The writer claims that "normal numbers" are those "numbers that have the same frequency of all the digits". This is not correct. A normal number to base 10 satisfies a much stronger property: namely, that every block of digits occurs with the expected frequency: if the block has length t then it must occur with limiting frequency 10^-t. An example of a number that "has the same frequency of all the digits", but is not normal, is .01234567890123456789... = 13717421/1111111111. No rational number can be normal, because the number of distinct blocks of length t that appear in a rational number is eventually constant.

What happens when bad mathematics journalism like this gets reposted by the World's Worst Journalist™, Denyse O'Leary? Why, she just quotes it verbatim with no understanding. Despite the fact that nobody knows for sure whether π is normal, and despite the fact that nearly all mathematicians suspect it probably is normal, she insists that it is not! Even when commenters try to set her straight, she still doesn't seem to understand that "normal" is a term of art in mathematics, and does not correspond to the ordinary English meaning.

Bad mathematics all around.

Evangelical Persecution Complex

This interesting article in the Atlantic, about how evangelical Christians perceive that they are the victims of persecution, is very revealing.

And so is a comment chain on Facebook about it by a guy whose name I will omit. Bracketed comments are inserted by me for clarity. It's like a greatest hits of creationist foolishness.

"They are [indeed discriminated against] and it mostly comes from the left. Which seems to be embracing islam."

"OK if my son who is also a Christian desides he would like to pray or read his bible on his free periods during the day he will be stopped and told that he can't do that in public schools. The same school will turn a blind eye to a Muslim. The poor kid has to listen to and be tested on the theory of evolution which is just a theory because there is no more proof of it than there is creationism. That's pretty big to a Christian. Another thing is Christians are refused certain venues and of course the reasons for that aren't stated because those venues could be sued. If you are a Christian and you want to be a journalist you will have a tough time getting a job at mainstream media outlets other than fox. The list goes on and on. There is a war against the sis white male and that include Christians. Don't act like you don't see it."

"There is not ample proof of evolution. At least macro evolution. There is and will never be proof of one species evolving to another. No such missing link has been found. And yes the sic white male is under attack and will eventually be downtrodden if leftist have anything to do with the laws"

"Whether it is legal or not it happened. I am not mixed up in the slightest bit. You are."

"There is no concrete evidence of it. When scientist discover anything that contradicts the theory of evolution they are laughed at and defunded. They have been standing on that falsehood for years and they refuse to let any evidence prove them wrong. The fact is they have never produced a missing link, they try to prove the earth is millions of years old with radiocarbon dating and calibrate that to striations and when asked how they know how old the striations are they refer back to radiocarbon dating. Circular logic. Most scientist worth their salt will tell you the if the planet was even a million years old there wouldn't be any carbon 14 left."

"Oh no Tim you just showed me a picture of fossils. Sorry that does not prove macro evolution. I do not reject science, in fact I have an engineering degree. Science is very important. The lack of proof of macro evolution is why I have a problem with it. And science has never been wrong about anything, right? I suggest that you look into it farther before you jump on the bandwagon. Here's a question that you won't read in natgeo because they can't answer it without having to throw evolution out the window. There are tons of fossils that are supposed to be millions of years old that still have soft tissue attached to it. By their own guidelines that tissue is not supposed to exist unless of course the animal was alive less than 1000 years ago. So to me I feel sorry for you for being suckered into believing lies. That's fine that you believe them but they don't show proof of any animal in transition from one to another. Fact"

"None of them [the examples given by another commenter] display macro evolution."

"So when they found a t-rex fossil with soft tissue on it. They can't explain why though."

"I did not make that up. Look into it."

"You are a fool. It is useless to argue with someone that has already convinced himself of the lie of evolution."

"Just for the record you have produced no facts of macro evolution."

"That's funny. I don't see an scientific understanding coming from any of you trolls. Your lack of evidence is solid proof of your ignorance"

"I haven't seen any substantial evidence of how old the earth is or real evidence of macro evolution. You guys on here are just trolling. Why is it so important to you that my son learns some thing that is still and will always be labeled as a theory, not scientific fact? Is it because you hate God for some reason?"

"I have studied it and I am not in the least bit humiliated."

"No Ann. I was indoctrinated with the theory of evolution from as long as I can remember. When I was saved I realized that to be a believer I couldn't just pick and choose what parts of the bible to believe. This was a big hurtle I had to get over so I started researching the so called evidence and I have found enough hole in it. I would like for my son to learn about all theories but I don't want him to be miss led into believing the theories are actual facts. They aren't."

"John you are a God less idiot"

"If you all are so smart than why did you start the name calling?"

"Tim, it's hard to find evidence that simply don't exist!"

"John, I wonder if you will say that when you are face to face with Jesus? All knees shall bow."

"I have wasted enough of my time arguing with Godless Sodomites for the night. I will pray for you all."

It's like they exist in a different universe. No fact can penetrate a brain this deluded.