Take the 2-minute tour ×

For a $t$-error correcting code of length $n$ over the finite field $\mathbb{F}_q$, the Lloyd polynomial is given by $$ L_t(n,x):=\sum_{j=0}^t(-1)^j\binom{x-1}{j}\binom{n-x}{t-j}(q-1)^{t-j}. $$ A well-known theorem by Lloyd and Lenstra is, that if the code is perfect, then $L_t(n,x)$ has $t$ distinct integral zeros among $1,2,\ldots ,n$. The converse is not true in general. For example, with $q=2$, $t=2$ we have $L_2(n,x)=2x^2+2(n+1)x+\frac{n^2+n+2}{2}$. This has integral roots if and only if $n=\ell^2+1$ for some integer $\ell$.

Question: What necessary, or sufficient conditions are known for the Lloyd polynomial to have only integral roots ? What else is known on integer roots for the Lloyd polynomial ?

share|improve this question

Your Answer



Browse other questions tagged or ask your own question.