Two-Sided Product Expanding Codes via Rademacher Matrices

1 Introduction

• Product expansion asks whether check-product codewords can be decomposed into few nonzero line-codewords relative to their Hamming weight, with a constant parameter as the component length grows.It is relevant to tensor codes used as local codes in cubical-complex constructions.Source: §1 · pp. 3–4
• Kalachev and Panteleev [KP25] proved an existence theorem for two-sided product-expanding collections with a fixed number of component codes, but their proof used explicit c^3-LTCs [DELLM22] [PK22].The earlier theorem allows component-code rates in intervals with nonempty interior in (0, 1).Source: §1 · p. 4

1.1 Motivation

• The work targets two-sided product-expanding codes whose components have nontrivial automorphism groups, and coboundary expanders usable as local codes on complexes such as simplicial HDXs.The random-code model of [KP25] cannot enforce the symmetry requirement because random linear codes have trivial automorphism groups with high probability [LWZ26].Source: §1.1 · pp. 4–5
• The c^3-LTC witness used in the prior approach is not known to lie in a family restricted to prescribed symmetries, leaving maximal extendability in that family without an established witness.The authors remove this barrier by proving extension properties directly rather than relying on c^3-LTCs.Source: §1.1 · p. 5

1.2 Our results

• For fixed D and rates bounded between ρ and 1 − ρ, the theorem gives two-sided ν-product expansion over prime fields with probability at least 1 − 1/log(n + 1).The constant in the field-size bound depends only on D; the result recovers existence without c^3-LTCs.Source: §1.2 · p. 6
• The proof requires the characteristic to grow with n and does not establish the result in characteristic two.The authors say this yields a constant-sized alphabet rather than a binary alphabet in applications such as.Source: §1.2 · p. 6
• The proof uses real generator matrices with independent Rademacher entries, reducing ε-closed-set extendability to a norm bound and then to counting labeled closed walks on bipartite graphs.The trace power argument uses weak Wigner word equivalence-class bounds from Anderson and Zeitouni, together with sparsity, before transferring the result to finite fields by a Schwartz-Zippel argument.Source: §1.2 · p. 6

AI Methodology

• ChatGPT Pro 5.6 and 6 helped check correctness and copy edit the paper.The tools also suggested the connection to.Source: AI Methodology · p. 7
• The authors take responsibility for all results, content, and presentation.Source: AI Methodology · p. 7

2.1 Reducing to showing a fixed ε-closed set is inner-generated

• For each fixed ε-closed set M, the proof constructs a code collection making M inner-generated; a maximally extendable code can inherit this property across different witness collections.Unlike the strategy attributed to Kalachev and Panteleev [KP25], the witnesses need not come from one collection. The real-matrix argument is transferred to finite fields using determinant polynomials and Schwartz–Zippel, requiring a sufficiently large prime characteristic.Source: §2.1 · p. 8

2.2 Proving an ε-closed set is inner-generated by the norm of its plane-interaction matrix

• If the plane-interaction matrix K_M has operator norm below 1, the associated map is injective and M is inner-generated; small ε ensures this for some real Rademacher-generator choice.The atom decomposition makes intersecting planes’ images orthogonal, leaving interactions between non-intersecting planes as the obstruction; the expected norm is made less than 1/2 before applying Markov’s inequality.Source: §2.2 · pp. 10–11

2.3 Bounding the norm of the plane-interaction matrix by the expected value of Rademacher chaos polynomials

• Bounding each plane-pair block separately fails because there can be many planes, so the proof groups blocks by direction into at most 4^D directional blocks.Each directional block is further decomposed into at most 2^D terms, allowing bounds on the grouped blocks to control the full matrix by the triangle inequality.Source: §2.3 · p. 11, Directional block decomposition · p. 11

Directional block decomposition

• For sparse coordinate restrictions, the proof applies a trace-power bound and expands it into Rademacher chaos polynomials whose expectations vanish unless every sign occurs an even number of times.The directional-block factors include sparse restrictions derived from ε-closed sets, with sparsity controlled by ε.Source: Directional block decomposition · p. 12

