Permutations of squares and finite fields

Question

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.$$

Answer 1

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<j}a_ia_j=0.$$ 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}$.

Answer 2

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$.