mixedmath

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

Comment via email