# Representation of a subset of a finite affine space as a variety

It is simple to see that every subset of a an affine space over a finite field is a variety - for example, it follows from the fact that finite subsets are closed in the Zariski Topology of every affine space.

My question is rather algorithmic - given a subset $S \subseteq \mathbb{F}_{q}^n$ for some prime power $q$ and positive $n$, how do I express it as the locus of some polynomial equations, as compactly as possible? By compactly I mean: minimizing the sum of degrees of the polynomials. I don't necessarily want an algorithm - lower\upper bounds will also be cool.

This is a useful question - for example, it has applications in algebraic combinatorics: when invoking the Chevalley-Warning theorem, one wants to write down polynomial equations with low degree in order to satisfy the theorem's conditions.

-

## 1 Answer

You are basically asking for the generators of the ideal defining $S$. I'm assuming $S \subset \mathbb{A}^n$ is finite here. Let $A=(a_{ij})_{1\le i\le n, 1\le j\le m}$ be the matrix whose column vectors are the points in $S$. The ideal of one point $(a_{1i},\ldots,a_{ni})$ is given by $(x_1-a_{1i},\ldots,x_n-a_{ni})$. Thus the ideal of $S$ is given by the intersection of these ideals, that is $$I=\bigcap_{i=1}^m(x_1-a_{1i},\ldots,x_n-a_{ni})$$Calculating the intersection of these ideals can be done using Grobner basis techniques or Macaulay2. The result is a set of generators for $I$ of minimal degree, which is what you want.

-
Thanks - that's really cool! And an opportunity to study Grobner basis. Do you know of any free windows software that does those kind of computations? (Macaulay2 is supported only by using cygwin). –  Ofir Apr 27 '12 at 16:42
Sagemath.org or wolframalpha perhaps? –  Bonanza Apr 27 '12 at 19:14