Blocky Matrices and Group Idempotents

Gaia Carenini

Source-linked AI summary

Blocky Matrices and Group Idempotents

Gaia Carenini

arXiv:2609.27951v1Aug 23, 2026math.COcs.CCmath.FA

TL;DR

The paper addresses how to recover exact equality-kernel structure when Hilbert-space factorizations provide closeness rather than equality. It proves an equivariant signed decomposition theorem, with quantitative consequences for matrices and groups, including a γ^4-exponent bound for finite Boolean Schur multipliers.

Problem
Hilbert-space factorizations provide a Euclidean notion of closeness, while the desired equality-kernel structure requires exact equality among entries.
Source: §1.5 · p. 4
Method
The paper proves that invariant integer-valued kernels with equivariant γ-factorizations decompose into signed Γ-equivariant equality kernels.
Source: §1.2 · p. 3
Results
Every finite Boolean Schur multiplier with multiplier norm at most γ is a signed sum of at most 2^{O(γ^4)} contractive idempotent Schur multipliers.
Source: §8 · p. 17
Takeaways & Limitations
Orbitwise equivariance preserves translation-invariant form during recursion, making the non-abelian consequence possible.
Source: §1.4 · p. 4
The recursion controls the number of coset terms, not the number of distinct subgroups, and currently does not coordinate period subgroups across leaves.
Source: §10 · p. 21

Abstract

from arXiv · show

We prove a common generalization of two structure theorems: the dimension-free decomposition theorem for idempotent Schur multipliers and the idempotent theorem in harmonic analysis. Roughly speaking, our result shows that an invariant integer-valued kernel with Hilbert-space factorization norm $γ$ admits a signed decomposition into at most $2^{O(γ^4)}$ elementary pieces. In the matrix setting these pieces are blocky matrices, while in the group setting they are indicators of cosets. In the locally compact abelian setting this quantitatively strengthens the theorem of Green and Sanders, while in the non-abelian setting it gives a quantitative strengthening of Host's idempotent theorem and, for finite groups, of Sanders's quantitative result. It also improves the exponent in the dimension-free matrix decomposition from $γ^6$ to $γ^4$.

1 Introduction

The paper unifies matrix and group decomposition results by showing that invariant integer-valued kernels with equivariant Hilbert-space factorizations decompose into signed equivariant equality kernels. Specializing the theorem gives blocky-matrix and coset decompositions, with a proof combining a martingale bound, rounding, and equivariant recursion.

1.1 A common decomposition problem

Blocky matrices and coset kernels are both equality tests; the paper proposes that group symmetry and small Hilbert-space factorization norm govern their common decomposition structure.The framework connects the matrix theorem with abelian and non-abelian idempotent theorems.Source: §1.1 · p. 2

1.2 Equality kernels and the master theorem

An invariant integer-valued kernel with an equivariant γ-factorization decomposes into signed Γ-equivariant equality kernels, under freeness and finite column-orbit-space hypotheses.Freeness supports equivariant choices in the terminal decomposition and splitting, while finiteness ensures orbit processing terminates.Source: §1.2 · p. 3

1.3 The trivial action: matrices

Finite integer matrices with bounded γ2-norm decompose into signed blocky matrices, strengthening the earlier dimension-free bound by improving its exponent from γ^6 to γ^4.The matrix specialization also applies to Boolean matrices of bounded Schur-multiplier norm.Source: §1.3 · p. 3

1.4 The regular action: groups

Orbitwise equivariant recursion preserves translation invariance and yields open period subgroups, enabling a single-exponential quantitative non-abelian idempotent result.For finite groups, this replaces Sanders’s tower-type bound; the conclusion also applies uniformly to locally compact groups.Source: §1.4 · p. 4

1.5 Proof strategy

The proof turns Hilbert-space closeness into exact equality by rounding, using a martingale dimension bound, a norm-decreasing split, and recursion.The weighted Littlestone bound is roughly γ^2 rounds; the split lowers squared-norm potential, and terminal subtraction yields equality kernels.Source: §1.5 · pp. 4–5

2 Equality kernels and reduced row mass

The section identifies equality kernels with blocky matrices, then introduces reduced row mass as a way to measure the complexity of integer kernels and obtain finite equality-kernel decompositions.

2.1 Equality kernels are exactly blocky matrices

A Boolean matrix is blocky if and only if it is an equality kernel, so equality kernels serve as the same decomposition atoms as blocky matrices.For blocky matrices, the labels identify matching row and column blocks.Source: §2.1 · p. 6

2.2 Reduced row mass

Reduced row mass counts distinct columns rather than repeated columns, making it more informative than a raw row sum when many columns agree.For finite matrices, it is the largest row sum after duplicate columns are removed.Source: §2.2 · p. 6
If an invariant integer kernel has finite reduced row mass D, it admits a decomposition into at most 2D equivariant equality kernels.The argument handles the positive and negative parts separately.Source: §2.2 · pp. 6–7
For a nonnegative kernel, selecting a positive column class in each nonzero row orbit yields an equality kernel whose subtraction reduces every nonzero row’s reduced mass by one.Repeating the step exhausts the kernel in at most D steps.Source: §2.2 · p. 7

