# Bound on the weight of the minimum weight generator of [n,k] cyclic codes?

I'm looking at creating sparse generator matrices for cyclic codes of a given length and dimension. A generator matrix of an [n,k] cyclic code can be expressed as

$G = \begin{bmatrix}g_0 & g_1 & \cdots& g_{n-k-1}& 1 & 0 & \cdots & 0\\ 0 &g_0 & g_1 & \cdots& g_{n-k-1}& 1 & 0 & 0\\ \vdots & & \ddots & & & \ddots & \ddots &&\\0 & \cdots & 0& g_0 & g_1 & \cdots& g_{n-k-1}& 1\end{bmatrix}$

Where the generator polynomial of the code is $g(x) = g_0 + g_1 x + \cdots + g_{n-k-1}x^{n-k-1} + x^{n-k}$

To get some guarantees on what sparsities are possible for a given n and k, I'm looking for bounds (lower and upper) on the number of non-zero generator polynomial coefficients in the lowest weight generator polynomial for n and k.

Or relating to my original problem, are there bounds on the sparsity of $G$'s of the above form?

Considering only primitive polynomials over $\mathbb{F}_2$ as your generating polynomial candidate, there is a conjecture that there are infinitely many primitive trinomials.
So, it may well be the case that there is an infinite sequence $d_i\geq 1,$ and generating polynomials $g_i(x)=(1+x^{a_i}+x^{d_i})$ for which there is (at least) a corresponding set of lengths $n_{i}$, where $g_i(x)|(x^{n_i}+1)$, (due to existence of splitting fields) and the sparsity of each row of $G$ is 3.
By the way, it is conjectured but as far as I know unknown [as stated by Golomb as recently as in 2007] whether infinitely many binary primitive $m-$nomimals (where $m$ must be odd) exist or not, for any finite odd $m$.
• By the way, clearly $(x+1)$ divides any $x^n+1$ but I considered that a degenerate case and did not mention above since it generates the two word repetition code. One thing that's unclear to me, whether taking appropriate products of irreducible polynomials can result in constant low weight product polynomials infinitely often, due to cancellation. That's likely to be even harder to prove, in my opinion. Mar 13, 2015 at 0:02
• I'll definitely look into it! I have worries about these polynomials being divisors of $x^n - 1$. I don't think adding the condition that my generator be primitive gives any bonus and it restricts my search space. Trinomials would make good sparse generators though! Thanks for the help! Mar 16, 2015 at 15:18