Coloring problems

My student Tommy Chartier completed his M.S. in December.

Here is a copy of the nice slides he used in his defense.

In his thesis, Coloring problems, Tommy studies some graph coloring problems. I wanted to emphasize the variety of problems that the title encompasses, so the examples he presents are all very different from one another.

1. First, Tommy talks briefly about the coloring number of the plane (the notoriously difficult Hadwiger-Nelson problem):

What is the smallest number of colors needed to color the plane, if no two points at distance 1 are to have the same color?

An excellent reference for this problem is the highly entertaining “The mathematical coloring book“, by Alexander Soifer.

There is a well-known finite graph, using 7 vertices, showing that at least 4 colors are needed. Tommy gives an argument showing that, on the other hand, any distance-1 graph with at most 6 vertices (in the plane) is 3-colorable. One can find this result in the literature; the reference is usually

“Solution to problem 10” by L. Moser and W. Moser. Canadian Mathematics Bulletin, 4 (1961), 187-189.

Unfortunately, although the articles of the Bulletin are available online, problems and solutions are not, so we reproved it. It would be interesting to see how far one can generalize this result. I know of only one paper that has attempted this,

“All unit-distance graphs of order 6197 are 6-colorable” by Dan Pritkin. Journal of Combinatorial Theory Series B, 73 (2) (1998), 159-163.

Besides the result in the title, Pritkin shows that any such graph of order at most 12 is 4-colorable. One should be able to improve this result with some work.

2. Tommy also presents some results we obtained during a reading course he took with me as an undergrad, on regressive Ramsey numbers, based on my paper:

“Regressive functions on pairs”. European Journal of Combinatorics 31 (3) (2010), 803–812.

in particular, Tommy presents his example showing that what I call $g(4,4)$ in the paper is precisely 85.

3. The main work on the thesis is on a problem that I find fascinating. The question (still open) originated on MathOverflow, and can be found here.

Is it true that for every $n$ , we can color ${\mathbb Z}^+$ with $n$ colors, in such a way that, for every $a$ , the numbers $a,2a,\dots,na$ all have different colors?

Given $n$ , let $K_n$ , the $n$ -core, denote the set of positive integers whose prime factorization only involves primes less than or equal to $n$ . As a first observation, the question above has a positive answer for $n$ iff it has a positive answer when ${\mathbb Z}^+$ is replaced with $K_n$ . In fact, if there is a coloring of $K_n$ as in the question (a satisfactory $n$ -coloring), then there are continuum many such colorings of ${\mathbb Z}^+$ using $n$ colors.

Tommy looks for sufficient conditions ensuring the existence of satisfactory $n$ -colorings for different $n$ . The first condition (identified by Victor Protsak) is number theoretic:

Theorem 1. Suppose that there is a number $k$ such that $p=nk+1$ is prime, and the numbers $1^k,2^k,\dots,n^k$ are all different modulo $p$ . Then the map $i\mapsto (i^k\mod p)$ is a satisfactory $n$ -coloring.

If $n+1$ or $2n+1$ is prime, then the other condition is automatically satisfied. For other values of $k$ , this is no longer the case. In fact, it is shown in Tommy’s thesis that $k$ can never be 3, for example, and that for any $k$ there are only finitely many possible $n$ , see here.

There is a more general approach, suggested for example by Ewan Delanoy.

Definition. A partial ${\mathbb Z}_n$ -homomorphism is a bijection $\varphi:\{1,\dots,n\}\to{\mathbb Z}_n$ such that whenever $ij\le n$ , then $\varphi(ij)=\varphi(i)+\varphi(j)$ .

Theorem 2. If there is a partial ${\mathbb Z}_n$ -homomorphism, then there is a satisfactory $n$ -coloring.

This is more general: If $p,k$ are as in Theorem 1, then the $k$ -th powers modulo $p$ form a multiplicative group isomorphic to ${\mathbb Z}_n$ , and a partial ${\mathbb Z}_n$ -homomorphism can be easily built. On the other hand, Tommy exhibits examples of partial ${\mathbb Z}_n$ -homomorphisms that do not come from any such prime $p$ .

