Lemma 2.16 — Polynomial-time counting, ranking and inverse ranking
OpenAMRangeAvoid.Characterization.Supplement.lemma_2_16complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance
For all integers and and every , put . There exist three deterministic algorithms, chosen uniformly before these inputs, that compute , the zero-based lexicographic ranking bijection, and its inverse:
All three run in time polynomial in the numerical quantities and . The rank and inverse-rank identities hold for every legal point and every legal rank. Counting includes empty intersections; then both indexing domains are empty. No bound on the translation is assumed.
Differences from the source:
- encoding: deterministic algorithms in time polynomial in n and numerical R → three finite Mathlib TM2 programs with one uniform positive constant and exponent, canonical binary inputs and outputs, and halting output-stack semantics; reason: every bit operation is charged, while early rejection may leave oversized unread input as in a standard Turing machine
Preamble
import Definitions.Def_AMRangeAvoid_Characterization_Supplement_Grid import Definitions.Def_AMRangeAvoid_Characterization_SSLB
Formal statement
namespace AMRangeAvoid.Characterization.Supplement theorem lemma_2_16 : GridIndexingAlgorithms := by sorry end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Lemma 2.16, printed p.13 (PDF p.15); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf