Suppose on a 2 dimension infinite grid, all nodes, or equivalently, all $(p,q)$ points, where $p, q \in \mathbb Z$, need to be painted with a color.
Is there a way that, given enough kinds of paiting colors, e.g. $n$, all sqaures will have at least 2 colors? i.e we can avoid to have any square that all its 4 vertexes are painted in the same color?
Or... is this impossible?
Solution for rectangles (now removed from question): In an infinite grid, you require an infinite number of colours. See the closing note in Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle? giving the size of a grid required to produce such a rectangle for $n$ colours:
For $n$ colours, using the same approach, we would adopt a grid of $(n+1)$ rows and then require $n{n+1 \choose 2}+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columns to find a rectangle with same-coloured corners.
Work on mono squares:
While the numbers are too big for comfortable imagination, these notes from Gasarch (link) gives a direction to infer the existence of a monochrome grid-aligned square in a sufficiently large 2- or 3-colored grid.
One of the key parts of the proof in that paper requires a rather large grid to guarantee the existence of a mono-colored $L$ (three points of the same colour in the form of an $L$: $(x,y),$ $(x+d,y),$ $(x,y+d)$). I wanted to improve on this, at least for two colours and I think the process can apply for more:
Consider the top left to bottom right diagonal of a two-coloured $n\times n$ grid.
If there are three regularly spaced points of the same colour on this diagonal, there is a mono $L$ in the grid. Proof: Consider the points that would form an $L$ with each possible pairing of these three points. If one of these is the relevant colour, that is a mono $L$. If all three are the opposite colour, they form a mono $L$ in that opposite colour.
How long a diagonal do we need to force three regular-spaced points of the same colour? Experimentally the answer is $9$, forced from the following initial patterns (shown red):
$\mathtt {\color{red}{OOXO}OXX?}$
$\mathtt {\color{red}{OOXX}OOX?X}$
$\mathtt {\color{red}{OXOO}XOXX?}$
$\mathtt {\color{red}{OXOX}XOXO?}$
$\mathtt {\color{red}{OXX}OOXXO?}$
Where in each case the $\mathtt{?}$ creates a regularly-spaced triplet whether filled with $\mathtt{O}$ or $\mathtt{X}$.
Thus any 2-coloured $9\times 9$ grid contains a mono $L$, improving from the above paper's requirement for a $1539\times 1539$ grid for this condition.
To force a mono-$L$ in a three-coloured grid by the same technique you would thus need $10$ regular-spaced points on the diagonal, creating a sparse lower-half grid of a suitable size to force an $L$ in the remaining two colours. I'm not sure how big this would be but again it should be lower than the corresponding grid size in the paper ($\approx 3^{3^{34}}$).
Another observation: the diagonal sequences $\mathtt {OOXOO}$, $\mathtt {OOXXOO}$, or $\mathtt {OXOOXO}$ will also produce a mono $L$ due to the pairs of matched colours at the same spacing. Effectively the three evenly-spaced matching colours is a special case of these where the central point does double duty to left and right. Thus the minimum diagonal length to guarantee a mono $L$ comes down to $8$:
$\mathtt {\color{red}{OOXO}XX?}$
$\mathtt {\color{red}{OOXX}OXO?}$
$\mathtt {\color{red}{OXOO}XX?}$
$\mathtt {\color{red}{OXOX}XOO?}$
$\mathtt {\color{red}{OXX}OO?X}$
Some references for solved parts of this problem:
On Monochromatic Subsets Of A Rectangular Grid - a $5{\times} 5$ 2-coloured grid must have a mono $L$.
Extremal binary matrices without constant
2-squares - a $15{\times} 14$ 2-coloured grid must have a mono square
