PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication Complexity of Integer Matrix Singularity

Chengu Wang

arXiv:2610.33521v1cs.CCquant-ph

TL;DR

The paper asks how communication complexity for rational singularity depends on entry length and whether additive and bitwise-XOR sharing have different costs. The paper combines an integer witness and local digit encoding for additive lower bounds, modular kernel-relation lifting for the additive upper bound, and a dense weighted equation with Fourier control for XOR. For k ≥ n log n, additive singularity’s lower and upper bounds match at Θ(n² log(nk)), including superpolynomial bit lengths.

  • Problem

    The paper asks how communication complexity for rational singularity depends on entry length and whether additive and bitwise-XOR sharing have different costs.

    Source: §1 · p. 4

  • Method

    The paper combines an integer witness and local digit encoding for additive lower bounds, modular kernel-relation lifting for the additive upper bound, and a dense weighted equation with Fourier control for XOR.

    Source: §1.4 · p. 8

  • Results

    For k ≥ n log n, additive singularity’s lower and upper bounds match at Θ(n² log(nk)), including superpolynomial bit lengths.

    Source: §1.2 · p. 6

  • Takeaways & Limitations

    For k ≥ n log n, prior entanglement and quantum communication do not change additive singularity’s asymptotic cost, whereas XOR remains proportional to the full input length.

    Source: §1 · p. 4, §1.2 · p. 6

    For short-entry additive singularity, the bounds leave open whether quantum and randomized complexities coincide or a protocol can improve the upper bound.

    Source: §1.5 · p. 9

Abstract

from arXiv · show

Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$-bit integers and decide whether it is singular over $\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\mathbb Q$. We prove a bounded-error quantum lower bound $\Omega(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. The bounds match at $\Theta(n^2\log(nk))$ for $k\ge n\log n$. The lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $\Omega(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.

1 Introduction

The paper studies communication for rational singularity when matrix entries are shared additively or by bitwise XOR. It establishes contrasting bounds and leaves additive complexity for short entries unresolved.

1.1 Previous results

  • Prior bounds include deterministic Θ(n^2k) and randomized O(n^2 min{k, log(nk)}), while the streaming Ω(n^2) result applies only to one-way communication.Source: §1.1 · pp. 4–5

1.2 Our results

  • Additive singularity has quantum lower bound Ω(min{n^3/2√(k log n), n^2 log(nk)}) and randomized upper bound O(n^2 min{k, log(k + log n)}), matching at Θ(n^2 log(nk)) for k ≥ n log n.Source: §1.2 · p. 6
  • For every k, XOR requires Ω(n^2k) quantum communication, matching trivial transmission even under the rank n −1 versus n promise.Source: §1.2 · p. 6

1.3 The role of the entry bit length

  • At k = n^2, additive complexity is Θ(n^2 log n) while XOR complexity is Θ(n^4); modular reduction does not directly transfer because XOR depends on both parties’ private bitwise AND.Source: §1.3 · p. 7

1.4 Proof ideas

  • The additive upper protocol lifts modular kernel relations through integral column operations, sending short quotient residues and removing one prime factor from the determinant per lift.Source: §1.4 · p. 7
  • The additive lower bound combines an integer witness with local digit expansion; the XOR proof uses a dense weighted equation and Fourier control of dyadic frequencies.Source: §1.4 · p. 8

1.5 Open questions

  • For short-entry additive singularity, it remains open whether the bounds can be tightened and whether randomized and entangled quantum complexities coincide.Source: §1.5 · p. 9

2 Preliminaries

Local reductions relate balanced column partitions to additive singularity while preserving the entry alphabet and corank. Schur complements support these reductions, and a signed-witness pairing bounds what entangled protocols can achieve, including under a promise.

2.1 Local reductions and Schur complements

  • For additive constructions, fixed ownership assigns each position to one party, and identity padding is local.The party adding the identity block uses zero off-diagonal blocks.Source: §2.1 · p. 9
  • Schur-complement identities reduce the relevant block determinant to det(U − V − W + Z), and apply to arbitrary rational blocks.The identities follow by invertible block row elimination.Source: §2.1 · pp. 9–10
  • Local maps reduce between balanced column partitions and additive singularity while preserving the entry alphabet and corank, including under a full-rank-versus-corank-one promise.In one direction, the parties place their owned columns in separate blocks; in the other, a block construction has the same corank as the sum of their inputs.Source: §2.1 · p. 10

2.2 Signed witnesses and entangled protocols

  • A signed witness pairs with a protocol’s acceptance probabilities; on promise problems, variation outside the promise adds a penalty of 2δ/3.The pairing bound uses operator norms and a factorization of the acceptance matrix for entangled protocols.Source: §2.2 · p. 11

3 Additive upper bound

The additive upper bound uses prime sampling and lifts modular kernel relations using quotient residues recoverable from additive shares. Choosing between that protocol and sending an input gives O(n^2 min{k, log(k + log n)}) communication.

3.1 Quotient residues from additive shares

  • A prime-modulus protocol recovers Mv/q mod p from additive shares when q divides Mv, using n⌈log p⌉ communicated bits.The quotient-residue method also works for negative shares.Source: §3.1 · p. 12

3.2 Lifting modular kernel relations

  • The lifting protocol sends modular kernel vectors and updates columns so the determinant-one basis is maintained while quotient residues update the implicit matrix.For nonzero det M, it stops after v_p(det M) lifts if the budget permits; Lemma 3.1 gives cost O((n^2 + nL) log p).Source: §3.2 · p. 12

3.3 Prime sampling and communication cost

  • O(n^2 min{k, log(k + log n)}) bits suffice, by choosing between the prime-sampling protocol and sending Alice’s input.The protocol’s error comes only when the sampled prime’s determinant valuation exceeds 3n; singular matrices are always accepted.Source: §3.3 · p. 13

4 Additive lower bound

The additive lower bound is built from hard integer matrices with a quantum witness, then transferred to bounded-bit inputs by local radix encoding. The encoding preserves corank and fixed ownership while controlling dimension growth.

4.1 Hard integer inputs and their quantum witness

  • With h = O(log d + (d + u) log(u + 1) + log m) bits per entry, singularity requires Ω(md log(u + 1)) qubits, even under the adjacent-rank promise.The promised ranks are m + d − 1 versus m + d.Source: §4.1 · p. 13
  • The witness retains the full input product because restricting it to the rank promise would not justify keeping its operator bound.Its variation on inputs of corank at least two is bounded by 1/40.Source: §4.1 · pp. 13–14

4.2 Local radix encoding

  • Expanding only the bottom d rows and rightmost d columns makes the dimension cost proportional to d times the digit count, rather than the number of integer entries.The expansion adds equal numbers of rows and columns, preserving corank.Source: §4.2 · pp. 14–15
  • For h-bit inputs, local radix encoding produces k-bit matrices of order n′ = m + d(6⌈h/k⌉−3), with rank(A′ + B′) = n′ − d + rank E.The encoding uses fixed ownership and disjoint supports.Source: §4.2 · pp. 14–15
  • A public recurrence constructs row weights that recover signed differences from radix digits by canceling public columns.For two binary digits, the weights are (1, −1, 1, 2, −2).Source: §4.2 · p. 14

4.3 Choosing the core size and scalar cutoff

The proof chooses the core dimension and scalar cutoff in two bit-length regimes. These choices fit the encoding within dimension n and yield the stated lower bound while preserving the rank promise.

4.3 Choosing the core size and scalar cutoff

  • For 1 ≤ k ≤ n log n, the construction gives a quantum lower bound Ω(n^(3/2)√(k log n)).The core dimension is chosen as a power of two proportional to min{n, nk / log n}.Source: §4.3 · p. 15
  • For k ≥ n log n, the lower bound is Ω(n^2 log(nk)), with d = Θ(n) and log(u + 1) = Θ(log k).The one-digit encoding has order at most n, and the rank promise is preserved.Source: §4.3 · p. 15
  • For k = 1, the lower bound is Ω(n^(3/2)√log n), and the result also holds under the adjacent-rank promise.Source: §4.3 · p. 15

4.4 Constructing the additive communication witness

The witness construction combines signed measures with controlled Fourier behavior and then restricts them to bounded integer inputs. Its frequency analysis and operator decomposition support the communication lower bound.

4.4.1 Structured residuals and scalar dilation

  • A signed measure on integer matrices has correlation at least 403/440 with singularity, variation at most one, and vanishing Fourier derivatives through order L at specified low-image frequencies.Its variation on coranks at least two is at most 1/40.Source: §4.4.1 · p. 16
  • Scalar dilation by λu extends the derivative-vanishing condition to matrices whose modular image groups have fewer than (u + 1)s + 1 elements.The dilation satisfies log λu ≤ u log(u + 1).Source: §4.4.1 · p. 16

4.4.2 A dichotomy for torus frequencies

  • At every torus frequency, either the concentration quantity CH(θ) is at most 1/B or the residual transform has magnitude at most 2^−(L+1).Source: §4.4.2 · p. 17

4.4.3 Fourier decomposition of the communication operator

  • Fourier transformation splits the communication operator into blocks of rank at most one, with norms controlled by the residual transform and the kernel factors.The construction first defines inputs modulo q using Z0 = P0 + a and Z1 = P1 + aF − E.Source: §4.4.3 · p. 18

4.4.4 Restricting the witness to bounded integer inputs

  • Restricting P to an integer interval prevents modular wrap while recovering the residual E exactly, so the singularity label and bounded-input witness estimates are retained.The resulting inputs are nonnegative and meet the required bit bound.Source: §4.4.4 · p. 19

4.5 Split isometries and singularity correlation

The proof constructs rational shear transformations with controlled rank, then uses differences of isometries to form a signed residual correlated with singularity. Rank parity links these constructions to determinant signs.

4.5.1 A parametrization by two shears

  • The shear transformations preserve the form J0 and have determinant one.Source: §4.5.1 · p. 19

4.5.2 Rank parity for orthogonal isometries

  • For an isometry preserving a nondegenerate symmetric bilinear form over Q, det g = (−1)^rank(I − g).This is the stated rank-parity identity for orthogonal isometries.Source: §4.5.2 · p. 20

4.5.3 Uniform transversality for two shears

  • For each rational J0-isometry G, rational skew-symmetric X,Y attain rank d when det G = 1 and d − 1 when det G = −1; random choices fail with probability at most 2d/L.Source: §4.5.3 · p. 20

4.5.4 A signed residual from isometry differences

  • Differences of isometries yield a signed integer measure of mass zero and variation one, with singularity correlation at least 39/40 when L0 = 80d.The rank-parity identity determines the sign of each contribution.Source: §4.5.4 · p. 21

4.6 Positive correction in Fourier algebra norm

This section characterizes the Fourier algebra norm on finite groups and uses a positive reweighting to correct small correlations exactly. The correction has bounded size and can be rational when the measure and coefficient functions are rational.

4.6 Positive correction in Fourier algebra norm

  • The finite-group Fourier algebra norm follows from Eymard’s coefficient-norm characterization and Fourier inversion; projection onto complete irreducible coefficient spaces is contractive.The passage also gives supremum and Banach-algebra bounds for this norm.Source: §4.6 · pp. 21–22
  • The correction solves a near-identity Gram system, making small correlations exactly zero while retaining positive weights.The method controls the correction in Fourier algebra norm, yielding the uniform bound used below.Source: §4.6 · p. 22
  • Lemma 4.13 constructs a real correction a in W with norm at most η/(1−η) ≤ 1/3.The resulting weights lie in [2/3, 4/3] before normalization.Source: §4.6 · p. 22
  • When the measure and defining coefficient functions are rational, the correcting weights can be rational.Source: §4.6 · p. 22

4.7 Mixing on frame orbits over odd finite fields

The section analyzes alternating-shear averages on frame fibers over odd finite fields. When r ≥ 8k, the shear groups act transitively on each fiber, without a nondegeneracy assumption on the prescribed Gram matrix.

4.7 Mixing on frame orbits over odd finite fields

  • Theorem 4.14 gives a uniform mixing bound for every starting frame, and the same bound holds with the upper and lower averages interchanged.Source: §4.7 · p. 23
  • For r ≥ 8k, the shear groups act transitively on the frame fiber, with no nondegeneracy assumption on C.The proof bounds 2δr,k(q) by 15q^(2k−r) < 1.Source: §4.7 · pp. 23–24
  • The estimates are uniform in the starting frame and do not require either block to have full rank.Source: §4.7 · p. 23
  • For a uniformly random r-by-k matrix B′, the probabilities of rank[B B′] < 2k and rank B′ < k are bounded by β = vkq^(k−r) and α0 = vkq^(−r), respectively.Source: §4.7 · p. 24

4.8 Congruence orbits of primitive frames

The congruence refinement establishes transitivity under the principal congruence kernel for primitive frames with fixed reduction and Gram matrix. The argument matches frames successively modulo higher powers of p.

4.8 Congruence orbits of primitive frames

  • This is a congruence refinement of Witt extension: the extension is additionally required to be the identity modulo p.Source: §4.8 · p. 24
  • For odd p and k ≤ d, Kq is transitive on rank-k frames with prescribed reduction modulo p and prescribed Gram matrix modulo q.Source: §4.8 · p. 25
  • The proof corrects a first-order frame difference at each p-adic layer using an orthogonal Lie algebra element and the Cayley map.Full column rank supplies the left inverse needed; the Gram matrix need not be nondegenerate.Source: §4.8 · p. 25

4.9 Finite-module designs and structured residuals

The section develops finite-module contraction and averaging tools, then constructs structured signed residuals with controlled height and Fourier zeros. Its results span module-level operator bounds, orbit properties, and bounds on the residual’s variation and entry height.

4.9.1 Representation levels on finite modules

  • For r ≥ 80b, Theorem 4.16 gives contraction by module size for every irreducible type of level ℓ ≥ 1, with a bound independent of the prime-power exponent a.Source: §4.9.1 · p. 25

4.9.2 The symplectic Fourier model

  • The symplectic Fourier model identifies the isotropic-subgroup space KI with a representation HM′ of a smaller finite abelian p-group M′.The quotient I⊥/I supplies the smaller group, and the identification intertwines the upper and lower shears.Source: §4.9.2 · p. 26

4.9.3 A subgroup expansion of the isotropic projection

  • The subgroup expansion uses Möbius inversion to express the isotropic projection, while compressed Fourier blocks vanish unless the pairing between W and W′ is perfect.A surviving block has |W| = |W′| ≤ |M| and norm at most |M|^(−r/2).Source: §4.9.3 · p. 27

4.9.4 Exact averaging at small odd moduli

  • Theorem 4.20 supplies a finite positive rational law on integral determinant-one J0-isometries, with support consisting of products of 32 alternating shears.The correction uses positive rational weights and preserves the word support.Source: §4.9.4 · p. 28

4.9.5 Determinant-sign cancellation over odd residue rings

  • For r ≥ 8s, every orthogonal isometry modulo p^a, including determinant −1, preserves each Γa-orbit on s-column inputs.Source: §4.9.5 · p. 29

4.9.6 Residual height and Fourier zeros

  • The residual ν has mass zero, variation at most one, correlation at least 403/440, and log2(K + 1) = O(log d + log B + log(L + 1)).Its variation on corank-at-least-two matrices is at most 1/40, and Fourier derivatives through order L vanish at the specified Q/t frequencies.Source: §4.9.6 · p. 29

4.10 Simultaneous modular Fourier jets

The section constructs rational scalar filters with small tail variation, then uses discrete interpolation to make matrix Fourier derivatives vanish at modular frequencies. These dilations preserve singularity correlation while controlling the filtered measure near those frequencies.

4.10.1 Scalar filters with small tail variation

  • N = O(B^4L^4 + BL^3/epsilon) support suffices for rational scalar filters with tail variation below epsilon and simultaneous residue-class polynomial constraints.The coefficient denominators are not bounded.Source: §4.10.1 · pp. 30–31, §4.10.2 · p. 32

4.10.2 Discrete interpolation with polynomial and Fourier features

  • Discrete interpolation combines polynomial and Fourier features to produce real rational weights, with the feature Gram matrix close to the identity.The construction spans the required residue-class and degree constraints.Source: §4.10.2 · pp. 31–32

4.10.3 From scalar filters to matrix Fourier derivatives

  • Theorem 4.25 makes every mixed Fourier derivative of positive order at most L vanish at modular frequencies Q/m for m ≤ B.Near such a zero, the transform is at most 2^-(L+1) when the entrywise-1 norm of the perturbation is at most (L+1)/(40K′).Source: §4.10.3 · p. 33
  • If the original transform also vanishes at every positive integer multiple of a modular frequency, the filtered transform’s zeroth-order value vanishes there too.Pre-existing modular frame zeros at other moduli remain preserved under integer scalar dilations, while the new derivative guarantee covers only m ≤ B.Source: §4.10.3 · p. 33
  • The constant-value hypothesis is essential: canceling every positive-order jet alone does not ensure a zeroth-order Fourier zero.For the stated scalar measure, the odd-coefficient sum has magnitude at least 1 − τ > 0.Source: §4.10.3 · p. 33

4.10.4 Preserving singularity correlation under dilation

  • Dilation preserves rational singularity labels, and the filtered residual retains positive correlation with singularity while every singular rank keeps its positive label.The residual uses L0 = 80d and epsilon = 1/32.Source: §4.10.4 · p. 33

5 Bitwise-XOR singularity

This section develops lower bounds for bitwise-XOR singularity, including a dense-equation witness with signed Fourier corrections that remove exceptional frequencies at small variation cost. It completes the Walsh-witness bound, reduces the dense equation to XOR singularity, and derives a Boolean entrywise-product singularity result through reductions that preserve corank, including under the stated rank promises.

5.4 A dense equation witness

  • The dense-equation witness uses public coefficients a_i, b_j bounded by N^4 and a real signed measure on matrix pairs to encode an integer equation.The section states that this witness supplies the full quantum bit-length factor, with constants and thresholds independent of the relation between dimension and bit length.Source: §5 · p. 34, §5.4 · p. 36

5.1 Sum encodings and the reduction from AND to XOR

  • A local encoding converts entrywise AND into XOR while preserving corank and keeping every output entry within k bits.The same construction converts a Boolean entrywise product into a Boolean XOR matrix.Source: §5.1 · p. 34

5.2 Randomized lower bound from disjointness

  • Θ(n^2k) randomized communication is necessary and sufficient for XOR singularity, by reducing disjointness using Razborov’s theorem [Raz92].The lower bound follows from packing disjointness inputs into matrix entries and padding; sending all n^2 entries gives the matching upper bound.Source: §5.2 · pp. 34–35

5.3 Boolean quantum lower bound from symmetric XOR functions

  • Ω(n^2) quantum communication is required for Boolean XOR singularity, even under the adjacent-rank promise, via Zhang–Shi’s symmetric-XOR theorem [ZS09].Boolean inputs are valid k-bit inputs for every k ≥ 1, so this lower bound applies for all k.Source: §5.3 · p. 35

5.4.1 A signed source with an integer output

  • The initial signed source has zero mass, variation one, and correlation one with the sign of the integer equation s(X) = y.Its two output supports are disjoint, and the source equations are ordinary integer equations even though y is temporarily treated modulo Q.Source: §5.4.1 · p. 36

5.4.2 Frequency estimates for binary words

  • The frequency analysis shows that large values of the binary-word product occupy at most N^σ intervals of length 1/N.A further progression-counting argument is used to force dense products toward nearby rational frequencies.Source: §5.4.2 · p. 37

5.4.3 Choosing the row and column coefficients

  • Suitable row and column coefficients ensure Fourier decay at every nonexceptional grid frequency, with at least d^2/100 coefficient pairs providing decay.The selected coefficient vectors satisfy two properties controlling bad pairs and residues; these bounds yield the stated decay outside dyadic neighborhoods.Source: §5.4.3 · p. 39, §5.4.4 · pp. 39–40

5.4.5 Removing dyadic neighborhoods at small variation cost

  • Removing neighborhoods of exceptional dyadic frequencies changes the signed measure by small variation, leaving variation at most 101/100 and correlation at least 99/100.The completion then begins encoding the output by listing the 4d^2 positions in a fixed public order.Source: §5.4.5 · pp. 40–41, §5.4.6 · p. 41

5.4.6 Encoding the output and bounding Walsh coefficients

  • Exceptional Walsh frequencies are removed, and the remaining coefficients are bounded uniformly to complete the witness-distribution theorem.The proof pushes the witness distribution through the output encoding, which preserves its mass, does not increase variation, and preserves the equation label.Source: §5.4.6 · p. 41

5.5 Reduction from the dense equation to XOR singularity

  • The quantum lower bound is Ω(n^2k) for XOR singularity, including when the output has rank n−1 or n.The reduction maps the dense equation to XOR shares with constant dimension growth and preserves corank.Source: §5.5 · p. 42

5.6 Boolean entrywise-product singularity

  • Boolean entrywise-AND singularity has randomized and entangled quantum complexity Θ(n^2), even at ranks n−1 versus n with all-one borders, via local corank-preserving reductions equivalent to Boolean XOR.The reductions have constant dimension growth.Source: §5.6 · pp. 42–43

AI disclosure

The author reports using OpenAI Codex and Claude Code to assist with manuscript and proof work, while taking full responsibility for the content.

AI disclosure

  • OpenAI Codex and Claude Code assisted with developing, checking, and simplifying proof arguments.The author takes full responsibility for the proofs and all other content.Source: AI disclosure · p. 43
  • OpenAI Codex and Claude Code assisted with researching related work and verifying citations.The author takes full responsibility for the references.Source: AI disclosure · p. 43
  • OpenAI Codex and Claude Code assisted with drafting and revising the manuscript.The author takes full responsibility for all content.Source: AI disclosure · p. 43
Loading 2610.33521v1…