arxiv: 2605.08973 · v1 · submitted 2026-05-09 · 💻 cs.IT · math.IT

Recognition: 2 theorem links

· Lean Theorem

Tight Lower Bounds on The Single-Error Detection Threshold for Analog Error-Correcting Codes

Bo Bai, Gong Zhang, Hanxu Hou, Wenhao Liu, Zhengyi Jiang, Zhongyi Huang

Authors on Pith no claims yet

Pith reviewed 2026-05-12 01:57 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords analog error-correcting codessingle-error detectionheight profileconvex optimizationlinear subspaces over realserror detection thresholdRoth's open problems

0 comments

The pith

Every (n-2)-dimensional subspace of R^n contains a nonzero vector whose largest absolute entry is at least (n/2 - 1) times the second-largest.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper gives an affirmative answer to an open question on the minimal height profiles of linear subspaces over the reals. It proves that when n is even, every subspace of dimension n-2 must contain a vector x where the ratio of its largest absolute component to the second-largest is at least n/2 minus one. The proof proceeds by recasting the search for the minimal ratio as a convex optimization problem whose solution yields the stated bound. The same technique is then applied to show that the general lower bound ceil(k/(n-k)) on the height profile of any [n, k] code holds exactly when n-k divides k.

Core claim

The authors establish that the answer to Problem 2 is affirmative: every (n-2)-dimensional subspace of R^n with n even contains a nonzero vector c satisfying h_1(c) >= n/2 - 1. They prove this using convex optimization and extend the method to show that for cases where n-k divides k, the bound h_1(C) >= ceil(k/(n-k)) is tight for every linear [n,k] code C over the reals.

What carries the argument

The height function h_1(x) defined as the ratio of the largest absolute entry of a vector x to its second-largest absolute entry, with the minimal value of this ratio over nonzero vectors in the subspace obtained via convex optimization.

Load-bearing premise

The convex optimization formulation exactly captures the smallest attainable height ratio over all nonzero vectors without hidden constraints or exceptional cases permitting a smaller value.

What would settle it

A concrete counterexample: an even n together with an (n-2)-dimensional subspace of R^n in which every nonzero vector has largest absolute entry strictly smaller than (n/2 - 1) times its second-largest absolute entry.

Figures

Figures reproduced from arXiv: 2605.08973 by Bo Bai, Gong Zhang, Hanxu Hou, Wenhao Liu, Zhengyi Jiang, Zhongyi Huang.

**Figure 1.** Figure 1: The geometric intuition from Eq. (3) to Eq. (5). Although Theorem 3 provides, from the perspective of coding theory combined with geometry, a geometric characterization of the value of Γ1(C) for any given linear code C, it does not provide the lower bound sought in Problem A. From an algebraic perspective, an [n, k] linear code C over R is essentially a k-dimensional subspace of R n and uniquely correspond… view at source ↗