2.4 Bounding the expected value of Rademacher chaos polynomials using weak Wigner words

• Each sign monomial corresponds to a closed walk on a bipartite graph, turning the norm bound into counting index choices that satisfy the even-sign condition.The overview says the final count uses ε-closure and weak Wigner word tools from Anderson and Zeitouni (2006).Source: §2 · p. 7, §2.4 · p. 13
• Sign monomials with expectation 1 correspond to closed, non-left-backtracking bipartite walks whose edges are each traversed an even number of times.The proof counts these walks by shape and vertex labels.Source: §2.4 · p. 13
• These walks are weak Wigner words, whose shape count is bounded using Anderson and Zeitouni’s equivalence-class bound, organized by walk deficiency.Deficiency is 2m+1 minus the number of distinct vertices in a walk of 4m edge traversals.Source: §2.4 · p. 13
• After fixing walk shapes, η-sparsity bounds valid vector labelings; summing over deficiencies and λ choices and taking the 2m-th root yields Equation (2) with m = D log n.When choosing a vector with f free coordinates, at most ηn^f valid choices remain.Source: §2.4 · pp. 14–15

3.1 Lines, planes, and sparseness

• An ε-closed set has each axis-parallel line either fully contained in it or intersecting it in at most εn points; an ε-sparse set contains no full axis-parallel line.Source: §3.1 · pp. 15–16

3.2 Maximal planes

• Maximal planes are maximal-by-inclusion planes contained in M, and together they cover M; their intersections provide additional planes for the framework.The section uses maximal planes as a structured decomposition of M.Source: §3.2 · pp. 16–17

3.3 Anchor sets

• For ε-closed M, the anchors of maximal I-planes form an ε-sparse set, and the anchors of intersection-generated planes have a bound with a factor of 2^D.The stated intersection-anchor bound assumes 0 < 2^Dε < 1.Source: §3.3 · pp. 17–18

3.4 Tensor codes and related notions

• The section defines product expansion and two-sided product expansion by requiring the expansion property for both component codes and their duals.The setup also defines tensor and check-product codes, extendability, and inner-generatedness.Source: §3.4 · pp. 19–20

3.5.1 Linear algebra facts; 3.5.2 A useful estimate on the distribution of primes

• The linear-algebra preliminaries collect operator-norm facts, while the prime estimate guarantees a prime p not dividing m with q < p ≤ C(q + log(2m)).Source: §3.5.1 · p. 20, §3.5.2 · p. 20

4.1 The tensor code, restrictions, and extendability

• A set M is extendable exactly when the restriction map from global tensor-code words to its locally valid words is surjective.The local words satisfy the component-code checks on every axis-parallel line contained in M.Source: §4.1 · p. 23

4.2 The check-product code, corestrictions, and inner-generatedness

• A set M is inner-generated exactly when the check-product corestriction map is injective, equivalently when its kernel is zero.Source: §4.2 · p. 25

4.3 Putting it all together

• Corestriction maps are dual to restriction maps, linking extendability to inner-generatedness; the section also defines polynomially parametrized insertion maps that specialize to the code maps.The polynomial identities remain compatible under specialization, including for matrices without a rank requirement.Source: §4.3 · pp. 25–27

4.4 Atom decomposition

• The direct sum of the plane atoms maps surjectively onto G(M), giving a decomposition that covers the space without asserting it is a direct-sum decomposition of G(M).The proof applies to the formal cokernel after real specialization.Source: §4.4 · pp. 27, 29

5 Two-Sided Product Expansion Over Random Codes

• The main result reduces to simultaneous injectivity of corestriction maps for a random tuple of codes and its dual on every ε-closed set.The paper proves this injectivity statement in Theorem 6.1.Source: §5 · p. 29
• For fixed D, ρ, and ε and sufficiently large n, independent random codes with dimensions ρn ≤ k_i ≤ (1−ρ)n are two-sided γ(ε, D)-product expanding over a prime field.The proof gives an expansion guarantee with probability at least 1−1/log(n + 1).Source: §5 · pp. 29–30
• With high probability, injectivity makes every ε-closed set inner-generated, and Lemma 5.2 converts inner-generatedness into product expansion for both tuples.The injectivity event has probability at least 1−1/log(n + 1).Source: §5 · p. 30

6 Injectivity of the Corestriction Map Via the Plane-Interaction Matrix

• Theorem 6.1 establishes simultaneous injectivity for every ε-closed set and for both the component codes and their duals under its stated random-code and parameter conditions.The theorem assumes fixed D, 0 < ρ < 1/2, sufficiently small ε, sufficiently large n, and ρn ≤ k_i ≤ (1−ρ)n.Source: §6 · p. 30

6.1 Interactions between the corestriction maps of planes

• For distinct intersecting planes, the global corestriction maps are orthogonal on their atoms, while the map for a single plane is an isometry on its atoms.These interaction identities motivate the matrix construction in the next subsection.Source: §6.1 · pp. 32–33

6.2 Constructing the plane-interaction matrix

• The plane-interaction matrix K packages the off-diagonal interactions of the planes’ restricted corestriction maps, while their Gram operator has identity diagonal blocks.The matrix H is the Gram operator minus the identity on the atom space; K extends this interaction operator to the larger space.Source: §6.2 · p. 34

6.3 Injectivity of τM over the reals

• For a fixed ε-closed set, τM is injective over the reals with probability at least 1 − C_D,ρ,ε under the Rademacher model.The proof reduces this to showing that K has operator norm less than one, which implies injectivity.Source: §6.3 · pp. 34–35

6.3.1 Injectivity of τM from the operator norm of K

• Since ∥H∥op ≤ ∥K∥op, a bound ∥K∥op < 1 yields injectivity; if all planes in P(M) pairwise intersect, K = 0 and τM is injective.The obstruction identified here is a pair of maximal planes with empty intersection.Source: §6.3.1 · pp. 35–36

6.4 From the reals to finite fields

• A real sign witness for a fixed ε-closed set yields injectivity for independent uniformly random codes over a sufficiently large prime field.The transfer applies for sufficiently large n and does not require a full-row-rank assumption for the real witness.Source: §6.4 · pp. 36–37
• Whenever fσ(x) ≠ 0, the rank bounds and βxαx = 0 imply Im αx = ker βx and injectivity of βx; full row rank identifies this with injectivity of τM.At the real sign witness, the determinant is nonzero because the image of ασ equals the kernel of βσ and their complementary spaces span the full space.Source: §6.4 · p. 37
• A prime p can be chosen with max{2D + 1, dσ log(n + 1)} < p, avoiding mσ so that fσ remains nonzero modulo p.The real inner product is used only to establish the nonzero determinant witness.Source: §6.4 · pp. 37–38
• One prime chosen before sampling preserves every witness polynomial across all ε-closed sets and both dimension profiles, enabling simultaneous injectivity over F_{p^t}.The same prime also works over every extension F_{p^t}.Source: §6.4 · pp. 39–40
• For random code tuples, the failure probabilities are at most d+/p^t for the codes and d−/p^t for their duals; a union bound combines them.The argument applies to simultaneous injectivity of the corestriction maps across the ε-closed sets.Source: §6.4 · p. 40

7 Bounding the Operator Norm of the Plane-Interaction Matrix

• For fixed D, ρ, ε and ε-closed M with ρn ≤ k_i ≤ n, Lemma 7.1 bounds E||K||op, which Markov’s inequality converts into the needed probability bound.The theorem and lemma statements specify these conditions, but the supplied passages omit the bound’s formula.Source: §7 · p. 41

7.1.1 Directional block decomposition

• Grouping plane blocks K_P,Q into directional blocks K_I,J reduces the bound on ||K||op to bounds on each block, combined by the triangle inequality.The text identifies at most 4^D direction pairs.Source: §7.1 · p. 41, §7.1.1 · p. 42

7.1.2 Decomposition over sets of mutually fixed coordinates

• Each K_I,J is further decomposed over subsets of coordinates fixed by both directions, yielding restricted operators whose norms factor into products of operator norms.This decomposition uses ε-closedness of M and the random Rademacher entries of the generator matrices.Source: §7.1 · p. 41, §7.1.2 · p. 43, §7.2 · p. 44

7.2 Bounding the expected operator norm of restricted directional blocks

• The restricted-block analysis bounds expected norms using generator-matrix norms and maxima of sparsely applied operators, with sparsity and independence conditions supplied by ε-closedness and the Rademacher signs.Proposition 7.11 treats fixed η-sparse index sets with |Λ| ≤ n^ν, ν + q ≤ D, and normalized Rademacher matrices satisfying k_i ≥ ρn.Source: §7.2 · pp. 44–45

7.3 Deferred proofs

• The deferred proofs verify the directional-block and restricted-operator factorizations and use standard Gaussian-matrix facts to support the Rademacher norm bounds.The passages describe coordinate reordering as norm-preserving and state that Gaussian-matrix facts are used to prove Proposition 7.9.Source: §7.3 · pp. 46, 49
• For k ≥ ρn, Proposition 7.9 bounds the expected operator norm of a normalized random Rademacher matrix.The bound’s formula is not present in the supplied passage.Source: §7.3 · pp. 49–50
• The proof compares the Rademacher matrix with a Gaussian matrix, then applies a bound on the norm of a random Gaussian matrix.The comparison uses Lemma 7.12 and the Gaussian matrix bound from Lemma 7.13, both attributed to.Source: §7.3 · pp. 49–50

8 Bounding the Operator Norm of Sparse Tensor Gram Matrices

• The section targets the expected maximum operator norm over a family of sparse operators formed from tensors of random Rademacher operators.The family is indexed by Λ with |Λ| ≤ n^ν, and its sets Xλ and Yλ are η-sparse for a fixed η.Source: §8 · p. 50
• The setup uses independent normalized Rademacher matrices Gi and their centered Gram matrices Di = Gi^T Gi − I, with coordinate projections onto sparse sets.Each Gi has ki rows, where ki ≥ ρn.Source: §8 · p. 50

8.1 Derivation of the sign monomials

• The trace-power method expands traces of powers of the operators into sign monomials, whose possible nonzero contributions can then be counted.The derivation computes the trace expression and expands its terms into products of the independent signs.Source: §8.1 · pp. 50–51

8.2 Graph view of the sign monomials

• The indices in each sign monomial are repackaged as a closed walk on a bipartite graph, with left and right vertices representing the two index sets.The construction gives a correspondence between the walk tuple and the indices used to form the monomial.Source: §8.2 · p. 52
• A monomial is nonzero exactly when its walk is closed and non-left-backtracking; its expected value is 1 if every edge is traversed an even number of times, and 0 otherwise.Backtracking at left vertices is allowed, while consecutive left vertices at a right vertex must differ.Source: §8.2 · pp. 52–53
• Bounding the trace expectation reduces to counting qualifying walk labelings, using operator sparsity and equivalence-class bounds for weak Wigner words from.The counted walks traverse every edge an even number of times.Source: §8.2 · pp. 52–53

8.3 Weak Wigner words

• A weak Wigner word is a closed word whose graph has every edge traversed at least twice.A word is a finite sequence of letters, and its graph has the letters as vertices and consecutive letters as edges.Source: §8.3 · p. 54

8.3.1 Equivalence and canonical representatives

• Word equivalence preserves length and the equality pattern among positions, encoding walk shape rather than the actual vertex labels.Equivalent words have isomorphic graphs, but graph isomorphism alone does not imply word equivalence.Source: §8.3.1 · p. 54
• The canonical representative relabels distinct letters in order of first appearance, giving equivalent words the same representative.The representative uses labels from 1 through the word’s weight.Source: §8.3.1 · p. 54

8.4 Weak Wigner words in the bipartite setting

