# Genus of algebraic curves with unknown degree

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$?

-
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.
I was wondering if there is a way to make use of the information $k$. –  user16007 Sep 10 '11 at 14:23