MathIdeasResearch in progressRepository ↗
← Research catalogOriginal Markdown ↓
On this page

Queryable permutation and sparse shuffle framework

Decision: Prototype sparse replay; defer a source-guaranteed seeded data loader. Edition: 9 October 2026 Australia/Brisbane. Commercial demand, performance advantage and profitability are unvalidated.

Research finding

Family 238's signed-tensor companion describes a decision forest that always outputs a permutation on n=2^d slots and computes each point using Ld adaptive queries to shared independent fair switch bits. For one absolute L, the full permutation law approaches uniform as d grows. The trace-smoothing companion supplies a stronger all-size bound: there exists an absolute P>=2 such that any integer v with 2v>=P gives full-law total variation at most (1/2)n^(-5). Its selected CoordinateTrace formal interface covers that latter mixing statement; it does not separately certify a production point-query compiler.

This makes an on-demand ordering API a concrete application hypothesis. The older primary cell-probe paper records an O(log^2 n) upper bound and distinguishes cell probes from bit probes. The source's O(log n) corollary is an improvement claim conditional on its proof, not an independently accepted finding here. Earlier primary paper, version-one PDF.

Problem and buyer

A data-infrastructure or large simulation team may need a few reproducible positions from a huge shuffled index space, inverse lookup, or a resumable random test schedule. Materializing an entire index array can be wasteful when only a small portion is queried. A fully stored int64 array for 2^30 slots occupies 8,589,934,592 bytes before other overhead; this is a representation cost, not a lower bound on every sampler. Candidate buyers must already have a sparse access workload whose memory, restart or inverse-lookup cost matters.

What the finding could enable

A framework could expose point(i), inverse(j), an immutable epoch plan and disjoint slot-based shard views. Shared switch addresses let every worker see the same permutation; reverse layer order gives inverse access. With a separately validated universal sweep count and independent fair-bit backend, the source could support an approximate-uniform full-law claim without constructing the full index table. The references supply switching/replay, exact tiny laws, decimal-wire queries, a seeded keyed backend and local append-only OS-bit assignment. Actual independent fairness, the universal threshold and a distributed data loader remain unverified.

Technical and commercial limits

queryable_permutation_reference.py accepts explicit sparse bit values, supports forward/inverse queries on dimensions up to 63, and returns unknown for missing bits or budget exhaustion. It caps 64 sweeps, 256 queries, 100,000 supplied bits, four million lookups/image evaluations and 5,000 retained trace records. Exact whole-law calculation is limited to at most eight slots, eight sweeps and 50,000 states; it can exhaust earlier. Replay uses deterministic supplied values and establishes no randomness distribution. Trace truncation does not truncate successful query results.

A short seed is a material bridge failure for the source's statistical claim. If a fixed deterministic system has only a b-bit seed as randomness, it can output at most 2^b permutations. Its statistical total variation from uniform is at least max(0,1-2^b/n!). For 64 slots, a 256-bit seed already forces a distance greater than 0.999. This is a support fact, not a cryptographic-security conclusion or a criticism of seeded training goals that require different guarantees. Lazy independent-bit storage preserves the intended model but its cache can grow substantially as more of the domain is queried.

Non-dyadic cycle restriction preserves bijection but is an additional conventional construction. Worst-case access can require n-m+1 full-permutation calls for m retained slots, so logarithmic worst-case access does not automatically survive. On the four-slot one-sweep fixture restricted to three slots, TV is 1/12 and marginals are biased, despite exact single-card uniformity on the full four-slot domain. Training quality, balanced batches, padding, fault recovery and security are separate obligations.

The provider reference adds canonical decimal-wire requests, a fixed plan identity, 256-bit HMAC mapping or local POSIX locked append-only bit assignment. Sixty-two initial and eleven post-fix controls cover ordering, restart, two local processes, capacity, exact 63-bit indices and refusal to change damaged/mismatched stores. This is local consistency evidence, not a distributed service, source mixing or security certificate. Hash-linked records are not authenticated against rewriting or tail removal.

The measured synthetic case has 256 slots/two sweeps: 16 sparse points retained 249 switches/35,972 file bytes, while materializing the same permutation reached 2,048 switches/293,486 bytes. A packed int64 index array is 2,048 bytes. This JSON backend loses that storage comparison. A needless 8 MB loader allocation was found and corrected; repeated sparse traced Python peak is 43,318 bytes, while full reload/parsing remains heavier. These are one small synthetic observation with a simple oracle, not a production speedup or real dataset benchmark.