3 Hilbert factorizations and the weighted mistake tree

This section sets up a weighted mistake-tree measure of a matrix’s combinatorial complexity and connects it to Hilbert-space factorization. Predictability of the tree’s queries is central to the later bound.

3 Hilbert factorizations and the weighted mistake tree

The factorization norm γ2 is the Hilbert-space quantity used in the argument; for finite matrices, it coincides with the Schur-multiplier norm.The factorization writes entries as inner products of vectors.Source: §3 · p. 7
A weighted mistake tree queries a row and threshold at each internal node, with branches representing whether the entry is large or small relative to that threshold.A matrix α-shatters the tree when columns can realize every root-to-leaf path with the required margin.Source: §3 · pp. 7–8
The weighted Littlestone dimension Ldimα(A) is the greatest depth of a tree α-shattered by A.Large dimension represents many strategies whose paths each have a consistent column.Source: §3 · p. 8
The row and threshold queried at each level depend only on earlier random signs, making them predictable for the filtration used in the martingale estimate.The setup also defines almost integer-valued kernels by entrywise rounding within a maximum error ε.Source: §3 · pp. 7–8

4 The martingale bound on weighted Littlestone dimension

The section bounds the depth of a weighted mistake tree by following a random path through a Hilbert-space factorization. Predictability makes the martingale estimate possible, yielding a quadratic rather than quartic dependence on the factorization norm.

4 The martingale bound on weighted Littlestone dimension

Along a random path, shattering forces the signed vector sum to pair with a consistent column by at least roughly αd/2.The path uses independent random signs to choose its successive branches.Source: §4 · p. 8
Predictability makes cross terms in the second-moment estimate average to zero, allowing the random signed sum to be bounded without incorporating thresholds into the factorization.The thresholds interact with mean-zero signs and disappear upon taking expectation.Source: §4 · pp. 8–9
d ≤ 4γ2/α2 bounds the α-shattered weighted Littlestone dimension of a real matrix with factorization norm γ2.The theorem obtains the bound by taking the infimum over γ-factorizations.Source: §4 · pp. 8–9
The martingale argument replaces an earlier Oα(γ4) dimension bound and contributes to reducing the paper’s final exponent from γ6 to γ4.The earlier route encoded thresholds directly in an enlarged factorization.Source: §4 · p. 9

5 From bounded dimension to near-constant columns

This section uses bounded weighted Littlestone dimension to obtain large sets of columns that are nearly constant across rows. Its inductive argument splits column classes when a row cannot be approximated by one interval.

5 From bounded dimension to near-constant columns

The argument turns a dimension bound into near-constancy by induction on weighted Littlestone dimension, following a weighted real-valued version of the Sauer–Shelah style argument.The near-constancy approach is identified as a quantitative reformulation of Goh and Hatami [3, Proposition 3.1].Source: §5 · pp. 9–10
When no interval of length 4α covers a (1−η)-fraction of columns in a row, partitioning the value range into α-intervals produces separated classes for a threshold split.At least one resulting restriction has weighted Littlestone dimension at most d−1.Source: §5 · p. 10
For finite nonempty Y with ∥A∥γ2 ≤ γ and ∥A∥max ≤ M, a large set S admits a row function g with Pr_y∈S[|A(x,y) − g(x)| > 1/4] ≤ η for every row x.The result is stated for η ∈ (0,1].Source: §5 · pp. 9–10
Specializing to α = 1/8 gives the 1/4 tolerance, while Theorem 4.1 supplies d ≤ 256γ2 and the interval count satisfies q ≤ C(1 + M).These parameter substitutions yield the stated exponent after absorbing constants.Source: §5 · p. 11

6 The local norm-decreasing split

The local split decomposes one column vector into two pieces that each have strictly smaller squared norm while remaining nearly integer-valued when tested against every row.

6 The local norm-decreasing split

Lemma 6.1 guarantees a family vector whose distance from the average is controlled by its squared norm and the squared norm of that average.The proof uses the bias-variance identity for Hilbert-space vectors.Source: §6 · p. 11
The sharper local threshold adapts [1, Lemma 2.4] and replaces its O(γ^4) weighted-Littlestone estimate with an O(γ^2) martingale estimate.This change yields the sharper threshold.Source: §6 · p. 11
A large family of columns agreeing in one row is shrunk to a set nearly constant in every row, whose average supplies the split.Distinct rounded columns are separated in Hilbert space, forcing the average vector to be small enough for a genuine norm decrease.Source: §6 · pp. 12–13
Both pieces reduce the squared column-norm bound by at least 1/16 and remain 3ϵ-almost integer-valued across every row.The pieces are the chosen column vector minus its near-constant average, and the average itself.Source: §6 · p. 13

7 The equivariant recursion

