coding theorists

Abstract: Let $2\le k\le n$ and let $U\le\mathbb{F}_q^n$ be a fixed $(k-1)$-dimensional linear code. We study the $[n,k]$ maximum distance separable (MDS) codes over finite extensions of $\mathbb{F}_q$ that contain the scalar extension of $U$. Our approach constructs an auxiliary linear code from \(U\). Its full-weight words characterize the desired MDS completions. We prove that \(U\) admits an \([n,k]\) MDS completion over some finite extension of \(\mathbb{F}_q\) if and only if \(d(U)\ge n-k+1\). When this condition holds, the number of these MDS codes over $\mathbb{F}_{q^m}$ is \[\#\left\{W\le\mathbb{F}_{q^m}^n:U\otimes_{\mathbb{F}_q}\mathbb{F}_{q^m}\subseteq W,\ \dim_{\mathbb{F}_{q^m}} W=k,\ W\text{ is MDS}\right\}=\frac{χ_{δ_GM(G)}(q^m)}{q^m-1},\] where $G$ is a generator matrix of $U$, $δ_GM(G)$ is its represented derived matroid, and $χ_{δ_GM(G)}$ is its characteristic polynomial. In particular, the formula determines existence over each extension field and the least extension degree for which such an MDS code exists. Examples show that these counts may distinguish different representations of the same column matroid, while monomially inequivalent codes may have identical counts over every finite extension.

Abstract: For every prime power $q>19683$, we settle the Cheng--Murray deep-hole problem for full-length Reed--Solomon codes in every dimension $2\le k\le q-2$, with the characteristic-two cases stated explicitly. For odd $q$, the deep holes are precisely the words of degree $k$. For even $q$ and $k\ge3$, the same conclusion holds except for an additional family when $k=q-3$. In even characteristic and dimension two, every deep hole has a unique expression $a h(X)+bX+c$, where $a\ne0$ and $h$ is a normalized $o$-polynomial. The proof combines quadratic quotient algebras, graph-theoretic weighted independent-set inequalities, and planar arc completion. We also obtain normal rational curve rigidity in the corresponding nonexceptional dimensions, the projective Reed--Solomon covering radii, and distinct-coordinate solvability and remainder criteria.

Abstract: Recovering latent geometric structure from graph observations is a well-studied problem in statistical inference. Kapralov, Trevisan, and Wrzos-Kaminska (2026) introduced the problem of recovering the coordinate structure of the Boolean hypercube from a small random sample of its edges. More specifically, there are $n=2^d$ vertices, each corresponding to a distinct "feature" vector in $\{\pm 1\}^d$. Between each pair whose feature vectors are at Hamming distance one, an edge is observed independently with probability $p$. As long as the expected degree $pd$ is $\gtrsim \log d = \log \log n$, we give a polynomial-time algorithm that, given only the graph of observed edges, correctly recovers the entire feature vector of all but a vanishing fraction of vertices. This matches the information-theoretic guarantee of Kapralov, Trevisan, and Wrzos-Kaminska in polynomial rather than exponential time, resolving the algorithmic question left open by their work. Our algorithm combines a degree-$4$ sum-of-squares certificate for the structure of balanced near-minimum cuts with a rounding scheme originally developed for tensor decomposition by Ma, Shi, and Steurer (2016). The analysis relies on two novel ingredients: a sum-of-squares version of the Friedgut-Kalai-Naor theorem in Boolean Fourier analysis and a spectral concentration result for the observed subgraph of the hypercube. Finally, we provide a justification for why higher-degree sum-of-squares might be needed by showing a limitation of the basic SDP relaxation of this problem.

Abstract: We study the dimension defect of finitely many subspaces over an arbitrary field. We derive a symmetric, nonrecursive Grassmann-type formula for the dimension of their sum. The formula expresses the total dimension loss through intersections of a distinguished subspace with partial sums of the remaining subspaces, with coefficients determined by the number of subspaces involved. We also show that the formula admits a Shapley-value interpretation for the associated representable polymatroid. Grouping the correction terms by the number of participating subspaces yields a nonnegative dimension-defect profile. We prove that this profile is monotone and identify its successive gaps with the discrete curvatures of the average-rank profile. These gaps give exact remainders in two-sided defect bounds. Equality in either bound holds precisely when the images of the subspaces in the quotient by their common intersection form an internal direct sum. We also give an exact geometric decomposition of the Kinser slack into nonnegative quotient dimensions and characterize equality. Averaging these slacks over permutations and contractions recovers every defect curvature except the final one; additional representability constraints remain in the individual ordered slacks. Weighted and dual formulas accompany the expansion, and entropy analogues express the defect levels and curvatures as averages of mutual and conditional mutual information, respectively.

Abstract: A de Bruijn sequence packs all $n$-bit binary words into a cycle of length $2^n$. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when $n = 2m + 1$ is odd and the torus and windows have two rows (i.e., the torus is a "tworus"). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into $2^{m-1}$ matching blocks where each block contains the same sequence of unordered columns. Furthermore, given one such block we can generate each successive column of a tworus in amortized $\mathcal{O}(1)$-time. We also prove non-existence results for certain sizes of tori and provide algorithms for constructing multiversal cycles (perfect necklaces) of unlabeled binary words.

Abstract: We prove the following inequality for Boolean functions: $2\sum_{x\in F_2^n}f(x)wt(x)\geq wt(f)(n-deg(f))$. Using this inequality, we establish the Fourier Entropy-Influence (FEI) conjecture for Boolean plateaued functions. In particular, we show that the sharp FEI constant for the class of plateaued functions is 4. We also prove the FEI conjecture for partially bent functions and show that the corresponding sharp constant is 2. Finally, we derive several estimates for the p-biased distribution on the Boolean hypercube. Keywords: Fourier entropy, total influence, average sensitivity, plateaued function, algebraic degree, Reed-Muller code, p-biased distribution.

Abstract: We consider infinite walks in $\mathbb{N}^k$ with standard unit basis vector steps that avoid $t$ collinear points, and show that these walks exist for $(k,t) \in \{(6,3), (4,4), (3,7)\}$. In particular, our construction for $k = 3$ improves the previous bound $189$, obtained by Lidbetter, to $7$. Our results also imply the existence of infinite words over small finite alphabets that are weakly abelian squarefree (resp., weakly abelian cubefree, weakly abelian 6th-power-free).

Abstract: Chen and Xie recently proved, using the Ashikhmin--Barg lemma on minimal vectors, that every binary linear $[n,k,d]$ code with $k=n-2d+2+v$ ($v\ge 0$) has no codewords of weight in the interval $[2d-v,\,2d-1]$. Their argument uses two of the five basic properties of minimal vectors established by Ashikhmin and Barg (1998). In this note we utilize the third property, the disjoint-support decomposition of non-minimal codewords in binary codes, to generate a \emph{mirror} vanishing band on the other side of $2d$: if $A_{d+1}=\cdots=A_{d+t}=0$ for some $t\ge 1$ and $k\ge n-2d+1$, then $A_w=0$ for all $w\in[2d+1,\,2d+t]$. Combining the two bands, the number of nonzero weights of such a code is at most $n-d-v-2t+1$, improving the Chen--Xie bound $n-d+1-v$ by $2t$.

Abstract: Let $A\in\mathbb{R}^{m\times n}$ have columns of Euclidean norm at most one. We prove that $\operatorname{disc}(A)\le2395\left(1+\log_+\frac n9\right)^{1/4}+2\sqrt2$. Here $\log_+t=\max\{0,\log t\}$. Building on Bansal and Jiang's affine spectral independence framework, we remove the $(\log\log n)^{7/4}$ factor from their bound. The fourth root comes from balancing the logarithmic decrease in the alive dimension against the fourth power of the row thresholds. Historical exponential sums control the covariance budget across size classes with summable thresholds. An exact threshold-sum certificate gives the coefficient $2395$, and rounding at most eight remaining fractional coordinates costs $2\sqrt2$. The finite construction also gives partial colourings from any prescribed starting point and at any prescribed depth, preserving existing signs. We formalize the partial- and full-colouring theorems in Lean, including the finite trajectory, exact threshold sum and final rounding, with Bansal--Jiang Theorem A.4 as the sole external research theorem assumption.