Source repair and a sharp quadratic specialization theorem

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.

Polynomial factorization writes a polynomial as a product of irreducible factors over a specified coefficient field. Absolute factorization allows an algebraic closure. A lattice basis is a finite set of independent integer vectors generating a discrete additive subgroup; basis reduction seeks a geometrically better basis. Approximate factorization instead measures distance between coefficient vectors after a norm is chosen. Structured condition numbers quantify sensitivity under perturbations respecting a matrix's defining structure.

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 extraction merges most of two PDF pages, including dense and sparse factorization, number-field factors, approximation, and unnamed challenge problems. Broken degree inequalities and missing norms prevent one exact target; these topics remain separate source questions. 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. How long does the gradual feeding (or some modification) algorithm actu-ally take to solve one approximate linear equation (with the ci's bounded by kn bits)? (Mark van Hoeij's Question) 2. (a) Can we do lattice basis reduction in essentially linear time in the total number of digits of the input? (Dan Bernstein's Question) (b) Is there a softly linear time reduction from linear system solving to basis reduction in lattices? (Joachim von zur Gathen's question)

3.2 Open Question

Can we use Niederreiter's equation to find a faster algorithm to factor dense polynomials in Q[x]? (Shuhong Gao's Question) The main possible advantage of such a technique would be to use linear algebra over Fp instead of lattice basis reduction.

4 Bivariate

4.1 Open Question

For Dense Bivariate polynomials over Fp with total degree, t: Can we improve on the probabilistic complexity ˜O$ d3$ + Factorization Complexity of Univariate, degree d, polynomial. Lecerf believes ˜O( dω ) is possible. The bottleneck is solving d2 equations in d variables.

4.2 Open Question

Can we find low-degree ( ≤ n) factors of a polynomial with t terms and degree

d $t d2, n d$

4.3 Open Question

Find an Absolute Factorization (or test for irreducibility) over fields with small $p < d 2$ characteristic, in ˜O$ d3$.

5 Intermezzo

Given f ∈ Q[x] irreducible, and f (α) = 0. Factor f over Q[α]. State of Art: Belabas 26 Numerical

6.1 Open Question

Challenge Problem #1 in Kaltofen's JSC 2000 paper.

6.2 Open Question

Given f ∈ C[x, y ] find the nearest polynomial that factors into linear factors in

C[x, y ]. Find/Bound the distance to the nearest polynomial that factors.

6.3 Open Question

Given f ∈ Q[x, y, z ], for which values of z ∈ Q does f factor (completely) in

C[x, y ]? What is the degree of a given z?

6.4 Open Question

How to compute/approximate the structured condition number of a Ruppert Matrix. 3 [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

This composite records several questions about lattice reduction, polynomial factorization, and numerical sensitivity.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001165 (AIM-COMPUTATION-0003). 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-0003. 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 20001165 and code AIM-COMPUTATION-0003 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 PDF was consulted across Sections 3.1--6.4, confirming the composite nature of this record. Section 6.2 asks a nearest-factorable-polynomial question without supplying a norm in the extracted statement. The following calculation chooses a norm and degree explicitly, while leaving every other bundled question and the unrestricted degree case intact.

Research attempt: A norm-specific quadratic distance calculation

For an affine quadratic $f(x,y)$ homogenize with a new variable $t$ and write $F(x,y,t)=w^TQw$, $w=(x,y,t)^T$, with $Q$ a symmetric $3\times3$ matrix. Choose the norm $\|F\|=\|Q\|_F$, the Frobenius matrix norm; off-diagonal coefficients are therefore weighted differently from a plain monomial-coefficient Euclidean norm. Permit homogeneous products of two linear forms, including degenerate cases, so that their dehomogenizations have degree at most two.

A homogeneous quadratic splits into two linear forms over $\mathbb C$ if and only if its symmetric matrix has rank at most two. In one direction, $F=(u^Tw)(v^Tw)$ has matrix $(uv^T+vu^T)/2$, of rank at most two. Conversely, a symmetric bilinear form over $\mathbb C$ can be reduced by completing squares: if a diagonal entry is nonzero, eliminate its row and column by a linear change; if all diagonal entries vanish but some entry is nonzero, the sum of its two basis vectors has nonzero self-pairing and becomes the first basis vector. Repeat. This gives a sum of $r$ independent squares, where $r$ is the rank. For $r=2$ it factors as $(z_1+iz_2)(z_1-iz_2)$, and rank one or zero is immediate. Thus the degree-two target is exactly $\det Q=0$.

For a real symmetric input $Q$ with eigenvalues $\lambda_1,\lambda_2,\lambda_3$, the distance, in the chosen norm, to complex symmetric singular matrices is \[ \min_j|\lambda_j|. \] Indeed let $B$ be any singular complex symmetric matrix and choose a unit complex vector $v$ with $Bv=0$. Then $\|Q-B\|_F\ge\|(Q-B)v\|=\|Qv\|\ge\min_j|\lambda_j|$, the last inequality following by expressing $v$ in an orthonormal real eigenbasis of $Q$. If $e_j$ is a unit eigenvector of smallest absolute eigenvalue, the real symmetric matrix $B=Q-\lambda_je_je_j^T$ is singular and has exactly that Frobenius distance. This proves attainment as well as the formula.

For example $f=x^2+y^2+1$ has $Q=I_3$, so the distance is one. The polynomial $x^2+y^2=(x+iy)(x-iy)$ attains it by removing the $t^2$ coefficient. This actually solves the stated restricted optimization, including possible complex perturbations; it is elementary linear algebra, with no novelty claim.

The attempted generalization would identify arbitrary complete factorization with one symmetric-matrix rank constraint. This is where it stops: the representation by a quadratic form used the exact degree two, and no analogous rank characterization or distance formula has been established for the higher-degree products in the source. Changing the coefficient norm also changes the optimization, so the formula cannot be substituted into the unqualified original question.

Verification and adversarial audit

Both implications in the rank criterion were proved, including rank zero and rank one. The lower bound allows complex perturbations, while the attaining matrix is real. The example's constant term removal was checked explicitly. No numerical optimization, factorization benchmark, or claimed complexity improvement for the other sections was performed.

Audit corrections.

The norm, degree, coefficient field of the input and allowed complex perturbations were stated explicitly; this restricted known linear-algebra calculation was not called a solution of the composite.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

All lattice-reduction, dense/sparse factorization, specialization and condition-number questions in the composite remain. Even Section 6.2 is only treated for real quadratic input in a specified matrix norm. The first gap is an appropriate general-degree algebraic description and a globally justified nearest-point computation in an agreed coefficient metric.

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.