Linear codes and character sums
\textit{G. Kalai} and \textit{N. Linial} [IEEE Trans. Inf. Theory 41, 1467-1472 (1995; Zbl 0831.94019)] conjectured that the size of the code with the distribution of distances near the minimal distance is exponentially small. The authors estimate the fraction of non-zero vectors of minimal weights in an \(r\cdot n\)-dimensional subspace of \(\mathbb{Z}_2^n\). Using the connection between the value distributions of character sums over \(\mathbb{Z}_2^n\) and extremal problems on linear codes the authors prove that for \(r\gg {{\log n}\over{\sqrt{n}}}\) the above fraction is exponentially small and does not exceed \(2^{-\Omega ({{r^2}\over{\log (1/r)+1}}n)}\). Let \(E\) be the affine subspace in \(\mathbb{Z}_2^n\) of dimension \(a\cdot n (a> {{1}\over{2}}, n\) is even and large) and \(L_k\) be the set of vectors in \(\mathbb{Z}_2^n\) whose Hamming weight is \(k\). The authors also answer a question of M. Ben-Or (preprint of Hebrew University, 1996) about the largest possible number of a given weight. They prove that for every \(0\leq k \leq n\) the inequality \[ |E\cap L_k |\leq C_a {{|E|}\over{\sqrt{n}}} \] is satisfied.
- Estimates for distribution of the minimal distance of a random linear code
- On the distance distribution of codes
- A nonconstructive upper bound on covering radius
- On covering radius lower bound for a class of binary codes
- Bounds for Binary Codes With Narrow Distance Distributions
- scientific article; zbMATH DE number 4218374
- The linear programming bound for binary linear codes
- One more proof of the first linear programming bound for binary codes and two conjectures
- An updated table of minimum-distance bounds for binary linear codes
- Code pairs with specified parity of the Hamming distances
- A coding theory bound and zero-sum square matrices
- Property testing lower bounds via a generalization of randomized parity decision trees
- On vectors of minimal support in transitive linear spaces
- scientific article; zbMATH DE number 431468 (Why is no real title available?)
- Bounds on distance distributions in codes of given size
- Small Linear Dependencies for Binary Vectors of Low Weight
- Investigation of Linear Codes Possessing Some Extra Properties
- scientific article; zbMATH DE number 2154157 (Why is no real title available?)
- Note on large subsets of binary vectors with similar distances
- scientific article; zbMATH DE number 1426191 (Why is no real title available?)
- Estimates of the neighborhood volumes of binary codes via their weight spectra
- On the weight distribution of random binary linear codes
- On the minimal distance of a polynomial code
- On the generalized weights of a class of trace codes
- Linear codes with exponentially many light vectors
- One more proof of the first linear programming bound for binary codes and two conjectures
- On the most weight w vectors in a dimension k binary code
This page was built for publication: Linear codes and character sums
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1410404)
