MathOverflow is a question and answer site for professional mathematicians. 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

I am not sure if this is a valid question but posting any way:

Say I am over $\mathbb{F}_{p}$ for a prime $p$.

I have a curve of form $x^{2} = f(y)$ where $f(y)$ has an unknown form (and hence degree). How many points do I need to know on the curve to estimate the genus of the curve?

$A.)$We also have the additional constraint that $f(y)$ has atmost $2k$ non-zero coeffients where $k$ is a constant. Assume that a bound to the degree is known.

$B.)$Assume $2k << y$-degree of the equation.

$C.)$Assume the coeffients of the highest half of the terms are $+1$ and the lowest half of terms are $-1$. (Just an artificial example - but this tells that one possibly may be able to get the genus without getting the coefficients. For a concrete realization of the artificial example, look at error correction codes over $3$ alphabets $\{ \pm1, 0 \}$. The errors can be in only $2k$ coordinates and I also know the errors in the top half will be $+1$ and the lower half will have errors with $-1$).

How many points do you need? If degree bound is $D$, then would $O(\log^{h(k)}{D})$ points suffice where $h(k)$ is independent of $D$ and of the curve and is fixed for a fixed $k$?

share|cite|improve this question
Have you tried finding the coefficients? I would take a bound $d$ for the unknown degree and get $d+C$ points. This gives overdetermined linear system in the coefficients. If you have guessed the degree, solving the system will find the coefficients. If the bound is too low maybe try higher value. – joro Sep 10 '11 at 13:28
I think one does not need to know the coeffients. Say even if I say all the $k$ coefficients are $1$. – user16007 Sep 10 '11 at 23:13
I will be very interested to learn how to find the genus without knowing the exact coefficients. Btw, I doubt you can find the coefficients with your sparse restriction with less than the $O(D)$ points unless you know exactly which degrees are nonzero. – joro Sep 11 '11 at 5:21
@joro: I am assuming the coefficients to be either $\pm1$. I do not know the exact coefficients. It is like error correction coding scenario where the errors have atmost $k$ non-zero coordinates. In my case the errors can be of two alphabets $\pm1$ with $0$ being the third alphabet. – user16007 Sep 11 '11 at 6:44

No finite set will do. If $f(y)$ is one such polynomial and $cy^m$ is a monomial occurring in it, then change this monomial to $cy^{m+q-1}$ for some power $q$ of $p$ such that your finite set is a subset of the field of $q$ elements. The two curves will go through the same finite set of points but will have different genera if $q$ is sufficiently large.

However, now the OP has decided to change the question.

share|cite|improve this answer
What if a bound to the degree is known? then finite number of points should help you reconstruct the curve and hence the genus? – user16007 Sep 10 '11 at 14:11
I was wondering if there is a way to make use of the information $k$. – user16007 Sep 10 '11 at 14:23
If a bound on the degree is known, then yes, as joro as already remarked. – Felipe Voloch Sep 10 '11 at 14:37
The question is how many would points would you need? what if k << degree bound or even actual degree? – user16007 Sep 10 '11 at 22:47
I mean that was what I was meaning to ask? – user16007 Sep 10 '11 at 22:54

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.