• A bipartite walk is one whose associated graph is bipartite, with left and right vertex sets defining its two sides.The right weight is the number of right-side vertices; weak Wigner words of length 4p + 1 have at most 2p + 1 vertices.Source: §8.4 · p. 55
• Deficiency measures the loss in vertices from the maximum possible weight of a weak Wigner word.The section introduces deficiency for these walks and uses it to classify equivalence classes.Source: §8.4 · p. 55
• Bipartite equivalence matches walks through separate bijections on their left and right vertex sets, and agrees with ordinary equivalence for these walks.The parity of walk positions ensures the vertex correspondence preserves the two sides.Source: §8.4 · p. 55

8.4.1 Equivalence classes from a specified deficiency

• Walks in one equivalence class have the same weight, length, and deficiency, so classes can be grouped by deficiency.The sets Wp(∆) collect classes of even non-left-backtracking closed walks of length 4p + 1 and deficiency ∆; admissible parts partition the tuples by their classes.Source: §8.4.1 · pp. 55–56

8.5 Bounding the number of equivalence classes

• Ordinary and bipartite equivalence agree for the weak Wigner words considered, allowing the weak Wigner word bound to count bipartite-equivalence classes.The argument uses the parity of left and right positions in the words.Source: §8.5 · p. 56
• For walks with every edge traversed an even number of times, the deficiency is nonnegative and at most 2p, and the right weight is at most p.These constraints follow from the 4p edge traversals, connectedness, and the non-left-backtracking condition.Source: §8.5 · p. 56
• The number of equivalence classes of the walks is bounded using Proposition 7.9 of, which counts weak Wigner words by length and weight.The resulting corollary applies the count with the walk’s length and weight determined by its deficiency.Source: §8.5 · pp. 56–57

8.6 Bounding the size of an equivalence class of a word using sparsity

• The key counting step bounds admissible tuples jointly, because fixing one word determines only its own coordinates while all coordinate rows must still lie in the sparse sets X and Y.This joint count is where sparsity enters the bound.Source: §8.6 · p. 57
• The admissible-part bound uses the equivalence classes’ left and right weights and their deficiencies to combine labelings across the component words.The resulting estimate is stated for η-sparse X and Y and tuples of classes with specified deficiencies.Source: §8.6 · pp. 57, 59
• For each row, the coordinates whose symbols first appear there are the only free choices; if there are |Fs| such coordinates, sparsity gives at most ηn^|Fs| choices.The argument relaxes non-left-backtracking and distinctness constraints, which only weakens the upper bound.Source: §8.6 · pp. 58–59
• With p = ⌈D log(n)⌉, Lemma 8.31 bounds the contribution for each index λ and its η-sparse sets Xλ and Yλ.Its proof combines the walk-counting and admissible-part estimates, then simplifies using the parameter choices.Source: §8.6 · pp. 60–61

8.7 Putting it all together

• Proposition 8.1 considers fixed ν and q with ν + q ≤ D and at most n^ν indices, each with η-sparse sets Xλ and Yλ.The sparsity parameter is fixed independently of the signs.Source: §8.7 · p. 61
• When the indexing set Λ is empty, the expectation in the proposition is zero..Source: §8.7 · p. 61
• The proof combines Hölder’s inequality, a sum over indices, and the preceding estimates to establish Proposition 8.1.It uses |Λ| ≤ n^ν and the parameter conditions to simplify the bound.Source: §8.7 · p. 62

• The finite-field transfer requires base-field characteristic O(2nDnD log n), leaving open whether the method can work over characteristic two.Source: §9 · p. 63
• Analyzing automorphism-constrained code families remains open because non-trivial parametrizations may relate the Rademacher signs whose independence the analysis uses.Source: §9 · p. 63
• For more general sheaf codes, the main components generalize, but the clean tensor decomposition is unavailable and alternatives depend on the specific codes.Source: §9 · p. 63
• The authors ask whether polynomially parametrized code families can yield the multiplication property in cubical and simplicial settings.They identify this as relevant to quantum codes useful for computation [Ngu25].Source: §9 · p. 63