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.
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ In general I don't think you can do much better. Consider the triangle with end points $(1,1), (n,1), (n,(n+1)/n), n \in \mathbb{N}$ for example. The area is equal to $1/2$, but there are $n$ integral points on the boundary. This is essentially the worst case though. $\endgroup$– Stanley Yao XiaoCommented Aug 28, 2020 at 11:59
-
2$\begingroup$ The question reduces to estimates of the sums $\sum_{k=1}^n \{\gamma k\}$. For fixed irrational $\gamma$ and large $n$ this is about $n/2$. $\endgroup$– Fedor PetrovCommented Aug 28, 2020 at 17:31
-
1$\begingroup$ Better upper bound on the deviation from the area? Certainly not: if you move $\beta$ and $\gamma$ by almost $1$ from some integer plus epsilon to the next integer minus epsilon, the number of integer points does not change but the area changes pretty much by the sum of the sides that is your current bound. Perhaps you wanted to ask something else or I misunderstood the question? $\endgroup$– fedjaCommented Aug 29, 2020 at 5:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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-\alpha\gamma|$; 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 $0\le i\le j\le a$. The latter triple inequality can be rewritten as $0\le i\le j\le n$, where $n:=\lfloor a\rfloor\ge0$, so that $n\le 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}2\ge\frac{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$.
answered Aug 28, 2020 at 14:20
-
1$\begingroup$ Since the question is posed in terms of the parameters $\alpha,\beta,\gamma$, I think one hopes for a bound in terms of these, rather than in terms of $a,b$. $\endgroup$ Commented Aug 28, 2020 at 23:38
-
$\begingroup$ @GerryMyerson : I have inserted expressions of $a,b$ in terms of $\alpha,\beta,\gamma$. However, the expression of the upper bound in terms of $a,b$ seems more transparent. $\endgroup$ Commented Aug 30, 2020 at 1:04