# Permutations of squares and finite fields

Let $$S_n$$ be the symmetric group of all permutations of $$\{1,\ldots,n\}$$, and let $$S(n)=\bigg\{\sum_{k=1}^nk^2\pi(k)^2:\ \pi\in S_n\}.$$ Motivated by Question 316142 of mine, here I ask the following question.

QUESTION 1: Is it true that for each integer $$n>4$$ the set $$S(n)$$ contains a complete system of residues modulo $$2n+1$$?

I conjecture that this question has a positive answer, and I have verified this for all $$n=5,6,\ldots,11$$.

If $$p=2n+1$$ is an odd prime, then the list $$1^2,2^2\ldots,n^2$$ gives all the $$n=(p-1)/2$$ quadratic residues modulo $$p$$. In view of this, I also formulate the following conjecture on finite fields.

Conjecture. Let $$\mathbb F_q$$ be a finite field of order $$q$$ with $$\text{ch}(\mathbb F_q)>3$$. Let $$a_1,\ldots,a_{(q-1)/2}$$ be all the $$(q-1)/2$$ nonzero squares in $$\mathbb F_q$$. Then $$\bigg\{\sum_{k=1}^{(q-1)/2} a_ka_{\pi(k)}:\ \pi\in S_{(q-1)/2}\bigg\}=\mathbb F_q.$$

QUESTION 2：Is my above conjecture for finite fields correct?

For the finite field $$\mathbb F_9=\mathbb Z_3[x]/(x^2+1)$$, the nonzero squares in $$\mathbb F_9$$ are $$a_1=1,\ a_2=-1,\ a_3=x$$ and $$a_4=-x$$. Note that $$\bigg\{\sum_{k=1}^4a_ka_{\pi(k)}:\ \pi\in S_4\bigg\}=\{0,\pm1,\pm x\}\not=\mathbb F_9.$$

• Note that the dot product of two vectors $(a_1,\ldots,a_n)$ and $(b_1,\ldots,b_n)$ is $\sum_{k=1}^na_kb_k$. – Zhi-Wei Sun Dec 2 '18 at 8:54

Using the notations of Sun and abc. If $$q\equiv 1\pmod 4$$ and $$q>9$$, since $$\prod_k(z-a_k)=z^{(q-1)/2}-1$$, then $$\sum_{k}(a_k)^2=(\sum_{k}a_k)^2-2\sum_{i It is known that any non-singular binary quadratic form over $$\mathbb{F}_q$$ can represent all non-zero elements of $$\mathbb{F}_q$$.
Given an $$\alpha=-\beta^2\in\mathbb{F}_q^{\times2}$$, there are some squares $$a,b$$ such that $$a-b=\beta$$. Then using the permutation $$\pi'_{a,b}$$, we get the desired result.
Given a non-square $$\gamma=-x^2-y^2$$, it is easy to see that $$\mid\{(u^2，v^2):\ u^2-v^2=x\}\mid \ge（q-1）/4.$$ When $$q$$ is large，there are many non-zero solutions $$u^2，v^2$$. Thus we can find four distinct square elements $$a,b,c,d$$ with $$a-b=x$$ and $$c-d=y$$. Then the desired result follows from the permutation $$\pi'_{a,b,c,d}$$.
Let $$A_q=\{x^2:x\in\mathbb{F}_q^{*}\}$$. Let $$\pi^{\prime}$$ be the permutation on $$A_q$$ defined by $$\pi^{\prime}(a_k)=a_{\pi(k)}.$$ Then $$\sum_{k=1}^{(q-1)/2}a_ka_{\pi(k)}=\sum_{a\in A_q}(a\pi^{\prime}(a))$$ so that if $$\pi$$ is the identity permutation $$\sum_{k=1}^{(q-1)/2}a_ka_{\pi(k)}=\sum_{a\in A_q}(a^2).$$ Hence if $$\pi$$ is the identity permutation and $$q$$ is a prime congruent to $$3\bmod 4$$, $$\sum_{k=1}^{(q-1)/2}a_ka_{\pi(k)}=\sum_{a\in A_q}(a)=0.$$ Let $$a\not=b$$ and $$\pi^{\prime}_{a,b}$$ be the transposition $$\pi^{\prime}_{a,b}(a)=b$$,$$\pi^{\prime}_{a,b}(b)=a$$ and $$\pi^{\prime}_{a,b}(c)=c$$, $$c\not=a,b$$. Hence if $$q$$ is a prime congruent to $$3\bmod 4$$, $$\sum_{m\in A_q}m\pi^{\prime}_{a,b}(m)=-(a-b)^2$$ where $$a,b\in A_q$$. Let $$\pi^{\prime}_{a,b,c,d}$$ be the product of two transpositions $$\pi^{\prime}_{a,b}$$, $$\pi^{\prime}_{c,d}$$, $$a,b,c,d$$ all distinct in $$A_q$$. Then if $$q$$ is a prime congruent to $$3\bmod 4$$, $$\sum_{k=1}^{(q-1)/2}a_ka_{\pi(k)}=\sum_{m\in A_q}(m\pi^{\prime}_{a,b,c,d}(m))=-(a-b)^2-(c-d)^2.$$ So for $$q$$ a prime congruent to $$3\bmod 4$$, $$\{\sum_{k=1}^{(q-1)/2}a_ka_{\pi(k)}:\pi\in S_{(q-1)/2}\}=\mathbb{F}_q$$ if every $$k\in\mathbb{F}_q$$ can be represented as $$k=(a-b)^2+(c-d)^2$$ where $$a,b,c,d$$ are distinct elements in $$A_q$$.
• If $p$ is an odd prime and $A=\{x^2:\ x\in\mathbb F_p\}$, then by the Cauchy-Davenport theorem we have $|A+A|\ge\min\{p,2|A|-1\}=p$ and hence $A+A=\mathbb F_p$. – Zhi-Wei Sun Dec 3 '18 at 13:28