CS Paper Radar

A Counterexample to the Tang Zhang Schatten Norm Conjecture and Sharp Positive Results

Zijian Zeng, Houde Liu, Kurunathan Ratnavelu

cs.LG math.COmath.FA ·submitted 2026-08-16 06:10 UTC · v1
theory

Abstract

For $m\geq 2$, let $c_p(m)$ be the all-dimensional best constant in $$ \left\|\sum_{k=1}^m A_k\right\|_p \leq c_p(m)\left\|\sum_{k=1}^m |A_k|\right\|_p. $$ Tang and Zhang conjectured an explicit formula for every finite $p>1$. We disprove the conjecture with two explicit real $2\times 2$ rank-one matrices at $p=3/2$. The comparison is certified by seven strict rational inequalities and, in particular, places the attained ratio above $207/200$, while the conjectured constant lies below $207/200$. On the positive side, we prove the conjectured sharp bound for every family of rank-at-most-one summands when $2\leq p<\infty$, and classify all equality cases. We also prove the corresponding endpoint statement for $p=\infty$. Finally, for arbitrary complex matrices, we establish the conjectured sharp constant in the case $m=2$, $p=4$.

Comment
9 pages, 0 figure,

Closest papers

Nearest neighbours by meaning across the whole index.

On integral polytopes related to Edmonds' problem

cs.DM math.CO ·2026-09-17 ·Hiroshi Hirai
similarity 0.62
Abstract

In this paper, we study polyhedral aspects on commutative and noncommutative Edmonds' problems for computing the rank of linear symbolic matrix $A = \sum_{k=1}^m A_k x_k$. We regard them as linear optimization over integral polytopes ${\cal P}(A)$ and ${\cal Q}(A)$, respectively, which are obtained by the convex hulls of exponent vectors of subdeterminants of~$A$ and its blow-ups $A^{\{d\}} = \sum_{k=1}^m A_k \otimes X_k$ $(d=1,2,\ldots)$. By extending previously known results on nc-rank, we establish a hierarchy of integral polytopes ${\cal P}(A) \subseteq {\cal P}^{\leq 2}(A) \subseteq {\cal P}^{\leq 3}(A) \subseteq \cdots = {\cal Q}(A)$ and show that the integrality gap of ${\cal Q}(A)$ relative to ${\cal P}(A)$ is at least $1/2$. Further, we show that if each $A_k$ is rank-2 skew-symmetric, then the above hierarchy terminates at the second level and the integrality gap is improved to $2/3$.

0.23

On the Binary Rank of Matrices with Constant Real Rank

cs.DM math.CO ·2026-09-24 ·Michal Parnas
theory similarity 0.61
Abstract

We study the problem of determining upper bounds on the maximal binary rank, $b_d$, of a $0,1$ matrix with real rank $d$, for small constant $d$. We prove a general upper bound of $b_d \leq \left\lfloor \sqrt{d2^d + 2d}\right\rfloor -1$. We also develop a general dimension reduction technique of bounding $b_d$ using known upper bounds on $b_{d-1}$ and $b_{d-2}$, as well as prove interesting general structural results on extremal matrices with binary rank $b_d$. This allows us to get improved non-trivial upper bounds on $b_d$ for constant values of $d$, which imply tight bounds on $b_d$ for $3 \leq d \leq 5$. Our results also imply bounds on the equivalent problem of finding the minimum number of bicliques needed to partition the edges of a bipartite graph whose reduced adjacency matrix has real rank at most $d$.

0.12

A linear-in-$q$ range of dimensions for the MDS conjecture over $\mathbb F_q$ in odd characteristic

cs.IT math.CO ·2026-09-22 ·Xiang Fan
theory similarity 0.59
Abstract · 23 pages. The proof has been reorganized to make its homological structure explicit. Other versions of this preprint are available on Zenodo…

Let $q$ be a power of an odd prime $p$. We prove the MDS conjecture over $\mathbb F_q$ in every dimension $k$ satisfying \[ 2\leqslant k\leqslant B(p,q) \quad\text{or}\quad q+2-B(p,q)\leqslant k\leqslant q, \qquad B(p,q)=\left\lfloor\frac{(p-2)q+6p-10}{2p-3}\right\rfloor. \] For fixed $p$, the first interval is linear in $q$; together with duality, the theorem covers an asymptotic proportion $1-1/(2p-3)$ of all dimensions. The proof rests on a vanishing theorem for determinant relations over an arbitrary field of characteristic $p>0$. It yields full row rank for Chowdhury's matrices over a larger range of arc sizes. In particular, at $|G|=2k-3+n$ it proves Chowdhury's full-row-rank conjecture without the $q$-dependent restriction. Specialization to $\mathbb F_q$, together with the Ball--Lavrauw construction, gives the stated MDS range. We also prove that, for every odd prime power $q$, every normal rational curve in $\mathrm{PG}(N,q)$ is complete for $2\leqslant N\leqslant q-2$, and every projective Reed--Solomon code of length $q+1$ and dimension $2\leqslant k\leqslant q-2$ has covering radius $q-k$.

0.59

An Exposition of the $\widetilde{O}(\log^{1/4} n)$ Bound for the Komlós Problem

cs.DM math.COcs.DSmath.PR ·2026-08-28 ·Nikhil Bansal, Haotian Jiang
publishedtheory similarity 0.59
Abstract · An extended abstract of this work appeared in STOC 2026: https://arxiv.org/pdf/2508.03961. The present article treats only the Komlós proble…

