Polynomially bounded forward search is unsound

Exact statement

There are signed permutation matrices of dimension $d$ whose least positive entrywise-nonnegative power is $\exp(\Theta(\sqrt{d\log d}))$ ; hence checking only polynomially many powers cannot decide power nonnegativity.

StatusProved by signed prime-cycle blocks

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

Context

A signed p-cycle with one negative edge first becomes nonnegative at exponent 2p. Block sums synchronize these periods by a least common multiple.

Proof or evidence

For distinct odd primes $p_i$ , the block sum has dimension $d=\sum_i p_i$ and least good exponent $2\prod_i p_i$ , which has the stated growth for the first k odd primes.

Signed-cycle lower-bound family →

Verification notes

The sign parity, least-common-multiple calculation, and distinction between exponent value and binary certificate length were checked. The first-hit formula was reproduced for p=3,5,7,11.

Limitations

This is not a complexity lower bound for the decision problem.
The construction only rules out a dimension-polynomial iteration cutoff.

Open work

Determine sharp certificate-size and least-hit bounds for restricted spectral classes.