# Problem about square permutation

A permutation $$P$$ of $$\{0,1, \dots n-1 \}$$ is called square permutation if $$P(i) + i$$ is a perfect square for all $$0 \leq i \leq n-1$$. Prove that:

if $$n=2023$$ and $$P$$ is a square permutation, then there exists $$i$$ such that $$3 \mid P(i) + i$$

My first thought was that it should be true for all $$n$$, but I've quickly recognized that it's not. For example, if $$n = k^2 + 1$$ for some $$3 \nmid k$$ then the permutation $$P(i) = k^2 - i$$ is square permutation (since $$P(i) + i = k^2$$) but $$3 \nmid P(i) + i$$ for all $$i$$.

Later, I've observed that a square permutation exists for all $$n$$. The proof by induction is quite direct: it is obviously true when $$n=1$$, then for any $$n > 1$$

1. select $$k$$ smallest so that $$k^2 \geq n-1$$,
2. for all $$i \geq k^2-n+1$$, set $$P(i) = k^2 - i$$, so $$P(i) + i = k^2$$ for all $$k^2 - n +1 \leq i \leq n-1$$.

The problem is reduced to construct a square permutation for $$n' = k^2 -n+1$$ which is smaller than $$n$$.

For example, $$n=12$$:

1. select $$k$$ = 4 (since $$4^2 = 16 \geq 12-1$$),
2. set $$P(i) = 16 - i$$ for $$5 \leq i \leq 11$$.

Now problem is reduced to $$n=5$$:

1. select $$k$$ = 2 (since $$2^2 = 4 \geq 5 - 1$$),
2. set $$P(i) = 4 - i$$ for $$0 \leq i \leq 4$$.

The square permutation constructed is: $$P=\Bigl(\begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 4 & 3 & 2 & 1 & 0 & 11 & 10 & 9 & 8 & 7 & 6 & 5 \end{matrix}\Bigr)$$

By this constructive proof, I've recognized that there are many cases of $$n$$ for which there is a square permutation so that $$3 \nmid P(i) + i$$ for all $$i$$. For example, in the example above, we have constructed a square permutation where $$P(i) + i$$ is either $$16$$ or $$4$$.

So $$2023$$ seems to be a special value, but I've no clue why.

Thanks for any hint.

NB. I believe that square permutation is first introduced in this paper. The proof for the existence is similar to mine.

It is actually simple. Suppose that $$3 \nmid P(i) + i$$ for all $$i$$, then $$P(i) + i \equiv 1 \pmod 3$$ for all $$i$$ (because $$P(i)+i$$ being a square implies $$P(i)+i\not\equiv 2\pmod 3$$). So
$$\sum\limits_{i=0}^{2023-1} (P(i) + i) \equiv 2023 \equiv 1 \pmod 3$$
$$\sum\limits_{i=0}^{2023-1} (P(i) + i) = 2 \times \sum\limits_{i=0}^{2023-1} i = 2022 \times 2023 \equiv 0 \pmod 3$$ So is a contradiction.
• You say that $3\nmid P(i)+i$ implies $P(i)+i\equiv1\pmod3$, but you could also have $P(i)+i\equiv2\pmod3$. Also, you never used the fact that $P$ is a square permutation. Commented Aug 3, 2023 at 18:34
• @MikeEarnest since $P(i) + i$ is a perfect square, so if $3 \nmid P(i) + i$ then $P(i) + i \equiv 1 \pmod 3$. Commented Aug 3, 2023 at 19:27