Integer approximation of a segment

M. M. Gallamov

Čebyševskij sbornik, Tome 23 (2022) no. 4, pp. 20-38.

Résumé

Let $OXY$ be a Cartesian coordinate system with an integer lattice whose unit squares are staggered. The integer approximation of the segment $AB$ is given using the cellular domain $\mathbb{S}_{AB}$ of (colored) cells, the interior of each of which.has a non-empty intersection with $AB$. If $P^{\pm}_{AB}$ — right and left closed half-planes defined by the line $l_{AB}$ by the point $A$ and $B$, then $\mathbb{S}^{\pm}_{AB}=\mathbb{S}_{AB}\cap P^{\pm}_{AB}$ — its right and left areas. (There are no integer points inside $\mathbb{S}_{AB}$.) Polyline $\mathrm{L}^{\pm}(A^{\pm},B^{\pm})$ from $\mathbb{S}^{\pm}_{AB}$ with ends $A^{\pm}$ and $B^{\pm}$ and whole vertices — right and left by (integer) approximations of the segment $AB$ — the ends are selected from the vertices of the extreme cells. If $l_{AB}$ is parallel to one of the coordinate axes, then we assume $\mathbb{ S}_{AB}=\varnothing$ and then approximation of the segment $AB$ is minimum segment with integer ends containing $AB$. Such approximations are constructed using the algorithm ‘pulling noses’, which is a geometric interpretation of the chain fraction of the angular coefficient of the straight line $l_{AB}$. Based on this construction method, an exact formula for calculating the number of integer points inside an arbitrary triangle is obtained, and the problem of S.V. Konyagin is partially solved. about chess coloring: If $\mathbf{U}(t)$ is the set of all colored cells from a triangle cut off by a straight line $f_{t}:y= -\alpha x+t$, $\alpha,\ t>0$, then the difference $u(t)$ between white and black cells from $\mathbf{U}(t)$ for every positive irrational $\alpha$ is bounded neither from below nor from above when $t\rightarrow\infty$. The solution is obtained for numbers of the form: $e^{\pm1}$, $\mathrm{tg}^{\pm1}$, $[a^{-}_{0}; a^{-}_{1},a^{-}_{2},\ldots]^{\pm1}$, $[a^{+}_{0};a^{+}_{1},a^{+}_{2}, \ldots]^{\pm1}$, $[a^{+}_{0};a^{-}_{1},a^{+}_{2}, \ldots]^{\pm1}$, where the superscript plus (minus) indicates on the parity (odd) of the element of the continued fraction defined by $\alpha$. The method of constructing an approximation of the segment was used to solve the problem of chess coloring for the numbers $\frac{\sqrt{5}+1}{2}$, $[ a^{+}_{0};a^{+ }_{1},a^{+}_{2},\ldots]$, $a^{-}_{2n+1}$ and $[a^{-}_{0};a^{-}_{1},a^{-}_{ 2}, \ldots]$, if limited \begin{equation*} \begin{array}{l} 2^{k-1}b_{3}b_{9} \cdots b_{6(k-1)+3} + \cdots + 2^{2}\sum^{k}_{i_{1}>i_{2}>i_{3}=1} b_{6(k-i_{1})+3}b_{6(k-i_{2})+3} \\ b_{6(k-i_{3})+3} + 2\sum^{k}_{i_{1}>i_{2}=1} b_{6(k-i_{1})+3}b_{6(k-i_{2})+3} + \sum^{k}_{i=1}b_{6(k-i_{1})+3} + 1, \end{array} \end{equation*} for some $b_{n}=\left\lfloor\frac{a^{-}_{n}-1}{2}\right \rfloor$ representing the whole part of $\frac{a^{-}_{n}-1}{2}$. So for $b_{n}=0$ the chain fraction is $[a^{-}_{0};a^{-}_{1},a^{-}_{2}, \ldots]=\frac{\sqrt{5}+1}{2}$.

Détail

Keywords: S.V.Konyagin's problem about chess coloring, a straight line with an irrational angular coefficient and chess coloring, a chain fraction, a geometric interpretation of a chain fraction, an algorithm for `pulling noses, an integer lattice, an approximation of a segment the number of integer points inside a triangle.

Bibliographie

