Theorems Are Forever: A Great One From 1492
Make that 1942
Raphaël Salem was a great mathematician who worked mainly on Fourier analysis. He will always be remembered for his many beautiful contributions and for the Salem Prize that is named after him. Also he has his own class of real numbers: a real algebraic number is a Salem number if all its conjugates have absolute value at most and one has absolute value exactly one. See this for a list of known Salem numbers.
Today I want to discuss a results that is simple to state, that is widely used, and that has a clever proof.
One of the great things about proving mathematical theorems is that they are forever. We still talk about results from Euclid, 2300 years later; perhaps we will talk about your result years from now. Franchino Gaffurio noted the importance of arithmetic progressions to harmony in his treatise Theorica musicae in 1492. The result in question is a bit more recent—it was proved in 1942 by Salem and Donald Spencer.
What made me think about their theorem is that it is used in very diverse areas of mathematics. For example, it plays a role in the study of , the matrix product exponent, and also was used recently by Dieter van Melkebeek in a proof of a beautiful result on the complexity of .
These applications of the theorem are quite different: one is looking for patterns in trilinear forms, and one is looking for the existence of a protocol that Alice and Bob can use to solve instances of boolean satisfaction. Very different problems, I think anyone would agree. Yet the same theorem is used.
Let’s turn to the statement of this wonderful theorem. Perhaps you will be able to use it in some proof in the future.
The paper of Salem and Spencer is titled: On Sets Of Integers Which Contain No Three Terms In Arithmetical Progression. The title kind-of gives away the whole result. This was probably more important in 1942, since a paper with a title like: A Result On Patterns In Numbers would be hard to find. Recall there was no search inside papers in those days. Nowadays we can use any title at all and people can still search and find your result. They can even search to see if you’ve worked on a particular equation. But then a good title was worth many citations.
Let be a set of integers. Say that the set is progression-free if for any three distinct integers in the set,
Note that this is the same as saying that there is no progression of length three in the set: if
are all in the set with , then
Salem and Spencer defined to be the maximum number of elements that can be in a subset of that is progression-free. They proved:
Theorem: For any ,
Note this means that is extremely close to , and that there always exists a set that is very dense yet avoids every three-term progression.
Unconventional Wisdom, Again
In their introduction they pointed out that at the time the result was surprising, since then the conventional wisdom was that had to behave like where . Clearly their result is much stronger than this—again people guessed wrong. Here the people are Paul Erdös and Paul Turán who made the guess. In that same paper Erdös and Turán made a small calculation error that was pointed out in one of the shortest papers I have every seen. It was in the Journal of the London Mathematical Society:
As I have quoted before, from Roger Brockett:
“It is hard to argue with a counter-example.”
The main idea of the proof is very simple. Let be a number in the range and use to denote the vector where
The vector is just the vector of the digits of in decimal notation. Look at the set of such so that all their digits restricted to be in the set . The the critical observation is that for and in the set ,
where the latter sum is the vector sum of the digits. This follows since there is no possible carry in adding and . For example,
The reason this is an important observation is: this replaces looking for a set without a three progression to a set of vectors that contains no line. This is much easier, as you might expect. The remainder of the proof is to replace decimal by a higher radix and to replace the restriction on the digits by a more complex one. The idea is to restrict the digits so that the sum of integers with the restriction are mostly like a vector sum.
See the paper for the details—it is less than three pages long and not hard to follow. Also see this recent paper by Bill Gasarch, James Glenn, and Clyde Kruskal, which covers constructions of 3-free sets for small with tables for , and their followup on theory and heuristics for higher . See also this 2010 post by Bill referencing also this by Gil Kalai on a “breakthrough” and “barrier.”
Can you use this wonderful theorem in your work? Do you know of another theorem like this that is widely used in very different parts of mathematics?