給定距離二元碼的基數上界 The Maximum Size of Given Distances Set
We use the linear programming method and Deza Theorem for intersection family to
prove the upper bound of two-distance sets(also three-distance sets) in Hamming space.
This problem comes from the paper, ”On the size of maximal binary codes with 2, 3, and
4 distances”[1], which has proven that the maximum size of two-distance sets in Hamming
space is 1
. Before this research, there
were no understandable methods for high school students. We are also unsatisfied with
the upper bound, so we aim to reduce the value of the upper bounds in certain specified
cases. By solving the system inequalities that come from the Krawchouk polynomial and
adopting former results such as Deza theorem, we achieve the upper bounds for the cases
including A(n, {1, 2}), A(n, {2, 3}), A{(n, {1, 2, 3}), A(n, {3, 6}) and A(n, {k, 2k}) for k
is an odd integer. For general {d1, d2} cases, we prove that A(n, {d1, d2)}) ≤ 2 when
{d1, d2} is a pair of odd numbers. Additionally, during this research, several properties
of the Krawchouk polynomial are also revealed, which can be applied in future discussions.