Monday, June 27, 2011

Avoiding Sum Cubes

One of the most interesting and challenging open problems in combinatorics on words is to decide whether there exists an infinite word over a finite subset of N, the non-negative integers, with the property that it contains no two consecutive blocks of the same length and the same sum (a "sum square").

For example, 01231301020103102310313231301020131013230 is a word of length 41 with this property, but if you append any one of {0,1,2,3} to it, it no longer does. Appending 0 gives the sum square 00; appending 1 gives the sum square (3231301020)(1310132301); appending 2 gives the sum square (103132313010)(201310132302); appending 3 gives the sum square (132)(303). So this word cannot be extended to an infinite word avoiding sum squares; the longest such is of length 50. Of course, there could be an infinite word avoiding sum squares over some other subset of N; no one currently knows.

This problem was originally stated by Pirillo and Varricchio in 1994, and independently by Halbeisen and Hungerbühler in 2000.

Today we posted a preprint in the arxiv that solves a related unsolved problem. Instead of avoiding sum squares, we show that we can avoid sum cubes: three consecutive blocks of the same length and same sum.

The construction is actually quite simple: the infinite word in question is the fixed point of the morphism
0 → 03
1 → 43
3 → 1
4 → 01,
and can be obtained by repeatedly applying this morphism starting with 0. Here are the first 50 terms:
03143011034343031011011031430343430343430314301103 .
I found this morphism several years ago.

However, proving that this word has the desired property is not simple. The proof was recently achieved by Luke Schaeffer, using ideas of James Currie at the University of Winnipeg and Julien Cassaigne at the Institute de Mathématiques at Luminy in France.

25 comments:

fudo said...

sounds very nice, gonna have a look at the preprint!

Groofius said...

How many of the words without sum cubes can dance on the head of a pin?

Curt Cameron said...

As a non-mathematician (although I always did very well in math classes and I got a EE degree so I had quite a lot of practical math), is there any practical use for number theory like this? It seems pretty far out in the abstract direction.

I'm currently reading Goedel, Escher, Bach and some of this problem reminds me of stuff I'm picking up there - true statements that maybe can't be proved within the formal system of mathematics.

Jeffrey, I'm curious about your opinion of this book. The title of this blog is exactly what the book focuses on. Do you recommend it? The Goedel's Incompleteness Theorem always sounded kinda interesting, but mysterious, and I had heard about Turing's halting problem but didn't really understand what they're about.

Jeffrey Shallit said...

Curt:

Probably no practical use today, but that is true for something like 95% of what mathematicians do.

Gödel, Escher, Bach is a fun book. I read it my senior year of university, when it came out. Yes, it's worth reading.

Tuition payer said...

Wow, 95%?
I think any professor who fits in this category should read the book:
The Faculty Lounges: And Other Reasons Why You Won't Get The College Education You Pay For (see reviews at Amazon)

Jeffrey Shallit said...

Tuition payer:

You don't know a damn thing about research in mathematics, do you?

Tuition payer said...

I understand when a greater-than-desired percentage of my tuition dollars goes for practically useless things. Read the book.

Jeffrey Shallit said...

Read the book

Sorry, I'm completely uninterested in what some right-wing journalist who knows nothing about research or education thinks.

20 years ago, conservatives were all hot about Profscam. I read it. It was utter junk.

Gerry said...

For Hofstadter's six-word autobiography, see http://xkcd.com/917/

Anonymous said...

I'm very interested in what Tuition payer considers "practically useless things." What about "watching television," "listening to music," "eating candy," "dancing in a disco," "riding a rollercoaster," or "replying to a blog post"?
What percent of your time and money is spent on "practically useful things"? What would you consider a "desired percentage"?

Tuition payer said...

"Right wing journalist" -- ahh, and that's what really matters!

You wouldn't listen to a right-wing anyone who said your pants were on fire.

As a magna cum laude graduate from Harvard, she might have more credibility than your uninvestigated conclusion might assume.

