MathOverflow Asked by Johnny T. on November 27, 2020

Let $T$ be a triangle in $mathbb{R}^2$ defined by $y = alpha x$, $y = beta$ and $x = gamma$ where

$alpha, beta, gamma in mathbb{R}_{>0}$. I am interested in obtaining an estimate for the number of integral points inside (either within or on the boundaries) of $T$ which I denote $N$. A simple computation yields

$$

N = Area(T) + E

$$

with

$$

|E| ll |gamma – frac{beta}{alpha}| + |beta – alpha gamma|

$$

in other words $E$ is bounded by the sum of the two side lengths. Are there ways to get better upper bound than this? Any comments are appreciated.

The bound on $|E|$ can certainly be improved: $|E|le|E|$; so, we get the "perfect" (but completely useless) upper bound, $|E|$, on $|E|$.

To make the problem meaningful, we need to specify the terms in which the upper bound is to be expressed. Counting the unit squares intersecting the boundary of the triangle, it is easy to see that $$|E|ll s:=a+b+1,$$ where $a$ and $b$ are the lengths of the horizontal and vertical sides of the right triangle (in terms of your $alpha,beta,gamma$, we have $a=|gamma-beta/alpha|$ and $b=|beta-alphagamma|$; your bound is missing "$+1$"). Note that $s>1$.

Let us show that $s$ is the best (up to a constant factor) upper bound on $|E|$ **in terms of $s$**. Indeed, take any real $s>1$ and consider the right triangle $T$ with vertices $(0,0),(0,a),(a,a)$, where $a:=(s-1)/2>0$, so that $a+a+1=s$. Then the area of $T$ is $A=a^2/2$ and
the number $N$ of integral points that are either inside $T$ or on the boundary of $T$ is the number of pairs $(i,j)$ of integers such that $0le ile jle a$. The latter triple inequality can be rewritten as $0le ile jle n$, where $n:=lfloor arfloorge0$, so that $nle a<n+1$. So, $N=(n+1)(n+2)/2$ and $A<(n+1)^2/2$. Hence,
$$|E|=|N-A|=N-A \
>frac{(n+1)(n+2)}2-frac{(n+1)^2}2 \
=frac{n+1}2gefrac{2(n+1)+1}6>frac{2a+1}6=frac s6.$$

Thus, the best upper bound on $|E|$ in terms of $s$ is $,asymp s$, as claimed.

Working a bit harder, one can show that $|E|le s$. So, the best upper bound on $|E|$ in terms of $s$ is between $s/6$ and $s$.

Correct answer by Iosif Pinelis on November 27, 2020

Get help from others!

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP