# American Institute of Mathematical Sciences

August  2010, 4(3): 345-361. doi: 10.3934/amc.2010.4.345

## On linear balancing sets

 1 Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742 2 Computer Science Department, Technion, Haifa 32000, Israel 3 Hewlett–Packard Laboratories, Palo Alto, CA 94304, United States

Received  November 2009 Revised  March 2010 Published  August 2010

Let $n$ be an even positive integer and $\mathbb F$ be the field GF$(2)$. A word in $\mathbb F$n is called balanced if its Hamming weight is $n$/$2$. A subset $\mathcal C\subseteq\mathbb F$n is called a balancing set if for every word $\mathbf y\in\mathbb F$n there is a word $\mathbf x\in \mathcal C$ such that $\mathbf y + \mathbf x$ is balanced. It is shown that most linear subspaces of $\mathbb F$n of dimension slightly larger than $\frac{3}{2} \log$2$n$ are balancing sets. A generalization of this result to linear subspaces that are "almost balancing" is also presented. On the other hand, it is shown that the problem of deciding whether a given set of vectors in $\mathbb F$n spans a balancing set, is NP-hard. An application of linear balancing sets is presented for designing efficient error-correcting coding schemes in which the codewords are balanced.
Citation: Arya Mazumdar, Ron M. Roth, Pascal O. Vontobel. On linear balancing sets. Advances in Mathematics of Communications, 2010, 4 (3) : 345-361. doi: 10.3934/amc.2010.4.345
 [1] Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119 [2] Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233 [3] Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399 [4] Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129 [5] Vianney Perchet, Marc Quincampoix. A differential game on Wasserstein space. Application to weak approachability with partial monitoring. Journal of Dynamics & Games, 2019, 6 (1) : 65-85. doi: 10.3934/jdg.2019005 [6] Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129 [7] Laurent Gosse. Well-balanced schemes using elementary solutions for linear models of the Boltzmann equation in one space dimension. Kinetic & Related Models, 2012, 5 (2) : 283-323. doi: 10.3934/krm.2012.5.283 [8] Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021 [9] Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025 [10] Otávio J. N. T. N. dos Santos, Emerson L. Monte Carmelo. A connection between sumsets and covering codes of a module. Advances in Mathematics of Communications, 2018, 12 (3) : 595-605. doi: 10.3934/amc.2018035 [11] Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008 [12] Gérard Cohen, Alexander Vardy. Duality between packings and coverings of the Hamming space. Advances in Mathematics of Communications, 2007, 1 (1) : 93-97. doi: 10.3934/amc.2007.1.93 [13] Qi Wang, Yue Zhou. Sets of zero-difference balanced functions and their applications. Advances in Mathematics of Communications, 2014, 8 (1) : 83-101. doi: 10.3934/amc.2014.8.83 [14] B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037 [15] Maciej J. Capiński. Covering relations and the existence of topologically normally hyperbolic invariant sets. Discrete & Continuous Dynamical Systems, 2009, 23 (3) : 705-725. doi: 10.3934/dcds.2009.23.705 [16] Aixian Zhang, Zhengchun Zhou, Keqin Feng. A lower bound on the average Hamming correlation of frequency-hopping sequence sets. Advances in Mathematics of Communications, 2015, 9 (1) : 55-62. doi: 10.3934/amc.2015.9.55 [17] Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333 [18] Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251 [19] Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409 [20] Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$n into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385

2019 Impact Factor: 0.734