Linear Codes and Character
Sums |
| |
Authors: | Nathan Linial Alex Samorodnitsky? |
| |
Institution: | (1) Hebrew University, Jerusalem, 91904, Israel;(2) Hebrew University, Jerusalem, 91904, Israel |
| |
Abstract: | Let V be an
rn-dimensional linear
subspace of
. Suppose the smallest
Hamming weight of non-zero vectors in V is d. (In coding-theoretic terminology,
V is a linear code of length
n, rate
r and distance
d.) We settle two extremal
problems on such spaces.First, we prove a (weak form) of a conjecture by Kalai and
Linial and show that the fraction of vectors in
V with weight
d is exponentially small.
Specifically, in the interesting case of a small
r, this fraction does not
exceed
.We also answer a question of Ben-Or and show that if
, then for every
k, at most
vectors of
V have weight
k.Our work draws on a simple connection between extremal
properties of linear subspaces of
and the distribution of
values in short sums of
-characters.* Supported in part by grants from the Israeli
Academy of Sciences and the Binational Science Foundation
Israel-USA. This work was done while the author was a student
in the Hebrew University of Jerusalem, Israel. |
| |
Keywords: | 94B65 05D05 |
本文献已被 SpringerLink 等数据库收录! |
|