we-solve (beta)

CS-88 · computer science · mathematics · Computer science

The robustness of the tensor product

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Fix a finite alphabet $A$. Let $R\subseteq A^n$ and $C\subseteq A^m$ be nonempty codes whose product $P=R\otimes C\subseteq A^{m\times n}$ is nonempty: every row of a matrix in $P$ belongs to $R$, and every column belongs to $C$. For words of equal length, relative Hamming distance is the proportion of differing coordinates; distance to a code is its minimum over codewords. Use the analogous normalized entry distance for matrices. For $M\in A^{m\times n}$, put \[ \rho(M)=\frac12\left(\frac1m\sum_{i=1}^m d(M_{i,*},R) +\frac1n\sum_{j=1}^n d(M_{*,j},C)\right). \] The pair is $\alpha$-robust if $\rho(M)\ge\alpha d(M,P)$ for every $M$. Characterize families $(R_t,C_t)$ for which one constant $\alpha>0$ works for all $t$ as the lengths grow.

The family quantifier is essential: every fixed nonempty finite product has some positive minimum ratio over matrices outside it. The desired bound is independent of the lengths. The source also allows the especially important case of linear codes over a finite field; the definition above does not require linearity. Characterize the component-code conditions that yield a uniform lower bound, using this average row-and-column test and this precise distance.

Short English statement

Which families of code pairs make average row and column errors control the distance of a whole matrix from their product code by one fixed constant?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

CS-88-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-88

The robustness of the tensor product

Definitions and mathematical statement

Fix a finite alphabet $A$. Let $R\subseteq A^n$ and $C\subseteq A^m$ be nonempty codes whose product $P=R\otimes C\subseteq A^{m\times n}$ is nonempty: every row of a matrix in $P$ belongs to $R$, and every column belongs to $C$. For words of equal length, relative Hamming distance is the proportion of differing coordinates; distance to a code is its minimum over codewords. Use the analogous normalized entry distance for matrices. For $M\in A^{m\times n}$, put \[ \rho(M)=\frac12\left(\frac1m\sum_{i=1}^m d(M_{i,*},R) +\frac1n\sum_{j=1}^n d(M_{*,j},C)\right). \] The pair is $\alpha$-robust if $\rho(M)\ge\alpha d(M,P)$ for every $M$. Characterize families $(R_t,C_t)$ for which one constant $\alpha>0$ works for all $t$ as the lengths grow.

The family quantifier is essential: every fixed nonempty finite product has some positive minimum ratio over matrices outside it. The desired bound is independent of the lengths. The source also allows the especially important case of linear codes over a finite field; the definition above does not require linearity. Characterize the component-code conditions that yield a uniform lower bound, using this average row-and-column test and this precise distance.

Short English statement

Which families of code pairs make average row and column errors control the distance of a whole matrix from their product code by one fixed constant?

Research attempt

Scope and process.
This is a GPT-6 Astra Ultra research attempt dated 2 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.
Literature and scope.
Goldreich and Meir [R1] construct good component codes whose tensor product is not robustly testable: positive rate and relative distance alone are insufficient. This is a warning against claiming a general characterization from those two parameters. The canonical question also allows nonlinear codes and does not require positive rate. We prove two elementary uniform robustness statements in that full setting and identify why a finite verification cannot settle a family. All distances below are normalized by the number of entries concerned.
Uniform robustness for repetition codes.
Take $R=\{a^n:a\in A\}$ and $C=\{a^m:a\in A\}$. Their product consists exactly of the constant matrices. Given $M$, replace each row by a nearest constant row and call the resulting matrix $U$. Write $r=d(M,U)$, the mean row distance. Independently replace each column by a nearest constant column to form $V$, and write $c=d(M,V)$. Ties can be resolved arbitrarily. The triangle inequality gives \[ \delta=d(U,V)\le r+c. \] Let $a_i$ be the constant symbol in row $i$ of $U$, and $b_j$ the symbol in column $j$ of $V$. If $p_a$ and $q_a$ are the proportions of row and column labels equal to $a$, then \[ 1-\delta=\sum_{a\in A}p_aq_a \le\max_{a\in A}p_a. \] Choose a symbol attaining that maximum. The distance from $U$ to the all-$a$ matrix is $1-p_a\le\delta$, so $d(M,P)\le r+\delta\le2r+c$. Interchanging rows and columns gives $d(M,P)\le r+2c$. Taking the smaller bound yields \[ d(M,P)\le\min(2r+c,r+2c) \le\tfrac32(r+c)=3\rho(M). \] Thus $\alpha=1/3$ works uniformly for all positive $m,n$ and every finite alphabet. No linearity or field operations were used.

This constant is a certificate, not a claim of optimality. Over the binary alphabet, take an even number of rows, half constantly zero and half constantly one. Then $r=0$, $c=1/2$ and $d(M,P)=1/2$. Any universal constant for repetition-code pairs is consequently at most $1/2$. The elementary argument confines that best constant to $[1/3,1/2]$ without deciding its exact value.

A second family and a failed necessary condition.
If $R=A^n$ is the full row code and $C$ is any nonempty code, columns can be repaired independently to their nearest codewords. There are no further row restrictions. Therefore \[ d(M,R\otimes C)=\frac1n\sum_j d(M_{*,j},C), \qquad \rho(M)=\tfrac12d(M,R\otimes C). \] Every such family is uniformly $1/2$-robust. For a proper product this constant is exact; when the product is the whole matrix space the inequality is vacuous. In particular, over $A=\{0,1\}$ let $C_m=\{0^m,10^{m-1}\}$ and let $R_n=A^n$. Both are linear binary codes, but their minimum relative distances are $1/m$ and $1/n$, tending to zero. The product remains $1/2$-robust as both dimensions grow. Thus a uniform positive lower bound on the distances of both components is not necessary for the broad characterization stated here. This example does not contradict results that impose additional rate or nontriviality hypotheses.
Verification and the family quantifier.
Certificate [R2] enumerates every binary matrix for all dimensions $1\le m,n\le3$, computes the row, column and constant-matrix distances exactly, and checks the $1/3$ inequality. It also checks the striped example above. These finite computations test normalizations and edge cases; the proof supplies the constant independently of dimensions. Indeed, for any fixed nonempty finite product, a matrix outside it has at least one invalid row or column. Correcting that line needs at least one entry change, giving $\rho(M)\ge1/(2mn)$. Since $d(M,P)\le1$, the bound $\rho(M)\ge d(M,P)/(2mn)$ follows. This establishes positivity for each fixed pair but tends to zero with the lengths and says nothing about a uniform family constant.
Final status and first remaining gap.
UNRESOLVED. Two broad special families admit uniform constants, and positive component distance is shown unnecessary in the stated generality. A characterization for arbitrary code pairs still requires control of the global compatibility of row and column repairs. The repetition proof obtains that control from constant labels; there is no replacement argument here for unrestricted codes.

Sources

Go to contribution →