We develop a topological framework for proving lower bounds on sign-rank via $\mathbb{Z}_2$–equivariant topology, and use it to resolve the sign-rank of the Gap Hamming Distance problem up to lower-order terms.

For every (partial) sign matrix $A$, we associate a free $\mathbb{Z}_2$–simplicial complex $S(A)$ and show that sign-rank of $A$ is characterized by the linear analog of $\mathbb{Z}_2$-index of $S(A)$. As a consequence, the classical $\mathbb{Z}_2$–index of $S(A)$ lower bounds the sign-rank of $A$, which reduces sign-rank lower bounds to topological obstructions.
This reduction allows us to use various tools from $\mathbb{Z}_2$–equivariant topology, particularly in regimes where classical lower-bound techniques break down.

As the main application, we consider the Gap Hamming Distance function
$\mathrm{GHD}_k^n$ (defined for $k < n/2$), which distinguishes pairs of strings in $\{0,1\}^n$
with Hamming distance at most $k$ from pairs with distance at least $n-k$.
We prove an essentially tight lower bound and show that for any $k$,
\[
\text{sign-rank}(\mathrm{GHD}_k^n) = (1-o_k(1))\,2k.
\]
where the $o_k(1)$ term is $O\left(\sqrt{\frac{\log k}{k}}\right)$.
This improves on the previous lower bound of
Hatami, Hosseini, and Meng (STOC 2023) who proved that sign-rank of
$\mathrm{GHD}_k^n$ is at least $\Omega(k/\log(n/k))$.

A key technical ingredient is a new analysis of the $\mathbb{Z}_2$-coindex (which lower bounds $\mathbb{Z}_2$-index) of the Vietoris--Rips complex of the hypercube in the sparse regime which yields an essentially tight lower bound. Previously, no results were known in the sparse regime.

fixed typos.

We develop a topological framework for proving lower bounds on sign-rank via $\mathbb{Z}_2$–equivariant topology, and use it to resolve the sign-rank of the Gap Hamming Distance problem up to lower-order terms.

For every (partial) sign matrix $A$, we associate a free $\mathbb{Z}_2$–simplicial complex $S(A)$ and show that sign-rank of $A$ is characterized by the linear analog of $\mathbb{Z}_2$-index of $S(A)$. As a consequence, the classical $\mathbb{Z}_2$–index of $S(A)$ lower bounds the sign-rank of $A$, which reduces sign-rank lower bounds to topological obstructions.
This reduction allows us to use various tools from $\mathbb{Z}_2$–equivariant topology, particularly in regimes where classical lower-bound techniques break down.

As the main application, we consider the Gap Hamming Distance function
$\mathrm{GHD}_k^n$ (defined for $k < n/2$), which distinguishes pairs of strings in $\{0,1\}^n$
with Hamming distance at most $k$ from pairs with distance at least $n-k$.
We prove an essentially tight lower bound and show that for any $k$,
\[
\text{sign-rank}(\mathrm{GHD}_k^n) = (1-o_k(1))\,2k.
\]
where the $o_k(1)$ term is $O\left(\sqrt{\frac{\log k}{k}}\right)$.
This improves on the previous lower bound of
Hatami, Hosseini, and Meng (STOC 2023) who proved that sign-rank of
$\mathrm{GHD}_k^n$ is at least $\Omega(k/\log(n/k))$.

A key technical ingredient is a new analysis of the $\mathbb{Z}_2$-coindex (which lower bounds $\mathbb{Z}_2$-index) of the Vietoris--Rips complex of the hypercube in the sparse regime which yields an essentially tight lower bound. Previously, no results were known in the sparse regime.