1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Zhi-Wei Sun Dec 2 '18 at 8:54
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Zhi-Wei Sun Dec 3 '18 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.