On minimum Hamming weights in polynomial arithmetic progressions over $\Bbb F_q[x]$ Given $a(x),b(x)\in\Bbb F_q[x]$ consider the arithmetic progression $$a(x)+\gamma(x) b(x)$$ where $\gamma(x)\in\Bbb F_q[x]$. Is there a $\gamma(x)$ such that Hamming weight of $a(x)+\gamma(x) b(x)$ is less than Hamming weight of $b(x)$?
 A: Listing the following immediate observations.


*

*The answer is clearly not always. Consider the case of $b(x)=x^n$ and $a(x)$ some polynomial of degree $<n$. Because all the terms of the product $\gamma(x)b(x)$ have degree $\ge n$ we always have $w(a(x)+\gamma(x)b(x))\ge w(a(x))$. 

*On the other hand if $b(x)$ is a so called primitive polynomial of degree $n$, then the cosets of $x^t, 0\le t\le q^n-2$ are all distinct. In other words, unless $a(x)$ is divisible by $b(x)$ we can find a polynomial $\gamma(x)$ such that $a(x)-\gamma(x) b(x)=x^t$ has weight one. The exponent $t$ may be quite large here. Of course, when $b(x)\mid a(x)$ the zero polynomial will be in your arithmetic progression (perhaps more propely called a coset of an ideal). Anyway, in the case of a primitive $b(x)\neq x$ the answer to your question is affirmative. This may be what Hurkyl was hinting at in their comment.

*Don't know what happens in general. The second bullet does generalize a bit in the sense that any non-monomial polynomial $b(x)$ is a factor of a binomial of the form $x^i-x^j, i>j$. Furthermore, $j$ here is the highest power of $x$ dividing $b(x)$. So knowing minimal $i$ tells us how many cosets modulo $b(x)$ have a representative of the form $x^t$. It should be possible to use this to see how many cosets have representative of weight $\le1$.



The number of primitive polynomials of degree $n$ is equal to $\dfrac1n\phi(q^n-1)$. In particular this is always positive.
