A malformed composite record and an Artin--Schreier certificate family

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

A polynomial over a field is irreducible if it has no factorization into two positive-degree polynomials. An irreducibility certificate is auxiliary data checked by a verifier to establish this property. Sparse encoding lists only nonzero monomials and coefficients. A finite field $\mathbb F_q$ has $q=p^n$ elements; sums involving powers $x^{p^i}$ are linearized expressions, while products of such powers can represent quadratic forms over $\mathbb F_p$.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The source text joins distinct questions and loses exponent, summation, and probability notation. Its claimed hardness and fraction of inputs cannot be interpreted as a precise algorithmic promise from this extraction. The supplied catalogue marks this record open; its present research status was not independently checked. The extraction is labelled unrecoverable and is retained as a literal source record; no exact conjecture is reconstructed. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim. The supplied catalogue marks this record as unrecoverable. Its extract and terminology are documented, but a complete original problem has not been reconstructed.

Statement recorded in the supplied source.

1. Finding better certificates for irreducibility (a) Are there certificates for irreducibility that one can verify faster than the existing irreducibility tests? (Victor Miller's Question) (b) Can you exhibit families of sparse polynomials for which you can find shorter certificates? 2. Find a polynomial-time algorithm in log( q), where q = pn, that solves

∑n−1

i,j =0

ai,j xpi +pj

+ ∑n−1

i=0

bixpi

+ c in Fq (or shows no solutions) and works for 1

poly

of the inputs, and never lies. (We know that this is NP-complete.) (Jintai Ding's Question) 13 Factoring over Q[x]

3.1 Open Question [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness.

Short English statement

The extraction combines irreducibility-certificate questions and a finite-field equation-solving question.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001164 (AIM-COMPUTATION-0002). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 AIM Workshop Problem Lists, source linked by catalogue record AIM-COMPUTATION-0002. https://aimath.org/WWN/polyfactor/polyfactor.pdf.

Preparation and review.

The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 20001164 and code AIM-COMPUTATION-0002 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

The AIM polynomial-factorization PDF was consulted at Section 2.2. It contains separate certificate and finite-field equation questions. The damaged combined extraction and its unspecified success fraction remain unrepaired as an original target. The following is a clearly declared sparse-family test, not a reconstruction of the missing promise or a solution of the composite.

Research attempt: A sparse-family generalization fails under Frobenius iteration

The supplied prior preparation treats the familiar family $T^p-T-a$ using trace. An attempted enlargement replaces $p$ by $p^k$ while keeping a three-term description, hoping that a nonzero base-field trace would still certify irreducibility. It already fails over the prime field.

Let $a\in\mathbb F_p^\times$ and $f(T)=T^{p^k}-T-a$. If $\alpha$ is any root in an algebraic closure, then $\alpha^{p^k}=\alpha+a$. Inductively, \[ \alpha^{p^{jk}}=\alpha+ja\qquad(j\ge1), \] since Frobenius fixes $a$; at $j=p$ this yields $\alpha^{p^{pk}}=\alpha$. Thus its orbit under the ordinary $p$-Frobenius has length at most $pk$. To see directly that its minimal polynomial has degree at most this length, multiply $T-\alpha^{p^i}$ over one complete orbit. Frobenius permutes the factors and fixes the coefficients; an algebraic-closure element fixed by $c\mapsto c^p$ lies in $\mathbb F_p$, since $T^p-T$ has exactly its $p$ prime-field roots. The orbit product is therefore a polynomial over $\mathbb F_p$ annihilating $\alpha$. This proves the degree bound without assuming irreducibility of $f$.

Consequently if $p^k>pk$, $f$ cannot be irreducible: any root has a nonconstant minimal polynomial of smaller degree dividing $f$ (division with remainder and evaluation proves divisibility). This is a systematic obstruction, not a single accidental factor. In the first example $p=2,k=3,a=1$, \[ T^8+T+1=(T^2+T+1)(T^6+T^5+T^3+T^2+1) \quad\hbox{over }\mathbb F_2. \] The trace of $a$ to the prime field is $1$, yet the polynomial is reducible. Multiplying the displayed factors verifies every coefficient.

For $k=1$ the degree obstruction does not apply; it says $p\le p$. For $a=0$ the polynomial has the evident root zero, a separate boundary case. Therefore this calculation rejects only the proposed larger sparse family, not the known prime-degree trace criterion. Short sparse encoding alone does not preserve a valid irreducibility certificate as exponents grow.

The other bundled equation-solving question is untouched: a factorization obstruction for this family provides neither a promised fraction of solvable instances nor a never-incorrect polynomial-time solver for quadratic linearized expressions over the extension field.

Verification and adversarial audit

Frobenius iteration was checked for all integers $j$ symbolically, and the factorization was multiplied by Python over $\mathbb F_2$, giving low-to-high coefficients $(1,1,0,0,0,0,0,0,1)$. The proof distinguishes prime field coefficients from arbitrary extension-field coefficients, where $a$ need not be fixed by one Frobenius step.

Audit corrections.

A tempting extension of the prior Artin--Schreier calculation was explicitly falsified rather than asserted. Both the damaged extraction and untouched second question remain disclosed.

External computation.

Python 3.14.2 exact binary-coefficient multiplication of the two displayed factors produced T^8+T+1.

Scope and remaining gaps

The record is composite and unrecoverable as a single precise conjecture. No new certificate-size or verification-complexity theorem for the intended general family is proved, and the equation-solving promise remains unspecified. The first gap in this attempted sparse-family route is an actually irreducible family with a sound cheap verifier under a fully charged field representation.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://aimath.org/WWN/polyfactor/polyfactor.pdf (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved. This is a research attempt with an explicit failed route or restricted calculation, not a full solution, not a current-status certification, and not a claim that the elementary material is new. The catalogue's original source-status label is preserved independently of this attempt status.