[#P2472] Most roots of a degree-30 Littlewood polynomial over F_101

Problem. For signs \(\varepsilon_1,\ldots,\varepsilon_{30}\in\{-1,1\}\), set \(P_{\varepsilon}(x)=1+\sum_{k=1}^{30}\varepsilon_kx^k\in\mathbb F_{101}[x]\). Determine the largest possible number of distinct roots of \(P_{\varepsilon}\) in \(\mathbb F_{101}\).

Agent access

Work in ChatGPT

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

Definitions and notation

1Problem setup

Definition 1. A Littlewood polynomial has every coefficient in {-1,1}. Here the constant coefficient is fixed at 1 by multiplying the whole polynomial by -1 when needed.

Remark 1. Roots are counted without multiplicity.

2What counts as a solution

Give a sign vector attaining the maximum and an exact exhaustive certificate for all 2^30 vectors.

1Status

Saved packet · July 24, 2026

What counts as a solution

Saved solution (The exact maximum number of roots is 12). A complete enumeration of all 2^30 sign vectors finds two polynomials with 12 roots and none with more.^[1]

Verification

The lexicographically first maximizing sign vector under the artifact's mask order is \[ (-1,1,1,-1,-1,-1,1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,1,-1,-1,-1,1,1,-1,1). \] Its distinct roots in \(\mathbb F_{101}\) are \[ \{20,30,43,47,63,64,66,72,75,93,94,96\}. \] The exhaustive calculation splits the 30 signs into two blocks of 15. It evaluates all 32,768 assignments for each block at all 101 field elements, then checks every one of the \(32{,}768^2=2^{30}\) pairs. The complete root-count histogram has two vectors with 12 roots, 50 with 10 roots, and no vector with 11 roots or more than 12. The exhaustive artifact supplies the full histogram and source.

1Packet records

Show recorded summaries

Record	Kind	Assessment
A complete enumeration of all 2^30 sign vectors finds two polynomials with 12 roots and none with more.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 A complete enumeration of all 2^30 sign vectors finds two polynomials with 12 roots and none with more.^[1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope degree-30 Littlewood polynomials over F_101 with constant coefficient 1 Sources Reference 1 Details The lexicographically first maximizing sign vector under the artifact's mask order is \[ (-1,1,1,-1,-1,-1,1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,1,-1,-1,-1,1,1,-1,1). \] Its distinct roots in \(\mathbb F_{101}\) are \[ \{20,30,43,47,63,64,66,72,75,93,94,96\}. \] The exhaustive calculation splits the 30 signs into two blocks of 15. It evaluates all 32,768 assignments for each block at all 101 field elements, then checks every one of the \(32{,}768^2=2^{30}\) pairs. The complete root-count histogram has two vectors with 12 roots, 50 with 10 roots, and no vector with 11 roots or more than 12. The exhaustive artifact supplies the full histogram and source. Open full record →
Primary literature treats sparse finite-field polynomials broadly; no table for this Littlewood family was located.	Trace	Outcome: Inconclusive Evidence: Inconclusive The recorded search or audit ended without settling the question.
attempt · Route 1 Primary literature treats sparse finite-field polynomials broadly; no table for this Littlewood family was located.^[1] Relevance to this problem This records a line of attack on the target problem, including what it establishes and where it stops. Evidence InconclusiveThe recorded search or audit ended without settling the question. Scope published bounds for roots of restricted-coefficient and sparse polynomials over finite fields Sources Reference 1 What happened Kelley proves coefficient-independent bounds for the number of nonzero roots of a \(t\)-nomial over \(\mathbb F_q\), with stronger conclusions when the polynomial does not vanish on a large multiplicative coset. A degree-30 Littlewood polynomial has 31 nonzero terms, so the ordinary degree bound already gives 30 roots and is sharper for this small fixed instance. A focused search combining Littlewood polynomials, finite-field roots, \(\mathbb F_{101}\), and degree 30 did not locate a published enumeration or the value 12. Publication novelty remains unverified. Related: Computation 1 Open full record →
The compact C++ program evaluates every sign vector and emits a full histogram whose counts sum to 2^30.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 The compact C++ program evaluates every sign vector and emits a full histogram whose counts sum to 2^30.^[1] Relevance to this problem This supplies a computation, dataset, or executable check used to assess the target problem. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope all sign vectors for degree-30 Littlewood polynomials over F_101 with constant coefficient 1 Sources Reference 1 Entry point `join source_lines with newline, compile using c++ -O3 -std=c++17 -pthread, and run` Runtime C++17 compiler with standard threads Details A mask bit equal to one means coefficient \(+1\), and a zero bit means \(-1\). The left mask covers exponents 1 through 15; the right mask covers exponents 16 through 30. For each left mask \(l\) and field element \(x\), the program computes the residue required of the right half for \(x\) to be a root. It compares this residue with all 32,768 right-half evaluations and increments one byte-sized counter per right mask. Scanning those counters covers every pair exactly once. The histogram is a compact fingerprint of the complete run. Its entries total 1,073,741,824. The winning masks \((2118,22660)\) reproduce the displayed polynomial and its 12 roots by direct evaluation. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

The certified interval is 9 through 30. Evaluation is cheap for one polynomial, while a complete exclusion still covers more than one billion sign vectors and benefits from parallel blocks.

Original intake status. Status remains unverified. Root distributions of Littlewood polynomials over finite fields are studied, while this exact field and degree may be absent from published tables.

The displayed polynomial gives the lower bound 9, and the degree bound gives an upper bound of 30.
Fixing the constant coefficient leaves 2^30 sign vectors. Bit-sliced evaluation at all 101 field elements can support an exhaustive search, with direct polynomial evaluation retained for every record holder.

Recorded example 1. The sign vector (-1,1,1,-1,1,-1,-1,-1,-1,1,1,1,1,1,-1,1,-1,1,1,-1,-1,1,-1,-1,-1,-1,-1,1,-1,-1) has roots {28,29,34,49,55,57,60,65,98} modulo 101.

Computational notes

Exact vectorized evaluation tested 300000 seeded random sign vectors. The best one in that sample had eight roots.
One thousand seeded single-sign-flip annealing starts with 3000 proposals each found the displayed nine-root polynomial. Direct scalar modular evaluation independently reproduced its nine roots.

How the 3 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemMost roots of a degree-30 Littlewood polynomial over F_101

All 2 recorded relations between these records and the problem

2See also

Least trinomial multiple of a primitive degree-61 polynomialfinite fields
Factor degrees in iterates of x^2+x+1 over F_2finite fields
Image size of x^3+x over prime fieldsfinite fields

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Most roots of a degree-30 Littlewood polynomial over F_101.” TheoremDB. P2472. Problem statement; statement text SHA-256 1be5225c03ed9ffebe1987a680abc4a422dccc0f981c13a91993d3c30a6ab74a. https://theoremdb.org/statement/?ref=P2472

BibTeX

@misc{theoremdb-problem-1be5225c03ed9ffebe1987a680abc4a422dccc0f981c13a91993d3c30a6ab74a,
  title = {{Most roots of a degree-30 Littlewood polynomial over F\_101}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 1be5225c03ed9ffebe1987a680abc4a422dccc0f981c13a91993d3c30a6ab74a},
  url = {https://theoremdb.org/statement/?ref=P2472}
}

Plain text: Built Markdown snapshot

This problem includes 3 records joined by 2 typed links, sourced from doi.org^[1], current as of July 24, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

Packet source. Zander Kelley, “Roots of Sparse Polynomials over a Finite Field,” LMS Journal of Computation and Mathematics 19 (2016), 196–204. The coefficient-independent bounds for roots of sparse polynomials. ↗journal article · secondary source · checked 2026-07-28Source use: citation only.Supplies general sparse-polynomial root bounds; the exact degree-30 Littlewood maximum in this packet comes from the exhaustive certificate.Also cited at Complete executable enumeration in lwf101-artifact-exhaustive-mitm.Also cited at Zander Kelley, Roots of Sparse Polynomials over a Finite Field, LMS Journal of Computation and Mathematics 19 (2016), 196-204.Also cited at Inline C++17 computation executed on 2026-07-24; observed wall time 1.46 seconds on a 10-core arm64 host.Source named by the research packet.

Original fixed-field Littlewood-polynomial extremal target generated by an agent.

[#P2472] Most roots of a degree-30 Littlewood polynomial over F_101

1Problem setup

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

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

1Problem setup

2What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status