Pseudorandomness · permutation branching programs · finite groups · Fourier analysis

Optimal Explicit PRGs for Width-3 Permutation Branching Programs

Collaboration beta

The packet reduces the generator problem to preserving one structured covariance average. Random and partially explicit constructions meet many surrounding requirements, but no uniformly explicit short-seed construction is yet reported for that final average.

s = O (\log n + \log \frac{1}{ϵ}), Δ_{TV} (P (G (U_{s})), P (U_{n})) \leq ϵ

Known results and sources

Exact reductions reach a rank-two covariance interface; the optimal uniform generator remains open in the source.

Research problem

Exact mathematical statement

For every input length $n\ge 1$ and error $0<\varepsilon\le 1/2$ , construct a uniformly explicit generator

G_{n,\varepsilon}: \{0,1\}^s\to\{0,1\}^n,\qquad s=O\left(\log n+\log\frac1\varepsilon\right),

such that for every sequence $(P_{i,0},P_{i,1})\in S_3^2$ , the output laws of $P(G(U_s))$ and $P(U_n)$ , where $P(x)=P_{0,x_0}\cdots P_{n-1,x_{n-1}}$ , have total variation distance at most $\varepsilon$ . Generator bits must be uniformly computable in time polynomial in $n$ and $1/\varepsilon$ , with exact binary sampling or an explicitly charged rounding error. The source does not report a complete construction.

Problem infographic

Problem at a glance

Problem-first explainer showing width-3 permutation products, unitriangular pure phases, an ideal rank-metric matrix comparator, established partial sectors, and the unresolved signed covariance transfer. — The packet reports exact structural reductions and partial constructions, but the signed rank-two covariance derandomization is still open.

Current mathematical picture

Where work on Optimal Explicit PRGs for Width-3 Permutation Branching Programs stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureCoefficientwise low-rank Fourier approximation and other cancellation-discarding architectures

The canonical coefficient mass can grow as q-star to the two-w after absolute summation, and affine-coset direct sums retain constant phase bias while every fixed additive energy stays at pairing scale. A four-state forward/backward seminorm, a bilinear covariance calculation before small-bias expansion, a pessimistic estimator, a matrix-valued expander analysis, or a route change to the explicitly retained trace, semidirect, averaged-lift, or block-source interfaces…

Route status · Narrowed route

Main reductionCurrent reduction

Normalize every program into a unitriangular abelian form, expand its pure mod-3 phase in a canonical Boolean Fourier cube, and derandomize the ideal rank-metric heat kernel only in the signed one- and two-frequency covariance aggregate before invoking the established pure-phase-to-total-variation compiler.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeProve the signed canonical rank-two covariance defect bound for one concrete uniformly explicit short-seed matrix-table distribution.Task status · Ready to work on

Work mapped so far

Optimal Explicit PRGs for Width-3 Permutation Branching Programs in numbers

1.2kretained lines of mathematical investigation1,209 in the current working snapshot

Argument development: 1,040 · 86%
Explored or eliminated routes: 39 · 3%
Computational analysis: 18 · 1%
Open obligations: 64 · 5%
Definitions and setup: 48 · 4%

8selected mapped statements1routes investigated4open questions4contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedAug 30, 2026

Source recordedAug 30, 2026

Recommended next task

Prove the signed canonical rank-two covariance defect bound for one concrete uniformly explicit short-seed matrix-table distribution.

Suggested move: Write the four-state rowwise transfer for a concrete expander, bilinear, recursive, or rank-condenser table family and test contraction against the exact ideal diagonal and off-diagonal constants.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

13 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded

Narrowed routeCoefficientwise low-rank Fourier approximation and other cancellation-discarding architectures

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

4 featured tasks

Prove the signed canonical rank-two covariance defect bound for one concrete uniformly explicit short-seed matrix-table distribution.Suggested move: Write the four-state rowwise transfer for a concrete expander, bilinear, recursive, or rank-condenser table family and test contraction against the exact ideal diagonal and off-diagonal constants.

Ready to work on

