-1
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – joro
    Sep 10, 2011 at 13:28
  • $\begingroup$ I think one does not need to know the coeffients. Say even if I say all the $k$ coefficients are $1$. $\endgroup$
    – user16007
    Sep 10, 2011 at 23:13
  • $\begingroup$ 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. $\endgroup$
    – joro
    Sep 11, 2011 at 5:21
  • $\begingroup$ @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. $\endgroup$
    – user16007
    Sep 11, 2011 at 6:44

1 Answer 1

5
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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