Faithful linear multiplicative summaries need \(2^m\) dimensions
On this page · Permalink · Source line 555
Suppose \(\Phi:K^W\to A\) is \(K\)-linear and multiplicative, and \(\Phi(\delta_v)\ne0\) for every \(v\in W\). Put \(e_v=\Phi(\delta_v)\). The images are nonzero orthogonal idempotents.
If \(\sum_v c_v e_v=0\), multiply by \(e_u\). Orthogonality removes every other term and idempotence gives \(c_u e_u=0\). Since \(K\) is a field and \(e_u\ne0\), \(c_u=0\). Hence all \(e_v\) are linearly independent and
No unital hypothesis is needed. At \(m=0\), there is one empty witness and the bound is simply \(\dim_K A\ge1\).
For a unital scalar map to \(K\), scalar idempotents are zero or one. Orthogonality permits at most one nonzero image, and preservation of one requires exactly one. Such a map is evaluation at one witness. For \(m\ge1\) it loses at least one other singleton verifier. For \(m=0\), there is no other witness to lose.
Model boundary. The theorem quantifies a fixed summary serving all predicates at a witness length, preserving linear combinations and exact pointwise multiplication. An unrestricted algorithm need not use such a summary. Syntax, nonlinear encodings, changing spaces, context-dependent operations, and succinct expressions are outside these hypotheses.
An exponentially large algebra can still contain short circuit expressions. Therefore exponential dimension does not imply exponential expression length or a lower bound for every algorithm on one explicit decision family.