Gröbner Bases for Increasing Sequences

Abstract

Let $q,n \geq 1$ be integers, $[q]=\{1,\ldots, q\}$, and $F$ be a field with $|F|\geq q$. The set
of increasing sequences

$$
I(n,q)=\{(f_1,f_2, \dots, f_n) \in [q]^n:~ f_1\leq f_2\leq\cdots \leq f_n \}
$$
can be mapped via an injective map $i: [q]\rightarrow F $ into a subset $J(n,q)$ of the affine space $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)$.