Explorations in math and programming
David Lowry-Duda

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.

Leave a comment

Info on how to comment

To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.

bold, italics, and plain text are allowed in comments. A reasonable subset of markdown is supported, including lists, links, and fenced code blocks. In addition, math can be formatted using $(inline math)$ or $$(your display equation)$$.

Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.

Comment via email