Minimal architecture

Immutable plan (domain, coordinate convention, sweep count, epoch and bit-source revision) -> shared switch provider -> point/inverse path evaluator -> optional cycle restriction -> disjoint logical-slot shard adapter -> replay and model report. A fair-bit provider must assign each key (epoch,sweep,coordinate,pair) one stable bit; changing it between queries can destroy the intended joint output. A seeded provider must visibly use a separate randomness/guarantee model. Do not make a production memory or latency promise before measuring lookup/cache cost.

Existing alternatives and differentiation

PyTorch's current DistributedSampler implementation generates a randperm index list and then pads or drops indices before rank slicing. It is a substantial baseline, including equal-length shard behavior. A sparse point/inverse API would need to improve a real workload while preserving the chosen batching policy. Primary implementation.

Random123 already provides stateless counter/key pseudorandom generators. Such a provider can be practical for reproducible switching bits but does not become the source's independent fair-bit oracle or preserve its statistical full-law guarantee merely by passing RNG tests. The library itself excludes cryptographic use. The proposed difference must be useful permutation/inverse/shard behavior plus honest guarantee tracking, not a new RNG. Random123.

Monetization hypothesis

Hypothesis: AUD 8,000–20,000 for a data-access benchmark and adapter, only after a team shows a recurring sparse lookup problem. At an assumed AUD 12,000 fee and 40 hours at AUD 180/hour, AUD 4,800 remains before support, sales and overhead; 70 hours exceed the fee. No quote, interview, workload or paid engagement exists. An open research SDK may be more appropriate until a measurable advantage is shown. Do not count the shared evidence adapter as a second customer subscription.

Validation experiment

176 finite controls compare independent physical-shuffle all-coin enumeration with coordinate laws, materialized switching with point/inverse replay, cycle deletion, missing-input/budget failures and a sparse 63-bit path. One sweep has uniform one-card marginals but full-law TV 1/3 on four slots and 283/315 on eight. Four/six sweeps on four slots have TV 1/192 and 1/3072 respectively. The trace target there is 1/2048; four and five sweeps fail, while six pass that one instance. No universal sweep selection follows.

21 entropy controls verify exact small support bounds and symbolic large-domain arithmetic. A 63-bit sparse replay uses 126 switch lookups in each direction with two sweeps, but those deterministic values do not demonstrate uniform mixing. Next compare a sparse access workload with the existing sampler under identical batching, randomness and restart requirements. Measure total memory, lookup latency, cache growth and numerical/model gaps; record training outcomes only if a training experiment actually runs.

The new exact palindrome reference adds a source-oriented two/four-slot numerical bridge, with 50 controls. At four slots its centered regular operator satisfies B^2=(1/4)B and has a displayed sharp eigenvector, while a separately constructed exponent-zero minorant has mass 3/4/gap bound 5/8. Conservative finite norm/minorant schedules are 13/37 sweeps; direct law enumeration already succeeds at six. This improves finite diagnostic evidence and does not supply the universal P, an unrestricted backend or business value. Factorial matrix storage caps this calibration at four slots.

Conditions to reject or defer

Defer the source statistical guarantee until P/u and the exact implementation/randomness bridge are validated. Reject a short-seed claim of statistical closeness to the full uniform permutation law when the support bound rules it out. Reject the memory-saving product hypothesis for workloads that query the whole domain and require a large persistent fair-bit cache, or if existing seeded permutation methods already solve sparse access cheaper. Defer non-dyadic worst-case latency, balanced distributed batching and security claims until separately justified. A short query-depth theorem alone is not an end-to-end speedup.

Next concrete action

Run the decimal-wire seeded fixture under the provider reference. Choose a realistic sparse access/inverse/resume task, implement a compact keyed store, and compare it with an appropriate existing baseline under the same provider and batching requirements. Read the selected contraction audit: eventual thresholds and a classically selected full-group minorant still leave numerical P open. The local append store and seeded mapping are implemented, but no source proof, full distributed SDK, real data task, customer pilot or security evaluation has been completed.

Pinned source evidence