A conjecture of Komlós states that the combinatorial discrepancy of any matrix $A\in\mathbb R^{m\times n}$ whose columns have Euclidean norm at most one is bounded by a universal constant. We prove that the combinatorial discrepancy of every such matrix is at most $O((\log n)^{1/4}(\log\log n)^{7/4})$. This is the first asymptotic improvement over the $O(\sqrt{\log n})$ bound established by Banaszczyk [Banaszczyk, Random Struct.\ Algorithms, 1998], and it refutes a conjecture of Hajela [Hajela, European J.\ Combin., 1988] that a lower bound of order $Ω(\sqrt{\log n})$ should hold.

0.38

Polynomial-Factor Deterministic NP-Hardness for SVP in Every $\ell_p$ Norm with $p>2$

cs.CC ·2026-08-14 ·Isaac M Hair, Amit Sahai
theory similarity 0.58
Abstract

We prove that for every constant $2<p<\infty$, the shortest vector problem in the $\ell_p$ norm is NP-hard to approximate within a polynomial factor under a deterministic reduction. More precisely, for lattices of rank $M$, we obtain a factor of $M^\varepsilon$ for every constant $0<\varepsilon<\min\{(p-2)/(4p),1/8\}$. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. Our reduction adapts OpenAI's encoding of a satisfying assignment for the closest vector problem ("Ten Advances in Mathematics and Theoretical Computer Science"). The encoding has one block of coordinates for each evaluation of a polynomial, with one position for each possible value. We allow the entries in a block to be arbitrary field elements, which can cancel when we take weighted sums of powers of these values. We show that on an unsatisfiable formula, a nonzero codeword with small support must have many nonzero entries in each block it uses. Applying a Hadamard matrix to each block, as in a work by Hair and Sahai (STOC 2026), gives the gap in vector length. The main results of this paper were discovered by Codex / ChatGPT 5.6 Sol Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

0.32

Norm-Query Complexity of Algorithmic Problems in Finite-Dimensional p-adic Normed Spaces

cs.CC math.NT ·2026-08-22 ·Zhefan Duan, Huawei Wu
theory similarity 0.58
Abstract

We study the deterministic norm-query complexity of computational problems in finite-dimensional vector spaces over $\mathbb{Q}_p$ equipped with an arbitrary ultrametric norm. For orthogonalization, we prove that no uniform finite query bound depending only on the dimension exists: for every deterministic algorithm that produces an $N$-orthogonal basis for every ultrametric norm $N$, the number of norm queries is unbounded as $N$ varies. We then study the Longest Vector Problem (LVP) for a rank-$m$ $p$-adic lattice. By adapting a brute-force search to the general norm-query setting and eliminating the scalar redundancy among nonzero coefficient vectors modulo $p$, we obtain an algorithm using exactly $(p^m-1)/(p-1)$ norm queries for $m\ge 2$, and prove that no deterministic norm-query algorithm can use fewer queries in the worst case. Finally, we consider the Closest Vector Problem (CVP). Apart from the trivial cases in which no norm query is needed, we prove that the deterministic worst-case norm-query complexity of the CVP is unbounded, even when the lattice and the target vector are fixed.

0.32

Small sums of roots of unity: polylogarithmic exceptional sets and conditional separation

cs.CC math.NT ·2026-10-19 ·Qi Cheng
theory similarity 0.57
Abstract

We prove a polylogarithmic exceptional-set estimate for symmetric five-term sums of roots of unity of arbitrary order. More precisely, at most $O((\log(2N))^{11})$ points of the $N$-grid satisfy $|1+2\cos(2πx)+2\cos(2πy)|<\exp(-C(\log(2N))^{13})$. This implies the corresponding bound for small conjugates at the reduced conductor: outside polylogarithmically many real embeddings, every such sum is at least quasipolynomially large. The proof is unconditional and combines a polynomial-vector-field multiplicity estimate, arithmetic jet determinants, analytic propagation, and interpolation determinants for nearby grid points. As a companion result, assuming a uniform number-field $abc$ conjecture, we prove that every sum of a fixed number of distinct prime-order roots of unity has modulus at least $\exp(-\varepsilon p)$ for every $\varepsilon>0$ and all sufficiently large primes $p$, uniformly in the exponents. That proof uses simultaneous compression of the exponents, discriminant estimates, and cyclic resultants.

0.34

Cubic lower bounds for the permanent in odd characteristic, for Pfaffian representations, and for polynomial entries

cs.CC math.AC ·2026-10-29 ·Karthik Sheshadri
theory similarity 0.57
Abstract · 18 pages; stand-alone; submitted to International Mathematical Research Notices

The determinantal complexity of a polynomial is the order of the smallest matrix whose entries are polynomials of degree at most one and whose determinant equals the polynomial. A lower bound for the permanent in this measure is the algebraic form of the question whether the permanent is harder to compute than the determinant. Over the complex numbers, the best known lower bound grows cubically in the size of the permanent. It holds even when the permanent only has to be a limit of such determinants. I prove that the cubic lower bound holds over every algebraically closed field of odd characteristic $p$, with a constant that depends on $p$. Hence the cubic bound does not depend on characteristic zero. I also prove the bound for Pfaffians, which are square roots of determinants of skew symmetric matrices. Lower bounds for Pfaffians imply the same bounds for determinants. Further, I prove the bound, divided by $a$, for matrices whose entries are polynomials of degree at most $a$. All three results come from one lower bound for smooth hypersurfaces. I prove it in every characteristic by counting intersection points together with their multiplicities.

0.28