Jeffrey Shallit said...

You wouldn't listen to a right-wing anyone who said your pants were on fire.

You don't know anything about me. I have an extensive library of books from all sides of the political spectrum, including William F. Buckley, Paul Johnson, and other conservatives.

she might have more credibility than your uninvestigated conclusion might assume.

Sorry, but life is short, and recommendations from pseudonymous commentators as clueless as you don't weigh much.

What are the chances some journalist with an agenda and no track record in studying education knows more about academia than I do - after teaching at 4 different schools over 28 years? Virtually nil.

Bob Oboc said...

You sure seem to draw a lot of irate pseudointellectual antagonists in the comments, pretty much on every post, even one as straightforward and logical as this. A shame really, the problem of sum squares and cubes is quite intruiging.

Tuition payer said...

You sure are good at defending those 5% of mathematicians, aren't you.

Tuition Payer said...

"What are the chances some journalist with an agenda and no track record in studying education knows more about academia than I do - after teaching at 4 different schools over 28 years? Virtually nil."

Which minister did you borrow this line from? You know what I mean, the one who sayid:

"What are the chances some professor with an agenda and no track record in studying religion knows more about Christianity than I do - after teaching at 4 different schools over 28 years? Virtually nil."

====

I'll admit that the sum cubes is intriguing. I enjoy math puzzles like this. I would just prefer that mathematicians worked on it on their own dime. Hopefully, most do.

Jeffrey Shallit said...

Hopefully, most do.


You have absolutely no idea about how research in mathematics is done, do you?

Amazing how someone so clueless can pontificate like that.

cody said...

Tuition payer, this is a subject close to my heart: I personally often lose interest once the practical applications become clear (it took me a very long time to realize this) and so I've argued this topic with many close friends (mostly application oriented EEs).

A good friend once argued that all mathematics was done for ultimately practical purposes—imaginary numbers, named for their supposed inapplicability (now used to understand electricity, quantum mechanics, signal processing, etc.) changed his mind.

Number theory is an even better example, which Gauss described as "the queen of mathematics". Number theory didn't find much practical application until the late 20th century when it was leveraged for encryption where it remains dominant. (There is some indication that quantum physics could benefit from pure number theory as well.)

Other examples include showing coworkers the Guggenheim museum in Bilboa Spain, and EE friends the beach artwork of Theo Jansen, all of whom responded with, "what's the point?" I'm not sure there is any sensible answer other than "because it pleases me [or others]."

But the easiest answer to understand is this: today's meaningless abstract theory is tomorrow's technological revolution. Just think of the inapplicability of Einstein's General Theory of Relativity in 1916 (essential for GPS satellites launched 1978).

To take this further, there is no clear indicator telling us which lines of research will be fruitful and which ones will be a waste of time. (I wonder if the undecidability of the halting problem suggests that this is not a problem which can be algorithmically solved?)

Anonymous said...

I say don't knock somebody for contributing to the advancement of human knowledge. A paper like this clearly took a tremendous amount of work to accomplish. I agree that most mathematics amounts to just spank material, with no real immediate benefit to our world civilization. Actually, I witnessed a fellow mathematics student in grad school "literally" spank off in class, well just before class to a female student in the front row. It only took about two minutes before he made the "O" face. Two other students witnessed the event with glee. I was upset though, not out of jealousy or the fact that a rather disabled person was enjoying himself at my expense mind you. But rather because it forced and me to take a long, hard look at myself to see if I really fit in. I do ... damn it, but I dropped out of grad school anyhow.

Tuition Payer said...

That was a great post, Cody. Food for thought.

James Cranch said...

Are there any obvious natural problems which are intermediate in strength between "avoid sum squares" and "avoid sum cubes"?

jeff said...

How did you find this morphism? I ask because it looks to have nice pattern to the natural partition of blocks, for lack of better expression. Please allow me to explain with an example as follows,

03
1
43
011
034343
031011011
03143034343034343
03143011031011011031011011
031430110343430314303434303434303143034343034343.

