This package has the code and data supporting Section 1.5 and Section 9 of:

• "Abelian varieties of prescribed order over finite fields" by Raymond van Bommel, Edgar Costa, Wanlin Li, Bjorn Poonen, Alexander Smith.

One may easily (re)generate the data for a desired q by calling section_9_check(q) from code/section9.py.

Method

We are using 3 methods that find a Weil polynomial of square-free ordinary abelian variety with m points:

1. Verbatim copy of Construction 9.5

2. 1. Do Construction 9.1

   2. Put g := f_A, and let S0 = {g, g^+, g^-} where g^+/- = g(x) +/- (qx^{n-1} - (q+1)x^n + x^{n+1}).

   3. Compute S := {h in S0 : h is Weil polynomial and square free}.

   4. If #{h^[n] % p : h in S} > 1, deform the middle coefficient of the polynomials in S, and keep the 2 best ones. Precisely, we call the function deform_middle_ordinary_squarefree (in deform.py) with following docstring:

      Let I_h = {h(1) + c: h(x) + c*x^(degree(h)/2) is a square free Weil polynonial}. Given a non-emtpy list S of q-symmetric polynomials such that h(1) = m for h in S, we return an interval [l, u] and two polynomials [h0, h1] < S such that:

      • h0, h1 are in S, square free Weil polynomials
      • [l, u] = I_h0 intersection I_h1
      • middle coefficient of h0 and h1 differ modulo p where h0 and h1 were picked such a way that minimizes l. If there is no such pair, we return None.
3. 1. Construction 9.1 1-3, to compute 1, c_1, ..., c_{n-2}.
   2. Compute S := {h: h is Weil polynomial, square free, degree(h) = 2*n, (h^[2n - i] = c_i for i = 1,.., n-2}.
   3. If #{h^[n] % p : h in S} > 1, deform the middle coefficient of the polynomials in S, and keep the 2 best ones, by calling deform_middle_ordinary_squarefree.

We try to cover the interval [start, end] with the intervals generated by these methods until all fail. Precisely, by applying them with the input (m,n), where m is the largest integer in [start, end] not yet covered, and with n = floor(log(m)/log(q)) + {1, 0}. This process ends up failing for small enough m, that we can take care of all the rest with abelian varieties of dimension <= 4.

Table comparing Proposition 9.3 and Corollary 9.4

q	ceil(3 sqrt(q) log(q) - 1/2)	n_0 such that equation in Proposition 9.3 holds for n >= n_0	First equation in Corollary 9.4 holds
3	6	24	32
4	8	19	25
5	11	18	24
7	15	19	26
8	18	19	26
9	20	21	28
11	24	22	30
13	28	25	34