Lattice Points Enclosed by Parabola and Line

For integers $a$ and $b$, we define $D(a, b)$ as the domain enclosed by the parabola $y = x^2$ and the line $y = a\cdot x + b$:$D(a, b) = \{(x, y) \mid x^2 \leq y \leq a\cdot x + b \}$.

$L(a, b)$ is defined as the number of lattice points contained in $D(a, b)$.
For example, $L(1, 2) = 8$ and $L(2, -1) = 1$.

We also define $S(N)$ as the sum of $L(a, b)$ for all the pairs $(a, b)$ such that the area of $D(a, b)$ is a rational number and $|a|,|b| \leq N$.
We can verify that $S(5) = 344$ and $S(100) = 26709528$.

Find $S(10^{12})$. Give your answer mod $10^8$.

Let’s start with analyzing the domain $D(a, b)$. This is the area between the parabola, $y = x^2$, and a line, $y = ax + b$.

The intersection of the parabola and the line occurs when $x^2 = ax + b$. Rewrite this as $x^2 – ax – b = 0$. The solutions for x (i.e., the x-coordinates where these two graphs intersect) can be found via the quadratic formula $x = \frac{a \pm \sqrt{a^2 + 4b}}{2}$.

$a^2 + 4b$ must be a perfect square (let this be $s^2$) in order for the area enclosed by the parabola and the line to be rational, and for the intersections of the parabola and the line to lie on lattice points.

So, now we get $s^2 – a^2 = 4b$. This is a difference of squares equation, and can be factored into $(s-a)(s+a) = 4b$. Thus $s-a$ and $s+a$ are divisors of $4b$. Hence, let $s – a = d$ and $s + a = 4b/d$, we got $2s = d + \frac{4b}{d} \rightarrow 2sd = d^2 + 4b \rightarrow 0 = d^2 – 2sd + 4b$.

Solve this quadratic equation for $d$ to get $d = s \pm \sqrt{s^2 – 4b}$, which is an integer for $b =bt^2$. Hence, for $s > t$ and $s > d > 0$, find all the divisors $d$ for $4bt^2$ and add up the value of $L(a, b)$.

Consider one quarter of the plane where $a > 0, b > 0$, the four quarters are symmetric. Consider the rectangle box of areas $b$ whose diagonal is the line of $y = ax + b$.

$L(a, b)$ can be computed as $\frac{(2a + 1)(2b + 1) + 1}{2}$ where $a$ and $b$ are integers.

To avoid overflow of Java long integer stemming from the computation of $L(a, b)$, compute $L(a, b)$ in reduction of modulo $10^8$. The modulo operation can be conducted at the step where $(2a + 1)(2b + 1)$ is computed as $(2a + 1)(b + b) = 2a(2b) + 2b = 4ab + 2b = (mod \, 10^8)$ where the intermediate result of $4ab$ can be reduced by Modulo $10^8$.

Finding all the factors of t^2 does not require one loop to $t$ because the factors of t^2 repeat after $\sqrt{t}$ and hence one loop to $\sqrt{t}$ is efficient.

The complexity of finding all the factors of an integer in each quarter is proportional to the sum of all the numbers up to the integer, in multiplication with a log factor. Thus, the computation is feasible by a computer program.

Hope this helps!

More Answers: