Uncertainty principles and sum complexes

Meshulam, Roy

Journal of Algebraic Combinatorics, Tome 40 (2014) no. 4, pp. 887-902.

Résumé

Let $p$ be a prime and let $A$ be a nonempty subset of the cyclic group $C_p$. For a field $\mathbb F$ and an element $f$ in the group algebra $\mathbb F[C_p]$ let $T_f$ be the endomorphism of $\mathbb F[C_p]$ given by $T_f(g)=fg$. The uncertainty number $u_{\mathbb F}(A)$ is the minimal rank of $T_f$ over all nonzero $f\in\mathbb F[C_p]$ such that $\mathrm{supp}(f)\subset A$. The following topological characterization of uncertainty numbers is established. For $1\leq k\leq p$ define the sum complex $X_{A,k}$ as the $(k-1)$-dimensional complex on the vertex set $C_p$ with a full $(k-2)$-skeleton whose $(k-1)$-faces are all $\sigma\subset C_p$ such that $|\sigma|=k$ and $\prod _{x\in\sigma}x\in A$. It is shown that if $\mathbb F$ is algebraically closed then $$ u_{\mathbb F}(A)=p-\max\{k:\tilde H_{k-1}(X_{A,k};\mathbb F)\neq 0\}.$$ The main ingredient in the proof is the determination of the homology groups of $X_{A,k}$ with field coefficients. In particular it is shown that if $|A|\leq k$ then $\tilde H_{k-1}(X_{A,k}\mathbb F_p)=0$.

Détail

Classification : 05E10, 05E45, 05C05, 55U10, 20C05
Keywords: uncertainty principle, simplicial homology