# P2904: Integral-root classification for Lloyd polynomials

- ID: `P2904`
- Reference: `lloyd-polynomial-integral-root-classification`
- Page: https://theoremdb.org/statements/P2904
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(q\) be a prime power, \(n\ge1\), and \(1\le t\le n\). Define the Lloyd polynomial \[L_{t,q,n}(x)=\sum_{j=0}^{t}(-1)^j\binom{x-1}{j}\binom{n-x}{t-j}(q-1)^{t-j},\] where generalized binomial coefficients are interpreted as polynomials in \(x\). Determine all triples \((q,n,t)\) for which \(L_{t,q,n}(x)\) has degree \(t\) and all of its \(t\) complex roots, counted with multiplicity, are distinct integers in \(\{1,\ldots,n\}\).

### Remarks

- **Remark.** For an indeterminate y and integer j>=0, the generalized binomial coefficient is binom(y,j)=y(y-1)...(y-j+1)/j!, with binom(y,0)=1.
- **Remark.** The Lloyd polynomial is a shifted Krawtchouk polynomial that supplies a necessary condition for a perfect t-error-correcting q-ary code.

### What counts as a solution

- Give a necessary-and-sufficient classification of all triples (q,n,t), with a proof that every listed polynomial has the required roots and every omitted triple fails at least one requirement.
- A computational component must use exact rational polynomial arithmetic and provide certificates for factorization, root integrality, distinctness, and the finite parameter ranges it eliminates.

## Status

Unresolved in this packet after the dated source check. Strongest checked result: The MathOverflow page has zero answers. Literature gives strong nonexistence conditions and classifications tied to perfect codes, but the dated search did not locate a classification of every parameter triple having the stated integral-root property. Exact unresolved remainder: Give a necessary-and-sufficient classification of all triples (q,n,t), with a proof that every listed polynomial has the required roots and every omitted triple fails at least one requirement. A computational component must use exact rational polynomial arithmetic and provide certificates for factorization, root integrality, distinctness, and the finite parameter ranges it eliminates. [3](#reference-3) [2](#reference-2) [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (Dated status and exact unresolved remainder).** Unresolved in this packet after the dated source check. Strongest checked result: The MathOverflow page has zero answers. Literature gives strong nonexistence conditions and classifications tied to perfect codes, but the dated search did not locate a classification of every parameter triple having the stated integral-root property. Exact unresolved remainder: Give a necessary-and-sufficient classification of all triples (q,n,t), with a proof that every listed polynomial has the required roots and every omitted triple fails at least one requirement. A computational component must use exact rational polynomial arithmetic and provide certificates for factorization, root integrality, distinctness, and the finite parameter ranges it eliminates.

The packet's cited sources and equivalent formulations were checked in the dated review recorded below.

Strongest checked result: The MathOverflow page has zero answers. Literature gives strong nonexistence conditions and classifications tied to perfect codes, but the dated search did not locate a classification of every parameter triple having the stated integral-root property.

Exact unresolved remainder: Give a necessary-and-sufficient classification of all triples (q,n,t), with a proof that every listed polynomial has the required roots and every omitted triple fails at least one requirement. A computational component must use exact rational polynomial arithmetic and provide certificates for factorization, root integrality, distinctness, and the finite parameter ranges it eliminates.

### Background and intake notes

Parameter sweeps produce exact factorizations and Diophantine constraints that are often omitted from final coding-theory papers. Storing them can prevent repeated searches and expose stable arithmetic families.

- Original intake status: UNKNOWN as of 2026-07-27. The MathOverflow page has zero answers. Literature gives strong nonexistence conditions and classifications tied to perfect codes, but the dated search did not locate a classification of every parameter triple having the stated integral-root property.
- On 2026-07-27 the Stack Exchange API reported zero answers, no accepted answer, and no closure for MathOverflow question 134715; the page contains no comments proposing a later resolution.
- Krasikov and Litsyn's 1996 work gives nonexistence conditions and upper bounds for integral zeros of binary Krawtchouk polynomials, a closely related partial result rather than the requested all-parameter classification.
- Shi, Krotov, and Solé, arXiv:2601.12818, restate Lloyd's integral-root condition as a central necessary tool for perfect-code classification; their broader association-scheme work does not classify all triples in this statement.
- A TheoremDB search for Lloyd polynomials, integral Krawtchouk zeros, and q-ary perfect-code root conditions found no duplicate.

- Recorded example: For q=2 and t=1, the polynomial is linear and its unique root is integral precisely when the corresponding explicit affine expression vanishes at an integer in {1,...,n}; higher t create genuinely coupled Diophantine conditions.

### Open directions

- **Route 1** (reported): Give a necessary-and-sufficient classification of all triples (q,n,t), with a proof that every listed polynomial has the required roots and every omitted triple fails at least one requirement. A computational component must use exact rational polynomial arithmetic and provide certificates for factorization, root integrality, distinctness, and the finite parameter ranges it eliminates. [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `lloyd-polynomial-integral-root-classification`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>MathOverflow question 134715, “Integral-root classification for Lloyd polynomials,” checked 2026-08-01. Question 134715 and all visible comments, checked through the Stack Exchange API on 2026-07-27. https://mathoverflow.net/questions/134715/when-does-the-lloyd-polynomial-have-only-integral-roots
   - Also cited at Full question, answers, and visible comments concerning Integral-root classification for Lloyd polynomials; checked 2026-08-01.
   - Also cited at Editorial research route recorded 2026-08-01.
   - forum; reference source; checked 2026-08-01
   - Source use: citation_only
   - Source used to formulate or check the problem record.
   - Source used to assess the problem's recorded status.
   - For Integral-root classification for Lloyd polynomials, the reviewed source scope is Full question, answers, and visible comments concerning Integral-root classification for Lloyd polynomials; checked 2026-08-01.. The packet makes no inference beyond that cited scope.
   - Source named by the research packet.
2. <a id="reference-2"></a>Minjia Shi, Jing Wang, and Patrick Solé, “Perfect codes in weakly metric association schemes,” arXiv:2601.12818 (2026). abstract on Lloyd-theorem nonexistence results for perfect codes in weakly metric schemes https://arxiv.org/abs/2601.12818
   - preprint; reference source; arXiv:2601.12818, checked 2026-08-01; checked 2026-08-01
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - For Integral-root classification for Lloyd polynomials, this source was excluded as status evidence because it does not classify integral-root triples for binary Hamming Lloyd polynomials; it is retained to document source-review history.
3. <a id="reference-3"></a>Ilia Krasikov and Simon Litsyn, “On Integral Zeros of Krawtchouk Polynomials,” Journal of Combinatorial Theory, Series A 74(1) (1996), 71-99. DOI 10.1006/jcta.1996.0038. main theorems restricting integral zeros of Krawtchouk polynomials https://doi.org/10.1006/jcta.1996.0038
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - For Integral-root classification for Lloyd polynomials, this source supplies direct root-arithmetic obstructions relevant to Lloyd polynomials without a classification of every (q,n,t).