A tight bound for affine-linearity, via universal ballot matrices

Abstract

Based on work with Greenfeld and with Ziegler, Tao showed a concatenation result that if a map $f:{\mathbb{F}}^2\to \mathbb{F}$ is affine-linear on every line parallel to the coordinate axes, and on all lines with a fixed nonzero slope (where the field $\mathbb{F}$ has size $>2$), then $f$ is affine-linear on ${\mathbb{F}}^2$. We extend this from ${\mathbb{F}}^2$ to ${\mathbb{F}}^n$ and obtain a tight minimum number of additional lines needed -- $N=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ -- for every field $\mathbb{F}$ with $3⩽n<|\mathbb{F}|$. The proof is constructive and shows a stronger result: the existence of a universal family of $0$-$1$ matrices of size $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\times \left(\genfrac{}{}{0ex}{}{n}{k}\right)$ (one for each pair $0⩽k⩽n$), which are indexed by ballot sets and are unimodular over all unital commutative rings. We also show a second tightness: of the assumption $n<|\mathbb{F}|$. Else, there exist multi-affine maps $f$ which are affine-linear on every line through the origin, but not affine-linear globally on ${\mathbb{F}}^n$. More strongly, we prove this dichotomy -- including the bound of $N$ -- over all integral domains, or Noetherian (e.g.\ finite or Artinian) rings, or products of these. This yields a novel numerical invariant for affine-linearity, for every product of Noetherian rings and integral domains.

13 pages