Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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 or wolframalpha perhaps? – Bonanza Apr 27 '12 at 19:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.