18
$\begingroup$

Can one color the positive integers with finitely many colors, so that no two different numbers of the same color add to a square?

Some easy to prove remarks:

  1. at least 4 colors are needed, since the sum of any two in $\{386, 2114, 3970, 10430\}$ is square;

  2. if $N$ colors suffice for each finite subset, then $N$ colors suffice for all of $\mathbb{N}$;

  3. two colors suffice if the squares are replaced by the powers of $2$.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Equivalently, you are asking whether the addition Cayley graph induced on $\mathbb N$ by the set of perfect squares has a bounded chromatic number, right? $\endgroup$
    – Seva
    Commented Oct 24, 2022 at 11:11
  • 1
    $\begingroup$ Thomas Bloom's answer here shows remark 1 cannot be arbitrarily extended to give a negative answer to the question. $\endgroup$
    – mathworker21
    Commented Oct 24, 2022 at 11:54
  • $\begingroup$ @Seva, that sounds kind of right, but I have to admit that I'm not familiar with graph theory terminology, including the "induced" notion. $\endgroup$
    – Yaakov Baruch
    Commented Oct 24, 2022 at 23:28
  • $\begingroup$ @YaakovBaruch: the graph with $\mathbb N$ as a vertex set with two vertices adjacent whenever the corresponding sum is a square. $\endgroup$
    – Seva
    Commented Oct 25, 2022 at 6:48

2 Answers 2

Reset to default
17
$\begingroup$

No. See the paper below, which handles more polynomials than just perfect squares.

On the number of monochromatic solutions of $x+y = z^2$. Ayman Khalfalah and Endre Szemerédi. Combinatorics, Probability and Computing (2006) 15, 213–227.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I suspected that euristics pointed to a negative answer for squares and also higher powers, but I'm completely surprised by the actual result you mention. Great answer, and thank you also for your insightful comments elsewhere in the thread! $\endgroup$
    – Yaakov Baruch
    Commented Oct 24, 2022 at 15:24
  • 1
    $\begingroup$ @YaakovBaruch Thank you for the nice question; wasn't aware of this paper previously. $\endgroup$
    – mathworker21
    Commented Oct 24, 2022 at 18:33
6
$\begingroup$

Edit: the first part of this isn't correct, see the comments from Zach Hunter below. I misinterpreted the question.

We can partition the integers into squares and non squares, so it would be sufficient to show that the squares can be partitioned with no sums. See this MathOverflow post from a little while ago for a discussion on partitioning the integers without Pythagorean triples.

It seems that this is an open problem, and only in 2016 was it shown that the squares cannot be 2-coloured to avoid monochromatic Pythagorean triples. If the integers were partitioned to avoid square sums, then certainly the squares would be, and the existence of a finite partition is an open problem. So, I believe this problem is open!

Previous answer:

This is unfortunately not a complete answer, but a collection of ideas.

A sufficient condition would be a colouring such that there are no monochromatic solutions to $x+y=z$. Unfortunately, this does not exist: by Schur's theorem, any partition of $\mathbb{Z}^+$ into finitely many parts, one part contains $x,y,z$ such that $x+y=z$. One way to try and proceed with this could be to try and modify a proof of Schur's theorem.

Recently, Bloom and Maynard showed the following density result: if $A \subseteq [N]$ has no solution to $a-b=n^2$ where $a,b \in A$ and $n \geq 1$, then $|A| = O\left( \frac{N}{(\log N)^{c \log \log \log N}}\right)$. Furthermore, $|A+A|^{3/4} \leq |A-A| \leq |A+A|^{4/3}$ is known, suggesting that the situation for $A+A$ to be square free should not be 'that different' from $A-A$ being square free.

My guess is that the answer to your question is no, but I cannot prove it. Perhaps someone with more knowledge than me will be able to answer properly, but until then I hope these comments are somewhat helpful for investigation.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I believe you mean "necessary" rather than "sufficient". $\endgroup$
    – Zach Hunter
    Commented Oct 24, 2022 at 10:50
  • $\begingroup$ @ZachHunter for which bit? $\endgroup$
    – Fred T
    Commented Oct 24, 2022 at 10:53
  • $\begingroup$ in paragraph 2. but actually I think necessary is wrong too. since in the linked problem, it asks for $x,y,z$ all the same color with $x^2+y^2=z^2$ (partition regularity), where here it's asked for $x,y$ the same color with $x+y=z^2$. $\endgroup$
    – Zach Hunter
    Commented Oct 24, 2022 at 10:54
  • $\begingroup$ @ZachHunter but my point was, once you partition out the non squares (which clearly don't contain a solution) you just need to partition the square numbers. So we only have to worry about the case when $x,y$ are square, which is why I claim its equivalent to the Pythagorean triple problem. I may be wrong though, so if I misunderstood your comment let me know! $\endgroup$
    – Fred T
    Commented Oct 24, 2022 at 10:57
  • 2
    $\begingroup$ @YaakovBaruch The question you asked last in your last comment is open problem 23 on Ben Green's open problem list. $\endgroup$
    – mathworker21
    Commented Oct 24, 2022 at 11:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .