Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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
    
Sagemath.org or wolframalpha perhaps? –  Bonanza Apr 27 '12 at 19:14
add comment

Your Answer

 
discard

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.