Exercise PLAN-518

The sharp randomized worst-input q-query success for a unique mark is(q+1)/N, achieved symmetrically. N-1 is a certainty threshold, not the threshold for success above one half; conditional zero-transcript ambiguity must not replace unconditional success.

1. Fix random coins, cache repeats and pad up to q<=N-1 distinct classical queries without reducing success, then follow the all-zero branch.
2. That branch leaves N-q unqueried labels; for q=N-2 exactly two remain, but the branch and pair may depend on coins.
3. Every mark outside the zero-branch query set gives the same transcript; a fixed output is correct for at most one of them.
4. Count at most q successful hit inputs plus one residual input, then average over coins before taking a fixed worst input to obtain success<=(q+1)/N.
5. The symmetric construction attains(q+1)/N, refuting N-1 for bounded error; strict success>1/2 needs floor(N/2) queries and certainty needs N-1.
6. This classical-transcript argument gives no quantum lower bound; superposed-query optimality needs a separate quantum proof.

The old bounded-error N-1 threshold is false even for a completely label-symmetric algorithm. For N=4 choose a uniform random permutation, query its first two entries, output any hit, and if both answers are zero guess uniformly among the remaining two. For each fixed mark the hit probability is2/4; on a miss the guess succeeds with probability1/2. Thus overall success is2/4+(2/4)(1/2)=3/4 using exactly2<N-1=3 queries. The algorithm is equivariant under every relabeling and has identical success for every marked input, so unbiasedness does not rescue the assertion. More generally, for0<=q<=N-1 the sharp worst-input success is(q+1)/N. For the upper bound fix every internal random choice, obtaining a deterministic adaptive algorithm. Repeated queries can be cached and removed. Early stopping can be padded to q distinct queries while retaining the original output, or with an output rule improved by any discovered hit; this cannot reduce success. Follow the resulting all-zero branch and let S be its q queried labels. A unique mark outside S gives precisely this same zero transcript, regardless of which of the N-q remaining labels is marked, so its single deterministic final output is correct for at most one such label. For a mark in S the algorithm can be correct on at most the q inputs in S. Under a uniform marked input it therefore succeeds on at most q+1 of N inputs. Averaging this inequality over the random coins preserves the uniform-input success upper bound(q+1)/N. Some FIXED input must have success no larger than that average, which proves the worst-input upper bound without any unbiasedness hypothesis. The order matters: no input is selected as a function of hidden coins. For attainment, choose q distinct labels uniformly without replacement, query them and output a hit; if no hit occurs, guess uniformly among the N-q unqueried labels. Each fixed mark has hit probability q/N and miss-and-correct probability((N-q)/N)/(N-q)=1/N, hence success(q+1)/N. This is label-symmetric and so satisfies the retained unbiased condition. Conditional on a fixed all-zero transcript, two residual candidates indeed cannot both have success greater than1/2. But this conditions away hit transcripts, which can succeed with probability one, and the residual pair for randomized queries depends on coins. The old proof improperly promoted that conditional statement to an unconditional worst-input conclusion. Strict success greater than1/2 is attainable exactly when q+1>N/2, with least integer q=floor(N/2); certainty needs q>=N-1. For N=1 the mark is known with zero queries and these formulas give success1 and both least counts0. For N>=2 the certainty bound is also the familiar deterministic all-zero indistinguishability argument: q<=N-2 leaves at least two possible marks; N-1 negative tests identify the final candidate. Constant-success classical complexity is therefore Theta(N), not the old exact threshold. This proof concerns classical Boolean query transcripts, not coherent superposed oracle calls, and establishes no quantum lower bound. Grover's separate upper-bound construction is consistent with this distinction; its optimality requires an independent genuinely quantum lower-bound argument not supplied here. No gate, finite-bit or physical query-cost conclusion follows from these oracle counts.

1. Refutes the old N-1 bounded-error assertion with the explicit N=4,q=2 symmetric algorithm and unconditional3/4 success for each fixed mark, not a biased guess or a changed promise. (1 weight)
2. Fixes coins before the deterministic all-zero transcript, justifies caching/padding, counts at most q hit inputs plus one successful residual guess under a uniform mark, and averages coins before selecting a worst input. (1 weight)
3. Proves attainment(q+1)/N by symmetric distinct queries plus a uniform residual guess; identifies the old conditional/unconditional and quantifier errors. (1 weight)
4. Derives least q=floor(N/2) for strict success>1/2 and N-1 for certainty, includes N=1, and separates classical transcript reasoning from an absent quantum lower-bound proof. (1 weight)

No aligned Lean view has been admitted for this native core in this textbook checkpoint. This is not a claim that the underlying mathematics lacks a formal proof. Contributions must preserve this exact target contract and split.

Read the Lean track and existing diagnostic warmups

• website/research/sources.json

  lin-wiebe-2026-qasc

  Source SHA-256: 9f85f45f20ed5a46931ad0dec3b94ee09748bc56e39fae29b0aefe910440b0ae · MIT metadata only
• Primary source

Contract: eefe47810cd6fdb8bf3d284522edd84d5a709a54e926e999568c06d8b200b046

Item digest: bd7ee62cefef1695c2dc120937d0ad38f484c73fad2e2cb269178b4cc5b85234

Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a

Authored support steps: 6. This is not measured graph distance or model difficulty.

{ "question_version": 2, "predecessor_key": "qcb-core-plan-518-classical-search-lower-bound", "predecessor_item_digest": "4a6f908a4ce62d5377927e6d3a035f06fdbb6322af5c18eff94cd84df876b9c2", "predecessor_contract_hash": "6d6f5612311dac1f0e44d408b9252b503fc88147ef8c39813b5b18f2a1106d18", "current_contract_hash": "eefe47810cd6fdb8bf3d284522edd84d5a709a54e926e999568c06d8b200b046", "changed_contract_fields": [ "question" ], "repair_record": "shared/repairs/plan-518-randomized-query-guarantee-question-successor.json", "repair_record_digest": "6b985ff85de798453a98d8edc6fec4d4619b7743e65c3527fae3629edb1426ff", "review_record": "reports/textbook-v1/repairs/plan-518-randomized-query-guarantee-question-successor-review.json", "review_digest": "2a5aee00bb94955a745d828ad81c98fc7cf7529a70d5c52b33cc1e83b8e63884", "equivalence_to_predecessor_claimed": false, "additional_core_count": 0 }