In my last post, I mentioned I would post my article proper on WordPress. Someone then told me about latex2wp, a python script that will translate a tex file into something postable on WordPress. So I did it, and it works pretty well! Other than changing references (removing them) and a few stylistic things here and there, and any \begin{align} type environments, it works perfectly.

So here it is:


In this, I present a method of quickly counting the number of lattice points below a quadratic of the form {y = \frac{a}{q}x^2}. In particular, I show that knowing the number of lattice points in the interval {[0,q-1]}, then we have a closed form for the number of lattice points in any interval {[hq, (h+1)q - 1]}. This method was inspired by the collaborative Polymath4 Finding Primes Project, and in particular the guidance of Dr. Croot from Georgia Tech.

1. Intro

Suppose we have the quadratic {f(x) = \frac{p}{q}x^2}. In short, we seperate the lattice points into regions and find a relationship between the number of lattice points in one region with the number of lattice points in other regions. Unfortunately, the width of each region is {q}, so that this does not always guarantee much time-savings.

This came up while considering

\displaystyle \sum_{d \leq x \leq m} \left\lfloor \frac{N}{x} \right\rfloor \ \ \ \ \ (1)


In particular, suppose we write {x = d + n}, so that we have {\left\lfloor \dfrac{N}{d + n} \right\rfloor}. Then, expanding {\dfrac{N}{d+n}} like {\dfrac{1}{x}}, we see that

\displaystyle \frac{N}{d+n} = \frac{N}{d} - \frac{N}{d^2} (n - d) + O\left(\frac{N}{d^3} \cdot (n-d)^2 \right) \ \ \ \ \ (2)


And correspondingly, we have that

\displaystyle \sum \left\lfloor \frac{N}{d+n} \right\rfloor = \sum \left\lfloor \frac{N}{d} - \frac{N}{d^2} (n - d) + O\left(\frac{N}{d^3} \cdot (n-d)^2 \right) \right\rfloor \ \ \ \ \ (3)


Now, I make a great, largely unfounded leap. This is almost like a quadratic, so what if it were? And then, what if that quadratic were tremendously simple, with no constant nor linear term, and with the only remaining term having a rational coefficient? Then what could we do?

2. The Method

We want to find the number of lattice points under the quadratic {y = \frac{a}{q}x^2} in some interval. First, note that

\displaystyle \left\lfloor \frac{a}{q} (x+q)^2 \right\rfloor = \left\lfloor \frac{a}{q} (x^2 + 2xq + q^2) \right\rfloor = \left\lfloor \frac{a}{q}x^2 \right\rfloor + 2ax + aq \ \ \ \ \ (4)


Then we can sum over an interval of length q, and we’ll get a relationship with the next interval of length q. In particular, this means that

\displaystyle \sum_{x=0}^{q-1} \left\lfloor\frac{a}{q}x^2\right\rfloor = \sum_{x=q}^{2q-1} \left\lfloor \frac{a}{q}x^2 \right\rfloor - \sum_{x=0}^{q-1} (2ax + aq) \ \ \ \ \ (5)


Now I adopt the notation {S_{a,b} := \sum_{x = a}^b \left\lfloor \frac{a}{q}x^2 \right\rfloor}, so that we can rewrite equation 5 as

\displaystyle S_{0,q-1} = S_{q, 2q-1} - \sum_0^{q-1} (2ax + aq)

Of course, we quickly see that we can write the right sum in closed form. So we get

\displaystyle S_{0,q-1} = S_{q, 2q-1} - a(q-1)(q) - aq^2 \ \ \ \ \ (6)


We can extend this by noting that {\frac{a}{q}(x + hq)^2 = \frac{a}{q}x^2 + 2ahx + ahq}, so that

\displaystyle S_{0,q-1} = S_{hq, (h+1)q-1} - \sum_0^{q-1}(2ahx + ahq) \ \ \ \ \ (7)


Extending to multiple intervals at once, we get

\lambda S_{0,q-1} = \sum_{h=1}^\lambda \left( S_{hq, (h+1)q - 1} - h\sum_0^{q-1}(2ax + aq) \right)

S_{q, (\lambda + 1)q-1}- \sum_{h=1}^{\lambda} h \left(\sum_0^{q-1} (2ax + aq) \right)

S_{q, (\lambda + 1)q-1}- \frac{\lambda (\lambda +1)}{2}[aq(q+1) + aq^2]

So, in short, if we know the number of lattice points under the parabola on the interval {[0,q-1]}, then we know in {O(1)} time the number of lattice points under the parabola on an interval {[0,(\lambda + 1)q-1]}.

Unfortunately, when I have tried to take this method back to the Polymath4-type problem, I haven’t yet been able to reign in the error terms. But I suspect that there is more to be done using this method.