A quadratic form

Question

Let $q$ be a power of 2. Let $P$ be the set of polynomials in $F_q [x]$ of degree d or less. Let $\mathbb{Z}$ be the ring of integers. For any $f \in P$, let $\psi(f)$ be the number of distinct roots of $f$ in $F_q$. Note that $\psi(0) = q$.

For any map $A$ from $P$ to $\mathbb{Z}$, one can compute the summation $$\sum_{f, g \in P} A(f)A(g) \psi (f+g).$$ My question is: what is the minimum positive value of the summation?

For $d=0,1$, the minimum is $q$. What happens if $d$ is bigger? I am especially interested in the case when d=q/2-1.

Thanks a lot,

Qi

Answer 1

For $d=q-1$, let $f$ be a polynomial vanishing at all points of $\mathbb F_q$ except $0$. Let $f_1$ $f_2$ such that $f_1+f_2=f$, and define $A$ such that $A(f_1)=1$ and $A(f_2)=-1$ and $A(g)=0$ for all other $g$. Then, the only terms surviving are

$$A(f_1)A(f_2)\phi(f_1+f_2)+A(f_2)A(f_1)\phi(f_2+f_1)+A(f_1)^2\phi(2f_1)+A(f_2)^2\phi(2f_2).$$

Then, we can compute the value to be

$$-\phi(f)+-\phi(f)+\phi(0)+\phi(0)=-(q-1)+-(q-1)+q+q=2.$$

Now, I can't prove that this is minimal, but this does show that $q$ isn't minimal for all $d$.

I'll edit this answer if I come up with anything for the $\frac{q}{2}-1$ case.

EDIT: Whenever 2 can be achieved, it is minimal, because the value must be an even number. The summation breaks up to $\sum_{f\neq g} A(f)A(g)\phi(f+g)+\sum_f A(f)^2\phi(2f)$. The latter is a multiple of $q$, which is even, so it suffices to show that the first sum is even. For all $f,g$, we get two terms, $A(f)A(g)\phi(f+g)$ and $A(g)A(f)\phi(f+g)$ that are equal, and, being equal integers, their sum is even. Every term in the first sum is of this form, and so the first sum must be even. So we have a sum of even integers, so the minimal number must be even, so the example above shows that 2 is minimal for $d=q-1$. In fact, it shows that 2 is minimal for $d\geq q-1$, by just throwing in extra copies of the fact $x-1$.

Still haven't worked it out for $d$ less than $q-1$, but there's a proof for large $d$.

Edit 2: In fact, the same line of argument shows that for $d$ less than $q$, we can bound above by $2(q-d)$, so for $d=q/2-1$, we can bound above by $2q-2(q/2-1)=2q-q+2=q+2$, don't yet know if this is sharp.

Answer 2

(Inspired from Charles Siegel's answer) what you can do for the $d=\frac{q}{2}$ case is:

Divide the $q$ elements of $F_q/\{0\}$ into two parts $\{\alpha_{1},\dots, \alpha_{\frac{q}{2}}\}$ and $\{\beta_1,\dots,\beta_{\frac{q}{2}-1}\}$ so that $\prod \alpha_i\neq \prod \beta_j$. Denote $S(x)=\prod (x-\alpha_i)$ and $T(x)=\prod(x-\beta_j)$. Let $r_1(x)+r_2(x)=S(x)+T(x)$ be arbitrary and $f_1=S+r_1,f_2=S+r_2$. Now we let $A(f_1)=A(f_2)=1,A(r_1)=A(r_2)=-1$ and all other $A(g)=0$. The quadratic form has the value $$-2\psi(f_1+r_1)-2\psi(f_1+r_2)-2\psi(f_2+r_1)-2\psi(f_2+r_2)+4\psi(r_1+r_2)+4q=4$$

I don't know if this can be lowered to 2...