% LaTEX source code
% Last modified April 24, 2001.
% Steve Miller

\documentclass[letterpaper,11pt]{article}
%\usepackage{pb-diagram}
\usepackage{epsfig}
\usepackage{amsmath}
\allowdisplaybreaks[1]
%\usepackage{graphics}
%\usepackage[psamsfonts][amssymb]
%\input{epsf.def}    %this works with Textures and Mac

% the percent sign comments out what follows
% the above are packages that are often useful to include graphics
% unfortunately, these are the ones to use with WinEDT (which is
% run from a windows environment. I've therefore commented this
% out here.

\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{exa}[thm]{Example}
\newtheorem{defi}[thm]{Definition}
\newtheorem{exe}{Problem}
\newtheorem{conj}{Conjecture}[section]

% here are some choices on how to define a structure for
% theorems, corollaries, lemmas, ....

    %=======================================================
    %   THIS IS WHERE YOU PUT SHORTCUT DEFINITIONS
    %========================================================

% if there is a symbol you use often, you can define a shortcut
% note: the configuration of xemacs is very nice: it replaces
% in your text what the simbol is. So, instead of seeing
% \alfpa (I've purposely mispelled it so it will NOT replace it)
% you see \alpha. Very convenient for reading what you type.

\newcommand{\lap}{\ensuremath{\triangle}} %short for "Laplacian"
\newcommand{\ga}{\alpha}  %now if you type \ga in math mode you
                          %get \ga
\newcommand{\js}[1]{ { \underline{#1} \choose p} } %(*/q), jacoby symbol
\newcommand{\hphi}{\hat{\phi}}  %phi^
\newcommand{\phiint}{\int_{-\infty}^{\infty} \phi(y) dy}
\newcommand{\foh}{\frac{1}{2}}  %onehalf
\newcommand{\jrsem}{\int_0^\infty x^{2t + 1}} %comment here  


    %=======================================================
    %   THIS IS USED TO LABEL THE EQUATIONS 1.1, 1.2, ..., 2.1
    %========================================================

\renewcommand{\theequation}{\thesection.\arabic{equation}}


\title{Numerical Investigations of The Sign Parity Conjecture for Elliptic Curves}

\author{Atul Pokharel \thanks{E-mail: \texttt{pokharel@math.princeton.edu}.  Many thanks to Prof. Andrew Wiles, Steven J. Miller, Harald A. Helfgott}}
\date{\today}
\begin{document}

\maketitle 
\centerline{Mathematics Department}
 \centerline{Princeton University}
 \centerline{Princeton, NJ 08544}

\begin{abstract}
It is conjectured that in a family of elliptic curves, in the limit, the sign of the functional equation of a curve in the family is equally likely to be +1 or -1.In these investigations, we explain the main theorems and conjectures leading up to this conjecture, henceforth called the Sign Parity Conjecture. 
Following this, we assume that the occurrence of sign are independent events and propose that it can thereby be modeled by a symmetric random walk, and give numerical evidence for two ``very special'' one parameter families of curves of rank 2: $y^2=x^3-t^2x+t^4$ and $y^2=x^3-t^2x+t^2$ \ \ Ultimately, we propose a method of checking whether or not the occurrence of signs are indeed independent events.
\end{abstract}

\newpage
\section{Introduction}
\setcounter{equation}{0}
    %=======================================================
    %   You need the setcounter command above to reset the
    %   equation counting in each section. without it, you'd
    %   have 1.1, 1.2, 1.3, 2.4, 2.5 -- with it (you put it
    %   after each new section) you have 1.1, 1.2, 1.3, 2.1,
    %========================================================
In this section, we review some of the basic concepts and terminology concerning Elliptic Curves in a nutshell before moving on to the L-Function. We follow the standard definitions and notation of %\cite{Knapp}%. As there are multiple representations of the same Elliptic Curve, some carrying more information than others, we introduce them at the outset.

\begin{defi}[Weierstrass Form]
A cubic over a field $\mathbf{k}$ in Weierstrass form is given projectively by 
\begin{equation}\label{weierstrass}
y^2w+a_1xyw+a_3yw^2=x^2+a_2x^2w+a_4xw^2+a_6w^3
\end{equation}
with coefficients in $\mathbf{k}$
\end{defi}
\begin{defi}[Elliptic Curve]
We define an Elliptic curve over a field $\mathbf{k}$ to be nonsingular cubic over $\mathbf{k}$ that is in Weierstrass Form.
\end{defi}

The behavior of the curve at (0,1,0) at infinity is well known (see Knapp .57), and so we can study much of the behavior of an elliptic curve by studying its affine form:

\begin{equation}\label{WeiNoInf}
  y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6
\end{equation}

Making the following standard change of variables, 
\begin{eqnarray}\label{WeiChangeB}
   b_2 & = & a_1^2+4a_2 \nonumber\\
   b_4 & = & 2a_4+a_1a_3 \nonumber\\
   b_6 &= & a_3^2+4a_6 \nonumber\\
   b_8 &= &a_1^2a_6+4a_2a_6-a_1a_3a_4+a_2a_3^2-a_4^2
\end{eqnarray}
and 
\begin{equation}\label{WeiChangeC}
  c_4=b_2^2-24b_4
  c_6=-b_2^3+36b_2b_4-216b_6
\end{equation}

If we assume that the character of the field $\mathbf{k}$, char($\mathbf{k}$)$\neq$2,
\begin{equation}\label{eqnSimpleWeierstrass1}
y^2=4x^3+b_2x^2+2b_4x+b_6
\end{equation}

If we assume that char($\mathbf{k}$)$\neq$2, and char($\mathbf{k}$)$\neq$3, 
\begin{equation}\label{eqnSimpleWeierstrass2}
y^2=x^3-27c_4x-54c_6
\end{equation}
\begin{defi}[Discriminant]
For any field $\mathbf{k}$, the discriminant $\mathbf{\lap}$ of the Elliptic Curve  is given by the formula
\begin{equation}\label{discriminant}
\lap=-b_2^2b_8-8b_4^3-27b_6^2+9b_2b_4b_6
\end{equation}
\end{defi}

\begin{defi}[j-invariant]
For an elliptic curve, we define the j-invariant as
\begin{equation}\label{jInvariant}
j=c_4^3/ \lap
\end{equation}
\end{defi}
The j-invairant is well defined since \lap$\neq$0 if the cubic is non singular.[Knapp, Theorem 3.2]. The j-invariant has weight 0, therefore is invariant under all admissible changes of variables. See knapp[p.63] for a definition of admissible change of variables.

\begin{defi}[Minimal Weierstrass Equation]
An equation of the form\ref{WeiNoInf} is minimal for a prime p if the power of p dividing \lap cannot be decreased by making an admissible change of variables over $\mathbf{Q}$ with the property that the new coefficients are p-integral.
\end{defi}

Equation 1.2 is called a global minimal Weierstrass equation if it is minimal for all primes and if the coefficients are integers.


\begin{thm} [Due to Neron]\label{neron}
For every elliptic curve \boldmath$E$ over $\mathbf{Q}$ there exists an admissible change of variables over $\mathbf{Q}$ such that the resulting equation is a global minimal Weierstrass equation. 
\end{thm}
Proof: see Knapp[1] p.292

In light of this theorem, henceforth, when we refer to an Elliptic Curve, $\mathbf{E}$ over $\mathbf{Q}$ we will assume it is given by the global minimal Weierstrass equation
\begin{equation}\label{globalMinWeierstrass}
y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6
\end{equation}
with discriminant \lap, without any loss of generality.

Next, we mention a rather important theorem by Mordell
\begin{thm}[Mordell's Theorem]\label{Mordell}
If $\mathbf{E}$ is an elliptic curve over $\mathbf{Q}$, then the abelian group $\mathbf{E(Q)}$ is finitely generated.
\end{thm}
Proof: see Knapp, IV

In the context of Mordell's theorem, we will define three more terms, which will be used freely later on.
\begin{defi}[Naive height] 
for P=(x,y) in $\mathbf{E(Q)}$ write $x=\frac{p}{q}$ with GCD(p,q)=1. We define the Naive height of the point P by

\begin{equation}\label{naiveHeighteqn}
h_0(P)=log max(|p|,|q|)\geq 0
\end{equation}
by convention we define $h_0(\infty)$=0
\end{defi}

\begin{defi}[Canonical Height]

  There exists a unique function h:$\mathbf{E(Q)}\to \mathbf{R}$ satisfying
(i) h(P)-$h_0$(P) is bounded
(ii) h(2P)=4h(P)
The function is given by 
\begin{equation}\label{canonicalHeight}
h(P)=\lim_{n \to \infty}\frac{h_0(2^nP)}{4^n}
\end{equation}
This has h(P)$\geq$ 0 with equallity iff P has finite order.
This function is called the canonical height.
\end{defi}
Using Mordells Theorem, we can now define a geometric rank. From Mordell's Theorem,
\begin{equation}\label{mordellEqn}
E(Q)\cong\mathbf{Z}^r\oplus F
\end{equation}
The group F is a finite abelian group, uniquely defined as the torsion subgroup.
The integer, $r$ is the geometric rank of $\mathbf{E(Q)}$
The analytic rank is the order of vanishing of the L-function (defined below) at s=1.
\section{The $L$-Function}
Let $\mathbf{E}$ be an elliptic curve over $\mathbf{Q}$. For each prime p, we consider the reduction $\mathbf{E_p}$ of $\mathbf{E}$ modulo p. $\mathbf{E_p}$ is defined over $\mathbf{Z/pZ}$ and singular iff $p|\lap$.

We now define
\begin{equation}\label{ap}
a_p=p+1-N_p
\end{equation}
where
\begin{equation}\label{Np}
N_p=\sharp E_p(Z/pZ) 
\end{equation}
$\mathbf{N_p}$ is the number of projective solutions of $\mathbf{E_p}$ in $\mathbf{Z_p}$ (i.e. including the solution at infinity)
\begin{defi}[Local L-Factor]
We define the local L factor for the prime p by

\begin{equation}\label{Llocal}
L_p(u)=\Bigg\{ {
\frac{1}{(1-a_pu+pu^2)} \ \ \ \ \ \ \mbox{if p does not divide}\ \ \lap \atop
\ \ \ \frac{1}{1-a_pu} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mbox{if} \ p|\lap \ \ \ \ \ \ \
\ \ \ \ \ }
\end{equation}
\end{defi}

The $L$-function of $E$ is the product of the local L-factors with $u$ replaced in the $p^{th}$ factor by $p^{-s}$and defined to be
\begin{equation}\label{lGlobal}
L(E,s)= \prod_{p|\lap}(1-a_pp^{-s})^{-1}\prod_{p \dagger  \lap}(1-a_pp^{-s}+p^{1-2s})^{-1}
\end{equation}
We will just make a note here that the L-function comes from a more naturally defined zeta function, or a variant of such a function. Refer to Knapp for details.
\begin{thm}[Hasse]\label{Hasse}
Let $\mathbf{E}$ be an elliptic curve over $\mathbf{Q}$ with integer coefficients. For each prime $p \dagger \lap$, let $\mathbf{E_p}$ be the reduction modulo $p$. Then
\begin{equation}
  |a_p|<2\sqrt{p}
\end{equation}
\end{thm}

\begin{cor}
  The Euler product defining $\mathbf{L(s,E)}$ converges for $Re(s)>\frac{3}{2} $ and is given there by an absolutely convergent Dirichlet series.
\end{cor}
\begin{thm}[Modularity Theorem]
Every elliptic curve over $Q$ is modular.
\end{thm}
Conjectured by Taniyama,Shimura,Weil.
I am still in search of a sketch of the proof.

Using this, we can prove the following theorem:
\begin{thm}
$L(E,s)$ has a meromorphic continuation to all of $C$ and satisfies the following functional equation:
\begin{equation}\label{continuation}
N^{\frac{2-s}{2}}(2\pi)^{s-2}\Gamma(2-s)L(E,2-s)=W(E)N^{\frac{3}{2}}(2\pi)^{-s}\Gamma(s)L(E,s)
\end{equation}
Where W(E) is called the root number of E and 
W(E)=+1 or -1. 
\end{thm}
Proof: See Knapp[1] p.386 \\
We will rewrite this as
\begin{equation}\label{simpleFunctional}
\Lambda(s)=\epsilon_E\Lambda(2-s)
\end{equation}
Where $\epsilon_E=\pm1$
Henceforth, when we refer to the functional equation, we will mean this one.
Since W(E) determines the sign, we will proceed by looking further at how it is determined. 

It is aa classical result that the root number can be expressed as a product at p finite and p=$\infty$:
\begin{equation}
\mathbf{W}(\mathbf{E})=\prod_pW_p(\mathbf{E})
\end{equation}

Where
\begin{enumerate}\label{conditionsW}
\item  $W_{\infty}(E)=-1$
\item  $W_p(E)=1$ if the reduction $E$ mod $p$ is good
\item $W_p(E)=-1$ if it is split multiplicative
\item $W_p(E)=1$ if it is non-split multiplicative
\item $W_p(E)=\frac{-1}{p}$ if it is potentially split multiplicative and p=2
\item $W_p(E)\cong \frac{c_6(E)}{2^\nu_2(c_6(E))}$ mod $4$ if it is potentially multiplicative and p=2 [Connell]
\item $W_p(E)=$ $\frac{-1}{p}$ \ \ \ \  \mbox{for gcd} $(\nu_p(\lap(E)),12)=$ 2 or 6 \\
 $W_p(E)=$ $\frac{-2}{p}$ \mbox{for gcd} $(\nu_p(\lap(E)),12) =$ 3 if it is potentially good and $p>3$ \\
 $W_p(E)=$$\frac{-3}{p}$ {for gcd}$(\nu_p(\lap(E)),12)=$4 [Rohlrich]
\item $W_p(E)$ given by the tables 1 and 2 of [9] if the reduction is potentially good and p= 2 or 3 [Halberstadt]
\end{enumerate}
 1-5 of the above results are classical. 

Here, $\lap(E)$ is the discriminant of the minimal Weierstrass equation of E and $(c_4(E),c_6(E))$ are the corresponding parameters \\

 Looking at the reductions of $\mathbf{E}$ mod p is the same as considering the curve $\mathbf{E_p}$ over $\mathbf{Z_p}$ with the $\mathbf{Z}$ coefficients taken modulo p. 

We can classify reductions of $\mathbf{E}$ modulo p as follows:
\begin{enumerate}
\item good if $p\dagger  \lap$ \\
A reduction that is good then the reduction $\mathbf{E}$ mod p gives an Elliptic curve over $\mathbf{Z}$/$p$.
\item split multiplicative if $p|\lap, p \dagger c_4$ and $\frac{-c_6}{p} =1$\\
A reduction that is split multiplicative has a node and the slopes at the node lie in $\mathbf{Z}$/$p$.
\item non-split multiplicative if $p|\lap$, $p \dagger c_4$ and $\frac{-c_6}{p}=-1$.\\
Such a reduction has a node, but the slopes at the node do not lie in $\mathbf{Z}$/$p$.
\item potentially multiplicative $\nu_p(c_4)=2, \nu_p(c_6)=3$ and $\nu_p(lap) >6$
\\ This reduction has a cusp, but becomes multiplicative in some extension of $\mathbf{Z}$/$p$.
\item potentially good otherwise \\
This reduction has a cusp, but becomes good in some extension of $\mathbf{Z}$/$p$.
\end{enumerate}
The function $\nu_p(a)$ returns the number of times the prime p divides a.
\begin{conj}[Sign-Parity Conjecture]\label{signParity}
In a family of elliptic curves, in the limit, the sign of the functional equation of a curve in the family is equally likely to be +1 or -1. 
\end{conj}
\section{Why Parity is Interesting}
First we must recall a conjecture by Birch,Swinnerton and Dyer
\begin{conj}[Birch Swinnerton and Dyer, (BSD)]
The BSD conjecture can also be stated as
\begin{equation}\label{strongBSD}
\mbox{Algebraic Rank of E = order of vanishing of L(E,s) at s=1}
\end{equation}
\end{conj}
The BSD conjecture also suggests the following
\begin{prop}
 $\mathbf{L(1)}$ = 0 iff $\mathbf{E(Q)}$ is infinite
\end{prop}


\begin{prop}
  (i)W(E)=1 if the order of vanishing of L(E,s) is even
  (ii)W(E)=-1 if the order of vanishing of L(E,s) is odd
\end{prop}

Therefore, we have that if BSD is true, then
\begin{equation}
  \mbox{root number} = \mbox{parity of the algebraic rank}
\end{equation}
Let us restate this
\begin{prop}
If the root number of an elliptic curve is -1 then the rank is positive.Morevoer, if the root number is +1, and we know that the algebraic rank is not 0, then the rank is ``High'' i.e. at least 2.
\end{prop}


\section{The Theory Underlying the Experiments}
In order to get numerical evidence for the sign parity conjecture for the purposes of this paper, we consider a one parameter family of elliptic curves of the form
\begin{equation} \label{oneparameter}
y^2=x^3+A(t)x+B(t)
\end{equation}
For every value of t, we get an elliptic curve in the family.
The discriminant in this case is $-4A^3-27B^2$, and zero if the curve is singular, non zero otherwise.

\begin{conj}[Independence of Sign]
 Given an elliptic curve, the sign of its functional equation is independent of the other curves in the family. More precisely, the occurrence of +1 and -1  within  a family are independent events.
\end{conj}
 Instead of providing a proof, we give numerical data that suggests this may be true.
%. 
% On first thought, this doesnt seem to be true, since knowing the sign of one curve tells you about the sign of the next (something to do with divisibility of primes) one. However, we saw that having made this assumption, the behavior of the sign resembles random coin flips. 
We address the question of independence further in section \ref{yettobedone}

\begin{defi}[Slightly Modified Random Walk]
Consider the classic example of a drunk man, staggering about in unit steps. He is restricted to two possible unique motions (usually one step forward or one step backward). Further, his movement is determined by his flipping an unbiased coin. If it turns up heads he goes in one direction, tails, the other. 
\end{defi}
We can then ask how likely is it that he will be some desired distance away from where he started. 

Let us make estimates of what is to be expected.
We define the probability function as usual.
\\ Let us suppose that for every heads,he moves 2 units forward and every tail does nothing. The probability of the coin being heads $P(h)=p$, of tails $P(t)=t$. p=q=$\frac{1}{2}$. Therefore p+q=1.\\
Suppose we flip the coin N times, the maximum distance that the man can possibly be from the starting position is then M=2N.
In a normal random walk, we usually take heads to be +1 and tails to be -1, however, to make calculations simpler, we add the constant 1 to both steps and make heads +2 and talks 0.
\\
Let us suppose we have H heads, and N-H tails. The total distance the man has travelled, d =2H, is independent of the order in which the heads and tails arrive.

Now since the trials are independent, 
\begin{equation}
\mbox{the probability of getting H heads} =\frac{{{N}\choose{H}}}{2^N}
\end{equation}

\begin{prop}\label{meanprop}
The mean distance,d, after N flips is therefore 
\begin{equation}
 \sum^N_{n=0}\frac{2n{{N}\choose{n}}}{2^N} = N
\end{equation}
\end{prop}
Proof:
\begin{equation}\label{e1}
(p+q)^N=\sum_{n=0}^N{N\choose n}p^nq^{N-n}
\end{equation}
\begin{eqnarray}
\mbox{Taking the derivative wrt} p, \mbox{we have,} & &\nonumber\\
(p+q)^{N-1}&=&\sum_{n=0}^N {N \choose n}np^{n-1}q^{N-n}\nonumber \\
 N &=&\sum_{n=0}^N {N \choose n}np^{n-1}q^{N-n}\nonumber  \\
\mbox{Multiplying by} p, & ~ & \nonumber \\
Np &=&\sum_{n=0}^N {N \choose n}np^nq^{N-n} \nonumber \\
\mbox{Since p=q=}\frac{1}{2} & ~ &\nonumber \\
\frac{N}{2}&=&\sum_{n=0}^N \frac{n{N \choose n}}{2^N}\nonumber \\
N&=&\sum_{n=0}^N \frac{2n{N \choose n}}{2^N} \label{e2} \\ 
\mbox{Since n is equivalent to the number of heads, it is proved.}\nonumber
\end{eqnarray}


\begin{prop}\label{stddevprop}
For N flips the standard deviation for the total distance,d, from the starting position, is $\sqrt{N}$
\end{prop}
Proof: Taking the second derivative wrt p of \ref{e1}
\begin{eqnarray}
N(N-1)(p+q)^{N-2} & = & \sum_{n=0}^N {N \choose n}n(n-1)p^{n-2}q^{N-n}\nonumber \\
\mbox{Multiplying by } p^2, & & \nonumber \\
N(N-1)p^2&=&\sum_{n=0}^N{N \choose n}n(n-1)p^n\nonumber \\
&=&\sum_{n=0}^N \frac{{N \choose n}n(n-1)}{2^N}\nonumber \\
&=&\sum_{n=0}^N \frac{{N \choose n}n^2}{2^N}-\sum_{n=0}^N \frac{{N \choose n}n}{2^N}
\nonumber \\
\mbox{from \ref{e2}} & & \nonumber \\
&=&\sum_{n=0}^N \frac{{N \choose n}n^2}{2^N}-\frac{N}{2}\nonumber \\
\mbox{We now have} & & \nonumber \\
\frac{N^2}{4}-\frac{N}{4}+\frac{N}{2} &=&\sum_{n=0}^N \frac{{N \choose n}n^2}{2^N}\nonumber \\
\frac{N^2}{4}+\frac{N}{4} &=&\sum_{n=0}^N \frac{{N \choose n}n^2}{2^N} \label{e3}
\end{eqnarray}
Again, since n is equivalent to the number of heads, we can further say  the Expected value of the distance squared is given by
\begin{eqnarray}
E(d^2)&=&\sum_{n=0}^N(2n)^2\frac{{N \choose n}}{2^N}\nonumber \\
&=& 4\sum_{n=0}^Nn^2\frac{{N \choose n}}{2^N}\nonumber \\
\mbox{from \ref{e3}} & & \nonumber \\
&=&N^2+N.
\end{eqnarray}
Hence the variance of the total distance satisfies
\begin{eqnarray}
\sigma ^2 = E(d^2)-E(d)^2 = N^2 + N - N^2 = N\label{eqvar} \\
\end{eqnarray}
Therefore, the standard deviation in distance after N flips is
\begin{eqnarray}
\sigma =\sqrt{N}\label{eqstddev}
\end{eqnarray}

 For every t, we get a value of the sign of the functional equation. Let S be this ordered set containing the signs of the functional equations of the elliptic curves in the one parameter family \ref{oneparameter} with $0<t\leq N$. 

Simply plotting the sign changes gives us no more information than that the changes occur. Therefore, we began by grouping the data into blocks of size m.

\begin{defi}[Block]
Given a block size $m$, we define the $i^{th}$  block as the ordered set $B_i$ of the $m(i-1)^{th}$ through $mi^{th}$ element of S.
\end{defi}

\begin{defi}[Block Value]
The Block Value, $n_i$ for the $i^{th}$ block, $B_i$, of block size m,  is defined as
\begin{equation}
n_i=\sum _{k=1}^m \epsilon_k
\end{equation}
Where $\epsilon_k$ is the $k^{th}$ element of $B_i$.
\end{defi}

If the signs are independently chosen from +1 and -1,then from \ref{stddevprop}, we expect each $n_i\approx \sqrt{m}$

Given the maximum and minumum block numbers, we place the blocks into bins of a histogram centered at 0. We therefore look at the number of blocks that have a sum within a given range. 
Since we have assumecd that each occurrence of sign is independent of the others, each block can therefore be assumed to be an independent random walk of $m$ coin flips. Therefore, the histogram can be interpreted as showing the distribution of distances that occurred after $N/m$ random walks.
We expect this probability distribution to be essentially gaussian.

\begin{defi}[Bin]
A bin is defined as an interval (a,b] on the real line.
\end{defi}

\begin{defi}[Bin Size]
Suppose we are given a set of Block Values,V, and a desired number of bins n, 
we can find r and s and create a histogram with n bins of size $B=\frac{(r-s)}{n}$ each,  with the middle interval centered at 0. 

Here, r and s are such that such that maximum block value in V$\leq r$ and minimum block value in V$\geq s$
 Therefore, starting at 0, and moving left, we reach another bin after $\frac{B}{2}$. We call B the Bin Size. 
\end{defi}

Let us suppose that now we consider the ``unit'' of the histogram baseline to be $\frac{B}{2}$ where B is the bin size.
We can now rewrite the intervals of each bin in terms of this new unit. We will have the central bin be the interval ($-1_B,+1_B$] (since it is centered at 0) and the $n^{th}$ bin to the right be  ($n_B$ to $n_B+2_B$], where the subscript B denotes that the numbers have been rescaled.

From this definition, we can determine which bin a given value falls into by rescaling the value as follows
\begin{equation}\label{rescale}
a_B=\frac{a}{(\frac{\mbox{B}}{2})}
\end{equation}
and determining which rescaled interval it falls into. That will be its bin. Here B is again the Bin Size.
\begin{prop}
If the standard deviation of m flips is $\sigma_N$ and the bin size is 2b, the distribution of n block values is a renormalized gaussian distribution 
\begin{equation}
P(x)=2bn\frac{1}{2\pi\sigma^2}e^\frac{{-x^2}}{2\sigma^2}
\end{equation}
with mean 0 and standard deviation $\sigma = \frac{\sigma_m}{b}$
\end{prop}
Proof: If we imagine that all the blocks, of size m,  are in a single bin, we see that the total area under our histogram is $2bn$ where $b=\frac{B}{2}$,  B is the bin size and n is the total number of blocks we have. \\
If our histogram represents a random walk, the area under this should be equal to a renormalized Gaussian distribution. Therefore, since the area under a normal Gaussian distribution is 1, we must multiply this by $2bn$ to reacale it to fit our histogram. Also, since the standard deviation must also be rescaled accrding to \ref{rescale}, we have that the standard deviation of our histogram should be  $\sigma = \frac{\sigma_m}{b}$ where $\sigma_m$ is the standard deviation for m coin flips.


\section{Experimental Results}
The two curves that we looked at were \\
\begin{equation} \label{curve1}
y^2=x^3-t^2x+t^4 
\end{equation}
and 
\begin{equation} \label{curve2}
y^2=x^3-t^2x+t^2
\end{equation}

for curve \ref{curve1} we let t go from 0 to $3$x$10^7$, hence N=$3$x$10^7$, \\
and for curve \ref{curve2} we let t go from 0 to $1$x$10^7$, hence N=$1$x$10^7$\\
In order to see something meaningful in the data, we needed then to choose reasonable values for the blocksize, m, and the number of bins, n. Let N be the total number of curves. The only two constraints on these were as follows\\
-the blocksize,m must be of the order of $\sqrt{N}$, the standard deviation.\\
-the number of bins,n, must be such that the binsize is much less than $\sqrt{m}$ which is the standard deviation for m trials.

We decided to let m=1000, which is of the order of the standard deviation for both experiments, and the number of bins, n to be 16, which is $<< \sqrt{1000}$.
These two parameters were kept constant throughout the experiments.


If the graphs do not appear below, please refer to the following pages for the data. 
\begin{center}

\epsfig{file=final_1000_18.eps,height=5in,width=6in}


\end{center}
We also see in the first graph, \ref{curve1} there is an excess positive sign of 3056. The expected deviation is $\sqrt{3x10^7}$ = 5477. Therefore it is within expectation.

\begin{center}

\epsfig{file=final_1000_16.eps,height=5in,width=6in}


\end{center}

And in the second graph, there is excess negative sign of -1322  .The expected Deviation is 3162, and therefore, it is again within expectation.


As far as eyballing goes, the graphs suggest that the data fits the expected values very well. Although finer discrepancy meaures are certainly in order.
The graphs seem to support our assumptions well.

\section{Conclusions}
 We saw that comparing the occurrence of sign to a symmetric random walk, the expected results fit nicely with what was observed- that the distribution is essentially gaussian. In light of the central limit theorem we may propose that it is not a random walk but a different distribution of finite variance, although this would also have to be checked by other means. \\
The main difficulties in programming came from tweaking the code to run fast enough to do a reasonable number of curves in a reasonable amount of time. Most of the difficulty came in understanding the theory enough to set up the data so that we could observe something meaningful instead of many sign changes.
 Although I would have liked to have done much finer measures of the discrepancy, my background in this was insufficient to do it in the available amount of time and therefore has been left out of this paper.

\section{Yet To be Done}\label{yettobedone}
 An interesting question that was raised while doing these experiments was whether or not the occurrence of sign are actually independent events. Although we assumed in this paper that they were, the next step is to check this claim. Steven and myself will investigate this in the coming weeks. A rough sketch of the method we propose is very simple and as follows: 

From now on, let us denote -1 by 0 (this simplifies the explanation and computation considerably)

Once this change is made, the data we have from the curves is a long string of bits. We will look for occurrences of all possible patterns of n bits in this data. From this, we get an observed probability of occurrence for each pattern. We can theoretically predict the probability of occurrence of the pattern, assuming random occurrence. Then we will define a tolerable discrepancy, and look for those patterns that occur more than an expected number of times, within error, if any. We propose that this is a reasonable measure of independence.

For example, suppose we had 50 curves, and we decided on looking for patterns 5 bits wide. More precisely, we want to look at the relative frequencies of 00000, 00001,00010,\ldots,11111 within the 50 bits. If the occurrences are independent,then all 32 patterns are equally likely. There are two ways to look for patterns: either we can allow overlapping patterns, or not. For instance, if the pattern we were looking for was 11111, then there is a possibility that if the next bit is 1, we get another occurrence. so 6 bits give us two occurrences. However if we are looking for a pattern 10011 then there is no way that this pattern can recur in less than 11 bits. So we will also have to consider these edge effects. Therefore, depending on which way we search for patterns we can get different expected frequencies.

The difficulties should mainly be computational ones: for instance, I feel the main question will be defining a pattern width that allows us to see recurrences, yet keeps the computation tractable. 

\section{Code, Optimizations, Suggestions}

In this section, I will explain the optimizations made to my code so that I could reach the number of curves that I reached, on the limited resources of the math dept. computers.

The first was the code itself. There are a few things that helped
\begin{enumerate}
\item{In PARI, the results are stored on an internal stack. Moreover, you have control over the stack pointer. Therefore, I linearized my code so that i didnt need to call the PARI garbage collection routines, but could simply reset the stack pointer to point to before the garbage, once we finished with calculations. This helped once the number of curves became large. Here is example code:\\
\texttt{
\indent      long lTop;\\
//Save the bottom of stack before computations \\
      lTop=avma; \\
        /* this is similar to what we have before, marking\\
           the start of what we'll call the garbage. */\\
\\
      gaffsg(0,(GEN) F[1]);        /* reassigns values of F */\\
      gaffsg(0,(GEN) F[2]);\\
      gaffsg(0,(GEN) F[3]);\\
      gaffsg(-27*(48*t-25),(GEN) F[4]);\\
      gaffsg(-54*(360*t-125),(GEN) F[5]);\\
\\
      E = initell(F,MEDDEFAULTPREC);  /* again, initializing E */\\
\\
  /* THE ABOVE IS WHERE WE CHOOSE WHAT CURVE WE'LL BE WORKING WITH. $y^2 = x^3 + A(t)x + B(t)$ */\\
\\
      sign = ellrootno(E,y);\\
      signSum+=sign;\\
      tsignSum+=sign;\\ \\
      /*restore the stack pointer to what it was before garbage.\\
        This works becuse signSum,tSignsum and sign were allocated before\\
        we started the calculations. So they dont lose their values.\\
        NOTE that E is no longer initialized after this point=>can't use\\
        it again without calling initell again.\\
      */\\
      avma=lTop;\\
\\
        /* note here he just sets avma = lTop, and doesn't\\
           use gerepile */\\
}

There is a good exposition of this in the PARI users guide.\\
http://modular.fas.harvard.edu/docs/
}
\item{We are given resource quotas (both CPU usage and memory) on math.princeton.edu. However, the amount of memory available to us allows us to make a potential optimzation by writing things to memory first, then dumping it to disk. I tried to cut down on the number of cpu intensive processes as far as possible. This ultimately meant that I stored my results to memory before dumping them in multiple very large chunks to disk. First declare a large(of the order of MB) array and use malloc to get memory for it. Then write all results to this. Then at the end of the calculations, use the write() system call to specify how much of this array to write at once. This is taken from the man page for write\\
\\
NAME\\
       write - write to a file descriptor\\
\\
SYNOPSIS\\
       \#include $<$unistd.h$>$\\
\\
       ssize\_t write(int fd, const void *buf, size\_t count);\\
\\
DESCRIPTION\\
       write  writes  up to count bytes to the file referenced by\\
       the file descriptor fd from the buffer  starting  at  buf.\\
       POSIX  requires that a read() which can be proved to occur\\
       after a write() has returned returns the new  data.   Note\\
       that not all file systems are POSIX conforming.\\


Here, fd would be the file, buf would be your array and count the number of bytes to write. You can invert this advice and use it for read()-ing  as well.
}
\item{A very simple optimization is to use int in place of long as far as possible, especially in loops. I found it easy to get mixed up and use long for counters, because I had declared them to be compatible with PARI data types. This just takes up space unnecessarily, and takes time when performing operations.}
\end{enumerate}

There was a major hardware optimization that I was lucky to find. Instead of using math.princeton.edu, I discovered two other machines testamd1.princeton.edu and testamd2.princeton.edu that were powerful(1GB RAM, two parallelized Athlon processors at $>$600Mhz), furthermore, they were relatively unused at the time of writing this. Using these machines is different from math.princeton.edu only in that you must ssh in first to math.princeton.edu, and from there ssh in to testamd1 or testamd2. For instance \\
from home computer somehow login to math.princeton.edu (use vnc, ssh or something)\\
then from math.princeton.edu: \\
ssh testamd1\\
and login as usual.\\

After that it is all the same. This really helped the speed of calculations considerably. Unfortunately, these may or may not exist in this state when you try to run your calculations as these are supposedly ``experimental'' machines.

\section{Acknowledgements}
 I just want to acknowledge those who helped with the paper. Mainly, Professor Wiles, Steve Miller, and Harald Helfgott as the stuff in this paper is mostly their work.


All the code, data and this paper can be found at \\
\texttt{http://www.math.princeton.edu/~pokharel/js}

This paper can be found at \\
\texttt{http://math.princeton.edu/~pokharel/js/paper}\\ in a plethora of formats.
\section{Bibliography}
\bibliographystyle{plain}
\bibliography{partiy}
\end{document}
