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.
Monday, June 27, 2011
Saturday, June 25, 2011
More Lousy Reporting from the Record
Yet another crappy article in my local paper, the Waterloo Region Record. This time it's about the Waterloo Region school board's decision to end the practice of distributing Gideon bibles in school.
From the headline ("Bible ban in schools ignores its influence") to the content, the article is misleading and inaccurate. Nothing was "banned" by the Board's decision. Students are free to bring bibles to school, and bibles aren't being removed from libraries. The only thing that was changed by the decision is that an explicitly evangelical organization will no longer be allowed special dispensation from a public school board to distribute its sacred text to a captive audience of 5th graders, a right granted to no other organization and no other religion.
The author's article, Liz Monteiro, didn't interview a single person in favor of the decision. False claims by Cindy Watson, the school board trustee who voted in favor of continuing the practice of distributing bibles, that it is "not proselytizing", were allowed to go unchallenged. David Seljak, who is usually sensible, is quoted as saying "To eliminate the study of religion from our curriculum is an exercise on mythmaking that borders on propaganda." Only problem? Nothing about "eliminat[ing] the study of religion" was at issue in the School Board's vote.
Andrew Mills, a youth pastor, is allowed to make the remarkable claim that "It's a false dichotomy to think faith is opposed to learning." Well, let's go to Wilmot Centre Missionary Church and see how many books on evolutionary biology (not creationist books) are in their library. Of course faith is opposed to learning. By its very definition, faith leads to beliefs that cannot be questioned and cannot be swayed by evidence.
All in all, more lousy reporting from the Record.
From the headline ("Bible ban in schools ignores its influence") to the content, the article is misleading and inaccurate. Nothing was "banned" by the Board's decision. Students are free to bring bibles to school, and bibles aren't being removed from libraries. The only thing that was changed by the decision is that an explicitly evangelical organization will no longer be allowed special dispensation from a public school board to distribute its sacred text to a captive audience of 5th graders, a right granted to no other organization and no other religion.
The author's article, Liz Monteiro, didn't interview a single person in favor of the decision. False claims by Cindy Watson, the school board trustee who voted in favor of continuing the practice of distributing bibles, that it is "not proselytizing", were allowed to go unchallenged. David Seljak, who is usually sensible, is quoted as saying "To eliminate the study of religion from our curriculum is an exercise on mythmaking that borders on propaganda." Only problem? Nothing about "eliminat[ing] the study of religion" was at issue in the School Board's vote.
Andrew Mills, a youth pastor, is allowed to make the remarkable claim that "It's a false dichotomy to think faith is opposed to learning." Well, let's go to Wilmot Centre Missionary Church and see how many books on evolutionary biology (not creationist books) are in their library. Of course faith is opposed to learning. By its very definition, faith leads to beliefs that cannot be questioned and cannot be swayed by evidence.
All in all, more lousy reporting from the Record.
Friday, June 24, 2011
More Egnorance
Just as I suspected, Egnor's blog provides even more hilarity.
Here he claims:
'Separation of church and state' is not in the Constitution and is not Constitutional Law.
Well, the words "separation of church and state" are not in the US Constitution, but neither are the words "right to a fair trial". Yet I doubt Egnor would make the same claim about the right to a fair trial.
It is a clear falsehood to imply that the concept of separation of church and state is not in the Constitution. Of course it is - right there in the First Amendment - and no reputable lawyer claims otherwise. It is just plain weird how someone can proclaim his religion with such pride, and yet violate its tenets so casually.
I really wonder why becoming unhinged about evolution means you also become unhinged about global warming, separation of church and state, etc.
Here he claims:
'Separation of church and state' is not in the Constitution and is not Constitutional Law.
Well, the words "separation of church and state" are not in the US Constitution, but neither are the words "right to a fair trial". Yet I doubt Egnor would make the same claim about the right to a fair trial.
It is a clear falsehood to imply that the concept of separation of church and state is not in the Constitution. Of course it is - right there in the First Amendment - and no reputable lawyer claims otherwise. It is just plain weird how someone can proclaim his religion with such pride, and yet violate its tenets so casually.
I really wonder why becoming unhinged about evolution means you also become unhinged about global warming, separation of church and state, etc.
Labels:
crackpots,
Egnorance,
separation of church and state
Waterloo Region School Board Ends Gideon Distribution
For years, the Gideons have distributed bibles to grade 5 students in local schools here in Waterloo. No other religious group was afforded this access, a practice which is clearly discriminatory.
Back in November, the issue came up in the Waterloo Region School Board, and the board then voted to continue the practice.
Kudos to Ted Martin and Kathleen Woodcock, who were the only members of the School Board sensible enough to vote no.
But then - horror of horrors - it was suggested that groups other than Christians be allowed to distribute their religious propaganda, too.
Suddenly the Board had a change of heart, and voted 8-3 to end the practice.
Here are the members who voted to continue it:
* Cindy Watson
* Harold Paisley
* Colin Harrington
Shame on them.
Back in November, the issue came up in the Waterloo Region School Board, and the board then voted to continue the practice.
Kudos to Ted Martin and Kathleen Woodcock, who were the only members of the School Board sensible enough to vote no.
But then - horror of horrors - it was suggested that groups other than Christians be allowed to distribute their religious propaganda, too.
Suddenly the Board had a change of heart, and voted 8-3 to end the practice.
Here are the members who voted to continue it:
* Cindy Watson
* Harold Paisley
* Colin Harrington
Shame on them.
Mary is the Ideal Christian?
Oh, look: the brilliant brain surgeon Michael Egnor has a blog, which is called (I kid you not), "Egnorance".
This is destined to be an endless fountain of unintended amusement.
Already we have the renowned Dr. Egnor claiming that Mary is "the original Christian disciple, and a model and a mother for all of us".
Let's see: Mary
* had affair with some guy not her husband
* got pregnant by him
* lied about it
* convinces gullible husband that it was actually some god who raped her
Yes, I'd say that she certainly is a good role model for theists.
This is destined to be an endless fountain of unintended amusement.
Already we have the renowned Dr. Egnor claiming that Mary is "the original Christian disciple, and a model and a mother for all of us".
Let's see: Mary
* had affair with some guy not her husband
* got pregnant by him
* lied about it
* convinces gullible husband that it was actually some god who raped her
Yes, I'd say that she certainly is a good role model for theists.
Thursday, June 23, 2011
T-Shirt Idea
Wikipedia says, "To understand recursion, you must first understand recursion." ThinkGeek even sells a t-shirt with that slogan on it.
But I think a much better version of this would be:
"To understand recursion, you must first understand recursion - 1".
Based on this, I submitted the following idea to ThinkGeek:
Who knows, maybe they'll make it into a t-shirt.
But I think a much better version of this would be:
"To understand recursion, you must first understand recursion - 1".
Based on this, I submitted the following idea to ThinkGeek:
Who knows, maybe they'll make it into a t-shirt.
Wednesday, June 22, 2011
Yet Another Boring Attack on Materialism
Here.
Kastrup's observation is trite and unoriginal.
Darwin himself remarked, "The horrid doubt always arises whether the convictions of man's mind, which has developed from the mind of the lower animals, are of any value or at all trustworthy. Would anyone trust the conviction of a monkey's mind, if there are any convictions in such a mind?"
And, of course, we know from extensive research that our perceptions are often wrong, and wrong in predictable ways.
But none of this provides the "profound contradiction" Kastrup thinks he has discovered. Yes, there are problems in perception and cognition, but the map between the real world and our mental model can't be wildly wrong. If it were, organisms with a better model would have outcompeted us. And the scientific method itself provides self-checking through replicability and peer review.
The bottom line: our own perceptions, and those of the instruments we devise, are all we have. So we use them, and in doing so, we try to be on our guard for mistakes in reason and perception caused by our own biology.
Kastrup's observation is trite and unoriginal.
Darwin himself remarked, "The horrid doubt always arises whether the convictions of man's mind, which has developed from the mind of the lower animals, are of any value or at all trustworthy. Would anyone trust the conviction of a monkey's mind, if there are any convictions in such a mind?"
And, of course, we know from extensive research that our perceptions are often wrong, and wrong in predictable ways.
But none of this provides the "profound contradiction" Kastrup thinks he has discovered. Yes, there are problems in perception and cognition, but the map between the real world and our mental model can't be wildly wrong. If it were, organisms with a better model would have outcompeted us. And the scientific method itself provides self-checking through replicability and peer review.
The bottom line: our own perceptions, and those of the instruments we devise, are all we have. So we use them, and in doing so, we try to be on our guard for mistakes in reason and perception caused by our own biology.
Tuesday, June 14, 2011
Doug Groothuis endorses Bachmann
Let's see: she's
- a pathological liar
- dumber than a bag of nails
- a nasty bigot
Despite those wonderful qualities, Michele Bachmann is still the ideal Presidential candidate in the opinion of Doug Groothuis.
(He doesn't allow any comments on that post - no wonder.)
- a pathological liar
- dumber than a bag of nails
- a nasty bigot
Despite those wonderful qualities, Michele Bachmann is still the ideal Presidential candidate in the opinion of Doug Groothuis.
(He doesn't allow any comments on that post - no wonder.)
Monday, June 06, 2011
Phillies Games, Old and New
We attended two games in Pittsburgh this past weekend. Pittsburgh is 5 hours away from where I live, but it's still the closest National League city to us. Since son #2 is a big Phillies fan, it's a reasonable choice.
We weren't alone. I'd guess that, conservatively, about a third of the people attending the games were Phillies fans. Red shirts were everywhere.
When I was a kid, nobody wore t-shirts or jerseys with the names of their favorite players. Now everybody does. And when I was a kid, everybody bought and waved pennants with the name of the team on them. Now nobody does.
I still remember my first game really clearly. It was on July 9 1967 at Connie Mack Stadium in Philadelphia. We got there early, sitting in our great front-row seats that cost only $3.25 each. During "pepper" before the game, a ball bounced near the little railing, and my father reached down and picked it up! I had my first real official major league baseball, and I never got another ball again since then.
Back in '67 the Phillies had some good players (Johnny Callison, Richie Allen, Cookie Rojas, Jim Bunning) but overall they were pretty mediocre. But on July 9, against the Cardinals, they produced practically the best first game a ten-year-old could see. In the 8th inning, Richie Allen hit one of the longest home runs ever at Connie Mack Stadium to tie the game. And then, in the bottom of the 10th, Tony Gonzalez pinch-hit the winning home run. Perfect!
But back to 2011. PNC Park is a really nice place to watch a game. Even the cheap seats were pretty good, and there is a spectacular view of the Pittsburgh skyline in the outfield.
We got there early for both games. On Friday we hung out in left field and watched batting practice. Ryan Madson, who has a bit of a reputation for being a jerk, confirmed it for us when he deliberately teased fans by pretending to throw them a ball, and then throwing it on the grass instead and laughing.
I'm glad to say that not all the players are like that. On Sunday we got there early to watch batting practice, and hung out by the right field line. There were a lot of pitchers shagging fly balls, including J. C. Romero, Kyle Kendrick, José Contreras, Danys Báez, and Cliff Lee. Danys Báez came over and tossed son #2 a ball, and then later J. C. Romero signed it.
But then Romero did something really classy: there was another kid with a Cliff Lee jersey that he wanted Lee to sign, but Lee was standing about 60 feet away. So Romero took the jersey over to Lee, had Lee sign it, and then returned it to the kid. Now there's a player who knows how to treat fans.
The Phillies lost the first game, but won the second. We got to see Chase Utley make a terrific play in the 7th to save the game, and a great double play by Wilson Valdez. We also got to see Halladay slide at home to score a run, something he apparently hasn't done since high school.
All in all, a fun time in Pittsburgh. Son #2 thanks J. C. Romero!
We weren't alone. I'd guess that, conservatively, about a third of the people attending the games were Phillies fans. Red shirts were everywhere.
When I was a kid, nobody wore t-shirts or jerseys with the names of their favorite players. Now everybody does. And when I was a kid, everybody bought and waved pennants with the name of the team on them. Now nobody does.
I still remember my first game really clearly. It was on July 9 1967 at Connie Mack Stadium in Philadelphia. We got there early, sitting in our great front-row seats that cost only $3.25 each. During "pepper" before the game, a ball bounced near the little railing, and my father reached down and picked it up! I had my first real official major league baseball, and I never got another ball again since then.
Back in '67 the Phillies had some good players (Johnny Callison, Richie Allen, Cookie Rojas, Jim Bunning) but overall they were pretty mediocre. But on July 9, against the Cardinals, they produced practically the best first game a ten-year-old could see. In the 8th inning, Richie Allen hit one of the longest home runs ever at Connie Mack Stadium to tie the game. And then, in the bottom of the 10th, Tony Gonzalez pinch-hit the winning home run. Perfect!
But back to 2011. PNC Park is a really nice place to watch a game. Even the cheap seats were pretty good, and there is a spectacular view of the Pittsburgh skyline in the outfield.
We got there early for both games. On Friday we hung out in left field and watched batting practice. Ryan Madson, who has a bit of a reputation for being a jerk, confirmed it for us when he deliberately teased fans by pretending to throw them a ball, and then throwing it on the grass instead and laughing.
I'm glad to say that not all the players are like that. On Sunday we got there early to watch batting practice, and hung out by the right field line. There were a lot of pitchers shagging fly balls, including J. C. Romero, Kyle Kendrick, José Contreras, Danys Báez, and Cliff Lee. Danys Báez came over and tossed son #2 a ball, and then later J. C. Romero signed it.
But then Romero did something really classy: there was another kid with a Cliff Lee jersey that he wanted Lee to sign, but Lee was standing about 60 feet away. So Romero took the jersey over to Lee, had Lee sign it, and then returned it to the kid. Now there's a player who knows how to treat fans.
The Phillies lost the first game, but won the second. We got to see Chase Utley make a terrific play in the 7th to save the game, and a great double play by Wilson Valdez. We also got to see Halladay slide at home to score a run, something he apparently hasn't done since high school.
All in all, a fun time in Pittsburgh. Son #2 thanks J. C. Romero!
Subscribe to:
Posts (Atom)