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

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.