Points under Parabola

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 $latex {y = \frac{a}{q}x^2}$. In particular, I show that knowing the number of lattice points in the interval $latex {[0,q-1]}$, then we have a closed form for the number of lattice points in any interval $latex {[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 $latex {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 $latex {q}$, so that this does not always guarantee much time-savings.

This came up while considering

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


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

$latex \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

$latex \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 $latex {y = \frac{a}{q}x^2}$ in some interval. First, note that

$latex \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

$latex \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 $latex {S_{a,b} := \sum_{x = a}^b \left\lfloor \frac{a}{q}x^2 \right\rfloor}$, so that we can rewrite equation 5 as

$latex \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

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


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

$latex \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

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

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

$latex S_{q, (\lambda + 1)q-1}-$ $latex \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 $latex {[0,q-1]}$, then we know in $latex {O(1)}$ time the number of lattice points under the parabola on an interval $latex {[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.


This entry was posted in Expository, Math.NT, Mathematics, Polymath and tagged , , , , . Bookmark the permalink.

Leave a Reply