Expressions for binomial residue sum $\sum_{k=0}^n {n \choose k} x^k \left( \frac{k}{q} \right)$

Question

I'm interested in the sum:

$$\sum_{k=0}^n {n \choose k} x^k \left( \frac{k}{q} \right)$$

where $q$ is a prime number. This is just the binomial expansion with an extra weight on quadratic residues modulo $q$.

$\it{Motivation:}$

I was trying to find the number of solutions to $x_1^2 + ... + x_n^2 = 1$ with the added condition that $x_i$ and $x_j$ are all distinct modulo $q$.

You can use this formula: The number of solution of $x_1^2 + \cdots + x_k^2 \equiv \lambda \bmod q$

and apply inclusion exclusion on the solutions to get it down to more or less the sum in my question.

So solving the above sum would amount to the same thing as finding distinct $x_i \ne x_j$ solutions to $x_1^2 + ... + x_n^2 = 1$. If we can solve either problem I'd be very happy.

Answer 1

Let $f(k)$ be any periodic function of period $q$. For $0\leq m\leq q-1$ let \begin{eqnarray*} F_{n,m}(x) & = & \sum_{k\equiv m\,(\mathrm{mod}\,q)} {n\choose k}x^k\\ & = & \frac 1q\sum_{\zeta^q=1} \zeta^{-m}(1+\zeta x)^n. \end{eqnarray*} (The last sum is over all $q$th roots $\zeta$ of 1.) Then $$ \sum_{k=0}^n f(k){n\choose k}x^k = \sum_{m=0}^{q-1} f(m)F_{n,m}(x). $$ Setting $f(k)=\left( \frac kq\right)$ gives your sum, but this formula probably isn't of much use. I don't know if there is some simplification for this special value of $f(k)$.

Answer 2

I do not know about the original sum, but here is a perspective on the problem you mention as motivation.

Suppose you want to count solutions $\mathbf{x} \in \mathbb{F}_q^{n}$ to $F(\mathbf{x})=0$ that satisfy $x_i \neq x_j$ for all $i\neq j$. One can write $$\prod_{i<j}\mathbf{1}_{x_i \neq x_j} = \Delta(\mathbf{x})^{q-1}$$ where $\Delta(\mathbf{x}) := \prod_{i<j}(x_i-x_j)$. Then $$\sum_{\mathbf{x}:\, F(\mathbf{x})=0,\, x_i \neq x_j} 1 = q^{-1} \sum_{a \in \mathbb{F}_q}\sum_{\mathbf{x} \in \mathbb{F}_q^n} \Delta(\mathbf{x})^{q-1} \psi(a F(\mathbf{x}))$$ where $\psi$ is a fixed nontrivial additive character $\mathbb{F}_q \to \mathbb{C}$. For $F(\mathbf{x})=\sum_{i=1}^{n} x_i^2 -1$ this is $$ q^{-1} \sum_{a \in \mathbb{F}_q}\psi(-a)\sum_{\mathbf{x} \in \mathbb{F}_q^n} \Delta(\mathbf{x})^{q-1} \prod_{i=1}^{n}\psi(a x_i^2).$$ This resembles in many ways the famous Selberg integral.

(Some authors write $\Delta(\mathbf{x})$ for $\prod_{i<j}(x_i-x_j)^2$; I did not use this convention as $q$ might be even.)