The recursion makes local column splits compatible with a group action by transporting each split around a free orbit. Repeated equivariant splits produce the master decomposition with a bounded number of equality kernels.

7.1 Splitting one orbit

A local split at one column is transported around its free orbit, preserving the norm and almost-integrality bounds.For an infinite row set, finite restrictions and weak compactness extend the split to all rows before transport.Source: §7 · p. 14, §7.1 · p. 14

7.2 One step of the recursion

Processing finitely many column orbits yields two equivariant, 3ϵ-almost integer-valued kernels and a residual kernel with reduced row mass at most T(γ, ϵ).On split orbits the rounded kernel is exactly the sum of the two rounded child kernels.Source: §7.2 · p. 15

7.3 Proof of the master theorem

Each genuine split lowers the squared column-norm parameter by at least 1/16, so a branch has at most 16γ^2 genuine splits.Summing node contributions through the binary recursion gives the theorem's signed equality-kernel decomposition.Source: §7.3 · pp. 16–17

8 Matrix consequences

For finite Boolean Schur multipliers, the matrix specialization gives a signed decomposition into contractive idempotent Schur multipliers. The improved exponent comes from a sharper martingale estimate.

8 Matrix consequences

Every finite Boolean Schur multiplier of multiplier norm at most γ is a signed sum of at most 2^O(γ^4) contractive idempotent Schur multipliers.The identification uses the characterization of blocky Boolean matrices as contractive idempotent Schur multipliers [1].Source: §8 · p. 17
The exponent improves from six to four because the weighted-Littlestone bound falls from O(γ^4) to O(γ^2), while the recursion tree adds only O(γ^2) to the logarithm.The earlier decomposition bound was 2^O(γ^6).Source: §8 · p. 17

9 The regular group action

Under the regular group action, coefficient functions yield equivariant factorizations, and the equality kernels correspond to cosets. This lets the recursion give signed open-coset decompositions for integer-valued functions in B(G).

9.1 Coefficient functions give equivariant factorizations

A real-valued coefficient function in B(G) gives an equivariant Hilbert-space factorization of the kernel f(x^-1y).The realification of a unitary representation supplies the orthogonal action, with factorization norm bounded by any γ greater than the B(G) norm.Source: §9.1 · p. 18

9.2 Why the terminal subgroups are open

For a δ-almost integer-valued coefficient with δ < 1/2, its right-period subgroup is open.Strong continuity gives uniform control near the identity, preventing rounded values from changing there.Source: §9.2 · pp. 18–19

9.3 Duplicate columns are exactly cosets

Columns of the convolution kernel for k agree exactly when their indices lie in the same coset of PerR(k).Translation-invariant Boolean equality kernels are precisely indicators of left cosets of subgroups.Source: §9.3 · p. 19

9.4 Proof of the non-abelian idempotent theorem

The recursion yields a signed decomposition into at most 2^C′M^4 indicators of cosets of open subgroups for nonzero integer-valued f in B(G), where M = ∥f∥B(G).Finiteness of the terminal reduced row mass ensures only finitely many cosets contribute.Source: §9.4 · p. 20

10 Abelian consequences, and a comparison with earlier bounds

Fourier transforms transfer the non-abelian theorem to idempotent measures on locally compact abelian groups, improving the earlier bound while retaining broader group scope. The comparisons also identify sharper bounds in a specific finite-abelian setting and limitations in tracking subgroup diversity.

Abelian consequences

Theorem 1.6 applies to an idempotent measure by Fourier-transforming it into a Boolean-valued function and applying the theorem on the dual group.This recovers the Green–Sanders setting, while Theorem 1.6 itself applies to arbitrary locally compact groups.Source: §10 · p. 21

Comparison with earlier bounds

A single-exponential bound removes one level from Green and Sanders’s earlier double-exponential bound for arbitrary locally compact abelian groups [4].Theorem 1.6 also permits arbitrary locally compact groups.Source: §10 · p. 21
exp(O(M^4)) removes the M^o(1) exponent loss in Sanders’s finite-abelian bound exp(M^4+o(1)), but his F_2^n bound exp(M^3+o(1)) remains sharper.The comparison concerns integer-valued functions on finite abelian groups and Sanders’s specific model group, respectively.Source: §10 · p. 21
The recursion controls the total number L of coset terms, not the number of distinct subgroups; its leaves may produce unrelated period subgroups.Coset decision trees control a different structural parameter, so their bounds are not directly comparable to signed coset-decomposition length.Source: §10 · p. 21
For finite groups, the Boolean case replaces Sanders’s tower-type non-abelian bound by a single-exponential bound, and applies to arbitrary locally compact groups.The cited quantitative theorem of Sanders is stated for finite groups.Source: §10 · p. 21
The matrix corollary improves the signed blocky-matrix decomposition exponent from six to four over the earlier 2^O(γ^6) bound [1].The earlier result treats Boolean matrices with γ2-norm at most γ.Source: §10 · p. 22