**Figure 2.** Figure 2: A geometric illustration of the meaning of Eq. ( [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

read the original abstract

Analog error-correcting codes (Analog ECCs) for approximate vector-matrix multiplication have been extensively studied as means to achieve fault-tolerant in-memory computation. The theoretical foundations for such coding schemes, particularly the characterization of their correction capabilities via the height profile, have been well established in recent literature. In this paper, we focus on the case of single-error detection Analog ECCs. Among several open problems related to this case proposed by Ron M. Roth in [1], Problem 1 asks: "Identify the values of $k$ and $n$ for which every linear $[n, k]$ code $\mathcal{C}$ over $\mathbb{R}$ satisfies: $$\mathsf{h}_1(\mathcal{C}):=\max_{\boldsymbol{c}\in \mathcal{C}\setminus{\{\boldsymbol{0}\}}}\mathsf{h}_1(\boldsymbol{c})\geq \Big\lceil \frac{k}{n-k} \Big\rceil.\text{"}$$ Here, for any $\boldsymbol{x}\in\mathbb{R}^n$, $\mathsf{h}_1(\boldsymbol{x})$ represents the ratio between the largest and second largest absolute values of $\boldsymbol{x}$'s entries. As the simplest special case of Problem 1 (with $n-k=2$), the following problem was posed as Problem 2 in [1]: "Must every $(n-2)$-dimensional subspace of $\mathbb{R}^n$, $n$ even, contain a nonzero vector in which the ratio between the largest and second largest absolute values of its entries is at least $(n/2)-1$?" These problems directly pertain to the lower bounds on the single-error detection threshold for Analog ECCs: Problem 1 corresponds to arbitrary $n-k$ and Problem 2 corresponds to $n-k=2$. In this paper, we provide an affirmative answer to Problem 2 and a rigorous proof using theories related to convex optimization. Furthermore, we extend our analytical method to show that the lower bound in Problem 1 is tight for the case where $n-k$ divides $k$. Our results fill the gap in the lower bound theory of thresholds for single-error detection in Analog ECCs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper affirmatively settles Roth's Problem 2 for even n and shows the general lower bound is tight when n-k divides k, via a convex-optimization argument that still needs its exactness checked.

read the letter

The paper closes two open questions from Roth on single-error detection thresholds for analog linear codes. It proves that every (n-2)-dimensional subspace of R^n with n even contains a nonzero vector whose largest-to-second-largest entry ratio is at least n/2 - 1, and it shows the ceil(k/(n-k)) bound from Problem 1 is achieved whenever n-k divides k. The approach relies on recasting the min-max height-profile question as a convex program and invoking standard duality results to obtain the claimed lower bounds. That is the concrete advance: prior work left these cases open, and this supplies explicit resolutions rather than just numerical checks or special cases. The convex-optimization route is a reasonable way to handle the ratio over subspaces, and if the formulation is faithful it gives a clean proof. The main uncertainty is whether the program exactly matches the original non-convex objective over every subspace. The abstract does not display the full derivation or the handling of boundary cases, so it is unclear if strong duality holds without qualification, whether the optimum is always attained, or if there exist lower-dimensional sets of vectors that slip below the bound. Those points are worth verifying directly from the manuscript rather than assumed from the sketch. Readers working on analog ECCs for in-memory or approximate computing will get the most from it, especially anyone who has been citing Roth's problems or designing codes around the height profile. The work is narrow but addresses a genuine gap in the existing theory. It is worth sending to peer review so that specialists can examine the optimization steps and any implicit assumptions about generic vectors or attainment.

Referee Report

2 major / 2 minor

Summary. The paper resolves two open problems on lower bounds for the single-error detection threshold of analog error-correcting codes. It affirmatively answers Problem 2 by proving that every (n-2)-dimensional subspace of R^n (n even) contains a nonzero vector c with height profile h1(c) at least n/2 - 1, via a convex-optimization argument. It further extends the method to prove that the general lower bound ceil(k/(n-k)) on h1(C) for any [n,k] code C is tight whenever n-k divides k.

Significance. If the central claims hold, the work closes key gaps in the lower-bound theory for analog ECC thresholds, directly addressing questions posed by Roth. The convex-optimization approach supplies a parameter-free derivation of the bound, which strengthens the foundations for fault-tolerant in-memory computation if the equivalence to the original min-max height-profile problem is fully rigorous.

major comments (2)

[Proof of the main result for Problem 2] The convex-optimization formulation used to prove the affirmative answer to Problem 2 (abstract and the corresponding proof section): the manuscript asserts that this program computes the exact infimum of max_{c≠0} h1(c) over all (n-2)-dimensional subspaces. However, it is unclear whether the formulation is an exact characterization or a relaxation; the derivation must explicitly rule out measure-zero exceptions or lower-dimensional subspaces that could achieve a strictly smaller ratio, including verification of strong duality and attainment for the non-convex objective when n is even.
[Extension to general n-k dividing k] Extension to tightness of the bound in Problem 1 when n-k divides k (the analytical-method section): the argument relies on the same convex-optimization technique, but the manuscript does not detail how the divisibility condition ensures the bound is achieved without hidden constraints on the height profile or edge cases where the second-largest entry vanishes.

minor comments (2)

[Introduction] Notation for h1(C) and h1(c) is introduced in the abstract but should be restated with the precise definition (ratio of largest to second-largest absolute entry) at the beginning of the technical sections for clarity.
[Introduction] The reference to Ron M. Roth [1] should include the full bibliographic details and a brief statement of which specific problems from that work are being addressed.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment of our work and for identifying points where additional clarification would strengthen the presentation. We address each major comment below, providing the strongest honest defense based on the manuscript's arguments while noting where we will expand the exposition in revision.

read point-by-point responses

Referee: [Proof of the main result for Problem 2] The convex-optimization formulation used to prove the affirmative answer to Problem 2 (abstract and the corresponding proof section): the manuscript asserts that this program computes the exact infimum of max_{c≠0} h1(c) over all (n-2)-dimensional subspaces. However, it is unclear whether the formulation is an exact characterization or a relaxation; the derivation must explicitly rule out measure-zero exceptions or lower-dimensional subspaces that could achieve a strictly smaller ratio, including verification of strong duality and attainment for the non-convex objective when n is even.

Authors: The formulation in Section 3 is not merely a relaxation; it is obtained by a sequence of equivalent transformations starting from the original min-max definition of h1(C). The non-convex ratio is homogenized and then dualized via linear programming, yielding a convex program whose optimum equals the original value. Strong duality holds by Slater's condition (strict feasibility is satisfied by any vector with distinct nonzero absolute entries), and the duality gap is zero. Attainment follows from compactness of the projective space of subspaces and continuity of the objective; lower-dimensional subspaces are ruled out because any such subspace can be embedded in an (n-2)-dimensional one without decreasing the maximum h1. For even n we exhibit an explicit achieving vector in the proof. We will insert a short paragraph after the duality derivation that explicitly states these equivalences and the zero duality gap. revision: partial
Referee: [Extension to general n-k dividing k] Extension to tightness of the bound in Problem 1 when n-k divides k (the analytical-method section): the argument relies on the same convex-optimization technique, but the manuscript does not detail how the divisibility condition ensures the bound is achieved without hidden constraints on the height profile or edge cases where the second-largest entry vanishes.

Authors: When n-k divides k the divisibility permits a uniform partition of the support into n-k equal-sized blocks of size k/(n-k). The convex program then admits an optimal solution in which the absolute values are constant on each block and strictly positive on the second-largest block, so the second-largest entry cannot vanish. This is verified by substituting the candidate solution into the dual and confirming zero duality gap. No additional hidden constraints appear because the feasible set is defined solely by the linear subspace condition and the normalization. We will add a brief illustrative example (e.g., the [6,4] case) and a sentence explaining why the second-largest entry remains positive under the divisibility hypothesis. revision: partial

Circularity Check

0 steps flagged

No circularity: proof uses external convex optimization on open problems from prior work

full rationale

The paper formulates Problems 1 and 2 from Roth [1] as convex programs and derives the claimed lower bounds and tightness results via standard convex optimization theory and linear algebra. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the cited reference [1] is external and states the open problems rather than supplying the solution. The derivation chain is therefore independent of the target claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard real-linear-algebra and convex-optimization facts; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

standard math Standard properties of convex sets and optimization over real vector spaces guarantee existence of a minimax vector achieving the claimed ratio bound.
Invoked to convert the height-profile minimization into a solvable convex program whose optimum meets the lower bound.

pith-pipeline@v0.9.0 · 5717 in / 1244 out tokens · 49372 ms · 2026-05-12T01:57:28.111644+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
h1(C) := max_{c∈C∖{0}} h1(c) ≥ ⌈k/(n−k)⌉ … ratio between the largest and second largest absolute values
IndisputableMonolith/Foundation/BranchSelection.lean RCLCombiner_isCoupling_iff unclear
Lemma 4 … Tr(A) ≤ 2 … rank(A) ≤ 2 … ||A||∞ ≤ 1

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages · 1 internal anchor

[1]

Analog error-correcting codes,

R. M. Roth, “Analog error-correcting codes,” IEEE Transactions on Information Theory , vol. 66, no. 7, pp. 4075–4088, 2020

work page 2020
[2]

Goodfellow, Y

I. Goodfellow, Y . Bengio, and A. Courville, Deep Learning . MIT Press, 2016, http://www.deeplearningbook.org

work page 2016
[3]

Dot- product engine for neuromorphic computing: Programming 1t1m crossbar to accelerate matrix-vector multiplication,

M. Hu, J. P . Strachan, Z. Li, E. M. Grafals, N. Davila, C. Graves, S. Lam, N. Ge, J. J. Y ang, and R. S. Williams, “Dot- product engine for neuromorphic computing: Programming 1t1m crossbar to accelerate matrix-vector multiplication,” in Proceedings of the 53rd annual design automation conference , 2016, pp. 1–6

work page 2016
[4]

An analog neural network processor with programmable topology,

B. Boser, E. Sackinger, J. Bromley, Y . Le Cun, and L. Jackel, “An analog neural network processor with programmable topology,” IEEE Journal of Solid-State Circuits , vol. 26, no. 12, pp. 2017–2025, 1991

work page 2017
[5]

Memory devices and applications for in-memory computing,

A. Sebastian, M. Le Gallo, R. Khaddam-Aljameh, and E. Eleftheriou, “Memory devices and applications for in-memory computing,” Nature nanotechnology, vol. 15, no. 7, pp. 529–544, 2020

work page 2020
[6]

Edge learning using a fully integrated neuro-inspired memristor chip,

W. Zhang, P . Y ao, B. Gao, Q. Liu, D. Wu, Q. Zhang, Y . Li, Q. Qin, J. Li, Z. Zhu et al. , “Edge learning using a fully integrated neuro-inspired memristor chip,” Science, vol. 381, no. 6663, pp. 1205–1211, 2023

work page 2023
[7]

Programmable analog vector-matrix multipliers,

F. Kub, K. Moon, I. Mack, and F. Long, “Programmable analog vector-matrix multipliers,” IEEE Journal of Solid-State Circuits, vol. 25, no. 1, pp. 207–214, 1990

work page 1990
[8]

Algorithm-based fault tolerance for matrix operations,

K.-H. Huang and J. A. Abraham, “Algorithm-based fault tolerance for matrix operations,” IEEE Transactions on Computers, vol. C-33, no. 6, pp. 518–528, 1984

work page 1984
[9]

Fault-tolerant matrix operations on multiple processor systems using weighted checksums,

J.-Y . Jou and J. A. Abraham, “Fault-tolerant matrix operations on multiple processor systems using weighted checksums,” in Real-Time Signal Processing VII , vol. 495. SPIE, 1984, pp. 94–101

work page 1984
[10]

Attnchecker: Highly-optimized fault tolerant attention for large language model training,

Y . Liang, X. Li, J. Ren, A. Li, B. Fang, and J. Chen, “Attnchecker: Highly-optimized fault tolerant attention for large language model training,” in Proceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, 2025, pp. 252–266

work page 2025
[11]

Analog error-correcting codes,

R. M. Roth, “Analog error-correcting codes,” in 2019 IEEE International Symposium on Information Theory (ISIT) , 2019, pp. 2419–2423

work page 2019
[12]

Multiple-error-correcting codes for analog computing on resistive crossbars,

H. Wei and R. M. Roth, “Multiple-error-correcting codes for analog computing on resistive crossbars,” IEEE Transactions on Information Theory , vol. 70, no. 12, pp. 8647–8658, 2024

work page 2024
[13]

Analog error-correcting codes: Designs and analysis,

A. Jiang, “Analog error-correcting codes: Designs and analysis,” IEEE Transactions on Information Theory , vol. 70, no. 11, pp. 7740–7756, 2024

work page 2024
[14]

Constructions of analog error-correcting codes for single-error detection and correction with efﬁcient decoding algorithm,

Z. Jiang, H. Shi, Z. Huang, B. Bai, G. Zhang, and H. Hou, “Constructions of analog error-correcting codes for single-error detection and correction with efﬁcient decoding algorithm,” in 2025 IEEE International Symposium on Information Theory (ISIT), 2025, pp. 1–6

work page 2025
[15]

A New Class of Geometric Analog Error Correction Codes for Crossbar Based In-Memory Computing

Z. Zhu, C. Y uan, R. M. Roth, P . H. Siegel, and A. Jiang, “A new class of geometric analog error correction codes for crossbar based in-memory computing,” arXiv preprint arXiv:2603.03723 , 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[16]

Zonotopes as bounding volumes,

L. J. Guibas, A. Nguyen, and L. Zhang, “Zonotopes as bounding volumes,” in Proceedings of the F ourteenth Annual ACM- SIAM Symposium on Discrete Algorithms (SODA 2003) . Baltimore, MD, USA: Association for Computing Machinery and Society for Industrial and Applied Mathematics, January 2003, pp. 803–812

work page 2003
[17]

Boyd and L

S. Boyd and L. V andenberghe, Convex Optimization. Cambridge University Press, 2004

work page 2004
[18]

On the dependability of bidirectional encoder representations from transformers (bert) to soft errors,

Z. Gao, Z. Yin, J. Wang, R. Su, J. Deng, Q. Liu, P . Reviriego, S. Liu, and F. Lombardi, “On the dependability of bidirectional encoder representations from transformers (bert) to soft errors,” IEEE Transactions on Nanotechnology , vol. 24, pp. 73–87, 2025

work page 2025
[19]

Soft error reliability analysis of vision transformers,

X. Xue, C. Liu, Y . Wang, B. Y ang, T. Luo, L. Zhang, H. Li, and X. Li, “Soft error reliability analysis of vision transformers,” IEEE Transactions on V ery Large Scale Integration (VLSI) Systems , vol. 31, no. 12, pp. 2126–2136, December 2023. [Online]. Available: https://ieeexplore.ieee.org/document/10273186

work page arXiv 2023
[20]

Soft errors in dnn accelerators: A comprehensive review,

Y . Ibrahim, H. Wang, J. Liu, J. Wei, L. Chen, P . Rech, K. Adam, and G. Guo, “Soft errors in dnn accelerators: A comprehensive review,” Microelectronics Reliability , vol. 115, p. 113969, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0026271420308003

work page 2020
[21]

Ft-blas: a high performance blas implementation with online fault tolerance,

Y . Zhai, E. Giem, Q. Fan, K. Zhao, J. Liu, and Z. Chen, “Ft-blas: a high performance blas implementation with online fault tolerance,” in Proceedings of the ACM International Conference on Supercomputing , ser. ICS 21. ACM, 2021, p. 127138. [Online]. Available: http://dx.doi.org/10.1145/3447818.3460364

work page doi:10.1145/3447818.3460364 2021
[22]

Making convolutions resilient via algorithm-based error detection techniques,

S. K. S. Hari, M. B. Sullivan, T. Tsai, and S. W. Keckler, “Making convolutions resilient via algorithm-based error detection techniques,” IEEE Transactions on Dependable and Secure Computing , vol. 19, no. 4, pp. 2546–2558, 2022

work page 2022
[23]

Realm: Reliable and efﬁcient large language model inference with statistical algorithm-based fault tolerance,

T. Xie, J. Zhao, Z. Wan, Z. Zhang, Y . Wang, R. Wang, R. Huang, and M. Li, “Realm: Reliable and efﬁcient large language model inference with statistical algorithm-based fault tolerance,” in 2025 62nd ACM/IEEE Design Automation Conference (DAC). IEEE, 2025, pp. 1–7

work page 2025
[24]

Practical coding-theoretic tools for machine learning systems and by machine learning systems,

J. Kosaian, “Practical coding-theoretic tools for machine learning systems and by machine learning systems,” Carnegie Mellon University, Tech. Rep. CMU-CS-23-110, April 2023, ph.D. Thesis. [Online]. Available: http: //reports-archive.adm.cs.cmu.edu/anon/anon/usr/ftp/home/ftp/home/anon/home/ftp/2023/abstracts/23-110.html

work page 2023
[25]

Partitioned encoding schemes for algorithm-based fault tolerance in massively parallel systems,

J. Rexford and N. Jha, “Partitioned encoding schemes for algorithm-based fault tolerance in massively parallel systems,” IEEE Transactions on Parallel and Distributed Systems , vol. 5, no. 6, pp. 649–653, 1994

work page 1994
[26]

58 Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré

H. Dai, S. Wu, H. Zhao, J. Huang, Z. Jian, Y . Zhu, H. Hu, and Z. Chen, “Ft-transformer: Resilient and reliable transformer with end-to-end fault tolerant attention,” 2025. [Online]. Available: https://arxiv.org/abs/2504.02211

work page arXiv 2025