MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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,


share|cite|improve this question
Surely there must be conditions on $A$ of some sort? You can't mean a map of rings, as there won't be any other than the zero map. – Charles Siegel Jan 12 '10 at 23:02
No it is not map of rings. No condition on A Qi – user3208 Jan 12 '10 at 23:14
You can call it an integer-valued function on P. – S. Carnahan Jan 13 '10 at 0:11

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


Then, we can compute the value to be


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.

share|cite|improve this answer

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

share|cite|improve this answer

Wait, are there any additional restrictions on A? Because it seems like if there aren't, the smallest positive possibility should always be 1 for $d \geq 1$, since you can just take $A(X) = 1$ and $A(g) = 0$ for all other $g \in P$... (except in characteristic 2)

(This would be a comment, but I don't have the rep for it. I assume that rule's meant to keep out spam bots?)

edit: doh, didn't see the "let q be a power of 2". In that case I'm reasonably sure it'll always be q; it certainly can't be more.

share|cite|improve this answer
In my question, the characteristic is 2. Qi – user3208 Jan 12 '10 at 23:12
Jakob, I came up with an example (below) where it is 2. I think that THAT is minimal, but I can't prove it yet. – Charles Siegel Jan 13 '10 at 2:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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