## Abstract

For a code C = C(n, M) the level k code of C, denoted C_{k}, is the set of all vectors resulting from a linear combination of precisely k distinct codewords of C. We prove that if k is any positive integer divisible by 8, and n = γk, M = βk ≥ 2k then there is a codeword in C _{k} whose weight is either 0 or at most n/2 - n(1/8γ - 6/(4β-2)^{2}) + 1. In particular, if γ < (4β - 2)^{2}/48 then there is a codeword in C_{k} whose weight is n/2 - Θ(n). The method used to prove this result enables us to prove the following: Let k be an integer divisible by p, and let f(k, p) denote the minimum integer guaranteeing that in any square matrix over Z_{p}, of order f(k, p), there is a square submatrix of order k such that the sum of all the elements in each row and column is 0. We prove that lim inf f(k, 2)/k < 3.836. For general p we obtain, using a different approach, that f(k, p) ≤ p^{(k/ln k)} (1+o_{k}(1)).

Original language | English (US) |
---|---|

Pages (from-to) | 449-457 |

Number of pages | 9 |

Journal | Graphs and Combinatorics |

Volume | 19 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1 2003 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics