Correlation-gap certificates for noisy hidden shift

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 hidden-shift problem asks for a group element $s$ relating functions, for example $g(x)=f(x+s)$ in an additive group, under specified promises and oracle access. Noisy versions perturb values or oracle behavior according to a stated model. Noninjective functions can admit several shifts, so collision and solution-count promises affect both identifiability and algorithmic guarantees.

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. No noise law, distance, function class, oracle, or collision promise is fixed. A quantitative tolerance or correlation threshold is not asserted. 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.

How much noise is tolerated in hidden shift algorithms? Consider too many solutions vs. too few. [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 how hidden-shift algorithms behave with noise or atypical numbers of solutions.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 20001333 (AIM-CRYPTOGRAPHY-0020). 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-CRYPTOGRAPHY-0020. http://aimpl.org/quantumalg/4/.

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 20001333 and code AIM-CRYPTOGRAPHY-0020 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

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. The primary abstract of Childs--Kothari--Ozols--Roetteler, on easy and hard Boolean hidden-shift functions, was consulted; it emphasizes dependence on the function rather than a universal oracle-independent cost. The following finite-group model fixes adversarial value noise and exact equality tests. It investigates identifiability and a simple classical estimator, without supplying a noise model absent from the source.

Research attempt: Hamming separation, an arbitrarily small noise obstruction, and sampling cost

Let $G$ be a finite additive group of size $N$, let $f:G\to\mathcal A$, and put $f_s(x)=f(x+s)$. Define the period subgroup $H=\{h:f(x+h)=f(x)\ \forall x\}$. It is a subgroup because zero is a period, sums of periods are periods, and translating the identity by $-h$ proves that $-h$ is a period. Also $f_s=f_t$ exactly when $s-t\in H$. If more than one distinct translate exists, define \[ \Delta=\min_{f_s\ne f_t}d_H(f_s,f_t), \] where $d_H$ counts differing coordinates. Suppose the observed function $g$ differs from some true translate $f_s$ on at most $e$ coordinates. If $2e<\Delta$, its nearest translate is uniquely $f_s$ modulo $H$. Indeed every different translate satisfies $d_H(g,f_t)\geq d_H(f_s,f_t)-d_H(g,f_s)\geq\Delta-e>e$.

The factor two cannot be discarded for adversarial noise. On coordinates where two functions at distance $\Delta$ disagree, construct $g$ by taking half the values from each. When $\Delta$ is even, $g$ has distance $\Delta/2$ from both; for odd $\Delta$ the two distances are the neighboring integers. More drastically, take $f=\mathbf1_{\{0\}}$ on any group of size $N\geq2$. Its distinct translates have distance two, and the all-zero observation is one corrupted coordinate away from every translate. Thus noise fraction $1/N$, tending to zero, can leave all $N$ shifts compatible with the same noisy data. A universal positive tolerated fraction cannot follow without a separation or function-class promise.

To quantify a route that does work under a gap, let $C_t=N^{-1}|\{x:g(x)=f(x+t)\}|$. Suppose a unique translate class maximizes $C_t$, and every other class is at least $\gamma>0$ below it. Draw $m$ independent uniform positions $X_j$, and estimate every score by \[ \widehat C_t={1\over m}\sum_{j=1}^m\mathbf1\{g(X_j)=f(X_j+t)\}. \] Each estimator has variance at most $1/(4m)$. Hence $\Pr\{|\widehat C_t-C_t|\geq\gamma/2\}\leq1/(m\gamma^2)$ by applying Markov's inequality to the squared deviation. A union bound over at most $N$ shifts makes all deviations strictly less than $\gamma/2$ with probability at least $1-N/(m\gamma^2)$. On that event no lower-score class can win. Therefore $m\geq N/(\eta\gamma^2)$ suffices for error probability at most $\eta$, with at most $m(N+1)$ straightforward function evaluations. Shared sampled positions create dependence between candidate scores, but neither the per-score variance bound nor the union bound needs independence across candidates.

Under the earlier adversarial-noise promise, the score gap is at least $(\Delta-2e)/N$, by the distance inequalities already proved. Substitution gives an explicit, generally inefficient recovery bound whenever that quantity is positive. If all translates are identical, every shift is compatible and the identification task must instead specify a convention for its output.

Verification and adversarial audit

The point-mass example falsifies a noise tolerance depending only on the fraction corrupted. The sampling argument uses independent sampled positions with replacement, not independent oracle noise. It recovers the translate class, and does not falsely distinguish shifts in the stabilizer.

Audit corrections.

Noise tolerance was tied to a proved translate separation. Noninjective shifts are treated modulo periods, and a small corruption fraction is not confused with a harmless perturbation.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The analysis is for adversarial Hamming corruption on a finite group, with an explicit score gap. It does not characterize noise tolerance of Kuperberg's algorithm, coherent oracle errors, or the source's unspecified too-many/too-few-solution regimes. The estimator is an auxiliary elementary route, not a quantum speedup.

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/1304.4642 (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.