Problem Analysis #8

[THOUGHT] The Fixed Length Levenshtein distance between two vectors of length n in $\mathbb{Z}_2^n$ is defined as the smallest $t$ such that $t$ deletions and $t$ insertions transform one vector to the other. This distance $t$ equals $n - L$, where $L$ is the length of the longest common subsequence (LCS) between the vectors.

For the ball of radius 1 centered at a vector $\mathbf{x} \in \mathbb{Z}_2^{100}$, we consider vectors $\mathbf{y}$ such that the distance to $\mathbf{x}$ is at most 1. This means:

• For $t = 0$, $\mathbf{y} = \mathbf{x}$.
• For $t = 1$, $n - L = 1$, so $L = 99$.

The LCS $L = 99$ occurs if and only if $\mathbf{y}$ differs from $\mathbf{x}$ in exactly one position. This is because:

• If $\mathbf{y}$ differs in one position, the LCS is 99 (by keeping all elements except the differing one).
• If $\mathbf{y}$ differs in more than one position, the LCS is at most 98 (by skipping the differing positions), so $t \geq 2$.

There are 100 positions in $\mathbb{Z}_2^{100}$, and for each position, flipping the bit gives a unique $\mathbf{y}$ differing in exactly one position. Thus, there are 100 such vectors.

The ball includes:

• The center $\mathbf{x}$ (1 vector).
• All 100 vectors differing in exactly one position.

The total size of the ball is $1 + 100 = 101$.

Since the space $\mathbb{Z}_2^{100}$ is symmetric, every ball of radius 1 has the same size. Therefore, the maximum size is 101.

Final answer: $\boxed{101}$

[THOUGHT] The ball of radius 1 in $\mathbb{Z}_2^{100}$ centered at any vector $\mathbf{x}$ includes:

• The center vector $\mathbf{x}$ (1 vector).
• All vectors that differ from $\mathbf{x}$ in exactly one position. There are 100 such positions, and flipping any one bit gives a unique vector.

The size of the ball is $1 + 100 = 101$.

We use Python to verify the number of vectors at Hamming distance 1 from $\mathbf{x}$, which is 100. [/THOUGHT] [PYTHON] n = 100 print(n) [/PYTHON]

$\boxed{101}$