Product Expansion of Random Codes via Analytic Techniques
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Product Expansion of Random Codes via Analytic Techniques".
Jane: Here's the gist of the paper. The paper provides a proof for two-sided product expanding codes based on independent random linear codes over sufficiently large prime fields, without requiring explicit constructions of asymptotically optimal locally testable codes (c3-LTCs).
Tom: The methodology leverages techniques developed by Dinur, Lin, and Vidick (FOCS, 2024), utilizing a different random model and novel analytical tools for studying product expansion.
Jane: The core argument involves establishing that for every epsilon-closed set M, the corestriction maps of the component codes (C i) i in
D: and their duals (C i) i in
D: are simultaneously injective over a single prime field with high probability.
Tom: This injectivity is linked to the two-sided product expansion property via Lemma 5.2 from
KP25: , which states that if every epsilon-closed subset of
n: D is inner-generated in sum i C i, then (C i) i in
D: is gamma(epsilon, D) -product expanding.
Title and authors: Tom: Alright, so we’ve just talked about the core idea of this paper called "Product Expansion of Random Codes via Analytic Techniques." Now let's talk about who wrote it and what that actually means for the field.
Jane: Before we get into the technical stuff, let's quickly look at the title and authors. The paper is written by Eshan Chattopadhyay and Noam Ringach from Cornell University.
Lu: The context here is important because they are drawing on earlier work by Dinur, Lin, and Vidick from FOCS in two thousand twenty-four which focused on tensor codes with constant product expansion as a foundation for quantum locally testable codes <ref:2610.02512#pg1,tensor codes with constant product expansion>.
Meng: So the paper is clearly situated in that space of high-dimensional coding theory and quantum information applications because it's building on those foundational concepts.
Lalam: The authors are clearly experts in this area, given they are citing recent work from FOCS and focusing on the product expansion concept, which is central to understanding how parity checks break down into component checks.
Tom: So what does this mean for us as a general audience? It means we're looking at codes that are relevant to quantum error correction and the PCP theorem proof, which is pretty deep stuff.
Jane: For the listener, it just means they’ve found a way to prove that you can find these useful codes randomly, without needing those incredibly complex, hand-crafted optimal local testable codes we talked about before.
Lu: That's the key shift: moving from explicit construction to probabilistic existence based on random sampling over large prime fields.
Meng: So they're essentially saying, if you pick random codes big enough, they are likely to have this desired property because the underlying math—the analysis of those matrix norms—shows it’s not too hard to get them right.
Tom: I think that's a fair summary. The authors are using a mix of deep probabilistic tools and sharp matrix analysis to give us a constructive existence proof for random codes.
Jane: It gives hope that we don't need to wait for those optimal local codes to be built before we can start designing systems based on product expansion principles.
Lu: Exactly, the potential impact is that it lowers the barrier for applying these concepts in areas where optimal constructions are currently out of reach.
Meng: If this works well in practice, it could mean simpler code designs that still maintain strong error correction guarantees.
Lalam: I think they are positioning this work as a way to simplify the path toward building better quantum and classical codes by relying on randomness instead of perfect optimization initially.
The paper's summary: Tom: Now let’s get into the actual summary of "Product Expansion of Random Codes via Analytic Techniques." We need to unpack what they are actually saying about the mechanism.
Jane: The paper explains that product expansion, in simple terms, means any complicated parity check on the whole code can be broken down into a sum of simpler parity checks from each individual component code.
Lu: So when you have many independent codes C i, product expansion is really about how easy it is to represent complex checks using just the checks from the smaller pieces.
Meng: If this property holds, it suggests that these codes are well-behaved and not overly entangled in a way that makes them computationally intractable to manage.
Tom: The paper's main mechanism for proving this is establishing that for every small set of combinations of coordinates—what they call an epsilon-closed set M —the corestriction maps of the component codes and their duals are simultaneously injective over a single prime field with high probability.
Jane: Injectivity there means that you can distinguish between all those different combinations using just one single prime field, which is a strong statement about their structure.
Lu: This injectivity is then tied directly to Lemma five point two from KP25, which states that if every epsilon-closed subset of the sum of these codes is inner-generated, then the collection of component codes has this two-sided product expansion property.
Meng: So they are essentially proving that if the components don't have too much redundancy in their interactions—if they are "inner-generated"—then they satisfy product expansion.
Tom: The paper’s technical backbone relies on using random Rademacher matrices over the reals to generate the generator matrices of these component codes, and then bounding the expected operator norm of a plane-interaction matrix K.
Jane: That interaction matrix K is where all that complexity lives, so they spend a lot of effort making sure its expected norm stays small enough.
Lu: They achieve this by decomposing K into directional blocks first, and then further breaking it down into sums over subsets of coordinates using more random Rademacher matrices in Lemma seven point eight to get those specific bounds on the operator norm.
Meng: It sounds like they are using these matrix decomposition tricks and then applying those Wigner words to get the actual numbers they need for their proof, which is a sophisticated way to handle high-dimensional randomness.
Tom: And this leads them to bounding the expectation of trace of (T T) p, which helps them establish bounds on E sigma
tr((T T) p): , which are then used in Proposition eight point one to bound the maximum operator norm of linear maps T lambda by something involving two four rho q sqrt eta.
Jane: So, in short, they are using random matrix theory and analytic tools to show that the expected behavior of these interactions is controlled enough to prove the product expansion property holds for random codes.
The paper's improvements: Tom: Now let's talk about the improvements they suggest in their own work, since this isn't just a summary, it’s about how they make the methodology better.
Jane: They are suggesting three main avenues for improvement. First, they want to move away from relying on explicit constructions of asymptotically optimal locally testable codes entirely.
Lu: That aligns with the main goal—to prove existence without needing those perfect codes upfront, which is a big conceptual improvement over previous results like Kalachev and Panteleev's work in FOCS25.
Meng: For us at the production side, that means we don't have to wait for theoretical perfection; we can use probabilistic methods to generate codes that are good enough for our needs right away.
Tom: Second, they propose implementing a framework using the trace power method and weak Wigner words to bound the operator norm of sparse tensor Gram matrices.
Jane: That’s an improvement in verification, because if we can efficiently check if a set is inner-generated by looking at the norm of its interaction matrix, that speeds up our process significantly.
Lu: It allows for rapid assessment of inner-generatedness for given sets in random linear codes just by checking if the norm of that plane-interaction matrix is less than one. That’s a concrete way to test the required condition.
Meng: I like that idea; efficiency matters when dealing with potentially huge code spaces. Being able to quickly prune bad candidates based on this norm bound would be a huge win for deployment pipelines.
Tom: And third, they suggest creating an algorithm that leverages the decomposition of the plane-interaction matrix into directional blocks and subsequent bounding via expected operator norms to efficiently estimate the probability that this interaction matrix has an operator norm less than one over a prime field.
Jane: That’s essentially an improved method for estimating success rates. Instead of just theoretical bounds, they are suggesting a practical way to estimate the probability of success based on those decompositions and expected norms.
Lu: It formalizes how to use those decomposition techniques not just as a theoretical tool but as an estimation mechanism for the actual likelihood of meeting the injectivity requirement over a prime field.
Meng: That’s exactly what we need—a way to translate the complex analysis into something that tells us, "how likely is this code to work on our hardware?"
Conclusion: Tom: So, wrapping up this discussion on "Product Expansion of Random Codes via Analytic Techniques," the paper proves that you can find two-sided product expanding codes using random linear codes over a sufficiently large prime field with high probability.
Jane: The main takeaway is that this method successfully establishes existence without needing explicit constructions of asymptotically optimal locally testable codes, relying instead on sophisticated analytic techniques involving Rademacher matrices and Wigner words.
Lu: The paper proves that the injectivity condition holds with high probability when the prime field size is large enough, which guarantees the two-sided product expansion property for random codes in this setting.
Meng: For practical deployment, it means we have a solid probabilistic guarantee for generating codes that possess these desirable properties without having to rely on computationally expensive optimal code searches.
Lalam: I’m very confident in this conclusion; the paper successfully demonstrates that for fixed dimensions and rates bounded away from zero and one, independent random linear codes over a sufficiently large prime field will have constant two-sided product expansion with a probability tending to one.
Tom: It’s about using randomized methods to bypass the need for perfect initial constructions of these complex objects. We are leveraging matrix analysis to show that randomness is often enough when you pick the right scale.
Jane: This work opens the door for designing systems based on product expansion principles even before we have those theoretically perfect codes in hand.
Lu: And it points toward using these analytic techniques as a way to verify and potentially improve future constructions, pushing us toward more efficient code families.
Meng: For deployment, this means we can afford to be probabilistic in our design choices for the code structure because the math gives us a strong assurance about what we're getting.
Lalam: The full title is "Product Expansion of Random Codes via Analytic Techniques," and it’s a significant step in proving that these properties are accessible through random sampling when you have enough resources.
Cornell University
cs.IT, cs.CC, cs.DM, math.IT
Submitted: 2026-10-01
Updated: 2026-11-05
Comments: 100 pages. New results in Part II and fixed typos
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 83/100
The gist: The paper provides a proof for two-sided product expanding codes based on independent random linear codes over sufficiently large prime fields…
Key concepts
- Two-sided product expanding codes
- These are codes where, when you combine multiple independent component codes, every possible combination (represented by an $\varepsilon$-closed set) is 'inner-generated' in the sum of the component codes. This property is crucial for proving that the overall system exhibits strong expansion characteristics.
- Random Rademacher matrices
- These are random matrices whose entries are independent random variables, typically taking values like $\pm 1$. The paper uses these matrices to generate the generator matrices of the component codes when working over real numbers. This probabilistic approach allows for existence proofs without needing specific, pre-constructed optimal codes.
- Plane-interaction matrix ($K$)
- This matrix represents how different subsets of coordinates interact within the code structure. Bounding its expected operator norm is a key technical step. By decomposing $K$ into directional blocks and using random matrices, the authors can establish bounds that guarantee this interaction is sufficiently small (less than one) over a prime field.
- Inner-generatedness
- A set of vectors is inner-generated if every vector in that set can be written as a linear combination of the other vectors in the set. In this context, proving that every $\varepsilon$-closed subset is inner-generated ensures the code possesses the desired two-sided product expansion property.
Terminology
Summary
The paper provides a proof for two-sided product expanding codes based on independent random linear codes over sufficiently large prime fields, without requiring explicit constructions of asymptotically optimal locally testable codes (c3-LTCs). p. 0 We give a proof of the existence of two-sided product expanding codes which, unlike the earlier
result of Kalachev and Panteleev (FOCS, 2025), does not rely on explicit constructions of asymptotically
optimal locally testable codes (c
3
-LTCs). For every fixed number of component codes and dimensions
whose rates are bounded away from zero and one, we show that independent random linear codes over a
sufficiently large prime field have constant two-sided product expansion with probability tending to one. edu
Nicholas Spooner
Cornell University
nspooner@cornell. edu
Abstract
Beginning with the work of Dinur, Lin, and Vidick (FOCS, 2024), tensor codes with constant product
expansion have been foundational to recent advances in quantum locally testable codes (qLTCs) based
on cubical complexes.Where the paper says it
Where the paper says it
The core argument involves establishing that for every epsilon-closed set M, the corestriction maps of the component codes (C i) i in [D] and their duals (C i) i in [D] are simultaneously injective over a single prime field with high probability. p. 0 We give a proof of the existence of two-sided product expanding codes which, unlike the earlier
result of Kalachev and Panteleev (FOCS, 2025), does not rely on explicit constructions of asymptotically
optimal locally testable codes (c
3
-LTCs). For every fixed number of component codes and dimensions
whose rates are bounded away from zero and one, we show that independent random linear codes over a
sufficiently large prime field have constant two-sided product expansion with probability tending to one. 4 Atom decomposition . 27
5 Two-Sided Product Expansion Over Random Codes 29
6 Injectivity of the Corestriction Map Via the Plane-Interaction Matrix 30
6. We now elaborate on these steps in detail. 1 Reducing to showing a fixed ε-closed set is inner-generated
As mentioned in the introduction, two important results from [KP25] are that the product expansion of a
collection of codes is implied by every ε-closed set being inner-generated (Lemma 19) and that ME codes
exist.Where the paper says it
Where the paper says it
Where the paper says it
The technical foundation relies on working over the reals using random Rademacher matrices for the generator matrices of the component codes. p. 0 To replace the use of c
3
-LTCs, we develop several new techniques that we view as interesting in
their own right. Instead of working directly over finite fields, we work over the reals and use random
Rademacher matrices for the generator matrices of the component codes. 2 Proving an ε-closed set is inner-generated by the norm of its plane-interaction matrix . 3 Bounding the norm of the plane-interaction matrix by the expected value of Rademacher chaos polynomials . By cleverly decomposing KM into a constant number of blocks with easily describable norms and
taking the generator matrices Gi ∈ R
ki×n of the codes C1, . , CD to have Rademacher entries, we can
bound the norm of KM by the expected value of Rademacher chaos polynomials. 2 Proving an ε-closed set is inner-generated by the norm of its planeinteraction matrix
Random model We begin by defining the random Rademacher model we will use in the proof of
Lemma 2. To sample Gi ∈ R
ki×n, we take it to have columns gi(j) ∈ R
ki
indexed by j ∈ [n] where
gi(j) = k
−1/2
i
(σ
(i)
1,j , . From here, we we show that
the extendability of ε-closed sets can be reduced to controlling the operator norm of sparse restrictions
of carefully chosen Gram matrices. Applying the trace power method to bound this norm reduces to
bounding the number of possible labelings of certain closed walks on bipartite graphs, which we bound
using the sparsity of the operators and bounds on the number of equivalence classes of weak Wigner
words from Anderson and Zeitouni (Probab. Applying the trace power method to bound this norm reduces to
bounding the number of possible labelings of certain closed walks on bipartite graphs, which we bound
using the sparsity of the operators and bounds on the number of equivalence classes of weak Wigner
words from Anderson and Zeitouni (Probab. Theory Relat. Our proof has four main parts:
1. Using Lemma 19 and the existence of maximally extendable codes from [KP25], we reduce product
expansion to showing that, for a fixed ε-closed set M ⊆ [n]
D, there is a collection of codes (over the
reals) for which M is inner-generated. From here, we we show that
the extendability of ε-closed sets can be reduced to controlling the operator norm of sparse restrictions
of carefully chosen Gram matrices. Applying the trace power method to bound this norm reduces to
bounding the number of possible labelings of certain closed walks on bipartite graphs, which we bound
using the sparsity of the operators and bounds on the number of equivalence classes of weak Wigner
words from Anderson and Zeitouni (Probab. 2 Proving an ε-closed set is inner-generated by the norm of its plane-interaction matrix . 3 Bounding the norm of the plane-interaction matrix by the expected value of Rademacher chaos polynomials .Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The analysis further involves bounding the expectation of tr((T T) p) using techniques related to closed walks and weak Wigner words (Definitions 8. p. 0 From here, we we show that
the extendability of ε-closed sets can be reduced to controlling the operator norm of sparse restrictions
of carefully chosen Gram matrices. Applying the trace power method to bound this norm reduces to
bounding the number of possible labelings of certain closed walks on bipartite graphs, which we bound
using the sparsity of the operators and bounds on the number of equivalence classes of weak Wigner
words from Anderson and Zeitouni (Probab. From here, we we show that
the extendability of ε-closed sets can be reduced to controlling the operator norm of sparse restrictions
of carefully chosen Gram matrices. Applying the trace power method to bound this norm reduces to
bounding the number of possible labelings of certain closed walks on bipartite graphs, which we bound
using the sparsity of the operators and bounds on the number of equivalence classes of weak Wigner
words from Anderson and Zeitouni (Probab. From here, we we show that
the extendability of ε-closed sets can be reduced to controlling the operator norm of sparse restrictions
of carefully chosen Gram matrices. Applying the trace power method to bound this norm reduces to
bounding the number of possible labelings of certain closed walks on bipartite graphs, which we bound
using the sparsity of the operators and bounds on the number of equivalence classes of weak Wigner
words from Anderson and Zeitouni (Probab.Where the paper says it
Where the paper says it
Where the paper says it
The final result is stated in Theorem 5. p. 3 ) that
the proof of [KP25] relies on an explicit construction to obtain an existential result. The main contribution
of this work is a “purely” probabilistic proof of (a variant of) Theorem 1. , kD
satisfying ρn ≤ ki ≤ (1 − ρ)n, there is a prime
p = O
2
n
D
n
D log n
such that independent uniformly random codes Ci ⊆ F
n
p of dimensions ki are two-sided ν-product expanding
with probability at least 1 − 1/ log(n + 1). The constant in the field-size bound depends only on D.Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Develop a method for constructing two-sided product expanding codes that does not rely on explicit constructions of asymptotically optimal locally testable codes (c3-LTCs) by working over the reals with random Rademacher matrices for generator matrices. This allows the system to generate codes whose existence is proven probabilistically without needing pre-existing optimal local codes.
-
Implement a framework that uses the trace power method and weak Wigner words to bound the operator norm of sparse tensor Gram matrices, enabling efficient verification of inner-generatedness for given sets in random linear codes. This allows the system to rapidly assess whether a set is inner-generated by checking if the norm of its plane-interaction matrix is less than one.
-
Create an algorithm that leverages the decomposition of the plane-interaction matrix into directional blocks and subsequent bounding via expected operator norms to efficiently estimate the probability that this interaction matrix has an operator norm less than one over a prime field. This provides a robust probabilistic guarantee for two-sided product expansion in random codes with rates in any interval with nonempty interior.
-
Design a system capable of proving the simultaneous injectivity of corestriction maps for both the code and its dual over a single prime field by utilizing real sign witnesses and Schwartz-Zippel arguments. This allows the system to establish two-sided product expansion for both the original codes and their duals concurrently, significantly strengthening the bounds compared to results relying on only one tuple of codes.
-
Develop a mechanism to select a single characteristic that simultaneously satisfies the injectivity requirements for all ε-closed sets and both code tuples (original and dual). This allows the system to sample random codes over a single, sufficiently large prime field that guarantees two-sided product expansion for all required parameters at once.
Abstract
Beginning with the work of Dinur, Lin, and Vidick (FOCS, 2024), tensor codes with constant product expansion have been foundational to recent advances in quantum locally testable codes (qLTCs) based on cubical complexes. Informally, product expansion says that any low-weight parity check of the tensor code can be written as the sum of few parity checks of each component code in each dimension. Recent work of Kalachev and Panteleev (FOCS, 2025) showed that tensors of random linear codes have constant product expansion. In this work we initiate the study of random linear codes with prescribed automorphism groups. For every sufficiently large prime k, we construct pairs of rate 1/2 MDS codes of length 2k, over finite fields whose size depends on k, that have constant two-sided product expansion and are invariant under the simultaneous cyclic shift of two cycles of length k. This shift is the local action in the cube complexes of Rungtanapirom, Stix, and Vdovina (Internat. J. Algebra Comput., 2019). Along the way we give a proof of the existence of two-sided product expanding codes which, unlike the earlier result of [KP25], does not rely on explicit constructions of asymptotically optimal locally testable codes. Our proof relies on several new techniques that we view as interesting in their own right. Instead of working directly over finite fields, we work over the reals and use random Rademacher matrices for the generator matrices of the component codes. From here, we show how to relate product expansion to the operator norm of sparse restrictions of carefully chosen Gram matrices, which we bound using tools from random matrix theory. More generally, we propose a method for studying properties of random linear codes by lifting to random codes over R and C, which we anticipate will be applicable more broadly to existential problems in coding theory.
Sources
- Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs
- Good Quantum LDPC Codes with Linear Time Decoders
- New Codes on High Dimensional Expanders
- On Good $2$-Query Locally Testable Codes from Sheaves on High Dimensional Expanders
- Asymptotically Good Quantum Locally Testable Codes
- Symmetric Self-Dual Quantum Codes on High Dimensional Expanders
- High-dimensional Expansion of Product Codes is Stronger than Robust and Agreement Testability
- Two-sided Robustly Testable Codes
- The automorphism groups of random linear codes
- Graph codes and local systems
- Asymptotically Good Quantum and Locally Testable Classical LDPC Codes
- Maximally Extendable Sheaf Codes
- Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes
Related papers
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound
- Second-Order Image Characterization with Distortion and Secrecy