Preserve cancellation in the alpha-S times conjugate-alpha-T aggregate without replacing it by coefficientwise absolute errors that cost q-star to the two-w.Suggested move: Form the full bilinear second moment before conditioning, or define a forward/backward seminorm whose local candidate-minus-ideal errors sum to order zeta squared.

Ready to work on

Signed rank-two canonical covariance

Construct a uniformly explicit optimal-seed matrix distribution whose signed canonical kernel covariance differs from the ideal heat-kernel comparator by at most zeta squared over four for every gauge and charge vector.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.

Ready to work on

Close the uniform-explicitness, exact-sampling, running-time, compiler, and adversarial-audit requirements for any candidate covariance theorem.Suggested move: Record every seed component and finite sampler exactly, prove polynomial-time output computation, instantiate zeta and delta, and replay the mod-3, affine-coset, recharge, selector-leaf, subfield, and rank-normalization tests.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 30, 2026

Current statusOpen problem

The additive-optimal ordinary PRG target remains open. Peer-reviewed 2025 sources report that low-error constant-width permutation programs still require multiplicative logarithmic seed overhead, and the July 2026 preprint gives O((log w + log(1/epsilon)) log n), which for width three does not reach O(log n + log(1/epsilon)).

[3][4][5]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026-07
PreprintCohen, Doron, and Goldgraber reported an ordinary PRG for width-w permutation read-once branching programs with seed O((log w + log(1/epsilon)) log n). For width three this improves a parameter boundary but…[5]
2025
Peer reviewedTwo peer-reviewed 2025 papers identify the low-error constant-width permutation case as still lacking additive-optimal seed length. They also distinguish ordinary PRGs from weighted generators and other…[3][4]
2019
Peer reviewedMeka, Reingold, and Tal obtained seed length polylogarithmically close to log(n) log(1/epsilon) for ordered width-3 read-once branching programs. This is a stronger program class but remains quantitatively…[2]
2017
Peer reviewedSteinke, Vadhan, and Wan gave an explicit generator with polylogarithmic seed length for the broader class of oblivious read-once width-3 branching programs in arbitrary input order. Its parameters do not…[1]

Mathematical neighborhood

Related results and reusable starting points

Current focusOptimal Explicit PRGs for Width-3 Permutation Branching Programs

Stronger or generalized formGeneral width-3 read-once branching programs

General width-3 read-once branching programs allow non-permutation layers. Known generators for that broader class have weaker seed parameters than the additive-optimal permutation target.

[2]

Stronger or generalized formPermutation read-once branching programs of arbitrary width

The 2026 preprint treats arbitrary width w, but its seed length specializes to O(log n log(1/epsilon)) at constant width rather than the additive optimum.

[5]

Related problemPseudorandomness for noncommutative group programs

Permutation branching programs are equivalent to group programs. The width-3 binary model can use the noncommutative group S3, while optimal low-error parameters remain sensitive to the group and order model.

[3]

Weaker or relaxed formWeighted generators and hitting-set generators

Weighted pseudorandom generators and hitting-set generators can attain bounds unavailable to ordinary PRGs, but their signed weights or one-sided guarantees do not satisfy this workspace's ordinary distributional generator target.

[4]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetA formal statement of binary-input permutation read-once branching programs, their S3 product semantics, uniform explicitness, and total-variation error for all output states.
Formalization targetFormal finite-group and representation-theoretic support for S3 together with Boolean Fourier analysis and exact probability distributions.
Formalization targetChecked quantitative constructions for small-bias spaces, expanders, INW-style recursion, exact binary sampling, and seed-length accounting.
Formalization targetA checked closing theorem achieving additive O(log n + log(1/epsilon)) seed length for the exact width-3 permutation target.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

6 standing statements2 proposed statements4 open questions1 narrowed routes

Statements by mathematical role8 selected mapped statements

theorem candidate1 of 81
reduction2 of 82
lemma3 of 83
special case1 of 81
negative result1 of 81

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.21 displayed rows · 1 route included

