I often see the following claim, or variants of it:
"In a computer (as we understand computers, at least), irrational numbers can't be fully accurately represented."
This one happens to be from Bradley Monton, Seeking God in Science: An Atheist Defends Intelligent Design, Broadview Press, 2009, p. 128, but Monton isn't alone.
This is a common misunderstanding that, I think, has two bases. First, for people without much mathematical training, a real number is inextricably linked with its base-10 (or perhaps base-2) representation. For them, the number π is 3.141592653 ..., as opposed to being defined by an integral or infinite series. Second, people without computational training often don't understand that some infinite objects -- including some base-10 or base-2 representations of irrational real numbers -- are routinely represented as finite objects in computers.
Let's take √2 as an example. Although it is irrational, symbolic algebra systems such as Maple and Mathematica routinely represent √2 "exactly" and allow manipulations with it. For example, if you type
> x := sqrt(2);
> x^2;
into Maple, it will happily return the "exact" answer 2. And, similarly, other arithmetic operations involving √2 will give the "exact" answers:
> expand((123+45*sqrt(2))^3);
3355317 + 2224665 √2;
Similarly, we can manipulate other famous irrational numbers such as e, π, etc, and often get "exact" results. The point is that many of the irrational numbers that people actually care about need not be stored in terms of their base-10 or base-2 representation.
But even if we insist that yes, they must be stored in this way, there can still be finite representations. For example, consider the base-10 number defined by having a "1" in the i'th digit if i is a perfect square (like 1,4,9,16, etc.), and 0 otherwise. Now it is easy to see that this number is irrational. But we can still store it in a finite way (for example, as a function that returns the i'th digit on input i), and do at least some simple manipulations on this representation. For numbers whose base-k representation is encoded by a finite automaton, for example, we can do addition, even if the carries come from "infinitely far" to the right. (This is not trivial.)
In fact, any algebraic number, and many others, can be stored as a finite program that on input i returns the i'th digit. In some cases we can even do this by a very simple recurrence. For example, Graham and Pollak, in a 1970 paper, gave a simple explicit recursion to compute the i'th bit of √2 .
The misguided claim I started with can be fixed. If instead we say, "The base-2 representation of most irrational real numbers is not compressible to a finite representation, so the entire base-2 representation of most irrational real numbers cannot be stored in a finite computer", we would be correct. Here "most" means "all but a set of measure zero". But this is not particularly interesting, since for actual computation we are rarely interested in "most" irrational numbers -- we are interested in the computable ones.
Showing posts with label computer science. Show all posts
Showing posts with label computer science. Show all posts
Thursday, April 28, 2011
Tuesday, September 21, 2010
An Array Initialization Trick
Here is a neat trick that lets you avoid initializing large arrays. I learned about it long ago from Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms, an old but still great book — but I think it is probably an old hacker's idea.
To illustrate the idea, suppose we are trying to solve the element distinctness problem on a restricted universe. In this problem we are given a list of integers and we want to determine if there are any repeated elements. The input is an array A[1..n] of integers, where each integer is between (say) 1 and M, where M is not so large compared to n — maybe M is about 10n or something like that.
The usual way to do this is to create an array B[1..M] such that B[j] = 1 if j is an element of A, and 0 otherwise. We start by initializing all the entries of B to 0. Then we loop through the elements of A. For each i, 1 ≤ i ≤ n, we first check B[A[i]]. If it equals 1, then the value A[i] already occurred in A. Otherwise, we set B[A[i]] := 1, to signify that we've seen A[i].
If M = O(n), this gives a linear-time algorithm for element distinctness. It even lets us list the repeated elements, if there are any.
Now here's the deal. Suppose we are solving element distinctness many times in a program, as a subroutine. Then it is conceivable that initializing all the entries of B to 0 could actually be a significant time drain. Although we have to allocate the memory for B once at the start, could there be a way to avoid the time-consuming Θ(M) initialization for B each time we call the subroutine again? We have to handle the problem that the entries of B could be arbitrary junk that we have no control over.
The answer is yes, using the following trick: instead of containing 1 or 0, we will set it up so that B[j] contains the position p in A where j is found. The key point is that we always actually verify this by looking at A[p], so we can never go wrong, even if B[j] is junk. More precisely, we want to ensure that if B[j] = p, then A[p] = j.
Now for each i we are going to check to see if A[i] = d has already been seen. To do this, we look in B[d]; say it equals c. If c is not between 1 and i-1, then we know that c represents uninitialized junk, so we can confidently ignore it and set B[d] = i.
If c is between 1 and i-1, then it either represents a true pointer back to the place in A where d was found earlier, or it just happens to be junk that is in the right range. In either case, we look at A[c]. Either it equals d, in which case we have found d earlier in the array at the entry A[c], or it equals something else. In the latter case we also set B[d] = i. This works whether B[d] is a true pointer or not!
Here's the code:
And that's it! This code fragment prints out the duplications. Of course, if you'd rather terminate as soon as a repeated element is found, you can do that instead. Or if you'd rather save the repeated elements in a linked list, you can do that, too. And of course, this trick can be used in other settings, such as large sparse matrices, where you want to avoid initialization costs.
To illustrate the idea, suppose we are trying to solve the element distinctness problem on a restricted universe. In this problem we are given a list of integers and we want to determine if there are any repeated elements. The input is an array A[1..n] of integers, where each integer is between (say) 1 and M, where M is not so large compared to n — maybe M is about 10n or something like that.
The usual way to do this is to create an array B[1..M] such that B[j] = 1 if j is an element of A, and 0 otherwise. We start by initializing all the entries of B to 0. Then we loop through the elements of A. For each i, 1 ≤ i ≤ n, we first check B[A[i]]. If it equals 1, then the value A[i] already occurred in A. Otherwise, we set B[A[i]] := 1, to signify that we've seen A[i].
If M = O(n), this gives a linear-time algorithm for element distinctness. It even lets us list the repeated elements, if there are any.
Now here's the deal. Suppose we are solving element distinctness many times in a program, as a subroutine. Then it is conceivable that initializing all the entries of B to 0 could actually be a significant time drain. Although we have to allocate the memory for B once at the start, could there be a way to avoid the time-consuming Θ(M) initialization for B each time we call the subroutine again? We have to handle the problem that the entries of B could be arbitrary junk that we have no control over.
The answer is yes, using the following trick: instead of containing 1 or 0, we will set it up so that B[j] contains the position p in A where j is found. The key point is that we always actually verify this by looking at A[p], so we can never go wrong, even if B[j] is junk. More precisely, we want to ensure that if B[j] = p, then A[p] = j.
Now for each i we are going to check to see if A[i] = d has already been seen. To do this, we look in B[d]; say it equals c. If c is not between 1 and i-1, then we know that c represents uninitialized junk, so we can confidently ignore it and set B[d] = i.
If c is between 1 and i-1, then it either represents a true pointer back to the place in A where d was found earlier, or it just happens to be junk that is in the right range. In either case, we look at A[c]. Either it equals d, in which case we have found d earlier in the array at the entry A[c], or it equals something else. In the latter case we also set B[d] = i. This works whether B[d] is a true pointer or not!
Here's the code:
for i := 1 to n do
d := A[i]
c := B[d]
if (c < 1) or (c ≥ i) then
B[d] := i
else if A[c] = d then
print(d, " occurred at positions ", c," and ", i)
else B[d] := i;
And that's it! This code fragment prints out the duplications. Of course, if you'd rather terminate as soon as a repeated element is found, you can do that instead. Or if you'd rather save the repeated elements in a linked list, you can do that, too. And of course, this trick can be used in other settings, such as large sparse matrices, where you want to avoid initialization costs.
Wednesday, May 19, 2010
Turing vs. the Creationists
Today we bring you your daily dose of breathtaking inanity from the creationist blog Uncommon Descent. A poster named "niwrad" (that's "Darwin" spelled backwards - the creationists are oh-so-clever) finds yet another reason to reject Darwinism.
"niwrad" draws an analogy with computer programming, and then "explain[s] as clearly as possible exactly what a program is". He goes on to say, "In order to process information – i.e. create software – it is necessary to create data and programs. Data is passive information: it cannot change or decide anything by itself" while "a program, in its simplest concept, is a blueprint specifying the reiteration of basic decision structures, about what to do and when to do it."
He/she then goes to say, "The argument which I am putting forward here cuts through these definitional controversies, because from my informatics-based perspective there are really only two possibilities, which can be summarized as follows: either (a) genes are data (which corresponds to the above old definition of a gene); or (b) genes are functions (which corresponds to the new definition)", gives incoherent reasons for rejecting both views, and concludes, "To sum up: Darwinism, from an informatics point of view, has absolutely zero credibility."
Poor "niwrad". He/she/it never learned much computer science, because we have known at least since 1936 that the artificial distinction between "program" and "data" is illusory. The existence of a universal machine shows that we can treat programs and data in the same fashion. That, indeed, was one of the fundamental insights of Alan Turing in his famous paper, "On computable numbers...". As Kleinberg and Papadimitriou remark, "Indeed, our style of writing programs and then executing them is so ingrained in our view of computation that it takes a moment to appreciate the consequences that flow from a universal machine. It means that programs and data are really the same thing: a program is just a sequence of symbols that looks like any other piece of input; but when fed to a universal machine, this input wakes up and begins to compute. Think of mobile code, java applets, e-mail viruses: your computer downloads them as data, and then runs them as programs."
Furthermore, we know from the field of DNA computing that very simple abstract operations, corresponding to the physics and chemistry of DNA, can simulate universal computation.
If creationists want to avoid being defeated by the ghost of Alan Turing, they need to spend more time reading about what is known in computer science and biology, and less time proclaiming (as "niwrad" did) that "God, also in this case, expects far less from us than what He Himself did and does".
"niwrad" draws an analogy with computer programming, and then "explain[s] as clearly as possible exactly what a program is". He goes on to say, "In order to process information – i.e. create software – it is necessary to create data and programs. Data is passive information: it cannot change or decide anything by itself" while "a program, in its simplest concept, is a blueprint specifying the reiteration of basic decision structures, about what to do and when to do it."
He/she then goes to say, "The argument which I am putting forward here cuts through these definitional controversies, because from my informatics-based perspective there are really only two possibilities, which can be summarized as follows: either (a) genes are data (which corresponds to the above old definition of a gene); or (b) genes are functions (which corresponds to the new definition)", gives incoherent reasons for rejecting both views, and concludes, "To sum up: Darwinism, from an informatics point of view, has absolutely zero credibility."
Poor "niwrad". He/she/it never learned much computer science, because we have known at least since 1936 that the artificial distinction between "program" and "data" is illusory. The existence of a universal machine shows that we can treat programs and data in the same fashion. That, indeed, was one of the fundamental insights of Alan Turing in his famous paper, "On computable numbers...". As Kleinberg and Papadimitriou remark, "Indeed, our style of writing programs and then executing them is so ingrained in our view of computation that it takes a moment to appreciate the consequences that flow from a universal machine. It means that programs and data are really the same thing: a program is just a sequence of symbols that looks like any other piece of input; but when fed to a universal machine, this input wakes up and begins to compute. Think of mobile code, java applets, e-mail viruses: your computer downloads them as data, and then runs them as programs."
Furthermore, we know from the field of DNA computing that very simple abstract operations, corresponding to the physics and chemistry of DNA, can simulate universal computation.
If creationists want to avoid being defeated by the ghost of Alan Turing, they need to spend more time reading about what is known in computer science and biology, and less time proclaiming (as "niwrad" did) that "God, also in this case, expects far less from us than what He Himself did and does".
Thursday, September 17, 2009
Giving a Bad Talk at a Scientific Conference
Here are some tips to give a really bad talk at a scientific meeting. The more tips you follow, the more likely you are to be memorably awful.
These are all based on talks I have witnessed.
1. Come with a retinue of students of the same ethnic background, assert a proof for a famous unsolved problem, give a proof for completely elementary simple cases and omit the proof of the main result, assert your results have been overlooked by those of a different ethnic background, insult established scientists who have recently made progress on similar problems, and have your students cheer wildly when you are done. Extra points if your talk is in "call and response" format.
2. Speak so softly that even with a microphone you are completely inaudible.
3. Speak rapidly with an extremely strong accent, and have your slides full of incomprehensible sentences that look like they were drawn randomly from a bag of scrabble tiles.
4. Sigh frequently during your talk, as if giving it is the most boring thing you can possibly imagine, and you can't wait for the damn thing to be over.
5. Give your talk by writing with a marker on overhead transparencies, and when you run out of transparencies, lick off one of the ones you already used. While it is still wet, put the slide, wet side down, on the projector so the ink mixes with your saliva and spreads all over the glass plate of the overhead.
6. Begin by insulting the organizers. State that you are so important, they should have found a larger room for you to speak in. Say that everyone else is stupid. Do not give any details, simply refer the audience to your web page.
7. Consistently point at the screen of your computer with your finger, as if you are convinced that by doing so the audience will magically see what you are pointing at on the screen of the projector.
8. Give results in your talk that are identical to those of the previous speaker. When you are questioned about it, deny that the results are the same.
I'm sure these helpful tips will create a memorable experience for you and your audience.
These are all based on talks I have witnessed.
1. Come with a retinue of students of the same ethnic background, assert a proof for a famous unsolved problem, give a proof for completely elementary simple cases and omit the proof of the main result, assert your results have been overlooked by those of a different ethnic background, insult established scientists who have recently made progress on similar problems, and have your students cheer wildly when you are done. Extra points if your talk is in "call and response" format.
2. Speak so softly that even with a microphone you are completely inaudible.
3. Speak rapidly with an extremely strong accent, and have your slides full of incomprehensible sentences that look like they were drawn randomly from a bag of scrabble tiles.
4. Sigh frequently during your talk, as if giving it is the most boring thing you can possibly imagine, and you can't wait for the damn thing to be over.
5. Give your talk by writing with a marker on overhead transparencies, and when you run out of transparencies, lick off one of the ones you already used. While it is still wet, put the slide, wet side down, on the projector so the ink mixes with your saliva and spreads all over the glass plate of the overhead.
6. Begin by insulting the organizers. State that you are so important, they should have found a larger room for you to speak in. Say that everyone else is stupid. Do not give any details, simply refer the audience to your web page.
7. Consistently point at the screen of your computer with your finger, as if you are convinced that by doing so the audience will magically see what you are pointing at on the screen of the projector.
8. Give results in your talk that are identical to those of the previous speaker. When you are questioned about it, deny that the results are the same.
I'm sure these helpful tips will create a memorable experience for you and your audience.
Wednesday, September 03, 2008
My New Book is Out!
My new book, A Second Course in Formal Languages and Automata Theory, is out!
Here's a web page that tells you a little more about the book. And, if you absolutely have to have your own copy, you can buy it at Amazon or Barnes and Noble.
Here's a web page that tells you a little more about the book. And, if you absolutely have to have your own copy, you can buy it at Amazon or Barnes and Noble.
Thursday, January 10, 2008
Happy Birthday, Donald Knuth!
Today is Donald Knuth's 70th birthday!
Donald Ervin Knuth was born in Milwaukee, Wisconsin, on January 10, 1938. He received his BS and MS degrees from Case Institute of Technology and his Ph.D. from the California Institute of Technology in 1963.
Knuth is probably best known for his three-volume work, The Art of Computer Programming, which popularized the analysis of algorithms as a basic tool of computer science. Volume 4, on combinatorial algorithms, is in preparation and parts have been published as "fascicles", preliminary to the final version.
Knuth is responsible for the theory of LR parsing, which he invented in a 1965 article. This method forms the basis for most modern compilers.
Knuth is the inventor of TeX, a system for typesetting mathematics that is used today by most mathematicians and computer scientists to prepare their papers.
Knuth is the recipient of many awards, including the 1974 Turing award (computer science's highest award).
My blogging friends in mathematics and computer science have put together a little birthday tribute to him:
- Mark Chu-Carroll, over at Good Math, Bad Math, offers this assessment of Knuth's contributions to typesetting.
- The irrepressible Doron Zeilberger sings Knuth's praises in this post, written in Zeilberger's inimitable style.
- From David Eppstein, a beautiful analysis of a backtracking algorithm to solve the exact cover problem.
- From Scott Aaronson, a review of Knuth's views on philosophy and God.
- From Luca Trevisan this lovely appreciation.
- From Bill Gasarch, an appraisal of Knuth's impact.
- From Suresh Venkatasubramanian, how to pick a random element from a set whose cardinality is unknown.
- Last but not least is my own little contribution.
There might be some more contributions later, so check back!
Still not satisified? You can look at this 1999 Salon piece, or this offbeat biography of Knuth from a future historian, or this NPR interview, or Knuth's own home page.
Happy birthday, Don!
Thursday, August 23, 2007
The Noncommutative Frobenius Problem is Solved!
I rarely get the opportunity to talk about research problems on this blog, but this is an exception.
Consider the famous "Chicken McNuggets problem": if Chicken McNuggets are sold at McDonald's only in boxes of 6, 9, or 20 McNuggets, what's the largest number of McNuggets you can't buy at McDonald's? The answer happens to be my favorite number, 43. (Why it is my favorite is a story that will have to wait for another day.) Notice that you can buy any number of McNuggets greater than 43. For example,
44 = 4*6 + 1*20,
45 = 5*9,
46 = 1*6 + 2*20,
47 = 3*6 + 1*9 + 1*20,
48 = 8*6,
49 = 1*9 + 2*20,
and any number greater than 49 can be obtained by adding an appropriate multiple of 6 to these.
In general, you're given a set S of integers, and you want to know the largest number that cannot be expressed as a non-negative integer linear combination of the elements of S. This is called the Frobenius number because Frobenius is supposed to have mentioned it often during his lectures.
Of course, such an integer may not exist. For example, if S = {4, 6}, then you can only get multiples of 2 by forming an integer linear combination of 4 and 6. So you need to impose an important condition: the greatest common divisor of the elements of S must be 1. If this is the case, then you can express every sufficiently large integer as a non-negative integer linear combination of the elements of S.
Now, solving the classical Frobenius problem is easy in some cases. For example, here's a well-known formula for the case when S has only two elements, x and y, and here it is: xy - x - y. So, for example, the Frobenius number of 5 and 7 is 23. Every number larger than 23 can be expressed as a non-negative integer linear combination of 5 and 7. 24, for example, would be 2*5 + 2*7, and so forth -- but 23 itself cannot.
Greenberg wrote a paper in 1988, and Davison wrote another paper in 1994, in which they gave an efficient algorithm for three numbers.
Unfortunately, the general problem was proved NP-hard (under Turing reductions) by Ramirez Alfonsin in 1996. Roughly speaking, this means the problem is at least as hard as many classical problems for which we still have no efficient solution, such as the traveling salesman problem.
About 6 years ago, I suggested generalizing this problem from numbers to strings of symbols (sometimes called "words"). This kind of generalization is a typical activity in mathematics and theoretical computer science. You take a well-studied problem over one kind of domain, and see how the problem translates in another. The classical Frobenius problem dealt with positive integers, so we'll replace them with strings. Now S will be a set of strings.
Now we have to find the analogue of a non-negative integer linear combination. This is no problem: strings like to join up with other strings, in a process called concatenation, so our non-negative integer linear combinations will be replaced by all possible ways to concatenate the strings of S, using any of them any number of times (including 0 times). This process is sometimes called Kleene closure after the American logician Stephen Kleene, and we write it as S*. For example, if S = {0, 01}, then S* = { ε, 0, 00, 01, 000, 001, 010, ... }. That funny ε at the beginning is the usual mathematical representation for the empty string: the string with no letters at all in it. Notice that order matters in concatenation (houseboat isn't the same as boathouse), so we've gone from a commutative setting to a noncommutative one.
So S* is an infinite set of strings. (By the way, in this particular example, where S = {0, 01}, the set S* happens to have a nice description: it's the set of all strings that don't begin with a 1, and don't have two consecutive 1's appearing anywhere.)
OK, now we've generalized the "non-negative integer linear combination" part. How about the condition that the greatest common divisor (gcd) of the elements of S must be 1? Well, the point of that condition was just to ensure that every sufficiently large integer had a representation, so rather than worrying about how to define the greatest common divisor of two strings, let's replace the gcd condition with: every sufficiently long string must be in S*. There's another way to say this: the complement of a set T is the set of all strings occurring in the universal set that don't occur in T. Here the universal set is just the set of all strings. So our condition is that the complement of S* should be finite. In the arcane lingo of mathematicians, we can abbreviate this as: S* is co-finite.
Now, are there any examples where S* is co-finite? Yes. One example is S = {1, 00, 01,10, 000, 01010}. It shouldn't be too hard to convince yourself that every string except 0 and 010 can be written as concatenation of strings in this set. So in this case S* is co-finite.
Finally, we need an analogue of the largest integer not representable. That's not hard --- it's just the length of the longest string not in S*. In the previous example, where S = {1, 00, 01,10, 000, 01010}, the answer would be 3, since 010 is the longest string omitted from S*. Let's call this the Frobenius number of the set of strings S.
Now it's not too hard to show that if the longest string in S is of length n, and S* is co-finite, then the Frobenius number is bounded by a function which is exponential in n. For example, over an alphabet of two letters, you can show that the Frobenius number is < (2/3)*(4n - 1). (In case the exponent doesn't show up well in your browser, that's 4 to the n power, minus 1, times two-thirds.)
I figured out this generalization a while ago, and the upper bound a year or so ago. But I could not find any example where the Frobenius number was anywhere near as big as that upper bound. Indeed, for a long time, the worst-case example I knew was when you took S to be the set of all strings of length n, together with all the strings of length n+1. In this case, the Frobenius number is easily shown to be n2 - n - 1.
I gave the problem to my Ph. D. student Zhi Xu, who only started a few months ago. We tried many different possibilities, but eventually we figured out that you should try sets S that contain almost all strings of some lengths, omitting only a few. And recently he made a big breakthrough: he was able to construct examples where the Frobenius number is exponentially large in n, the length of the longest string. Here's one of his examples: take S to be over a binary alphabet, that is, over {0,1}, and let it contain all the strings of length 3, all the strings of length 5, except that you remove the strings {00001, 01010, 10011}. Then S* is co-finite, and the length of the longest string not in S* is 25. For example, 0000101001100000001010011 can't be gotten by concatenating the strings of S.
So our understanding of Frobenius problem for strings is now greatly improved, in the sense that there is an exponential upper bound and a class of examples that provides an exponential lower bound. The bounds are not exactly tight, but they are much tighter than ever before. Zhi Xu has many other results on this problem, and you can see our paper on the subject here. We wrote it together with Jui-Yi Kao, another student of mine who also made some very nice contributions. I expect this paper will form the basis of Zhi Xu's Ph. D. thesis. Of course, there is much more to be done in this area.
I hope you enjoyed this tour of my recent research, and congratulations to Zhi Xu for a job well done!
Consider the famous "Chicken McNuggets problem": if Chicken McNuggets are sold at McDonald's only in boxes of 6, 9, or 20 McNuggets, what's the largest number of McNuggets you can't buy at McDonald's? The answer happens to be my favorite number, 43. (Why it is my favorite is a story that will have to wait for another day.) Notice that you can buy any number of McNuggets greater than 43. For example,
44 = 4*6 + 1*20,
45 = 5*9,
46 = 1*6 + 2*20,
47 = 3*6 + 1*9 + 1*20,
48 = 8*6,
49 = 1*9 + 2*20,
and any number greater than 49 can be obtained by adding an appropriate multiple of 6 to these.
In general, you're given a set S of integers, and you want to know the largest number that cannot be expressed as a non-negative integer linear combination of the elements of S. This is called the Frobenius number because Frobenius is supposed to have mentioned it often during his lectures.
Of course, such an integer may not exist. For example, if S = {4, 6}, then you can only get multiples of 2 by forming an integer linear combination of 4 and 6. So you need to impose an important condition: the greatest common divisor of the elements of S must be 1. If this is the case, then you can express every sufficiently large integer as a non-negative integer linear combination of the elements of S.
Now, solving the classical Frobenius problem is easy in some cases. For example, here's a well-known formula for the case when S has only two elements, x and y, and here it is: xy - x - y. So, for example, the Frobenius number of 5 and 7 is 23. Every number larger than 23 can be expressed as a non-negative integer linear combination of 5 and 7. 24, for example, would be 2*5 + 2*7, and so forth -- but 23 itself cannot.
Greenberg wrote a paper in 1988, and Davison wrote another paper in 1994, in which they gave an efficient algorithm for three numbers.
Unfortunately, the general problem was proved NP-hard (under Turing reductions) by Ramirez Alfonsin in 1996. Roughly speaking, this means the problem is at least as hard as many classical problems for which we still have no efficient solution, such as the traveling salesman problem.
About 6 years ago, I suggested generalizing this problem from numbers to strings of symbols (sometimes called "words"). This kind of generalization is a typical activity in mathematics and theoretical computer science. You take a well-studied problem over one kind of domain, and see how the problem translates in another. The classical Frobenius problem dealt with positive integers, so we'll replace them with strings. Now S will be a set of strings.
Now we have to find the analogue of a non-negative integer linear combination. This is no problem: strings like to join up with other strings, in a process called concatenation, so our non-negative integer linear combinations will be replaced by all possible ways to concatenate the strings of S, using any of them any number of times (including 0 times). This process is sometimes called Kleene closure after the American logician Stephen Kleene, and we write it as S*. For example, if S = {0, 01}, then S* = { ε, 0, 00, 01, 000, 001, 010, ... }. That funny ε at the beginning is the usual mathematical representation for the empty string: the string with no letters at all in it. Notice that order matters in concatenation (houseboat isn't the same as boathouse), so we've gone from a commutative setting to a noncommutative one.
So S* is an infinite set of strings. (By the way, in this particular example, where S = {0, 01}, the set S* happens to have a nice description: it's the set of all strings that don't begin with a 1, and don't have two consecutive 1's appearing anywhere.)
OK, now we've generalized the "non-negative integer linear combination" part. How about the condition that the greatest common divisor (gcd) of the elements of S must be 1? Well, the point of that condition was just to ensure that every sufficiently large integer had a representation, so rather than worrying about how to define the greatest common divisor of two strings, let's replace the gcd condition with: every sufficiently long string must be in S*. There's another way to say this: the complement of a set T is the set of all strings occurring in the universal set that don't occur in T. Here the universal set is just the set of all strings. So our condition is that the complement of S* should be finite. In the arcane lingo of mathematicians, we can abbreviate this as: S* is co-finite.
Now, are there any examples where S* is co-finite? Yes. One example is S = {1, 00, 01,10, 000, 01010}. It shouldn't be too hard to convince yourself that every string except 0 and 010 can be written as concatenation of strings in this set. So in this case S* is co-finite.
Finally, we need an analogue of the largest integer not representable. That's not hard --- it's just the length of the longest string not in S*. In the previous example, where S = {1, 00, 01,10, 000, 01010}, the answer would be 3, since 010 is the longest string omitted from S*. Let's call this the Frobenius number of the set of strings S.
Now it's not too hard to show that if the longest string in S is of length n, and S* is co-finite, then the Frobenius number is bounded by a function which is exponential in n. For example, over an alphabet of two letters, you can show that the Frobenius number is < (2/3)*(4n - 1). (In case the exponent doesn't show up well in your browser, that's 4 to the n power, minus 1, times two-thirds.)
I figured out this generalization a while ago, and the upper bound a year or so ago. But I could not find any example where the Frobenius number was anywhere near as big as that upper bound. Indeed, for a long time, the worst-case example I knew was when you took S to be the set of all strings of length n, together with all the strings of length n+1. In this case, the Frobenius number is easily shown to be n2 - n - 1.
I gave the problem to my Ph. D. student Zhi Xu, who only started a few months ago. We tried many different possibilities, but eventually we figured out that you should try sets S that contain almost all strings of some lengths, omitting only a few. And recently he made a big breakthrough: he was able to construct examples where the Frobenius number is exponentially large in n, the length of the longest string. Here's one of his examples: take S to be over a binary alphabet, that is, over {0,1}, and let it contain all the strings of length 3, all the strings of length 5, except that you remove the strings {00001, 01010, 10011}. Then S* is co-finite, and the length of the longest string not in S* is 25. For example, 0000101001100000001010011 can't be gotten by concatenating the strings of S.
So our understanding of Frobenius problem for strings is now greatly improved, in the sense that there is an exponential upper bound and a class of examples that provides an exponential lower bound. The bounds are not exactly tight, but they are much tighter than ever before. Zhi Xu has many other results on this problem, and you can see our paper on the subject here. We wrote it together with Jui-Yi Kao, another student of mine who also made some very nice contributions. I expect this paper will form the basis of Zhi Xu's Ph. D. thesis. Of course, there is much more to be done in this area.
I hope you enjoyed this tour of my recent research, and congratulations to Zhi Xu for a job well done!
Subscribe to:
Posts (Atom)
