On covering radius and deep holes of Roth-Lempel codes

The covering radius problem stands as one of the fundamental problems in coding theory, with applications in decoding, data compression, cryptography and football pool problems etc. In recent years, the classification problem of deep holes has emerged as a particularly active research frontier, especially for Reed-Solomon codes, Reed-Muller codes and their variants. This paper focuses on determining the covering radius and classifying deep holes of the Roth-Lempel code—a notable family of non-GRS MDS codes constructed by Roth and Lempel in 1989. First, we establish equivalent algebraic conditions characterizing the covering radius and identifying deep holes, building upon the syndrome-based framework developed for projective Reed-Solomon codes. Next, we solve the covering radius and deep hole classification for the related E R S ( k , δ ) codes—a class of extended Reed-Solomon type codes—over certain parameter range where q is an odd prime power. Finally, leveraging these intermediate results together with the structural relationship between Roth-Lempel codes and GRS codes, we derive explicit characterizing conditions for the Roth-Lempel code R L ( k ) and completely classify its deep hole classes for specific dimensions k .