Private Selection under Scalar Access: Allocation, Noise Primitives, and the Limits of Scalar Observation

We study private selection using sensitivity-one scalar observations and pathwise additive charging. For N losses, K = ceil(log_2 N), fixed epsilon > 0 and sufficiently large N, the fixed-common-scale Laplace minimax expected excess lies between c K^(3/2) / (epsilon sqrt(ln K)) and C K^(3/2) [ln(e K)]^(3/2) / epsilon. The lower bound permits arbitrary adaptive nonlinear queries and finite public randomized caps. The improved construction uses a coded gap finder to remove a growing individual-confidence requirement. Unequal predetermined charges achieve C K (1 + ln K) exp(sqrt(2 ln(2) ln K)) / epsilon; we prove matching order for its shared-budget certificate template, not for all algorithms. A separate adaptive lower bound gives Omega(K sqrt(ln ln K) / epsilon) at fixed epsilon, so general unequal allocation still cannot achieve the unrestricted O(K / epsilon) rate. A finite-grid envelope extends both obstructions to arbitrary unit-distance pure-DP kernels whose private parameter is one real scalar, without differentiability assumptions. Quadratic allocation caps have matching leading exponents. An attributed ordered-quantile construction attains O(K / epsilon) on a restricted workload, but its measured constants are not competitive. The main common-scale lower and upper bounds have end-to-end Lean proofs; the precise scope of the further formal results is reported separately. These are access-model results, not lower bounds for all private mechanisms. Preprint; independent human mathematical review has not been established. This research, writing and formalization used substantial AI assistance, disclosed in the manuscript and accompanying provenance file. Formal scope and reproduction limits are documented in FORMAL_SCOPE.md. The manuscript is licensed under CC BY 4.0. Bundled third-party source code retains its stated licenses.