Effective hidden dimension for arbitrary polynomial invariants

Exact statement

It remains open here whether one can compute, from an arbitrary rational polynomial $p$ , a finite state bound sufficient to find a nontrivial rational linear loop whenever one exists; no uniform bound $N(d,D,L)$ or $N(d)$ is established either.

StatusOpen after checking the graph, quadratic, pure-difference-binomial, and bit-bounded subclasses

External reviewNo documented external or specialist review of this FPRD exposition is recorded.

Context

Published work solves substantial subclasses but does not supply an arbitrary-polynomial bound on hidden coordinates.

Hypotheses and scope

p is an explicitly encoded rational polynomial.
The desired witness has an infinite visible orbit.

Proof or evidence

ISSAC 2023 handles pure-difference binomials; STACS 2024 decides affine synthesis for one quadratic equation; POPL 2025 proves PSPACE decidability for bit-bounded synthesis and NP at fixed program dimension. None states the requested arbitrary-polynomial hidden-dimension bound.

What remains open →

Verification notes

The subclass hypotheses and the distinction between fixed dimension and a computed dimension bound were checked against the primary sources.

Limitations

This is a bounded literature-status conclusion, not a universal novelty claim.
A future theorem must choose one explicit quantifier pattern.

Open work

Formalize the target parameterization, then minimize d+r(u)-q(u) over all infinite rational C-finite orbits in V(p).