|
 |
[1] ai.viXra.org:2609.0017 [pdf] submitted on 2026-09-08 16:35:15
Authors: Marian Opial
Comments: 13 pages. Licensed under CC BY 4.0. AI-assisted.
For a finite set S of integers, its integer Turnpike data record the multiplicity of every positive difference. In the dense frequency-vector encoding, realizability reduces to parity of self-reciprocal irreducible factors and is therefore decidable in polynomial time by ordinary polynomial factorization. Sparse binary-exponent encoding is different: the associated reciprocal polynomial can have exponentially large degree. We construct an infinite family of sparse, coefficientwise nonnegative, Fourier-nonnegative, arithmetically admissible Turnpike instances with the fixed point count n = 107,520 that are nevertheless nonrealizable. Each instance contains, to odd multiplicity, a primitive noncyclotomic self-reciprocal irreducible of degree 2^k, while the sparse input length is Theta(k). Thus Fourier positivity, elementary count identities, and visible monomial-composition tests do not imply any polynomial bound on the degree of the remaining obstruction. Several complementary results locate the residual difficulty. Under the Turnpike scalar identities, an integral Hermitian sum of squares collapses to one binary rank-one factor; a parity-safe multiplier cannot raise the square-root-total/center ratio; and a strictly Fourier-positive integer NO instance can lie in the midpoint of two YES instances. Every odd self-reciprocal factor has infinitely many reciprocal quadratic shadows modulo primes, with a density lower bound in terms of permutation rank, but cyclotomic examples rule out naive small-prime enumeration. Finally, a ramified quadratic trace gadget converts a Legendre symbol into the desired characteristic-zero reciprocal-parity bit while preserving Fourier positivity. A local-to-global counterexample shows why this gadget does not yet yield a hardness reduction.
Category: Combinatorics and Graph Theory