Exact period-quotient reduction and unary lift cost for hidden shift on Z^d

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

A hidden-shift instance consists of functions $f_0,f_1$ on a group $G$ related by $f_1(x)=f_0(xs)$ for an unknown shift $s$, with the additive version $f_1(x)=f_0(x+s)$ for abelian groups. The task is to recover a compatible shift from the stipulated function access. For $G=\mathbb Z^d$, periodicity under a sublattice means $f(x+\lambda)=f(x)$ for every period $\lambda$. Shifts differing by a period are indistinguishable. Unary query cost counts the size of an integer argument in unary, rather than only its binary length.

Statement recorded in the supplied source.

Hidden shift on $\mathbb Z^d$ where $f_0$ and $f_1$ are periodic under unary oracle cost. [S2]

Scope qualification.

The source does not say which periods are provided, the lattice rank, or the collision promise; the question is retained with these unresolved oracle details.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness.

Short English statement

What is the cost of finding a hidden shift between periodic functions on an integer lattice when queries have unary cost?

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001332 (AIM-CRYPTOGRAPHY-0019). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 AIM Workshop Problem Lists, original problem source linked by catalogue record AIM-CRYPTOGRAPHY-0019 http://aimpl.org/quantumalg/4/.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 20001332 and source code AIM-CRYPTOGRAPHY-0019 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The original AIM URL was attempted on 2026-10-11, but the web fetch timed out and a direct retrieval failed at DNS resolution. Its supplied extract is preserved above; fresh access to that page is not claimed. Kuperberg's primary abstract was consulted for the abelian hidden-shift setting, without importing a full complexity theorem. The original question leaves the periods and their rank unspecified. The following exact reduction assumes known rectangular periods; its failure to preserve a logarithmic cost under unary encodings is proved explicitly.

Research attempt: Exact rectangular quotients and the cost of unary representatives

Assume known positive integers $N_1,\ldots,N_d$, and that $f_0,f_1$ are periodic under $N_i e_i$ for every coordinate. Put $G=\prod_i\mathbb Z/N_i\mathbb Z$, and define $F_b(\bar x)=f_b(x)$ for any integer representative $x$. This is well defined: two representatives differ by a sum of the stated periods. If $f_1(x)=f_0(x+s)$ then $F_1(\bar x)=F_0(\bar x+\bar s)$, with exactly the same oracle outputs. A quotient query can therefore be implemented by lifting each coordinate to $0,\ldots,N_i-1$ and making one original query.

If $f_0$ has exactly the stated period lattice $\Lambda=\prod_iN_i\mathbb Z$, the quotient shift is unique. Indeed, if both $s,t$ work then $f_0(x+s)=f_0(x+t)$ for all $x$, so $t-s$ is a period, hence lies in $\Lambda$. Injectivity of $F_0$ is a stronger sufficient promise. Merely knowing that the displayed vectors are periods does not imply either property: $f_0(x)=x\bmod2$ with a supplied even period $N>2$ also has period two, and shifts differing by two are indistinguishable in $\mathbb Z/N\mathbb Z$.

Now specify a literal unary encoding whose length for one integer $z$ is $1+|z|$, with a separate sign convention. A quotient representative set for $\mathbb Z/N\mathbb Z$ must contain $N$ distinct integers. If all have absolute value at most $B$, then $N\leq2B+1$, so $B\geq(N-1)/2$. Thus even the best choice of representatives has a worst-case unary length linear in $N$. Moreover, at most $2B+1$ residue representatives can have absolute value at most $B$. With $N\geq8$ and $B=\lfloor N/8\rfloor$, at least half have absolute value greater than $B$, proving an average unary cost at least $N/32$ for a uniform quotient query. The crude constant follows from $B\geq N/16$ for $N\geq8$.

The standard nonnegative lifts have total unary length at most $d+\sum_i(N_i-1)$, whereas their binary lengths are $O(\sum_i\log(2N_i))$. A coherent query using fixed-size literal unary registers must accommodate the largest representative in its support. Consequently a finite-group routine polynomial in the logarithms of the periods does not acquire the same unary cost by this simulation. For $d=1$, $N=2^k$, merely holding a supported unary representative can require order $2^k$ positions while its binary description uses order $k$ bits.

These are lower bounds for the explicit quotient-lift representation, not lower bounds against every possible hidden-shift algorithm. An algorithm that avoids large integer arguments or uses a different oracle interface would need its own analysis. When the period lattice is not given or does not have full rank, this finite quotient construction is not automatically available at all.

Verification and adversarial audit

For $N_i=1$ the corresponding coordinate is trivial, and it contributes no hidden information. The average-cost estimate is only stated for $N\geq8$; the finite smaller cases do not affect the claimed asymptotic obstruction. Extra periods are tested by an explicit collision example, rather than ruled out by terminology.

Audit corrections.

A supplied period is not assumed to be a fundamental period. The cost lower bound is explicitly about lifting quotient representatives into a literal unary interface, not a universal quantum lower bound.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

No optimal unary-cost algorithm for the original periodic problem is established. Determining or representing unknown periods, handling nonrectangular or lower-rank lattices, and meeting a specified collision/success model remain outside the proved reduction.

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://arxiv.org/abs/quant-ph/0302112 (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 written mathematical review at the declared scope; 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.