Even more generally, we can replace ${\mathbb Z}_n$ with any abelian group $(G,\cdot)$ of size $n$ : If there is a bijection $\varphi:\{1,\dots,n\}\to G$ such that $\varphi(ij)=\varphi(i)\varphi(j)$ whenever $ij\le n$ , then there is a satisfactory $n$ -coloring. We call these induced colorings multiplicative.

The requirement that $G$ is abelian is a technical necessity to ensure a satisfactory coloring can be obtained from $\varphi$ . It is interesting to ask whether there is such a bijection, even without this requirement. In

“Groups formed by redefining multiplication”, by K. Chandler. Canadian Mathematics Bulletin, 31 (4) (1988), 419-423,

it is shown that $G$ must be abelian if $n$ is odd, but whether this is always the case seems to be open.

Moreover,

“What is special about 195? Groups, $n$ th power maps and a problem of Graham”, by R. Forcade and A. Pollington. Proceddings of the First Conference of the Canadian Number Theory Association, Ban, 1988, R.A. Mollin, ed., Walter de Gruyter, Berlin, 1990,

it is shown that $n=195$ is least such that there is no such bijection, for any $G$ . Forcade provided us with the list of all $n\le 500$ for which there is no such bijection. We call such $n$ groupless. It is currently open whether any of them admit a satisfactory coloring.

Such colorings would by necessity be non-multiplicative and currently we do not have a framework to explain where they would come from, see here.

I have found examples of non-multiplicative colorings (for $n=6$ ), so we cannot currently rule out that there are satisfactory colorings for every $n$ . On the other hand, even though my examples are non-multiplicative, one can define multiplicative colorings from them. The situation for $n=195$ is very much open.

Many interesting questions remain. For example, it is possible that, for $n$ large enough, there are $p,k$ as in Theorem 1 iff either $n+1$ or $2n+1$ are prime. On the other hand, by a result of Kummer and Mills, see

“Characters with preassigned values”, by W.H. Mills. Canadian Journal of Mathematics, 15 (1963), 169-171,

we know that for $n=34$ there must be such a $p$ , but extensive computer search has not found it. As an indication of the difficulties of the search, the smallest $p$ for $n=32$ is $p=5209690063553$ , and we expect any $p$ for $34$ to be orders of magnitude larger.

It is worth mentioning that the difficulties found with the problem were to be expected. As shown in the thesis, the existence of a satisfactory $n$ -coloring trivially implies the case $m=n+1$ of the following result:

Theorem. (Balasubramanian-Soundararajan, 1996) Let $m\ge 1$ , and let $0<a_1<\dots<a_m$ be integers. Then $a_i/\gcd(a_i,a_j)\ge m$ for some $i,j$ .

The Balasubramanian-Soundararajan theorem solved a conjecture of Graham from 1970. The proof appears in

“On a conjecture of R. L. Graham”, by R. Balasubramanian and K. Soundararajan. Acta Arithmetica, 75 (1) (1996), 1-38.

The work of Forcade-Pollington mentioned above was carried out in connection with this conjecture.

It would be nice to revisit the problem in the future. I think there is still much to say about it.

One Response to Coloring problems

Coloring the n-smooth numbers with n colors | A kind of library says:

February 5, 2019 at 8:59 am

[…] Pál Pach, my former master’s student Thomas A. C. Chartier and myself have just submitted our paper Coloring the -smooth numbers with colors. Meanwhile, you […]

Reply

Leave a Reply Cancel reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

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

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

Cancel

Connecting to %s

Categories

Mathoverflow

Answer by Andrés E. Caicedo for Question about Jech's proof of V = L implies GCH June 3, 2019

