Coloring the integers

Here is a problem I composed, which recently appeared on the Colorado Mathematical Olympiad.

If one wishes to color the integers so that every two integers that differ by a factorial get different colors, what is the fewest number of colors necessary?

I might describe a solution, as well as some related history, in a future post. But for now I’ll just say that Adam Hesterberg solved this problem at Canada/USA Mathcamp a few summers ago, claiming the $20 prize I offered almost as soon as I offered it. At the time, I suspected but still did not know the exact answer.

Although the wording of the problem strongly suggests that the answer is finite, I don’t think that this is entirely obvious.

Along those lines, here is another infinite graph with finite chromatic number.

If one wishes to color the points of the Euclidean plane so that every two points at distance one get different colors, what is the fewest number of colors necessary?

This is one of my favorite unsolved math problems, just for being geometrically appealing and apparently intractably hard. After fifty years of many people thinking about it, all that is known is that the answer is 4, 5, 6, or 7. Recent work of Shelah and Soifer suggests that the exact answer may depend on the choice of set theoretic axioms.

This inspired the following related question.

If one wishes to color the points of the Euclidean plane so that every two points at factorial distance get different colors, do finitely many colors suffice?

More generally, if S is a sequence of positive real numbers that grows quickly enough (say exponentially), and one forbids pairs points at distance s from receiving the same color, one would suspect that finitely many colors suffice. On the other hand, if S grows slowly enough (say linearly), one might expect that infinitely many colors are required.

About these ads

5 thoughts on “Coloring the integers

  1. We (Jack D’Aurizio and Maurizio Monge from the University
    of Pisa, Italy) are proud to announce a solution:
    the chromatic number of the graph G, whose nodes
    are the integers, in which

    (a-b)=n! -> a and b have different colors,

    is -exactly- 4; details can be found in the PDF file.
    We have an additional question: is it possible to color
    the integers with a finite number of colors, in order that
    two integers that differs by a positive square have
    different colors?

  2. matthewkahle says:

    Jack and Maurizio, I’d like to see your solution. Is the PDF file posted anywhere?

    Also, I like this question about squares…

  3. The PDF is there; we’ve got some server issues, now it should be fine.

    Recently (2003) Bergelson has proved that, in the quadratic case, a finite amount of colors is not sufficient: http://www.math.ohio-state.edu/~vitaly/vbkatsiveli20march03.pdf

    His techniques deeply rely on the theory of ultrafilters and ergodic, measure-preserving systems; however, we suspect that a simpler proof (maybe using the Mycielski construction and the fact that the squares are an additive base of order 4) is possible.

  4. After a full immersion in the bibliography, we have an alternative proof that the chromatic number of the graph G over the integers, where

    (ab) belongs to E(G) |b-a| is a positive square

    is unbounded. Suppose that X(G)=k, then call

    C_1, … , C_k

    the chromatic components.

    First step: without loss of generality, we can assume
    that every C_i is infinite and syndetic.
    Proof: shifts and compactness. If C_1 has unbounded gaps,
    for every M there exist a coloring of [1,…,M]
    requiring only (k-1) colors, so X(G)=k-1,
    contradiction.

    Second step: Lovasz conjecture is true. Sarkozy proved
    (http://www.renyi.hu/~p_erdos/1978-19a.pdf) through the
    Hardy-Littlewood circle method, that, if A is a subset
    of [1,..,N] such that (A-A) does not contain the square
    of a positive integer, then the asymptotic density of A
    satisfy:

    alpha(N) = O( (log N)^(-1/3) (log log N)^(2/3) ) = o(1)

    So, for every infinite and syndetic C, there is a
    positive integer m with the property that

    m^2 belongs to (C-C).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s