[1] Khinchin A. Ya., Tsepnye drobi, 4-oe izd., Nauka, M., 1978, 112 pp. | MR

[2] Bukhshtab A. A., Teoriya chisel, Prosveschenie, M., 1966, 376 pp.

[3] Nesterenko Yu..V., Teoriya chisel, Izdatelskii tsentr “Akademiya”, M., 2008, 272 pp.

[4] Nesterenko Yu. V., Nikishin E. N., “Ocherk o tsepnykh drobyakh”, Kvant, 1983, no. 5, 16–20 ; No 6, 26–30

[5] Mikhalovich Sh. X, Teoriya chisel, Vysshaya shkola, M., 1967, 336 pp.

[6] Aleksandrov P. S, Markushevich A. I., Khinchin A. Ya. (red.), Entsiklopediya elementarnoi matematiki, v. 1, Arifmetika, TTL, M.–L., 1951, 448 pp.

[7] Vasilev H. B., “Vokrug formuly Pika”, Kvant, 1974, no. 12, 39–43

[8] Vavilov V. V., Ustinov A. V., Mnogougolniki na reshetkakh, MTsNMO, M., 2006, 72 pp.

[9] Grunbaum B., G. C. Shephard, “Pick's Theorem”, The American Mathematical Monthly, 100:2 (2001), 150–61 | DOI | MR

[10] Arnold V. I., Tsepnye drobi, MTsNMO, M., 2001, 40 pp.

[11] Devenport G., Vysshaya arifmetika. Vvedenie v teoriyu chisel, Nauka, M., 1965, 176 pp.

[12] Klein F., Elementarnaya matematika s tochki zreniya vysshei, v. I, Arifmetika. Algebra. Analiz, 4-oe izdanie, Nauka, M., 1987, 432 pp. | MR

[13] Khovanova T., Konyagin S., Sequences of Integers with Missing Quotients and Dense Points Without Neighbors, 2011, 20 pp., arXiv: 1104.0441v1 [math.CO] | MR | Zbl

[14] Gallamov M. M., “Pryamye $y=-e\cdot x+t$ i shakhmatnaya raskraska”, Algebra, teoriya chisel i diskretnaya geometriya: sovremennye problemy, prilozheniya i problemy istorii, Materialy XVI Mezhdunarodnoi konferentsii, posvyaschennoi 80-letiyu so dnya rozhdeniya professora Mishelya Deza (Tula, 13–18 maya 2019 g.), 247–250

[15] Gallamov M. M., “Pryamye $y=\frac{1-\sqrt{5}}{2}\cdot x+s$ i shakhmatnaya raskraska”, Algebra, teoriya chisel i diskretnaya geometriya: sovremennye problemy, prilozheniya i problemy istorii, Materialy XVII Mezhdunarodnoi konferentsii, posvyaschennoi stoletiyu so dnya rozhdeniya professora Nauma Ilicha Feldmana i devyanostoletiyu so dnya rozhdeniya professorov Askolda Ivanovicha Vinogradova, Aleksandra Vasilevicha Malysheva i Borisa Faddeevicha Skubenko (Tula, 23–29 sentyabr 2019 g.), 142–245

[16] Gallamov M. M., “Pryamye $y=-[a^{\pm}_{0};a^{\pm}_{1},a^{\pm}_{2},...]\cdot x+t$ s chetnymi $a^{+}_{n}$ i nechetnymi $a^{-}_{n}=a(\neq1)$ i shakhmatnaya raskraska”, Algebra, teoriya chisel i diskretnaya geometriya: sovremennye problemy, prilozheniya i problemy istorii, Materialy XVIII Mezhdunarodnoi konferentsii, posvyaschennaya stoletiyu so dnya rozhdeniya professorov Borisa Maksimovicha Bredikhina, Vasiliya Ilicha Nechaeva i Sergeya Borisovicha Stechkina (Tula, 23–26 sentyabrya 2020 g.), 261–265

[17] Gallamov M. M., “Tselochislennaya approksimatsiya otrezka”, Algebra, teoriya chisel i diskretnaya geometriya: sovremennye problemy, prilozheniya i problemy istorii, Materialy XXI Mezhdunarodnoi konferentsii, posvyaschennaya 85-letiyu so dnya rozhdeniya A. A. Karatsuby (Tula, 17–21 maya 2022 g.), 235–238