Gröbner Bases for Increasing Sequences

Abstract

Let $q,n\ge 1$ be integers, $[q]=\{1,\dots ,q\}$, and $\mathbb{F}$ be a field with $|\mathbb{F}|\ge q$. The set of increasing sequences $$I(n,q)=\{(f_1,f_2,\dots ,f_n)\in [q{]}^n:f_1\le f_2\le \cdots \le f_n\}$$ can be mapped via an injective map $i:[q]\to \mathbb{F}$ into a subset $J(n,q)$ of the affine space ${\mathbb{F}}^n$. We describe reduced Gröbner bases, standard monomials and Hilbert function of the ideal of polynomials vanishing on $J(n,q)$. As applications we give an interpolation basis for $J(n,q)$, and lower bounds for the size of increasing Kakeya sets, increasing Nikodym sets, and for the size of affine hyperplane covers of $J(n,q)$.

18 pages