# P2662: Most irreducible constant slices of a sparse quintic over F_101

- ID: `P2662`
- Reference: `irreducible-quintic-f101-slices`
- Page: https://theoremdb.org/statements/P2662
- Record maturity: Reviewed problem with recorded work

## Problem

For nonzero \(a,b\in\mathbb F_{101}\), let \(N(a,b)\) be the number of \(c\in\mathbb F_{101}\) for which \(x^5+a x^2+b x+c\) is irreducible over \(\mathbb F_{101}\). Determine \(\max_{a,b\ne0}N(a,b)\).

### Problem setup

- **Definition.** Irreducible means having no factor of positive degree below five over F_101.
- **Remark.** Each pair (a,b) defines a slice of 101 polynomials indexed by c.

### What counts as a solution

- Give coefficients attaining the maximum and an exact sweep or theorem certifying every one of the 10000 slices.

## The answer

A complete sweep finds 29 irreducible quintics in each maximizing slice and certifies that every other slice has at most 28. [3](#reference-3)

**Review status:** Reproduced.

**Lean verification:** not Lean-verified.

### Verification

The answer is
\[
\max_{a,b\in\mathbb F_{101}^{*}}N(a,b)=29.
\]
Exactly 100 ordered pairs attain the maximum. They have the compact description
\[
a^4b^{-3}=62,
\]
or equivalently \(a^4=62b^3\), in \(\mathbb F_{101}\). The pair \((a,b)=(1,32)\) is one representative. Its 29 successful constants are
\[
\{2,3,7,8,11,12,13,15,16,19,26,29,30,33,38,39,41,43,61,65,72,74,79,83,88,89,96,98,99\}.
\]
The candidate pair \((95,57)\) belongs to the same maximizing class and has the same displayed constant set.

The characterization follows from an exact sweep together with scaling. For \(u\ne0\), substitution and normalization give
\[
u^{-5}f_{a,b,c}(ux)=f_{a u^{-3},b u^{-4},c u^{-5}}(x).
\]
This preserves irreducibility and leaves \(a^4b^{-3}\) unchanged. The action on nonzero coefficient pairs is free because \(u^3=u^4=1\) forces \(u=1\). Its 100-element orbits are exactly the fibers of \(a^4b^{-3}\). The exhaustive table has one maximizing orbit, with invariant 62.

Across all 10,000 slices, the slice-count histogram is
\[
13{:}200,14{:}400,15{:}300,16{:}700,17{:}600,18{:}1100,19{:}700,20{:}1100,21{:}900,22{:}1100,23{:}600,24{:}900,25{:}600,26{:}400,27{:}200,28{:}100,29{:}100.
\]
The counts sum to 10,000 slices. Those slices contain 204,200 irreducible polynomials in total.

## Work

### Proof and evidence for the resolution

**Computation 1 (The exact maximum slice count is 29).** A complete sweep finds 29 irreducible quintics in each maximizing slice and certifies that every other slice has at most 28.

The answer is
\[
\max_{a,b\in\mathbb F_{101}^{*}}N(a,b)=29.
\]
Exactly 100 ordered pairs attain the maximum. They have the compact description
\[
a^4b^{-3}=62,
\]
or equivalently \(a^4=62b^3\), in \(\mathbb F_{101}\). The pair \((a,b)=(1,32)\) is one representative. Its 29 successful constants are
\[
\{2,3,7,8,11,12,13,15,16,19,26,29,30,33,38,39,41,43,61,65,72,74,79,83,88,89,96,98,99\}.
\]
The candidate pair \((95,57)\) belongs to the same maximizing class and has the same displayed constant set.

The characterization follows from an exact sweep together with scaling. For \(u\ne0\), substitution and normalization give
\[
u^{-5}f_{a,b,c}(ux)=f_{a u^{-3},b u^{-4},c u^{-5}}(x).
\]
This preserves irreducibility and leaves \(a^4b^{-3}\) unchanged. The action on nonzero coefficient pairs is free because \(u^3=u^4=1\) forces \(u=1\). Its 100-element orbits are exactly the fibers of \(a^4b^{-3}\). The exhaustive table has one maximizing orbit, with invariant 62.

Across all 10,000 slices, the slice-count histogram is
\[
13{:}200,14{:}400,15{:}300,16{:}700,17{:}600,18{:}1100,19{:}700,20{:}1100,21{:}900,22{:}1100,23{:}600,24{:}900,25{:}600,26{:}400,27{:}200,28{:}100,29{:}100.
\]
The counts sum to 10,000 slices. Those slices contain 204,200 irreducible polynomials in total.

### Background and intake notes

A slice is a natural independent work unit, and every positive test has a short finite-field certificate.

- Original intake status: Status remains unverified. Counts of irreducible polynomials with prescribed coefficients are well studied, while this exact finite slice maximum may lack a published value.
- Run Rabin irreducibility tests for all 10000 nonzero coefficient pairs and their 101 constants. Preserve per-slice counts and exact modular-power traces for every record.
- Trap: absence of a root does not prove a quintic irreducible, since it may factor as an irreducible quadratic times an irreducible cubic.

- Recorded example: For (a,b)=(95,57), the 29 successful constants are [2,3,7,8,11,12,13,15,16,19,26,29,30,33,38,39,41,43,61,65,72,74,79,83,88,89,96,98,99].

### Prior approaches

- **Route 1** (inconclusive): Rabin supplies the exact test, and prescribed-coefficient papers place the family in a well-studied class. This audit found no published value for the fixed maximum. [1](#reference-1) [3](#reference-3) [2](#reference-2)

### Runnable artifacts

- **Artifact 1** (reproduced): A dependency-free C++17 program tests every polynomial, records every successful constant, and cross-checks two finite-field irreducibility criteria. [3](#reference-3)

### Computational notes

- Exact Rabin tests verified all 29 displayed quintics, giving a lower bound of 29. For fixed a,b, the map x->x^5+a*x^2+b*x has image size at least ceil(101/5)=21. Every c producing an irreducible quintic must avoid the negative of this image, so N(a,b)<=80.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `irreducible-quintic-f101-slices`, 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.

## Lean verification

An informal proof is recorded. A Lean formalization still needs to be attached.

[Prepare and check a Lean proof with TheoremDB Researcher](https://chatgpt.com/g/g-6a6c206c5acc8191b184bb55fb72c5b3-theoremdb-researcher?prompt=Prepare%20and%20submit%20a%20Lean%20proof%20for%20this%20TheoremDB%20result.%0A%0AExact%20problem_ref%3A%20irreducible-quintic-f101-slices%0A%0AExact%20title%3A%20Most%20irreducible%20constant%20slices%20of%20a%20sparse%20quintic%20over%20F_101%0A%0ACanonical%20packet%3A%20https%3A%2F%2Ftheoremdb.org%2Fstatements%2Firreducible-quintic-f101-slices%2F%23lean-verification%0A%0AStart%20with%20prepareLeanProof%20for%20this%20exact%20problem_ref.%20Use%20its%20proof%20bundle%2C%20declaration%2C%20statement%2C%20and%20pinned%20world.%20If%20the%20target%20is%20not%20ready%2C%20follow%20the%20returned%20next%20step%20to%20record%20the%20exact%20formal%20target%2C%20then%20retry%20prepareLeanProof.%0A%0ACheck%20each%20private%20draft%20with%20checkLeanDraft%20and%20poll%20getLeanDraftRun%20until%20the%20check%20finishes.%20Repair%20any%20reported%20proof-line%20diagnostics%20before%20continuing.%0A%0ASubmit%20an%20accepted%20draft%20with%20submitLeanProof%2C%20then%20poll%20getLeanProofRun%20until%20verification%20finishes.%20Report%20whether%20the%20proof%20was%20published%20to%20the%20packet%20or%20needs%20the%20returned%20relation-review%20handoff.).

## References

1. <a id="reference-1"></a>Robert Granger, On the Enumeration of Irreducible Polynomials over GF(q) with Prescribed Coefficients, Finite Fields and Their Applications 57 (2019), 156-229; Michael O. Rabin, SIAM Journal on Computing 9 (1980), 273-280; Zhicheng Gao, Simon Kuttner, and Qiang Wang, Finite Fields and Their Applications 80 (2022), 102023 https://doi.org/10.1016/j.ffa.2019.01.001
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Most irreducible constant slices of a sparse quintic over F_101, the reviewed source scope is Robert Granger, On the Enumeration of Irreducible Polynomials over GF(q) with Prescribed Coefficients, Finite Fields and Their Applications 57 (2019), 156-229; Michael O. Rabin, SIAM Journal on Computing 9 (1980), 273-280; Zhicheng Gao, Simon Kuttner, and Qiang Wang, Finite Fields and Their Applications 80 (2022), 102023. The packet makes no inference beyond that cited scope.
2. <a id="reference-2"></a>Zhicheng Gao, Simon Kuttner, and Qiang Wang, “Counting irreducible polynomials with prescribed coefficients over a finite field”. Finite Fields and Their Applications 80 (2022), 102023. DOI 10.1016/j.ffa.2022.102023. Full journal article relevant to Most irreducible constant slices of a sparse quintic over F_101. https://doi.org/10.1016/j.ffa.2022.102023
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Most irreducible constant slices of a sparse quintic over F_101: Provides a source or neighboring result used in the packet for “irreducible quintic f101 slices.”
3. <a id="reference-3"></a>Michael O. Rabin, Probabilistic Algorithms in Finite Fields, SIAM Journal on Computing 9 (1980), 273-280; exact executable sweep run on 2026-07-25 Complete exact sweep in iqf101-artifact-rabin-sweep https://doi.org/10.1137/0209024
   - Also cited at Michael O. Rabin, Probabilistic Algorithms in Finite Fields, SIAM Journal on Computing 9 (1980), 273-280; exact executable sweep run on 2026-07-25
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Provides Rabin's finite-field irreducibility test used to cross-check the packet's complete computation over F_101.