[#P2904] Integral-root classification for Lloyd polynomials

Contents

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\}\).

An illustration accompanying the statement of Integral-root classification for Lloyd polynomials. — An illustration accompanying the statement. The statement alone defines the problem.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

1Context

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.

2Remarks

Remark 1. 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 2. The Lloyd polynomial is a shifted Krawtchouk polynomial that supplies a necessary condition for a perfect t-error-correcting q-ary code.

3What 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.

1Status

Saved packet · August 1, 2026

What counts as a solution

Saved packet status (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.^[3][2][1]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 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][2][1] Relevance to this problem For Integral-root classification for Lloyd polynomials, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 3, Reference 2, Reference 1 Details 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. Open full record →
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.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 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] Relevance to this problem For Integral-root classification for Lloyd polynomials, record lloyd-polynomial-integral-root-classification-next-route-20260801 (“Complete the stated acceptance conditions”) documents a concrete method, search boundary, or failed route. The record states: 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. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Work against the displayed statement and preserve every hypothesis and quantifier. 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. Any computation must retain a replayable witness and a matching exclusion or completeness certificate. Open full record →
No records match these filters.

Notes and companion material

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.
Independent source, duplicate, exact-title, and equivalent-formulation review completed on 2026-08-01.

Recorded example 1. 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.

2See also

A 368-word code in the fifth strong power of the 7-cyclecoding theory
A binary q-analog of the Fano planecoding theory
An extremal Type II binary code of length 72coding theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Integral-root classification for Lloyd polynomials.” TheoremDB. P2904. Problem statement; statement text SHA-256 5f2d57236a3872dea3b2f099e87c453b1964e217d2d9739e37fc896dc1d451b0. https://theoremdb.org/statement/?ref=P2904

BibTeX

@misc{theoremdb-problem-5f2d57236a3872dea3b2f099e87c453b1964e217d2d9739e37fc896dc1d451b0,
  title = {{Integral-root classification for Lloyd polynomials}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 5f2d57236a3872dea3b2f099e87c453b1964e217d2d9739e37fc896dc1d451b0},
  url = {https://theoremdb.org/statement/?ref=P2904}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 2 typed links, sourced from mathoverflow.net^[1], current as of August 1, 2026.

1References

Packet source. MathOverflow question 134715, “Integral-root classification for Lloyd polynomials,” checked 2026-08-01. Question statement, visible answers and comments, or the linked article sections described in the source record. ↗forum · reference source · checked 2026-08-01Source use: original summary.Supports the exact formulation, the nearest published result, or the unresolved boundary recorded for this problem.Also cited at Question 134715 and all visible comments, checked through the Stack Exchange API on 2026-07-27.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.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.
Minjia Shi, Jing Wang, and Patrick Solé, “Perfect codes in weakly metric association schemes,” arXiv:2601.12818 (2026). Question statement, visible answers and comments, or the linked article sections described in the source record. ↗preprint · primary source · arXiv:2601.12818, checked 2026-08-01 · checked 2026-08-01Source use: original summary.Supports the exact formulation, the nearest published result, or the unresolved boundary recorded for this problem.Also cited at abstract on Lloyd-theorem nonexistence results for perfect codes in weakly metric schemes.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.
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. Question statement, visible answers and comments, or the linked article sections described in the source record. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Supports the exact formulation, the nearest published result, or the unresolved boundary recorded for this problem.Also cited at main theorems restricting integral zeros of Krawtchouk polynomials.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).

Original CC0 textbook restatement.

Discussion

Loading discussion.

[#P2904] Integral-root classification for Lloyd polynomials

1Context

2Remarks

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Remarks

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance