Intersection problems for linear codes and polynomials over finite fields

Abstract

This paper proves a stability result for a variation of the Erdős-Ko-Rado theorem in the context of polynomials over finite fields. Let $\mathcal{F}$ be a family of polynomials of degree at most $k\ge 3$ in ${\mathbb{F}}_q[X]$. Call $\mathcal{F}$ intersecting if for any two polynomials $f,g$ in $\mathcal{F}$, there exists a point $x\in {\mathbb{F}}_q$ for which $f(x)=g(x)$. An intersecting family is called a star if it consists of all polynomials $f$ with $\mathrm{deg}f\le k$ such that $f(x)=y$ for some fixed points $x,y\in {\mathbb{F}}_q$. In this paper we prove that if $\mathcal{F}$ is an intersecting family with $|\mathcal{F}|\ge \frac{1}{\sqrt{2}}{q}^k+\mathcal{O}(q^{k-1})$, then $\mathcal{F}$ is contained in a star. In fact, we prove that this is still true if we also evaluate the polynomials "at infinity", which is equivalent to studying the problem for homogeneous bivariate polynomials. The proof technique extends to a general framework for intersection problems of linear codes $C$. One has to investigate the geometry of the projective system $\mathcal{S}$ associated to $C$. If the hyperplanes that don't intersect $\mathcal{S}$ are well spread out with respect to the points not on $\mathcal{S}$, then one obtains stability results, showing that any intersecting family of reasonably large size is contained in a star.

26 pages + 3 pages appendix