Combinatorial Theory

For $p$ prime, let ${\mathcal{H}}^n$ be the linear span of indicator functions of hyperplanes in $(\mathbb{Z}/p^k\mathbb{Z}{)}^n$. We establish new upper bounds on the dimension of ${\mathcal{H}}^n$ over $\mathbb{Z}/p\mathbb{Z}$, or equivalently, on the rank of point-hyperplane incidence matrices in $(\mathbb{Z}/p^k\mathbb{Z}{)}^n$ over $\mathbb{Z}/p\mathbb{Z}$. Our proof is based on a variant of the polynomial method using binomial coefficients in $\mathbb{Z}/p^k\mathbb{Z}$ as generalized polynomials. We also establish additional necessary conditions for a function on $(\mathbb{Z}/p^k\mathbb{Z}{)}^n$ to be an element of ${\mathcal{H}}^n$.

Mathematics Subject Classifications: 05B20, 05B25, 05A10

Keywords: Hyperplanes, generalized polynomials, binomial coefficients