Rank-profile compression for finite-field time-series models

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 time-series model describes the evolution of a state from previous observations or states. Algorithmic complexity measures computation as a function of an encoded input's size, including state dimension, sample length, and parameter precision. Faster model fitting must preserve a stated output or approximation guarantee.

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 relevant algorithms and input model are not identified. No finite-field assumption, rank-profile compression method, or complexity bound is inferred from the catalogue title. The supplied catalogue marks this record partially solved; its present research status was not independently checked. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim.

Statement recorded in the supplied source.

Question 67 (Laubenbacher). What is the complexity of the algorithms used for time series modelling? How can we make the algorithms faster? [S2]

Source status.

The supplied catalogue labels this source record partially solved; 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 source asks about the complexity and speed of time-series algorithms.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001244 (AIM-COMPUTATION-0082). 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-0082. https://aimath.org/WWN/compalgstat/compalgstat.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 20001244 and code AIM-COMPUTATION-0082 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

AIM Question 67 does not identify a particular time-series algorithm or input encoding. The route below concerns exact fitting in a fixed feature dictionary over a field. Its cost is an arithmetic-operation bound for that subproblem, not a complexity classification of general time-series modelling.

Research attempt: An exact streaming compression route and its inconsistency trap

For $N$ sampled states, let $E\in K^{N\times r}$ contain feature evaluations and $Y\in K^{N\times d}$ the observed next states. Exact coefficient fitting asks for $C\in K^{r\times d}$ with $EC=Y$. A tempting acceleration keeps only a basis of rows of $E$. This loses contradictory responses unless the same dependencies are checked in $Y$. The smallest counterexample has \[ E=\begin{pmatrix}1\\1\end{pmatrix},\qquad Y=\begin{pmatrix}0\\1\end{pmatrix}. \] Either single row gives a solvable fitted system, while both rows require $C=0$ and $C=1$.

The corrected streaming algorithm stores an echelon basis of feature rows, together with the corresponding transformed response rows. Reduce each incoming pair $(e,y)$ by the stored pivot rows using identical row operations on its feature and response parts. If the reduced feature row is nonzero, normalize its new pivot and retain the pair. If it is zero and the response row is also zero, discard the pair. If it is zero and the response row is nonzero, report inconsistency.

Here is a correctness proof. Subtracting a stored equation from a new equation leaves their joint solution set unchanged, because the operation is reversible when the stored equation is retained. Scaling a row by a nonzero field element is similarly reversible. A zero feature and zero response row is the tautology $0=0$. A zero feature with a nonzero response row requires $0=y\ne0$ in at least one output coordinate, so no solution exists. Inductively the stored system has exactly the same coefficient solutions as all processed rows, unless a verified inconsistency was found. There can be at most $r$ stored rows because each retained row has a new feature pivot. After successful processing, back substitution and arbitrary choices of free coefficients describe every exact fit.

With dense row storage, an incoming row uses at most $r$ eliminations, each touching at most $r+d$ entries. Thus streaming reduction costs $O(Nr(r+d))$ field operations and stores $O(r(r+d))$ field elements. Feature evaluation and final coefficient reconstruction incur their own costs. For rational arithmetic this is not a bit-complexity bound: numerator and denominator lengths may grow. For noisy real measurements exact inconsistency is not evidence against every statistical model; it rejects only the exact deterministic fitting formulation.

Verification and adversarial audit

The two-row example detects the precise information lost by feature-only compression. The proof handles zero feature rows at the start, multiple response coordinates, and free coefficients. The operation count follows directly from the number and length of row eliminations.

Audit corrections.

Responses are carried through every row operation. Field-operation cost is not presented as bit complexity or as total time including feature generation.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

This is elementary exact linear algebra for a declared dictionary. Dictionary search, polynomial degree growth, approximate inference, noise handling, and unspecified source algorithms remain unresolved. No general speedup theorem is asserted.

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/compalgstat/compalgstat.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, repository-format review, and a model-assisted mathematical audit of the written arguments; 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 as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.