pith. sign in

arxiv: 2604.01510 · v2 · submitted 2026-04-02 · 🧮 math.CO

A mathbb{Z}₂-Topological Framework for Sign-rank Lower Bounds

Florian Frick , Kaave Hosseini , Aliaksei Vasileuski This is my paper

Pith reviewed 2026-05-13 21:38 UTC · model grok-4.3

classification 🧮 math.CO
keywords sign-rankZ2-indexGap Hamming Distanceequivariant topologysimplicial complexeslower boundshypercube
0
0 comments X

The pith

Sign-rank of Gap Hamming Distance equals nearly 2k for any fixed gap parameter k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds a topological reduction that turns sign-rank lower bounds into questions about the Z2-index of a simplicial complex constructed from the matrix. For any sign matrix A they define a free Z2-complex S(A) and prove that the linear version of its Z2-index equals the sign-rank of A, so the ordinary Z2-index supplies a lower bound. They apply the reduction to the Gap Hamming Distance matrix GHD_k^n and obtain an essentially tight result: its sign-rank is (1 minus a small term) times 2k, with the small term bounded by O of the square root of log k over k. This improves the previous Omega(k over log(n/k)) lower bound and works in sparse regimes where earlier methods did not apply. The key new ingredient is a tight lower bound on the Z2-coindex of the Vietoris-Rips complex of the hypercube when the distance parameter is small.

Core claim

For every partial sign matrix A we associate a free Z2-simplicial complex S(A) such that sign-rank(A) equals the linear analog of the Z2-index of S(A). The ordinary Z2-index of S(A) therefore lower-bounds sign-rank(A). For the Gap Hamming Distance function GHD_k^n this yields sign-rank(GHD_k^n) = (1-o_k(1))2k where o_k(1) is O(sqrt(log k over k)). The proof relies on a new analysis of the Z2-coindex of the Vietoris-Rips complex of the hypercube in the sparse regime.

What carries the argument

The free Z2-simplicial complex S(A) associated to a sign matrix A, whose Z2-index lower-bounds the sign-rank of A.

If this is right

  • Sign-rank lower bounds for any matrix reduce to finding Z2-index obstructions in the associated complex S(A).
  • The sign-rank of GHD_k^n is asymptotically 2k, matching the trivial upper bound up to lower-order terms.
  • The reduction applies to partial matrices and yields new bounds in sparse regimes where classical techniques give weaker results.
  • Tools from Z2-equivariant topology become directly usable for communication and sign-rank problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same complex-construction technique may produce tight sign-rank bounds for other explicit matrices such as inner-product or disjointness matrices.
  • Higher-order equivariant invariants beyond the plain Z2-index could be substituted to obtain even sharper lower bounds in future work.
  • Direct verification of the S(A) index versus sign-rank on small random matrices would test how often equality holds outside the GHD case.

Load-bearing premise

The linear analog of the Z2-index of the constructed complex S(A) exactly equals the sign-rank of A.

What would settle it

Compute the sign-rank of GHD_k^n directly for small fixed k and moderate n, then compute the Z2-index of the associated S(A); any mismatch between the two values would disprove the claimed characterization.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops a Z2-equivariant topological framework for sign-rank lower bounds: for any partial sign matrix A it constructs a free Z2-simplicial complex S(A) and asserts that sign-rank(A) equals the linear analog of the Z2-index of S(A). This reduces sign-rank lower bounds to classical topological obstructions on S(A). The main application is an essentially tight bound sign-rank(GHD_k^n) = (1-o_k(1))2k with o_k(1)=O(sqrt(log k/k)), obtained by computing a matching lower bound on the Z2-coindex of the Vietoris-Rips complex of the hypercube in the sparse regime; this improves the prior Omega(k/log(n/k)) bound of Hatami-Hosseini-Meng.

Significance. If the central characterization holds exactly, the framework supplies a new, flexible tool for sign-rank lower bounds that works in sparse regimes where algebraic and combinatorial methods have been limited. The matching upper and lower bounds for GHD_k^n up to lower-order terms would be a notable advance in communication complexity and sign-rank theory, and the new coindex analysis of the hypercube complex in the sparse regime is itself a technical contribution.

major comments (2)
  1. [Framework section (characterization theorem)] The manuscript invokes the exact equality sign-rank(A) = linear analog of Z2-index of S(A) to convert the coindex lower bound on S(GHD_k^n) into the claimed (1-o_k(1))2k bound. Please supply the full derivation of this characterization (including the definition of the linear analog, the equivariant map or linear embedding it encodes, and the proof that it matches sign-rank with no additive or multiplicative slack). Any gap or slack would prevent the (1-o(1)) factor from following directly from the Vietoris-Rips coindex calculation.
  2. [GHD application and coindex calculation] § on the GHD application: the o_k(1) term is stated as O(sqrt(log k/k)); confirm that the coindex lower bound and the linear-index characterization together produce precisely this error term without hidden dependencies on n or additional logarithmic factors that would appear in the sparse regime k << n.
minor comments (2)
  1. [Notation and definitions] Clarify the precise definition of the 'linear analog' of the Z2-index early in the framework section, including how it differs from the classical index and coindex.
  2. [Abstract and introduction] The abstract and introduction should explicitly state whether the characterization holds for all partial sign matrices or only under additional conditions satisfied by GHD.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below. We will revise the manuscript to expand the requested derivation and add explicit confirmation of the error term.

read point-by-point responses

  1. Referee: [Framework section (characterization theorem)] The manuscript invokes the exact equality sign-rank(A) = linear analog of Z2-index of S(A) to convert the coindex lower bound on S(GHD_k^n) into the claimed (1-o_k(1))2k bound. Please supply the full derivation of this characterization (including the definition of the linear analog, the equivariant map or linear embedding it encodes, and the proof that it matches sign-rank with no additive or multiplicative slack). Any gap or slack would prevent the (1-o(1)) factor from following directly from the Vietoris-Rips coindex calculation.

    Authors: The characterization theorem (Theorem 3.1) establishes exact equality: sign-rank(A) equals the linear analog of the Z2-index of S(A), defined as the minimal dimension d such that there exists a Z2-equivariant linear map from the vector space spanned by the vertices of S(A) to R^{d+1} that is fixed-point-free on the unit sphere. The proof constructs an explicit correspondence: any sign matrix of rank r induces such an embedding of dimension r via the rows of the factorization, and conversely any such embedding yields a sign matrix of rank at most d with no additive or multiplicative slack. We will expand this proof into a fully self-contained subsection with all intermediate steps in the revision. revision: yes

  2. Referee: [GHD application and coindex calculation] § on the GHD application: the o_k(1) term is stated as O(sqrt(log k/k)); confirm that the coindex lower bound and the linear-index characterization together produce precisely this error term without hidden dependencies on n or additional logarithmic factors that would appear in the sparse regime k << n.

    Authors: The O(sqrt(log k/k)) term arises directly from the new Z2-coindex lower bound on the Vietoris-Rips complex of the hypercube in the sparse regime (Section 5), where the radius parameter depends only on k. The analysis uses only the combinatorial geometry of the hypercube and is independent of n for all n > 2k; no additional logarithmic factors in n appear. The exact linear-index characterization then transfers this bound without slack, producing precisely the stated (1-o_k(1))2k. We will add an explicit remark confirming n-independence in the revised Section 5. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via proved characterization

full rationale

The paper defines S(A) for any partial sign matrix A and proves (rather than assumes or fits) that sign-rank(A) equals the linear analog of the Z2-index of S(A). This theorem converts topological lower bounds on the index/coindex into sign-rank lower bounds. The GHD_k^n application then relies on an independent computation of the Z2-coindex of the Vietoris-Rips complex of the hypercube in the sparse regime, which is not obtained by fitting parameters or renaming prior results. No load-bearing step reduces by construction to its own inputs, self-citations, or ansatzes; the central (1-o_k(1))2k claim follows from the new coindex analysis.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The framework rests on a new characterization theorem equating sign-rank to a linear Z2-index; the coindex computation in the sparse regime is the novel technical step. No explicit free parameters are named in the abstract.

axioms (1)
  • domain assumption Sign-rank of A equals the linear analog of the Z2-index of the free Z2-complex S(A).
    This is the load-bearing reduction stated in the abstract; if false, the topological lower bounds do not transfer to sign-rank.
invented entities (1)
  • Free Z2-simplicial complex S(A) no independent evidence
    purpose: Encodes the sign matrix A so that its Z2-index lower-bounds sign-rank.
    Newly associated object whose index is claimed to characterize sign-rank.

pith-pipeline@v0.9.0 · 5693 in / 1374 out tokens · 35901 ms · 2026-05-13T21:38:37.094465+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Geometrical realization of set systems and probabilistic communication complexity

    [AFR85] Noga Alon, Peter Frankl, and Vojtech Rodl. Geometrical realization of set systems and probabilistic communication complexity. In26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 277–280. IEEE,

    work page 1985

  2. [2]

    On the connectivity of the Vietoris–Rips complex of a hypercube graph.arXiv preprint arXiv:2311.06407, 2023

    [BG23] Martin Bendersky and Jelena Grbic. On the connectivity of the vietoris-rips complex of a hypercube graph.arXiv preprint arXiv:2311.06407,

    work page arXiv

  3. [3]

    Borsuk-ulam and replicable learning of large-margin halfspaces.arXiv preprint arXiv:2503.15294,

    [BHH+25a] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak. Borsuk-ulam and replicable learning of large-margin halfspaces.arXiv preprint arXiv:2503.15294,

    work page arXiv

  4. [4]

    Simpli- cial covering dimension of extremal concept classes.arXiv preprint arXiv:2511.11819,

    [BHH+25b] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak. Simpli- cial covering dimension of extremal concept classes.arXiv preprint arXiv:2511.11819,

    work page arXiv

  5. [5]

    The complexity of computing the minimum rank of a sign pattern matrix.arXiv preprint arXiv:1503.04486,

    [BK15] Amey Bhangale and Swastik Kopparty. The complexity of computing the minimum rank of a sign pattern matrix.arXiv preprint arXiv:1503.04486,

    work page arXiv

  6. [6]

    Equality alone does not simulate randomness

    [CLV19] Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. Equality alone does not simulate randomness. In34th Computational Complexity Conference (CCC 2019), pages 14–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,

    work page 2019

  7. [7]

    Spherical dimension.arXiv preprint arXiv:2503.10240,

    [CMW25] Bogdan Chornomaz, Shay Moran, and Tom Waknine. Spherical dimension.arXiv preprint arXiv:2503.10240,

    work page arXiv

  8. [8]

    Sign-rank of k-hamming distance is constant.arXiv preprint arXiv:2506.12022,

    [GHIS25] Mika G¨ o¨ os, Nathaniel Harms, Valentin Imbach, and Dmitry Sokolov. Sign-rank of k-hamming distance is constant.arXiv preprint arXiv:2506.12022,

    work page arXiv

  9. [9]

    Lower bound methods for sign-rank and their limitations

    [HHP+22] Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, and Rosie Zhao. Lower bound methods for sign-rank and their limitations. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), pages 22–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik,

    work page 2022