There is an offset to struggle with, but it looks like we can transform the infinite word like so,
03
(a0):= 1
(a1):= 43
(a2):= 0(a0)(a0)
(a3):= 03(a1)(a1)
(a4):= 03(a0)(a2)(a2)
(a5):= 03(a0)(a1)(a3)(a3)
(a6):= 03(a0)(a1)(a2)(a4)(a4)
(a7):= 03(a0)(a1)(a2)(a3)(a5)(a5).

Which gives: 031430(a0)(a0)03(a1)(a1)03(a0)(a2)(a2)03(a0)(a1)(a3)(a3)03(a0)(a1)(a2)(a4)(a4)...

Of course I have not provided a rigorous transformation, and we'd need a tracking mechanism to get the lengths and sums of arbitrary sized blocks for the transformation to be of any use. But for fun I wanted to see if could guess the closed form for the partial sums of the digits of these blocks as they get appended.

I'm posting what I did, as beyond this "manual" effort (which is better than doing sudoku, at least to me) I'd try to do a rigorous derivation and write some code to help verify things.

I simplified the partial sums in terms of (a0) and (a1) to get,

031430(a0)(a0) = 8+2(a0)+3
031430(a0)(a0)03(a1)(a1) = 8+2(a0)+2(a1)+6
8+7(a0)+2(a1)+9
8+8(a0)+7(a1)+18
8+21(a0)+8(a1)+27
8+26(a0)+21(a1)+51
8+60(a0)+26(a1)+78
8+79(a0)+60(a1)+144
8+169(a0)+79(a1)+225
8+234(a0)+169(a1)+408
8+475(a0)+234(a1)+648,

Where 8 is the sum of 1 + 4 + 3, and the last term of each partial sum is the running sum of the digits of the occurrences of the block 03. The other terms are obvious, and I omitted the left-hand side of the equation for most of the example. As a guess regarding occurrences of (a0) I noticed: 2-2 = 0, 8-7 = 1, 26-21 = 5, 79-60 = 19, 234-169 = 65. The formula appears to be (A001047) 3^n - 2^n, where n >= 0. Also, I noted: 7-2 = 5, 21-8 = 13, 60-26 = 34, 169-79 = 90, 475-234 = 241. The formula appears to be (A023425) the Generalized Catalan Numbers. As the occurrences of (a1) appear to be a shifted version of these formulas, we'd have a piecewise function to account for an even or odd numbered partial sum.
Finally, the sequence 3,9,27,78,225,648 looks to be given by (A090401) the expansion of 1/(1-3x+3x^4). Perhaps we can key off this observation to find a similar formula for the sequence 6,18,51,144,408? In any event, it looks tough to derive a closed form, at least to me.

Lastly, it seems like the pattern I mentioned and the fact that we skip the number 2 play a big role in getting the desired property. So I was just wondering if it was found by "design" or by a computer search...

Jeffrey Shallit said...

Jeff:

It's easy to get the partial sums, but the "right" way to do it is to use the matrix of the morphism, M, as defined in our paper.

We found the morphism by an "intelligent" search - having some idea of what it might look like and then searching the space.

Jeffrey Shallit said...

James:

I don't know about "natural", but yes, there are intermediate problems. For example, you could try to avoid blocks x x' x'', where |x| = |x'| and sum x = sum x', and alpha |x| <= |x''| <= |x| for some alpha <= 1 and sum x'' <= sum x. (In other words, x'' is a block that could possibly be extended to a block x''' of the right length and sum.) The case alpha = 1 is sum cubes.

jeff said...

Thanks Dr. Shallit, I was interested (for fun) in looking for a closed-form for the specific sequence of partial sums I mentioned. As an example, Binet's formula for the Fibonacci sequence. I will try using the matrix.

Jeffrey Shallit said...

jeff:

That's what I was explaining. You can obtain such a closed form using the eigenvalues of the matrix.