You assume $\omega_\alpha\subseteq M$ and $X\in M$ so that $X$ belongs to the transitive collapse of $M$ (because if $\pi$ is the collapsing map, $\pi(X)=\pi[X]=X$. You assume $|M|=\aleph_\alpha$ so that the transitive collapse of $M$ has size $\aleph_\alpha$. Since you also have that this transitive collapse is of the form $L_\beta$ for some $\beta$, it fol […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Smallest $\beta$ such that it is provable that $2^{\aleph_\beta} > 2^{\aleph_0}$ January 16, 2019

Perhaps the following may clarify the comments: for any ordinal $\delta$, there is a Boolean-valued extension of the universe of sets where $2^{\aleph_0}>\aleph_\delta$ holds. If you rather talk of models than Boolean-valued extensions, what this says is that we can force while preserving all ordinals, and in fact all initial ordinals, and make the contin […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Arguments against large cardinals October 29, 2010

I do not know of any active set theorists who think large cardinals are inconsistent. At least, within the realm of cardinals we have seriously studied. [Reinhardt suggested an ultimate axiom of the form "there is a non-trivial elementary embedding $j:V\to V$". Though some serious set theorists found it of possible interest immediately following it […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Nonessential use of large cardinals December 10, 2010

There is a fantastic (and not too well-known) result of Shelah stating that $L({\mathcal P}(\lambda))$ is a model of choice whenever $\lambda$ is a singular strong limit of uncountable cofinality. This is a consequence of a more general theorem that can be found in 4.6/6.7 of "Set Theory without choice: not everything on cofinality is possible", Ar […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for What definitions were crucial to further understanding? December 3, 2018

In set theory, definitely the notion of a Woodin cardinal. First, it is not an entirely straightforward notion to guess. Significant large cardinals were up to that point defined as critical points of certain elementary embeddings. This is not the case here: Woodin cardinals need not be measurable. If $\kappa$ is Woodin, then $V_\kappa$ is a model of set the […]

Andrés E. Caicedo

Math.StackExchange

Answer by Andrés E. Caicedo for Does there exist a sequence that has countably infinite convergent subsequences? August 21, 2019

Take $a_n=p$, where $p$ is the smallest prime dividing $n$. If a subsequence converges, it converges to a prime $p$, in which case except for finitely many initial terms, the sequence is eventually constant with value $p$. But the number of initial terms is arbitrary.

Andrés E. Caicedo

Answer by Andrés E. Caicedo for What is the consistency strength of generalized failure of the continuum hypothesis. April 14, 2019

The precise consistency strength of the global failure of the generalized continuum hypothesis is somewhat technical to state. As far as I know, it has not been published, but I think we have a decent understanding of what the correct statement should be. The most relevant paper towards this result is MR2224051 (2007d:03082). Gitik, Moti Merimovich, Carmi. P […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Is "integrability" equivalent to "having antiderivative"? March 9, 2014

There are integrable functions that are not derivatives: Any function that is continuous except at a single point, where it has a jump discontinuity, is an example. (Derivatives have the intermediate value property.) More interestingly, we can ask whether the existence of an antiderivative ensures integrability. The answer depends on what integral you are co […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Meaning of $0^{¶}$ in set theory May 2, 2019

$0^¶$ is the sharp for an inner model with a strong cardinal in the same sense that $0^\dagger$ is the sharp for an inner model with a measurable cardinal. In terms of mice, this is the first mouse containing two overlapping extenders. The effect of this is that, by iterating its top measure throughout the ordinals, you extend the bottom extender in a variet […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for ¿Is, for $1\le n May 1, 2019

Clearly $\omega^\omega\le(\omega+n)^\omega$. Also, $(\omega+n)^\omega\le (\omega^2)^\omega=\omega^{(2\cdot \omega)}=\omega^\omega$, and the equality follows. If you do not feel comfortable with the move from $(\omega^2)^\omega$ to $\omega^{(2\cdot \omega)}$, simply note the left-hand side is $\omega\cdot\omega\cdot\omega\cdot\dots$, where there are $2\cdot\o […]

Andrés E. Caicedo

	Anthea M. on No durians
	580 -Some choiceless… on 580 -Some choiceless results…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…
	Set theory seminar -… on Set theory seminar -Forcing ax…

A kind of library