retained route statementCan width-3 permutation branching programs be fooled with the optimal logarithmic seed?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementUnitriangular pure-phase compilerintermediate
retained route statementNonuniform optimal-order affine listintermediate
retained route statementExplicit logarithmic-charge sourceintermediate
retained route statementIdeal rank-two second momentintermediate
retained route statementScoped cancellation-discarding barriersintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureCoefficientwise low-rank Fourier approximation and other cancellation-discarding architecturesreported failure
Research targetProve the signed canonical rank-two covariance defect bound for one concrete uniformly explicit short-seed matrix-table distribution.open
Research targetPreserve cancellation in the alpha-S times conjugate-alpha-T aggregate without replacing it by coefficientwise absolute errors that cost q-star to the two-w.open
Research targetClose the uniform-explicitness, exact-sampling, running-time, compiler, and adversarial-audit requirements for any candidate covariance theorem.open
Research targetSigned rank-two canonical covarianceopen
Narrowed routeCoefficientwise low-rank Fourier approximation and other cancellation-discarding architecturesThe canonical coefficient mass can grow as q-star to the two-w after absolute summation, and affine-coset direct sums retain constant phase bias while every fixed additive energy stays at pairing scale. A four-state forward/backward seminorm, a bilinear covariance calculation before small-bias expansion, a pessimistic estimator, a matrix-valued expander analysis, or a route change to the explicitly retained trace, semidirect, averaged-lift, or block-source interfaces remains open.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeProve the signed canonical rank-two covariance defect bound for one concrete uniformly explicit short-seed matrix-table distribution.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointProve the signed canonical rank-two covariance defect bound for one concrete uniformly explicit short-seed matrix-table distribution.

Optimal Explicit PRGs for Width-3 Permutation Branching Programs · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

The current work reduces the generator problem to preserving one structured covariance average. Random and partially explicit constructions meet many surrounding requirements, but no uniformly explicit short-seed construction is yet reported for that final average.

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references5 cited works · next context review by Nov 30, 2026

The mathematical context was checked on Aug 30, 2026. Status can be refreshed sooner after a material result or claim.

1
Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programspeer reviewed result · Thomas Steinke, Salil Vadhan, Andrew Wan · Theory of Computing · 2017 · DOI 10.4086/toc.2017.v013a012 · accessed Aug 30, 2026
2
Pseudorandom Generators for Width-3 Branching Programspeer reviewed result · Raghu Meka, Omer Reingold, Avishay Tal · 51st Annual ACM Symposium on Theory of Computing · 2019 · DOI 10.1145/3313276.3316319 · accessed Aug 30, 2026
3
Pseudorandom Bits for Non-Commutative Programspeer reviewed result · Chin Ho Lee, Emanuele Viola · 40th Computational Complexity Conference · 2025 · DOI 10.4230/LIPIcs.CCC.2025.9 · accessed Aug 30, 2026
4
Implications of Better PRGs for Permutation Branching Programspeer reviewed result · Dean Doron, William M. Hoza · APPROX/RANDOM 2025 · 2025 · DOI 10.4230/LIPIcs.APPROX/RANDOM.2025.28 · accessed Aug 30, 2026
5
A Forward-Backward Weight Analysis of INW for Permutation Branching Programspreprint · Gil Cohen, Dean Doron, Noam Goldgraber · Electronic Colloquium on Computational Complexity, TR26-123 · 2026-07-21 · accessed Aug 30, 2026

Important qualifications

This was a bounded primary-source status pass, not an exhaustive bibliography, priority review, or review of the private packet's mathematical claims.
No submitted URL or packet attachment was opened, fetched, executed, compiled, or treated as external authority.
The local workspace target asks for additive-optimal O(log n + log(1/epsilon)) seed length and total-variation control of the full S3 output law; cited papers sometimes use Boolean acceptance tests, a fixed input order, arbitrary input order, weighted generators, or broader width-3 models, so those scopes are kept distinct.
The July 2026 ECCC report is a preprint and is not promoted to peer-reviewed status.
A bounded search found no statement-aligned formalization, checked certificate, or independently reproduced computation; this does not establish nonexistence.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces