Exercise 4.1.24* (Number of points under a line)

Question

For positive real numbers $\alpha, \beta, \gamma$ define $f(\alpha, \beta, \gamma)$ as the sum of all positive terms of the series
$$\left \lfloor \frac{\gamma - \alpha}{\beta} \right \rfloor + \left \lfloor \frac{\gamma - 2\alpha}{\beta} \right \rfloor +\left \lfloor \frac{\gamma - 3\alpha}{\beta} \right \rfloor +\left \lfloor \frac{\gamma - 4\alpha}{\beta} \right \rfloor + \cdots.$$

(If there are no positive terms, define $f(\alpha, \beta, \gamma) = 0$).

Prove that $f(\alpha, \beta, \gamma) = f(\beta, \alpha, \gamma)$.

\bigskip
Hint. $f(\alpha, \beta, \gamma)$ is related to the number of solutions of $\alpha x + \beta y \leq \gamma$ in positive integer pairs $x,y$.

Richard Ganaye · Accepted Answer

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

\begin{proof} 
We define
$$A = \{(x,y) \in \N^* 	imes \N^* \mid \alpha x + \beta y \leq \gamma\}.$$
$A$ is the set of points with positive integer coordinates under or on the line of equation $\alpha x + \beta y = \gamma.$

For some fixed positive integer $k$, let 
$$A_k = \{(x,y) \in A \mid x = k\},  \qquad A'_k = \{ y \in \N^* \mid \alpha k + \beta y \leq \gamma\}.$$
Then the map $\varphi:A_k 	o A'_k$ defined by $\phi(x,y) = y$ is a bijection (such that $\varphi^{-1}(y) = (k,y)$), so $|A_k| = |A'_k|$. Moreover
$$A = \bigcup_{k \in \N^*} A_k\qquad 	ext{(disjoint union)},$$
thus
\begin{align}
|A| = \sum_{k \in \N^*} |A_k| = \sum_{k \in \N^*} |A'_k|.
\end{align}
Moreover, 
\begin{align*}
y \in A'_k  &\iff 1 \leq y \leq \frac{\gamma - k\alpha }{\beta}\
&\iff 1 \leq y \leq \left \lfloor \frac{\gamma - k\alpha }{\beta} ight floor\
&\iff y \in [\![ 1 , n_k ]\!], &	ext{where }n_k =\left \lfloor \frac{\gamma - k\alpha }{\beta} ight floor ,
\end{align*}
thus $|A'_k| = [\! [ 1 ,  n_k ]\!]$, so
$$A'_k = 
\begin{cases}
\left \lfloor \frac{\gamma -k \alpha }{\beta} ight floor  & 	ext{if } \gamma - k\alpha >0,\
0 & 	ext{otherwise}.
\end{cases}
$$
Then equation (1) gives
\begin{align*}
|A| &= \sum_{k \geq 1, \gamma - k \alpha  >0} \left \lfloor \frac{\gamma -  k \alpha }{\beta} ight floor  = \sum_{k = 1}^{\lfloor \gamma/\alpha floor}  \left \lfloor \frac{\gamma - k \alpha }{\beta} ight floor\
&= f(\alpha, \beta, \gamma).
\end{align*}

\bigskip
Similarly, for some fixed positive integer, let 
$$B_j = \{(x,y) \in A \mid y = j\},  \qquad B'_j = \{ x \in \N^* \mid \alpha x + \beta j \leq \gamma\}.$$
Then 
$$|B_j| = |B'_j| = \left \lfloor \frac{\gamma - j\beta}{\alpha} ight floor 	ext{ if } \gamma - j \beta >0 \quad(0 	ext{ otherwise}).$$
Therefore 
\begin{align*}
|A| &= \sum_{j \geq 1, \gamma - j \beta  >0} \left \lfloor \frac{\gamma - j \beta}{\alpha} ight floor  = \sum_{j = 1}^{\lfloor \gamma/\beta floor}  \left \lfloor \frac{\gamma - j \beta }{\alpha} ight floor\
&= f(\beta, \alpha, \gamma).
\end{align*}
In conclusion, if $\alpha, \beta, \gamma$ are positive real numbers,
$$
f(\alpha, \beta, \gamma) = f(\beta, \alpha, \gamma),
$$
that is
$$\sum_{k = 1}^{\lfloor \gamma/\alpha floor}  \left \lfloor \frac{\gamma - k \alpha }{\beta} ight floor = \sum_{j = 1}^{\lfloor \gamma/\beta floor}  \left \lfloor \frac{\gamma - j \beta }{\alpha} ight floor.$$
\end{proof}

Exercise 4.1.24* (Number of points under a line)

Answers

Comments

Exercise 4.1.24* (Number of points under a line)

Answers

Comments

Add answer