Coloring the n-smooth numbers with n colors

February 5, 2019

Péter Pál Pach, my former master’s student Thomas A. C. Chartier and myself have just submitted our paper Coloring the n-smooth numbers with n colors. Meanwhile, you can access it through my papers page, or at the ArXiv.

The paper discusses the current status of a question asked by Pach around 10 years ago. I found out about the problem when Dömötör Pálvölgyi asked about it on MathOverflow. Chartier was my master’s student at Boise State and I suggested to him to work on this problem. His thesis covers the results we obtained in the process, see here. At some point I thought it seemed reasonable to publish the current partial results and contacted Pach to check whether he was indeed the originator of the problem. He mentioned he was thinking of doing the same, so we decided to exchange notes and expand what we had, and this paper is the result.

The question is the following: given n, can we color the positive integers using precisely n colors in such a way that for any a, the numbers a,2a,\dots,na all receive different colors?

The problem remains open in this generality. We discuss the cases where a positive answer is known and several related problems. The results involve combinatorics, number theory and group theory. We also discuss a nice reformulation in terms of tilings that ends up being quite helpful.

Comments are welcome!



February 1, 2019

Partiti is a puzzle created by Thinh Van Duc Lai, a Vietnamese puzzle enthusiast most of whose puzzles involve mathematics in some form. His work has been featured in The New York Times, see here. Partiti puzzles appeared on Mathematics Magazine throughout 2018.

Brittany Shelton and I coauthored a short piece introducing the puzzle to the Magazine readers at the invitation of Michael Jones, the magazine editor and a colleague at Mathematical Reviews. It is titled Of puzzles and partitions. Introducing Partiti, and can be found on the arXiv or through my papers page.